leetcode刷题记录14（2023-08-09）【零钱兑换(一维动态规划、记忆化搜索) | 打家劫舍 III(树形dp) | 比特位计数(动态规划、位运算) | 前 K 个高频元素(快排)】

爱被打了一巴掌 2024-03-23 20:22 7阅读 0赞

## 322. 零钱兑换 ##

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：  
输入：coins = \[1, 2, 5\], amount = 11  
输出：3  
解释：11 = 5 + 5 + 1

示例 2：  
输入：coins = \[2\], amount = 3  
输出：-1

示例 3：  
输入：coins = \[1\], amount = 0  
输出：0

提示：  
 1 < = c o i n s . l e n g t h < = 12 1 <= coins.length <= 12 1<=coins.length<=12  
 1 < = c o i n s \[ i \] < = 2 31 − 1 1 <= coins\[i\] <= 2^\{31\} - 1 1<=coins\[i\]<=231−1  
 0 < = a m o u n t < = 1 0 4 0 <= amount <= 10^4 0<=amount<=104

动态规划方法，就是从下向上进行dp数组的状态转移，最终返回dp\[amount\].

// 动态规划做法
    class Solution {
        
    public:
        int coinChange(vector<int>& coins, int amount) {
        
            vector<int> dp(amount + 1);
            dp[0] = 0;
            for (int i = 1; i < amount + 1; i++) {
        
                int minNum = INT_MAX;
                for (int j = 0; j < coins.size(); j++) {
                        
                    if (coins[j] <= i && dp[i - coins[j]] != -1) {
        
                        minNum = min(minNum, dp[i - coins[j]] + 1);
                    }
                }
                if (minNum != INT_MAX) {
        
                    dp[i] = minNum;
                }
                else {
        
                    dp[i] = -1;
                }
            }
    
            return dp[amount];
        }
    };

记忆化搜索是采用自顶向下的搜索，把搜索的中间结果保存在数组中，防止后面重复计算。

在初始化vector时，要注意避免初始化赋值（可能会造成超时）。

// 记忆化搜索做法
    class Solution {
        
    private:
        vector<int> memo;
        int dp(vector<int>& coins, int amount) {
        
            if (amount == 0) {
        
                return 0;
            }
            if (amount < 0) {
        
                return -1;
            }
            if (memo[amount] != 0) {
        
                return memo[amount];
            }
            int minNum = INT_MAX;
            for (int i = 0; i < coins.size(); i++) {
        
                int res = dp(coins, amount - coins[i]);
                if (res != -1) {
        
                    minNum = min(minNum, res + 1);
                }
            }
            if (minNum != INT_MAX) {
        
                memo[amount] = minNum;
            }
            else {
        
                memo[amount] = -1;
            }
            return memo[amount];
        }
    public:
        int coinChange(vector<int>& coins, int amount) {
        
            // 这里不要写成 memo = vector<int>(amount + 1, -1); 会超时。
            // 用 0 表示未计算过，-1 表示无解，会省去最初循环赋值的事件
            memo = vector<int>(amount + 1);
            memo[0] = 0; // 0元不需要硬币
            return dp(coins, amount);
        }
    };

## 337. 打家劫舍 III ##

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

![在这里插入图片描述][492e55a91b9a4fd2997085f20ed8f5c5.png]

输入: root = \[3,2,3,null,3,null,1\]  
输出: 7  
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

![在这里插入图片描述][b81dfe71b33e4053a2f8c17c2a3ec87f.png]

输入: root = \[3,4,5,1,3,null,1\]  
输出: 9  
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：

树的节点数在 \[ 1 , 1 0 4 \] 范围内 树的节点数在 \[1, 10^4\] 范围内 树的节点数在\[1,104\]范围内  
 0 < = N o d e . v a l < = 1 0 4 0 <= Node.val <= 10^4 0<=Node.val<=104

第一种思路较为好理解，就是借助dfs后续遍历树，然后每个节点有2种状态，分别为选择和不选择。中途记录每个节点选择和不选择的值，保存到哈希表中来。

最终选择根节点选择与不选择两种情况中较大的。

代码如下：

