优选算法
双指针
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;}