LeetCode热题100(25.10.16)

一：寻找重复数

1. 二分查找

最简单的方式应该直接对其排序，然后遍历一遍找出重复值，但是题目要求不能修改原数组且使用常量空间，因此不能应用。这里我们可以注意到值的范围，如果我们把该范围的中间值作为一个临界值，那么数组应该被分为大致相等的两部分，存在重复值的一部分会稍大

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int len = nums.size();
        int left = 1, right = len - 1;
        int mid = 0;
        int ans = -1;
        while (left <= right)
        {
            int count = 0;
            mid = ((right - left) >> 1) + left;
            for (int i = 0; i < len; ++i)
                if (nums[i] <= mid) ++count;
            if (count <= mid) left = mid + 1;
            else 
            {
                ans = mid;
                right = mid - 1;
            }
        }
        return ans;
    }
};

2. 二进制

该方法使用二进制位来记录数组中不同元素的二进制位并与值域的二进制位比较

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int len = nums.size();
        int ans = 0;
        int bitCnt = 0;
        int temp = len - 1;
        while (temp >>= 1) ++bitCnt;
        for (int i = 0; i <= bitCnt; ++i)
        {
            int x = 0, y = 0;
            for (int j = 0; j < len; ++j)
            {
                if (nums[j] & (1 << i)) ++x;
                if (j > 0 && (j & (1 << i))) ++y;
            }
            if (x > y) ans |= (1 << i);
        }
        return ans;
    }
};

3. 快慢指针

数组的索引为0~n-1，值域为1~n-1，那么每个索引都会对应一个值域，至少存在一个值域被两个索引指向，此时构建从索引到值的环，环的入口就是重复节点

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        do 
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = 0;
        while (slow != fast)
        {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

二：打家劫舍

1. 动态规划

由题目可知，一间房子和两间房子的情况是确定的，也就是我们的边界条件，对于房间k，我们有偷和不偷两个选项，但要取其中的较大值

class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) return 0;
        if (len == 1) return nums[0];
        vector<int> sum(len, 0);
        sum[0] = nums[0];
        sum[1] = max(nums[0], nums[1]);
        for (int i = 2; i < len; ++i)
        {
            sum[i] = max(sum[i - 1], nums[i] + sum[i - 2]);
        }
        return sum.back();
    }
};

// 滚动数组优化空间
class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) return 0;
        if (len == 1) return nums[0];
        int pre = nums[0], next = max(nums[1], nums[0]);
        int temp = 0;
        for (int i = 2; i < len; ++i)
        {
            temp = next;
            next = max(next, nums[i] + pre);
            pre = temp;
        }
        return next;
    }
};

三：完全平方数

1. 动态规划

该题需要寻找一个索引使得n - j * j的平方和的数量最小

class Solution {
public:
    int numSquares(int n) {
        vector<int> step(n + 1);		// 索引0作为辅助
        for (int i = 1; i <= n; ++i)
        {
            int minStep = INT_MAX;
            for (int j = 1; j * j <= i; ++j)
            {
                minStep = min(minStep, step[i - j * j]);
            }
            step[i] = minStep + 1; 
        }
        return step[n];
    }
};

2. 数学

四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和。

同时四平方和定理包含了一个更强的结论：当且仅当 $n \ne 4^k \times (8m+7)$ 时，$n$ 可以被表示为至多三个正整数的平方和。
因此，当 $n = 4^k \times (8m+7)$ 时，(n) 只能被表示为四个正整数的平方和。此时我们可以直接返回 4。

当 $n \ne 4^k \times (8m+7)$ 时，我们需要判断到底多少个完全平方数能够表示 $n$。我们知道答案只会是 (1,2,3) 中的一个

class Solution {
public:
    int numSquares(int n) {
        if (static_cast<int>(sqrt(n)) * static_cast<int>(sqrt(n)) == n) return 1;
        if (IsFormat(n)) return 4;
        for (int i = 1; i * i <= n; ++i)
        {
            int j = n - i * i;
            if (static_cast<int>(sqrt(j)) * static_cast<int>(sqrt(j)) == j) return 2;
        }
        return 3;
    }
    bool IsFormat(int x)
    {
        while (x % 4 == 0) x /= 4;
        return x % 8 == 7;
    }
};