#include<unordered_map>
    
    using namespace std;
    
    // Definition for a binary tree node.
    struct TreeNode {
        
    	int val;
    	TreeNode* left;
    	TreeNode* right;
    	TreeNode() : val(0), left(nullptr), right(nullptr) {
        }
    	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
        }
    	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {
        }
    };
    
    // 利用hash表记录，然后进行动态规划
    class Solution {
        
    private:
    	unordered_map<TreeNode*, int> selected;
    	unordered_map<TreeNode*, int> unselected;
    	void dfs(TreeNode* node) {
        
    		if (node == nullptr) {
        
    			return;
    		}
    		dfs(node->left);
    		dfs(node->right);
    		selected[node] = node->val + unselected[node->left] + unselected[node->right];
    		unselected[node] = max(selected[node->left], unselected[node->left]) +
    			max(selected[node->right], unselected[node->right]);
    	}
    public:
    	int rob(TreeNode* root) {
        
    		dfs(root);
    		return max(selected[root], unselected[root]);
    	}
    };

这种做法的时间复杂度相当于遍历了所有节点一遍，为O(N)。

空间复杂度也为O(N)，因为递归栈调用了N次，同时哈希表也存储了N的节点次。

第二种思路进行内存优化，可以将哈希表去掉，主要思路是，建立一个结构体，之前的结果其实不需要保存，没用了，我们只需要保存当前的结果就好了。

#include<unordered_map>
    
    using namespace std;
    
    // Definition for a binary tree node.
    struct TreeNode {
        
    	int val;
    	TreeNode* left;
    	TreeNode* right;
    	TreeNode() : val(0), left(nullptr), right(nullptr) {
        }
    	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
        }
    	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {
        }
    };
    
    struct IsSelected
    {
        
    	int selected;
    	int unselected;
    };
    
    // 不利用hash表记忆，内存优化
    class Solution {
        
    	IsSelected dfs(TreeNode* node) {
        
    		if (node == nullptr) {
        
    			return {
         0,0 };
    		}
    
    		auto l = dfs(node->left);
    		auto r = dfs(node->right);
    
    		int selectCur = node->val + l.unselected + r.unselected;
    		int unselectCur = max(l.selected, l.unselected) + 
    			max(r.selected, r.unselected);
    
    		return {
         selectCur, unselectCur };
    	}
    public:
    	int rob(TreeNode* root) {
        
    		auto isSelectRoot = dfs(root);
    		return max(isSelectRoot.selected, isSelectRoot.unselected);
    	}
    };

时间复杂度不变，空间复杂度数量级没变还是O(N)，但进行了常数级别的优化。

## 338. 比特位计数 ##

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：  
输入：n = 2  
输出：\[0,1,1\]  
解释：  
0 --> 0  
1 --> 1  
2 --> 10

示例 2：  
输入：n = 5  
输出：\[0,1,1,2,1,2\]  
解释：  
0 --> 0  
1 --> 1  
2 --> 10  
3 --> 11  
4 --> 100  
5 --> 101

提示：

0 < = n < = 1 0 5 0 <= n <= 10^5 0<=n<=105  
自己最初想到的，能过：

![在这里插入图片描述][2e590b73dd0d4e9692a187bb8c0dc57f.png]

// O(n*log(n)) 的解法
    class Solution {
        
    public:
        vector<int> countBits(int n) {
        
            vector<int> res;
            for (int i = 0; i <= n; i++) {
        
                int sum = 0;
                int num = i;
                while (num > 0) {
        
                    sum += 1 & num;
                    num = num >> 1;
                }
                res.push_back(sum);
            }
            return res;
        }
    };

