202. 快乐数
题目：
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
解题思路：
我们先通过这两个测试用例来看看是什么情况
我们发现不管是19还是2都会形成一个环状结构（19的环状结构内都是1）
那这样我们就可以使用快慢指针来操作！！！
定义一个slow和fast，slow一次走一步，fast一次走两步
他们一定会相遇的，只不过相遇的时候会有两种情况，相遇的数是1或者不是1
那为什么一定会形成环状结构呢？我们来简单论证一下！
鸽巢原理：就是当n个巢穴，n+1个鸽子的时候，一定至少有一个巢穴的鸽子>1
我们注意一下n的范围，n最大为2的31次方，也就是2亿多（10位数）,那我们将它放大10个9（也就是最大的那个10位数，我懒得打9了），也就是说，它最多就是10个9，经过f操作最大就是9^2*10=810,也就是相当于我们最多有810个位置，我们处理813次的f，肯定会有重复的数出现！
那同理：
解题代码：
1. class Solution { 2. public: 3. int f(int n) 4. { 5. int arr[11] = { 0 }; 6. int i = 1; 7. for (int i = 1; i < 11; ++i) 8. { 9. if (n < 10) 10. { 11. arr[i] = n; 12. break; 13. } 14. arr[i] = n % 10; 15. n = n / 10; 16. } 17. int x = 0; 18. for (int i = 1; i < 11; ++i) 19. { 20. x += (arr[i] * arr[i]); 21. } 22. return x; 23. } 24. bool isHappy(int n) { 25. //快慢双指针 26. int slow = n; 27. int fast = n; 28. //更新slow和fast 29. slow = f(slow); 30. fast = f(fast); 31. fast = f(fast); 32. if (slow == fast && slow == 1)return true; 33. while (slow != fast) 34. { 35. //更新slow和fast 36. slow = f(slow); 37. fast = f(fast); 38. fast = f(fast); 39. } 40. if (slow == 1) 41. return true; 42. else 43. return false; 44. } 45. };
11. 盛最多水的容器
题目描述：
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
解题思路：
体积V=h*w,当我们利用双指针从左右两边向中间逼近，w一定是减小的，只有当h增大才可能增大
解题代码：
1. class Solution { 2. public: 3. int maxArea(vector<int>& height) { 4. int left=0; 5. int right=height.size()-1; 6. int ret=0; 7. while(left<right) 8. { 9. int v=min(height[left],height[right])*(right-left); 10. ret=max(v,ret); 11. if(height[left] < height[right]) left++; 12. else right--; 13. } 14. return ret; 15. } 16. };
