当前位置：首页 > ops >正文

机试备考笔记 18/31

ops 2025/8/23 15:07:13

2025年8月18日
小结：省流，5道 Medium，22 号写完的啧啧

LeetCode

46. 全排序

秒了

class Solution {
public:vector<bool> visited;int N;vector<vector<int>> results;vector<int> NUMS;void dfs(int t, vector<int> current) {if (t == N) {results.push_back(current);return;}for (int i = 0; i < N; i++) {if (visited[i] == true) continue;visited[i] = true;current.push_back(NUMS[i]);dfs(t + 1, current);current.pop_back();visited[i] = false;}}vector<vector<int>> permute(vector<int>& nums) {N = nums.size();NUMS = nums;visited.resize(N, false);dfs(0, {}); // 我想传空的vector<int>但其实主函数不需要它，我能不能传个不声明的return results;}
};

39. 组合总和

题目
给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

Emmm 收获很大

[2, 2, 3] 和 [3, 2, 2] 是一种情况，如果用常规的搜索（对于当前都 for 循环一遍可用的参数，解决不了（解决方法见后附）
搜索中，如果数量很大的值引用和地址引用，后者快的多多了

在这里插入图片描述
这个搜索思路实在是太棒了，最右那支是先给我用光某，二分的路径太棒了

在这里插入图片描述
1是最开始写的 vector<int> 传递，涉及很多次 cv 操作啥的，太慢
23是改成 vector<int> & 传递 👍🏿👍🏿

class Solution {
public:vector<vector<int>> results;vector<int> CANDIDATES;int N;void dfs(int left_target, int begin_idx, vector<int> &current) {if (left_target == 0) {results.push_back(current);return;}if (begin_idx == N) return;// 跳过当前 idxdfs(left_target, begin_idx + 1, current);// 选择当前 idxif (left_target - CANDIDATES[begin_idx] >= 0) {current.push_back(CANDIDATES[begin_idx]);dfs(left_target - CANDIDATES[begin_idx], begin_idx, current);current.pop_back();}return;}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {CANDIDATES = candidates;N = candidates.size();vector<int> tmp;dfs(target, 0, tmp);return results;}
};

22. 括号生成

题目
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

n 组括号，2n 个位置，暴力

class Solution {
public:int N;bool is_valid(string &str) {int open = 0, close = 0;bool flag = true;for (int i = 0; i < str.length(); i++) {if (str[i] == '(') {open++;if (open > N) {flag = false;break;}} else {close++;if (close > open) {flag = false;break;}}}return flag;}vector<string> results;void generate(string &str) {if (str.length() == 2*N) {if (is_valid(str)) {results.push_back(str);// 这里存的是一份拷贝，不会再受 &str 影响}return;}cout << str << endl;str += '(';generate(str);str.pop_back();str += ')';generate(str);str.pop_back();return;}vector<string> generateParenthesis(int n) {N = n;string str;generate(str);return results;}
};

优化一下，不到最后才判断合法性（很 ez 嘛，挑衅

class Solution {
public:int N;vector<string> results;void generate(string &str, int open, int close) {if (str.length() == 2*N) {results.push_back(str);// 这里存的是一份拷贝，不会再受 &str 影响return;}// cout << str << endl;if (open + 1 <= N) {str += '(';generate(str, open + 1, close);str.pop_back();} if (close + 1 <= open) {str += ')';generate(str, open, close + 1);str.pop_back();}return;}vector<string> generateParenthesis(int n) {N = n;string str;generate(str, 0, 0);return results;}
};

31. 下一个排序

题目
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须原地修改，只允许使用额外常数空间。

class Solution {
public:void nextPermutation(vector<int>& nums) {next_permutation(nums.begin(), nums.end());}
};

字典序是被玩明白了，太厉害了这个题解（所以我选择STL 🤭

在这里插入图片描述

class Solution {
public:void nextPermutation(vector<int>& nums) {int i = nums.size() - 2;while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}if (i >= 0) {int j = nums.size() - 1;while (j >= 0 && nums[i] >= nums[j]) {j--;}swap(nums[i], nums[j]);}reverse(nums.begin() + i + 1, nums.end());}
};作者：力扣官方题解
链接：https://leetcode.cn/problems/next-permutation/solutions/479151/xia-yi-ge-pai-lie-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

538. 把二叉搜索树转换为累加树

题目
给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

democlass Solution {
public:int up2now = 0;void dfs(TreeNode* fa) {if (fa == nullptr) return;dfs(fa->right);fa->val += up2now;up2now = fa->val;dfs(fa->left);return;}TreeNode* convertBST(TreeNode* root) {dfs(root);return root;}
};