题解给出了几种O(N)时间复杂度的方法，主要采用了dp的思路，自己着实想不到。[https://leetcode.cn/problems/counting-bits/solutions/627418/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/][https_leetcode.cn_problems_counting-bits_solutions_627418_bi-te-wei-ji-shu-by-leetcode-solution-0t1i]

一种最低有效位的做法较为好理解，主要就是计算 ⌊ i 2 ⌋ \\lfloor \\frac\{i\}\{2\} \\rfloor ⌊2i⌋，然后判断它是奇数偶数，都通过位运算来实现，效率较高，如下：

// 时间复杂度为 O(n) 的解法
    class Solution {
        
    public:
        vector<int> countBits(int n) {
        
            vector<int> bits(n + 1);
            bits[0] = 0;
            for (int i = 1; i <= n; i++) {
        
                // 这里异或运算的括号一定要加，否则会出错
                bits[i] = bits[i >> 1] + (i & 1); 
            }
            return bits;
        }
    };

**补充**：bits\[i\] = bits\[i >> 1\] + (i & 1); 与bits\[i\] = bits\[i >> 1\] + i & 1;两个语句在C++中的区别 ？

这两个语句在C++中的区别在于运算符的优先级。C++中运算符有不同的优先级，可能会影响表达式的求值顺序。

1.  `bits[i] = bits[i >> 1] + (i & 1);`  
    在这个语句中，位运算符 `>>` 的优先级高于加法和位与运算符，所以 `i >> 1` 会先计算，然后 `(i & 1)` 计算。最后将这两个结果相加，然后赋值给 `bits[i]`。
2.  `bits[i] = bits[i >> 1] + i & 1;`  
    在这个语句中，加法运算的优先级高于位与运算符，所以 `bits[i >> 1] + i` 会先计算，然后再与 `1` 做位与运算。最后将这个结果赋值给 `bits[i]`。

如果你想要的是第一个语句的效果，确保使用括号来明确运算的优先级，以避免出现错误的结果。即 `(i & 1)` 应该在括号中，这样可以确保在位运算之前进行加法运算。

## 347. 前 K 个高频元素 ##

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:  
输入: nums = \[1,1,1,2,2,3\], k = 2  
输出: \[1,2\]

示例 2:  
输入: nums = \[1\], k = 1  
输出: \[1\]

提示：

1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105  
k 的取值范围是 \[1, 数组中不相同的元素的个数\]  
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

主要思路就是写一个快排，思路较为清晰，但中间出了较多bug。

#include<vector>
    #include<iostream>
    #include<unordered_map>
    using namespace std;
    
    class Solution {
        
        void quickSort(vector<pair<int, int>>& frequencyNum, int begin, int end, int k) {
        
            if (begin >= end)return;
    
            int pivot = rand() % (end - begin + 1) + begin;
            swap(frequencyNum[begin], frequencyNum[pivot]);
            pivot = begin;
            int index = begin; // index左边表示比pivot大的数
            for (int i = begin + 1; i <= end; i++) {
        
                if (frequencyNum[i].second > frequencyNum[pivot].second) {
        
                    swap(frequencyNum[index + 1], frequencyNum[i]);
                    index++;
                }
            }
            swap(frequencyNum[index], frequencyNum[pivot]);
            pivot = index;
    
            if (pivot > k) {
         // 在左边
                quickSort(frequencyNum, begin, pivot - 1, k);
            }
            else if (pivot < k) {
         // 在右边
                quickSort(frequencyNum, pivot + 1, end, k);
            }
            else {
         // 当前位置就是 k
                return;
            }
    
        }
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
        
            // 统计频率
            unordered_map<int, int> mp;
            for (int i = 0; i < nums.size(); i++) {
        
                mp[nums[i]]++;
            }
            // 频率统计好之后，将频率表转化位vector
            vector<pair<int, int>> frequencyNum;
            for (auto it : mp) {
        
                frequencyNum.push_back(it);
            }
    
            quickSort(frequencyNum, 0, frequencyNum.size() - 1, k);
            vector<int> res(k);
            for (int i = 0; i < k; i++) {
        
                res[i] = frequencyNum[i].first;
            }
            return res;
        }
    };
    
    int main() {
        
        Solution sol;
        vector<int> vec = {
         5,1,-1,-8,-7,8,-5,0,1,10,8,0,-4,3,-1,-1,4,-5,4,-3,0,2,2,2,4,-2,-4,8,-7,-7,2,-8,0,-8,10,8,-8,-2,-9,4,-7,6,6,-1,4,2,8,-3,5,-9,-3,6,-8,-5,5,10,2,-5,-1,-5,1,-3,7,0,8,-2,-3,-1,-5,4,7,-9,0,2,10,4,4,-4,-1,-1,6,-8,-9,-1,9,-9,3,5,1,6,-1,-2,4,2,4,-6,4,4,5,-5 };
        vector<int> res= sol.topKFrequent(vec, 7);
        for (int i = 0; i < res.size(); i++) {
        
            cout << res[i] << " ";
        }
    }

[492e55a91b9a4fd2997085f20ed8f5c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/69b0056ec80d432d9d21e13ce945380c.png
[b81dfe71b33e4053a2f8c17c2a3ec87f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/f9280b5108224e17b803cf5d60281653.png
[2e590b73dd0d4e9692a187bb8c0dc57f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/6a5d2610a5f24bc7a1957f85f7434284.png
[https_leetcode.cn_problems_counting-bits_solutions_627418_bi-te-wei-ji-shu-by-leetcode-solution-0t1i]: https://leetcode.cn/problems/counting-bits/solutions/627418/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/