软件开发后端_四川省建设网_互联网seo是什么_互联网推广是什么工作内容

1.题目

1. 202. 快乐数 - 力扣（LeetCode）
2. 11. 盛最多水的容器 - 力扣（LeetCode）

2.题目解答

1.快乐数

题目及题目解析

算法学习

无论是情况一还是情况二,都会进入到一个循环中

我们只需要判断链表是否有环:之前使用的是快慢双指针的方法,判断相遇时候的值即可

如何指向?

仍然不是真实的指针,而是用%10或者/10来取到数字计算和,通过计算的和来模拟快慢指针

我们可以先写一个求和函数

int Sum(int n) {int sum = 0;while (n) {int t = n % 10;sum += t * t;n /= 10;}return sum;}

后续通过调用Sum就可以来实现快慢指针了

bool isHappy(int n) {int slow = n, fast = Sum(n);while (slow != fast) {slow = Sum(slow);//慢指针走一步fast = Sum(Sum(fast));//快指针走两步}return slow == 1;}

代码提交

class Solution {
public:int Sum(int n) {int sum = 0;while (n) {int t = n % 10;sum += t * t;n /= 10;}return sum;}bool isHappy(int n) {int slow = n, fast = Sum(n);while (slow != fast) {slow = Sum(slow);fast = Sum(Sum(fast));}return slow == 1;}
};

2.题目2

题目及题目解析

容器的容水量计算方法:V = 最小的那个边*中间相差的距离

算法学习

这里我们可以先用一下暴力解法:

class Solution {
public:int maxArea(vector<int>& height) {int utmost = 0;for (int i = 0; i < height.size(); i++) {for (int j = i + 1; j < height.size(); j++) {int sum = 0;if (height[i] < height[j]) {sum = height[i] * (j - i);} else {sum = height[j] * (j - i);}if (sum > utmost) {utmost = sum;}}}return utmost;}
};

当然是过不了的,时间复杂度过大了

那么该如何解决呢?

通过用两个指针将数组分开来算就可以从O(N*2)的时间复杂度转化为O(N)了

代码提交

class Solution {
public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1, ret = 0;while (left < right) {int v = min(height[left], height[right]) * (right - left);ret = max(ret, v);// 移动指针if (height[left] < height[right])left++;elseright--;}return ret;}
};