个人网站备案地址,阿里云增加网站,创建一个网址需要多少钱,做网站用phpcms还是STL
【C】蓝桥杯必备 算法竞赛常用STL万字总结_蓝桥杯算法竞赛_Cpt1024的博客-CSDN博客
day1 1#xff1a;正确
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
// 中序遍历一遍二叉树#xff0c;并统计节点数目
class Solution {
public:int c…STL
【C】蓝桥杯必备 算法竞赛常用STL万字总结_蓝桥杯算法竞赛_Cpt1024的博客-CSDN博客
day1 1正确
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
// 中序遍历一遍二叉树并统计节点数目
class Solution {
public:int count 0; // 统计节点数void inorder(TreeNode* root) {if(!root) return;inorder(root-left);count 1;inorder(root-right);}int countNodes(TreeNode* root) {inorder(root);return count;}
}; 2不会
93. 复原 IP 地址 - 力扣LeetCode
class Solution {
public:vectorstring restoreIpAddresses(string s) {// 对于 25525511135 中最左边的255我们有不同的划分方式// 25 5 和 255 具体划分的依据不清楚是什么}
};
3解答错误
123. 买卖股票的最佳时机 III - 力扣LeetCode
class Solution {
public:int maxProfit(vectorint prices) {// 1 特判// 如果数组只有一个元素不能交易返回 0if (prices.size() 1) return 0;// 如果数组有两个元素判断能否交易if (prices.size() 2) {return (prices[1] - prices[0]) 0 ? (prices[1] - prices[0]) : 0;} // 2 先判断能否完成至少一次交易// 先找到最左边的 [a, b] 可交易区间 a bint l1, r1, l2, r2;bool flag1 false; // flag1 true 表示至少可以完成一次交易bool flag2 false; // flag2 true 表示至少可以完成一次交易for(int i 0; i prices.size() - 2; i) {for(int j i 1; j prices.size() - 1; j) {if (prices[j] prices[i]) {flag1 true;l1 i;r1 j;break;}}}if (flag1 false) {return 0;}// 再找最右边的 [a, b] 可交易区间 a bfor (int i prices.size() - 1; i 1; --i) {for (int j prices.size() - 2; j 0; --j) {if (prices[i] prices[j]) {l2 i;r2 j;break;}}}if (r1 l2) {flag2 true;}// 3 如果只有一段可交易区间int value -1;if (flag1 true flag2 false) {for(int i 0; i prices.size() - 2; i) {for(int j i 1; j prices.size() - 1; j) {if (prices[j] prices[i]) {value max((prices[j] - prices[i]), value);}}}return value;}// 4 如果可能有两段可交易区间if (flag1 true flag2 true) {int i1, j1, i2, j2;j2 prices.size() - 1;i2 prices.size() - 2;for(i1 0; i1 prices.size() - 2; i1) {for(j1 i1 1; j1 prices.size() - 1; j1) {if (prices[j1] prices[i1]) {for (i2 prices.size() - 2; i2 j1; --i2) {for (j2 prices.size() - 1; j2 i2; --j2) {if (prices[j2] prices[i2]) {value max(value, (prices[j1] - prices[i1]) (prices[j2] - prices[i2]) );}} }}}}return value;}return 0;}
};
4: 解答错误
不知道动规错在哪
416. 分割等和子集 - 力扣LeetCode
class Solution {
public:bool canPartition(vectorint nums) {// 1 特判// 如果只有一个元素不可能if (nums.size() 1) {return false;}// 如果和为奇数不可能int sum accumulate(nums.begin(), nums.end(), 0);int frac sum % 2;int half sum / 2;if (frac 1) {return false;}// 如果最大值大于一半不可能int maxValue -1;for (int i 0; i nums.size() - 1; i) {maxValue max(maxValue, nums[0]);}if (maxValue half) {return false;}// 2int n nums.size();sort(nums.begin(), nums.end());vectorvectorbool dp(n, vectorbool(half 1, false));for (int i 0; i n; i) {dp[i][0] true;}for (int j 1; j half; j) {if (j nums[0]) {dp[0][j] true;} else {dp[0][j] false;}}for (int i 1; i n; i) {for (int j 1; j half; j) {if (j nums[i]) {dp[i][j] dp[i - 1][j - nums[i]] || dp[i - 1][j];} else {dp[i][j] dp[i - 1][j];}}}return dp[n - 1][half 1];}
};
5解答错误
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
class Solution {
public:int length 0; // 记录最大长度void bfs(vectorvectorint matrix, int i, int j, int m, int n) {length 1;matrix[i][j] -10;if ( ((i - 1) 0) ((matrix[i - 1][j]) matrix[i][j]) ) {bfs(matrix, i - 1, j, m, n);length -1;}if ( ((j - 1) 0) ((matrix[i][j - 1]) matrix[i][j]) ) {bfs(matrix, i, j - 1, m, n);length -1;}if ( ((i 1) m - 1) ((matrix[i 1][j]) matrix[i][j]) ) {bfs(matrix, i 1, j, m, n);length -1;}if ( ((j 1) n - 1) ((matrix[i][j 1]) matrix[i][j]) ) {bfs(matrix, i, j 1, m, n);length -1;}}int longestIncreasingPath(vectorvectorint matrix) {int m matrix.size(), n matrix[0].size();for (int i 0; i m; i) {for (int j 0; j n; j) {bfs(matrix, i, j, m, n);}}return length;}
}; 6有思路
class Solution {
public:int equalSubstring(string s, string t, int maxCost) {int n s.size();vectorint cost(n, 0);for (int i 0; i n; i) {cost[i] abs(s[i] - t[i]);}// 双指针滑动窗口求最大长度// 计算滑窗内的 cost 值int l1 0, r1 0;int ans 0;int res 0;while (r1 n l1 r1) {int costRange 0;// 计算当前窗口中的 cost 和 长度for (int i l1; i r1; i) {costRange cost[i];ans r1 - l1 1;}// 区间cost小则递增右边界// 此时也需要更新 resif (costRange maxCost) {res max(res, ans);r1;}// 区间 cost 相等递增左边界// 储存当前值if (costRange maxCost) {res max(res, ans);l1;}// 区间 cost 大则递增左边界if (costRange maxCost) {l1;}}return res;}
}; 7不会
410. 分割数组的最大值 - 力扣LeetCode 8正确
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {int n nums.size();vectorint next(n, -1);for (int i 0; i n; i) {int j (i 1) % n;while (j ! i) {if (nums[j] nums[i]) {next[i] nums[j];break;}j (j 1) % n;}}return next;}
};
回溯
1: 77 √
path递归路径
index下标
停止条件path.size() k
递归方向[index, n]
class Solution {
public:// 储存递归路径vectorint temp;vectorvectorint res;void dfs(int index, int n, int k) {// 剪枝temp 长度加上区间 [index, n] 的长度小于 k不可能构造出长度为 k 的 tempif ((temp.size() (n - index 1)) k) {return;}// 停止条件if (temp.size() k) {res.push_back(temp);return;}// 从 index 到 n 进行回溯for (int i index; i n; i) {// 考虑当前位置temp.push_back(i);dfs(i 1, n, k);temp.pop_back();}}vectorvectorint combine(int n, int k) {dfs(1, n, k);return res;}
}; 2: 39 √
class Solution {
public:// 有序数组可以优化vectorvectorint res;vectorint temp;vectorvectorint combinationSum(vectorint candidates, int target) {dfs(0, 0, candidates, target);return res;}void dfs(int index, int sum, vectorint candidates, int target) {if (sum target) {if (sum target) {res.push_back(temp);}return;}for (int i index; i candidates.size() - 1; i) {temp.push_back(candidates[i]);// 这次选的是i则继续从i考虑不考虑小于 i 的dfs(i, sum candidates[i], candidates, target);temp.pop_back();}}
};
class Solution {
public:// 有序数组可以优化vectorvectorint res;vectorint temp;vectorvectorint combinationSum(vectorint candidates, int target) {sort(candidates.begin(), candidates.end());dfs(0, 0, candidates, target);return res;}void dfs(int index, int sum, vectorint candidates, int target) {if (sum target) {if (sum target) {res.push_back(temp);}return;}for (int i index; i candidates.size() - 1; i) {// 优化if (sum candidates[i] target) return;temp.push_back(candidates[i]);// 这次选的是i则继续从i考虑不考虑小于 i 的dfs(i, sum candidates[i], candidates, target);temp.pop_back();}}
}; 3: 40 : 同层去重 √
class Solution {
public:vectorvectorint res; // 存储结果的二维向量vectorint temp; // 存储临时组合的向量vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(), candidates.end()); // 对候选数字进行排序以方便去重和处理dfs(0, 0, temp, candidates, target); // 开始深度优先搜索return res; // 返回结果}// 深度优先搜索函数void dfs(int index, int sum, vectorint temp, vectorint candidates, int target) {if (sum target) { // 如果当前和大于等于目标值if (sum target) { // 如果当前和等于目标值res.push_back(temp); // 将临时组合加入结果中}return; // 结束当前递归}unordered_setint occ; // 使用哈希集合来处理去重for (int i index; i candidates.size() - 1; i) {if (occ.find(candidates[i]) ! occ.end()) { // 如果当前数字已经在组合中出现过continue; // 继续下一次循环避免重复组合}occ.insert(candidates[i]); // 将当前数字加入哈希集合中temp.push_back(candidates[i]); // 将当前数字加入临时组合中dfs(i 1, sum candidates[i], temp, candidates, target); // 递归搜索下一层temp.pop_back(); // 回溯将最后一个数字从临时组合中移除}}
};4: 216
class Solution {
public:vectorint path;vectorvectorint res;vectorvectorint combinationSum3(int k, int n) {dfs(1, 0, k, n);return res;}void dfs(int index, int sum, int k, int n) {if (sum n) {if (sum n path.size() k) {res.push_back(path);}}for (int i index; i 9; i) {if (sum i n) return;path.push_back(i);dfs(i 1, sum i, k, n);path.pop_back();}}
};
5: 93
#include iostream
#include stringint main() {std::string str Hello, World!;// 从索引位置2开始截取5个字符得到 llo, std::string sub1 str.substr(2, 5);// 从索引位置7开始截取到字符串末尾得到 World!std::string sub2 str.substr(7);std::cout sub1: sub1 std::endl;std::cout sub2: sub2 std::endl;return 0;
}class Solution {
public:vectorstring res; // 存储结果的向量vectorstring restoreIpAddresses(string s) {vectorstring segments(4); // 创建一个具名的向量对象用于存储 IP 地址的 4 段dfs(0, 0, segments, s); // 开始深度优先搜索return res; // 返回结果}// 将向量 segments 转换为字符串表示string toString(vectorstring segments) {string result;for (int i 0; i 3; i) {result segments[i] .;}result segments[3];return result;}// 检查字符串是否满足 IP 地址的要求bool check(string s) {return (s[0] ! 0 || s 0) stoi(s) 256; // 满足 IP 地址范围条件}// 深度优先搜索函数void dfs(int index, int segindex, vectorstring segments, string s) {if (segindex 4 || index s.length()) {if (segindex 4 index s.length()) {res.push_back(toString(segments)); // 将合法的 IP 地址加入结果向量}return; // 结束当前递归}for (int i 1; i 3; i) { // 尝试将当前段长度从 1 到 3if (i index s.length()) return; // 如果超过字符串长度结束本次尝试string sub s.substr(index, i); // 获取当前段if (check(sub)) {segments[segindex] sub; // 将当前段加入向量 segmentsdfs(index i, segindex 1, segments, s); // 递归尝试下一段}}}
};6: 78 √
class Solution {
public:vectorvectorint res;vectorint path;vectorvectorint subsets(vectorint nums) {dfs(0, nums);return res;}void dfs(int index, vectorint nums) {res.push_back(path);for (int i index; i nums.size() - 1; i) {path.push_back(nums[i]);dfs(i 1, nums);path.pop_back();}}
}; 7: 491 √
class Solution {
public:vectorvectorint res;vectorint path;vectorvectorint findSubsequences(vectorint nums) {dfs(0, nums);return res;}unordered_setint appear;void dfs(int index, vectorint nums) {if (path.size() 2) {res.push_back(path);}// 同层去重 [4, 6, 6, 7]unordered_setint occ;for (int i index; i nums.size() - 1; i) {if (path.size() 0 nums[i] path.back() || occ.find(nums[i]) ! occ.end()) continue;occ.insert(nums[i]);path.push_back(nums[i]);dfs(i 1, nums);path.pop_back();}}
};
8: 46 排列问题 √
排列问题
class Solution {
public:vectorint path;vectorint used; // 将 vectorbool 改为 vectorintvectorvectorint res;vectorvectorint permute(vectorint nums) {used.resize(nums.size(), 0); // 初始化 used 向量dfs(nums);return res;}void dfs(vectorint nums) {if (path.size() nums.size()) {res.push_back(path);return;}for (int i 0; i nums.size(); i) {if (!used[i]) {used[i] 1; // 将 false 改为 1表示已使用path.push_back(nums[i]);dfs(nums);path.pop_back();used[i] 0; // 将 true 改为 0表示未使用}}}
};9: 47
class Solution {
public:vectorvectorint res;vectorint used;vectorint path;vectorvectorint permuteUnique(vectorint nums) {used.resize(nums.size(), 0);dfs(nums);return res;}void dfs(vectorint nums) {if (path.size() nums.size()) {res.push_back(path);return;}unordered_setint occ;for (int i 0; i nums.size(); i) {if (used[i] 0 occ.find(nums[i]) occ.end()) {occ.insert(nums[i]);used[i] 1;path.push_back(nums[i]);dfs(nums);path.pop_back();used[i] 0;}}}
}; 10698
class Solution {
public:vectorint subs; // subs 向量用于存储当前每个子集的和int ave; // ave 存储每个子集的目标平均和// 判断是否能将数组分成 k 个和相等的子集bool canPartitionKSubsets(vectorint nums, int k) {int sumN 0; // sumN 存储数组 nums 中所有元素的和subs.resize(k, 0); // 初始化 subs 向量包含 k 个元素初始值为 0sumN accumulate(nums.begin(), nums.end(), 0); // 计算数组 nums 的总和if (sumN % k ! 0) {return false; // 如果总和不能被 k 整除无法分成 k 个和相等的子集}ave sumN / k; // 计算每个子集的目标平均和sort(nums.begin(), nums.end(), greater()); // 对 nums 数组进行逆序排序以便从大到小选择元素return dfs(0, nums, k); // 调用深度优先搜索函数判断是否能分成 k 个和相等的子集}// 深度优先搜索函数尝试将每个元素分配到不同的子集中bool dfs(int index, vectorint nums, int k) {if (index nums.size()) {for (int sub : subs) if (sub ! ave) return false; // 如果有子集的和不等于 ave返回 falsereturn true; // 所有子集的和都等于 ave返回 true}unordered_setint occ; // 使用哈希集合记录已经尝试过的和for (int i 0; i k; i) {if (subs[i] nums[index] ave || occ.find(subs[i]) ! occ.end()) continue; // 如果加入到当前子集后超过 ave 或者已经尝试过当前和跳过occ.insert(subs[i]); // 将当前子集和加入到哈希集合subs[i] nums[index]; // 将当前元素加入到当前子集if (dfs(index 1, nums, k)) return true; // 递归尝试将下一个元素加入子集subs[i] - nums[index]; // 回溯将当前元素从子集中移除}return false; // 无法将元素分配到子集中}
};
