【刷题】优选算法

优选算法

双指针

202. 快乐数

链接：. - 力扣（LeetCode）

【思路】

第一个实例是快乐数，因为会变为1且不断是1的循环

第二个实例不可能为1，因为会陷入一个没有1的循环

根据两个实例和鸽巢原理可以发现不断的平方和最终都会形成环，所以我们可以联想到用快慢指针，慢指针走一步，快指针走两步，最终会在环相遇，判断相遇时是否为1。

    //‘平分和’操作int squareSum(int num){int sum = 0;while(num){int unit = num % 10;num /= 10;sum += unit*unit;}return sum;}bool isHappy(int n) {//快慢指针int fast = n, slow = n;//相遇才停下do {//慢指针操作一次slow = squareSum(slow);//快指针操作两次fast = squareSum(squareSum(fast));} while(fast != slow);//相遇的值等于1才行return slow == 1;}

11. 盛最多水的容器

链接：. - 力扣（LeetCode）

【思路】

容量 = 底(下标相减) * 高(数组元素较小值)

如图，我们先算出最左边(1)和最右边(7)围起来的容量，然后，7不动，1继续和7的左边3，8，4...遍历算出容量，你会发现底是不断缩短的，同时高一直都是1，因为高只有两种情况，比它小或和它相等，所以1和7左边的值算出来的容量都是比1和7的容量小的，因为底在不断变小同时高可能不变也可能变小。

所以可以得出结论，每次算完容量后，元素较小的直接移动，不用遍历其他结果。

    int maxArea(vector<int>& height) {int head = 0, tail = height.size() - 1;int final_cap = 0;while(head < tail){//计算容量,保留较大值int capacity = (tail - head) * min(height[head], height[tail]);   final_cap = max(final_cap, capacity);//思路的推断移动高度小的一方if(height[head] < height[tail]){++head;}else{--tail;}}return final_cap;}

611. 有效三角形的个数

链接：. - 力扣（LeetCode）

【思路】

判断三角形：最长边小于其它边之和。

先排序获取单调性配合双指针解决问题。

先固定最长边，然后先从剩下的区间两端作为另外两条边，2+9>10，同时因为单调性，left的右边都比left大，所以right和左边任意一条组合都大于10，计算完组合后, right--继续找下一条边，此时2+5<10，因为单调性，right的左边都比right小，所以left和right左边的任意一条组合都小于10，排除left，left++, 继续找下一条边，这样一个区间找完就视为完成一次最大边的固定，需要固定下一条最大边，直到固定完所有最大边，最后一条最大边是倒数第三条，因为还剩最后两条构不成三角形。

    int triangleNumber(vector<int>& nums) {//排序获取单调性sort(nums.begin(), nums.end());//固定一个最大边int ret = 0;for(int i = nums.size() - 1; i >= 2; --i){//将区间两端作为两条边，不断缩小int left = 0, right = i - 1;while(left < right){if(nums[left] + nums[right] > nums[i]){ret += right - left;--right;}else{++left;}}}return ret;}