刷题链接
LeetCode 热题 100
LeetCode 经典面试题 150
牛客 竞赛题库
洛谷 题目列表
OnlineJudge IO 练习
OJ在线编程常见输入输出练习场 | nowcoder
逗号分隔的输入
字符串排序(3) | nowcoder
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include <iostream> #include <vector> #include <algorithm> using namespace std;int main () { string strline; while (cin >> strline) { vector<string> strvec; string substr; int pos = 0 ; while ((pos = strline.find (',' )) != string::npos) { substr = strline.substr (0 , pos); strvec.push_back (substr); strline.erase (0 , pos+1 ); } strvec.push_back (strline); sort (strvec.begin (), strvec.end (), less<>()); for (int i=0 ; i<strvec.size ()-1 ; i++) cout << strvec[i] << "," ; cout << strvec.back () << endl; } return 0 ; }
如果输入是 int 型, 使用 stoi()
将 string 转换成 int;
如果输入是 float 型, 使用 stof()
将 string 转换成 float;
如果输入是 double 型, 使用 stod()
将 string 转换成 double;
未知元素个数的多行输入
A+B(7) | nowcoder
1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <iostream> using namespace std;int main () { int sum = 0 ; int num; while (cin >> num) { sum += num; if (getchar () == '\n' ){ cout << sum <<endl; sum = 0 ; } } }
数组
删除有序数组中的重复项
26. 删除有序数组中的重复项 | leetcode-hot100
1 2 3 4 5 6 7 8 9 10 11 class Solution {public : int removeDuplicates (vector<int >& nums) { int left=0 , right=0 , len=nums.size (); for (right=0 ; right<len; right++){ if (nums[right] != nums[left]) nums[++left] = nums[right]; } return left+1 ; } };
删除有序数组中的重复项 II
80. 删除有序数组中的重复项 II | leetcode-hot150
1 2 3 4 5 6 7 8 9 10 11 12 class Solution {public : int removeDuplicates (vector<int >& nums) { if (nums.size () <= 1 ) return nums.size (); int slow = 1 , fast = 2 ; for (; fast<nums.size (); ++fast) { if (nums[slow-1 ] == nums[fast]) continue ; nums[++slow] = nums[fast]; } return slow+1 ; } };
Hash
三数之和
15. 三数之和 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution {public : vector<vector<int >> threeSum (vector<int >& nums) { vector<vector<int >> ans; sort (nums.begin (), nums.end (), less ()); for (int i = 0 ; i < nums.size () - 2 ; i++) { if (i > 0 && nums[i] == nums[i-1 ]) continue ; int min = nums[i]; unordered_set<int > numset; for (int j = i + 1 ; j < nums.size (); j++) { if (j + 1 < nums.size () && nums[j] == nums[j+1 ]) { numset.insert (nums[j]); continue ; } int max = nums[j]; int res = -max-min; if (numset.find (res) != numset.end ()) ans.push_back ({min, res, max}); numset.insert (max); } } return ans; } };
注意上面注释的部分, 如果使用注释的逻辑, 会通过不了测试用例 nums = [0,0,0]
. 因为这个方法选择让 n 个重复元素的第 1 个元素进入循环体, 而 continue 掉后 n-1 个元素. 这样第 1 个重复元素进入循环体并被 insert 进 numset, 但是后面的重复元素全部被 continue 掉了, 没有机会进入循环体并被 numset.find(.)
1 if (j > i + 1 && nums[j] == nums[j-1 ]) continue ;
而下面的方法会 continue 掉 n 个重复元素的前 n-1 个元素, 只让最后 1 个元素进入循环体. 这样前 n-1 个重复元素会被 insert 到 numset 中 (由于 unordered_set 不保存重复元素, 所以最后 numset 中只有 1 个重复元素), 而最后 1 个重复元素会进入循环体, 并执行 numset.find(.)
.
1 2 3 if (j + 1 < nums.size () && nums[j] == nums[j+1 ]) { numset.insert (nums[j]); continue ; }
使用 multiset (超时)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : vector<vector<int >> threeSum (vector<int >& nums) { sort (nums.begin (), nums.end (), less ()); vector<vector<int >> ans; for (int i = 0 ; i < nums.size ()-2 ; i++) { int min = nums[i]; if (i > 0 && min == nums[i-1 ]) continue ; vector<int > numvec (nums.begin()+i+1 , nums.end()) ; for (int j = 0 ; j < numvec.size ()-1 ; j++) { int mid = numvec[j]; if (j > 0 && mid == numvec[j-1 ]) continue ; int res = -mid-min; multiset<int > numset (numvec.begin()+j+1 , numvec.end()) ; if (numset.find (res) != numset.end ()) ans.push_back ({min, mid, res}); } } return ans; } };
字符串
反转每对括号间的子串
1190. 反转每对括号间的子串 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution {public : string reverseParentheses (string s) { stack<string> strstack; string str = "" ; for (char ch : s) { if (ch == '(' ) { strstack.push (str); str = "" ; } else if (ch == ')' ) { reverse (str.begin (), str.end ()); str = strstack.top () + str; strstack.pop (); } else { str += ch; } } return str; } };
滑动窗口
3.无重复字符的最长子串
3. 无重复字符的最长子串 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : int lengthOfLongestSubstring (string s) { int n = s.size (); vector<int > numofch (128 , 0 ) ; int maxlen = 0 ; for (int left=0 , right=0 ; right<n; ++right) { ++numofch[s[right]]; while (left <= right && numofch[s[right]] == 2 ) { --numofch[s[left]]; ++left; } maxlen = max (maxlen, right-left+1 ); } return maxlen; } };
438.找到字符串中所有字母异位词
438. 找到字符串中所有字母异位词 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : vector<int > findAnagrams (string s, string p) { int slen = s.size (), plen = p.size (); if (slen < plen) return vector <int >(); vector<int > charp (26 , 0 ) , chars (26 , 0 ) ; for (char ch : p) ++charp[ch - 'a' ]; for (int i=0 ; i<plen; ++i) ++chars[s[i] - 'a' ]; vector<int > ans; if (chars == charp) ans.push_back (0 ); for (int i=0 ; i+plen<slen; ++i) { --chars[s[i] - 'a' ]; ++chars[s[i+plen] - 'a' ]; if (chars == charp) ans.push_back (i+1 ); } return ans; } };
KMP算法
【最浅显易懂的 KMP 算法讲解】| bilibili
28. 实现 strStr() | 代码随想录
28. 找出字符串中第一个匹配项的下标 | leetcode
前缀表
1 2 模式串: A B A B C 部分匹配表: 0 0 1 2 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution {public : void getNext (int * next, const string& s) { int j = 0 ; next[0 ] = 0 ; for (int i = 1 ; i < s.size (); i++) { while (j > 0 && s[i] != s[j]) { j = next[j - 1 ]; } if (s[i] == s[j]) { j++; } next[i] = j; } } int strStr (string haystack, string needle) { if (needle.size () == 0 ) { return 0 ; } vector<int > next (needle.size()) ; getNext (&next[0 ], needle); int j = 0 ; for (int i = 0 ; i < haystack.size (); i++) { while (j > 0 && haystack[i] != needle[j]) { j = next[j - 1 ]; } if (haystack[i] == needle[j]) { j++; } if (j == needle.size () ) { return (i - needle.size () + 1 ); } } return -1 ; } };
树
94.二叉树的中序遍历
94. 二叉树的中序遍历 | leetcode-hot100
使用递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution {public : vector<int > ans; void inorder (TreeNode* root) { if (root == nullptr ) return ; inorder (root->left); ans.push_back (root->val); inorder (root->right); } vector<int > inorderTraversal (TreeNode* root) { inorder (root); return ans; } };
使用栈
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution {public : vector<int > ans; vector<int > inorderTraversal (TreeNode* root) { if (root == nullptr ) return vector <int >(); stack<TreeNode*> st; st.push (root); while (!st.empty ()) { TreeNode* cur = st.top (); st.pop (); if (cur != nullptr ) { if (cur->right != nullptr ) st.push (cur->right); st.push (cur); st.push (nullptr ); if (cur->left != nullptr ) st.push (cur->left); } else { cur = st.top (); st.pop (); ans.push_back (cur->val); } } return ans; } };
102.二叉树的层序遍历
102. 二叉树的层序遍历 | leetcode-hot100
使用 queue<pair<TreeNode*, int>>
数据结构来记录层数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution {public : vector<vector<int >> levelOrder (TreeNode* root) { if (root == nullptr ) return vector<vector<int >>(); vector<vector<int >> ans; queue<pair<TreeNode*, int >> node2layer; node2layer.push ({root, 0 }); while (!node2layer.empty ()) { auto cur = node2layer.front (); node2layer.pop (); TreeNode* node = cur.first; int layer = cur.second; if (node->left != nullptr ) node2layer.push ({node->left, layer+1 }); if (node->right != nullptr ) node2layer.push ({node->right, layer+1 }); if (ans.size () < layer+1 ) ans.push_back (vector <int >()); ans[layer].push_back (node->val); } return ans; } };
使用 nullptr
来分隔不同的 layer
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution {public : vector<vector<int >> levelOrder (TreeNode* root) { if (root == nullptr ) return vector<vector<int >>(); queue<TreeNode*> q; q.push (root); q.push (nullptr ); vector<vector<int >> ans; vector<int > layer; while (!q.empty ()) { auto cur = q.front (); q.pop (); if (cur == nullptr ) { ans.push_back (layer); layer = vector <int >(); if (!q.empty ()) q.push (nullptr ); continue ; } if (cur->left != nullptr ) q.push (cur->left); if (cur->right != nullptr ) q.push (cur->right); layer.push_back (cur->val); } return ans; } };
101.对称二叉树
101. 对称二叉树 | leetcode-hot100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution {public : bool check (TreeNode* left, TreeNode* right) { if (left == nullptr && right == nullptr ) return true ; if (left == nullptr && right != nullptr ) return false ; if (left != nullptr && right == nullptr ) return false ; if (left->val != right->val) return false ; return check (left->left, right->right) && check (left->right, right->left); } bool isSymmetric (TreeNode* root) { return check (root->left, root->right); } };
543.二叉树的直径
543. 二叉树的直径 | leetcode-hot100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution {public : int diameter = 0 ; int maxdepth (TreeNode* root) { if (root == nullptr ) return 0 ; int leftdepth = maxdepth (root->left); int rightdepth = maxdepth (root->right); diameter = max (leftdepth + rightdepth, diameter); return max (leftdepth, rightdepth) + 1 ; } int diameterOfBinaryTree (TreeNode* root) { maxdepth (root); return diameter; } };
108.将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树 | leetcode-hot100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution {public : TreeNode* sortedArrayToBST (vector<int >& nums) { int size = nums.size (); if (size == 0 ) return nullptr ; vector<int > leftpart (nums.begin(), nums.begin()+size/2 ) ; vector<int > rightpart (nums.begin() + size/2 + 1 , nums.end()) ; TreeNode *root = new TreeNode (nums[size/2 ]); root->left = sortedArrayToBST (leftpart); root->right = sortedArrayToBST (rightpart); return root; } };
105.从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树 | leetcode-hot100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution {public : TreeNode* buildTree (vector<int >& preorder, vector<int >& inorder) { if (preorder.size () == 0 ) return nullptr ; int rootVal = preorder[0 ]; auto rootIter = find (inorder.begin (), inorder.end (), rootVal); vector<int > leftInorder (inorder.begin(), rootIter) ; vector<int > rightInorder (rootIter+1 , inorder.end()) ; vector<int > leftPreorder (preorder.begin()+1 , preorder.begin()+1 +leftInorder.size()) ; vector<int > rightPreorder (preorder.begin() - rightInorder.size(), preorder.end()) ; TreeNode* root = new TreeNode (rootVal); root->left = buildTree (leftPreorder, leftInorder); root->right = buildTree (rightPreorder, rightInorder); return root; } };
437.路径总和 III
437. 路径总和 III | leetcode-hot100
回溯法遍历树的每条分支
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution {public : int ans = 0 ; long long target, cursum = 0 ; unordered_map<long long , int > sum2count = {{0 , 1 }}; void backtrace (TreeNode* root) { if (root == nullptr ) return ; cursum += root->val; if (sum2count.find (cursum - target) != sum2count.end ()) ans += sum2count[cursum - target]; sum2count.find (cursum) == sum2count.end () ? sum2count[cursum] = 1 : sum2count[cursum]++; backtrace (root->left); backtrace (root->right); sum2count[cursum]--; cursum -= root->val; } int pathSum (TreeNode* root, int targetSum) { target = targetSum; backtrace (root); return ans; } };
使用 multiset 可以简化代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution {public : multiset<long long > presum = {0 }; long long tempsum = 0 , ans = 0 ; void backtrace (TreeNode* root, int targetSum) { if (root == nullptr ) return ; tempsum += root->val; ans += presum.count (tempsum - targetSum); presum.insert (tempsum); if (root->left) backtrace (root->left, targetSum); if (root->right) backtrace (root->right, targetSum); presum.erase (presum.find (tempsum)); tempsum -= root->val; } int pathSum (TreeNode* root, int targetSum) { backtrace (root, targetSum); return ans; } };
124. 二叉树中的最大路径和
124. 二叉树中的最大路径和 | leetcode-hot100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution {public : int maxpathsum = INT16_MIN; int maxFork (TreeNode* cur) { if (cur == nullptr ) return 0 ; int maxleft = maxFork (cur->left); int maxright = maxFork (cur->right); int maxfork = cur->val + max (0 ,max (maxleft, maxright)); maxpathsum = max (maxpathsum, maxleft + cur->val + maxright); return max (0 , maxfork); } int maxPathSum (TreeNode* root) { maxFork (root); return maxpathsum; } };
236.二叉树的最近公共祖先
236. 二叉树的最近公共祖先 | leetcode
递归是回溯的思想
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution {public : TreeNode* lowestCommonAncestor (TreeNode* root, TreeNode* p, TreeNode* q) { if (root == nullptr || root == p || root == q) return root; TreeNode* left = lowestCommonAncestor (root->left, p, q); TreeNode* right = lowestCommonAncestor (root->right, p, q); if (left == nullptr && right == nullptr ) return nullptr ; if (left == nullptr && right != nullptr ) return right; if (left != nullptr && right == nullptr ) return left; return root; } };
208.前缀树 Trie (26叉树)
208. 实现 Trie (前缀树)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 class Trie {private : vector<Trie*> children; bool isEnd; public : Trie () : children (26 , nullptr ), isEnd (false ) {} void insert (string word) { Trie* node = this ; for (char ch : word) { if (node->children[ch-'a' ] == nullptr ) { node->children[ch-'a' ] = new Trie (); } node = node->children[ch-'a' ]; } node->isEnd = true ; } bool search (string word) { Trie* node = this ; for (char ch : word) { if (node->children[ch-'a' ] == nullptr ) return false ; node = node->children[ch-'a' ]; } return node->isEnd; } bool startsWith (string prefix) { Trie* node = this ; for (char ch : prefix) { if (node->children[ch-'a' ] == nullptr ) return false ; node = node->children[ch-'a' ]; } return true ; } };
动态规划
背包问题
背包问题 :给定一组物品,每种物品都有自己的重量、价格以及数量。再给定一个最多能装重量为 W 的背包。现在选择将一些物品放入背包中,请问在总重量不超过背包载重上限的情况下,能装入背包的最大价值总和是多少?
根据物品限制条件的不同,背包问题可分为:0-1 背包问题、完全背包问题、多重背包问题、分组背包问题,以及混合背包问题等。
0-1 背包问题 :有 n 件物品和有一个最多能装重量为 W 的背包。第 i 件物品的重量为 weight[i],价值为 value[i],每件物品有且只有 1 件。请问在总重量不超过背包载重上限的情况下,能装入背包的最大价值是多少?
完全背包问题 :有 n 种物品和一个最多能装重量为 W 的背包,第 i 种物品的重量为 weight[i],价值为 value[i],每种物品数量没有限制。请问在总重量不超过背包载重上限的情况下,能装入背包的最大价值是多少?
0-1 背包问题
NC145 01背包
NC145 01背包 | nowcoder
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution {public : int knapsack (int V, int n, vector<vector<int >>& vw) { vector<int > dp (V+1 , 0 ) ; for (vector<int > vwi : vw) { for (int v = dp.size ()-1 ; v >= vwi[0 ]; v--) { dp[v] = max (dp[v], dp[v-vwi[0 ]] + vwi[1 ]); } } return dp[V]; } };
494.目标和
一个限制条件的01背包
494. 目标和 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution {public : int findTargetSumWays (vector<int >& nums, int target) { int sum = accumulate (nums.begin (), nums.end (), 0 ); int positive = (sum + target) / 2 ; if ((sum + target) % 2 == 1 ) return 0 ; if (sum < abs (target)) return 0 ; vector<int > dp (positive + 1 , 0 ) ; dp[0 ] = 1 ; for (int i=0 ; i<nums.size (); i++) { int num = nums[i]; for (int j=dp.size ()-1 ; j>=num; j--) { dp[j] = dp[j] + dp[j-num]; } } return dp[positive]; } };
回溯法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution {public : vector<int > temp; int tempsum = 0 ; int count = 0 ; void backtrace (vector<int >& nums, int positive, int curindex) { if (tempsum == positive) { count++; } if (tempsum > positive) return ; for (int i=curindex; i<nums.size (); i++) { temp.push_back (nums[i]); tempsum += nums[i]; backtrace (nums, positive, i+1 ); temp.pop_back (); tempsum -= nums[i]; } } int findTargetSumWays (vector<int >& nums, int target) { int sum = accumulate (nums.begin (), nums.end (), 0 ); int Positive = (sum + target) / 2 ; if ((sum + target) % 2 == 1 ) return 0 ; if (sum < target) return 0 ; backtrace (nums, Positive, 0 ); return count; } };
416.分割等和子集
416. 分割等和子集 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution {public : bool canPartition (vector<int >& nums) { int sum = accumulate (nums.begin (), nums.end (), 0 ); if (sum % 2 == 1 ) return false ; int target = sum / 2 ; vector<bool > dp (target+1 , false ) ; dp[0 ] = true ; for (int num : nums) { for (int i = target; i-num>=0 ; --i) { dp[i] = dp[i] || dp[i-num]; } } return dp[target]; } };
474.一和零
两个限制条件的01背包
474. 一和零 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution {public : int count0 (string str) { int numof0 = 0 ; for (char c : str) { if (c == '0' ) numof0++; } return numof0; } int findMaxForm (vector<string>& strs, int m, int n) { vector<vector<int >> dp (m+1 , vector <int >(n+1 , 0 )); for (int k=0 ; k<strs.size (); k++) { string str = strs[k]; int zeros = count0 (str); int ones = str.size () - zeros; for (int i=m; i>=zeros; i--) { for (int j=n; j>=ones; j--) { dp[i][j] = max (dp[i][j], dp[i-zeros][j-ones]+1 ); } } } return dp[m][n]; } };
回溯法(超时)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution {public : vector<string> tempStrs; int maxSubSize = 0 ; int zeros=0 , ones=0 ; int count0 (string str) { int numof0 = 0 ; for (char c : str) { if (c == '0' ) numof0++; } return numof0; } void backtrace (vector<string>& strs, int m, int n, int startIndex) { if (zeros <= m && ones <= n && tempStrs.size () > maxSubSize) { maxSubSize = tempStrs.size (); } if (zeros > m || ones > n) return ; for (int i=startIndex; i<strs.size (); i++) { tempStrs.push_back (strs[i]); zeros += count0 (strs[i]); ones += strs[i].size () - count0 (strs[i]); backtrace (strs, m, n, i+1 ); tempStrs.pop_back (); zeros -= count0 (strs[i]); ones -= strs[i].size () - count0 (strs[i]); } } int findMaxForm (vector<string>& strs, int m, int n) { backtrace (strs, m, n, 0 ); return maxSubSize; } };
完全背包问题
完全背包问题
完全背包问题 | 有道小图灵
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <iostream> using namespace std;int main () { int M, N; cin >> M >> N; int W[N], C[N]; for (int i=0 ; i<N; ++i) cin >> W[i] >> C[i]; int dp[M+1 ] = {0 }; for (int i=0 ; i<N; ++i) { int w=W[i], c=C[i]; for (int j=w; j<=M; ++j) { dp[j] = max (dp[j], dp[j-w] + c); } } cout << "max=" << dp[M] << endl; return 0 ; }
139.单词拆分
139. 单词拆分 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution {public : bool wordBreak (string s, vector<string>& wordDict) { vector<bool > dp (s.size()+1 , false ) ; dp[0 ] = true ; for (int i=0 ; i<=s.size (); i++) { for (string word : wordDict) { int wordsize= word.size (); if (i-wordsize < 0 ) continue ; string substr = s.substr (i-wordsize, wordsize); dp[i] = dp[i] || (dp[i-wordsize] && substr == word); } } return dp[s.size ()]; } };
377.组合总和 Ⅳ
377. 组合总和 Ⅳ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : int combinationSum4 (vector<int >& nums, int target) { vector<int > dp (target+1 , 0 ) ; dp[0 ] = 1 ; for (int i=0 ; i<=target; i++) { for (int num : nums) { if (i - num < 0 ) continue ; if (dp[i] > INT_MAX - dp[i - num]) continue ; dp[i] = dp[i] + dp[i - num]; } } return dp[target]; } };
322.零钱兑换
322. 零钱兑换
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : int coinChange (vector<int >& coins, int amount) { vector<int > dp (amount+1 , INT16_MAX) ; dp[0 ] = 0 ; for (int i=0 ; i<=amount; i++) { for (int coin : coins) { if (i-coin < 0 ) continue ; dp[i] = min (dp[i], dp[i-coin]+1 ); } } return dp[amount] == INT16_MAX ? -1 : dp[amount]; } };
518.零钱兑换 II
518. 零钱兑换 II | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int change (int amount, vector<int >& coins) { vector<int > dp (amount+1 , 0 ) ; dp[0 ] = 1 ; for (int coin : coins) { for (int i=coin; i<=amount; i++) { dp[i] = dp[i] + dp[i-coin]; } } return dp[amount]; } };
300.最长递增子序列
300. 最长递增子序列 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int lengthOfLIS (vector<int >& nums) { int n = nums.size (); vector<int > dp (n, 1 ) ; for (int i=0 ; i<n; ++i) { for (int j=0 ; j<i; ++j) { if (nums[i] > nums[j]) dp[i] = max (dp[i], dp[j] + 1 ); } } return *max_element (dp.begin (), dp.end ()); } };
5.最长回文子串
5. 最长回文子串 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution {public : string longestPalindrome (string s) { int n = s.size (); string ans (1 , s[0 ]) ; vector<vector<bool >> P (n, vector <bool >(n, true )); int bias = 1 ; for (int i=0 ; i<n-1 ; ++i) { int j = i + bias; P[i][j] = (s[i] == s[j]); if (P[i][j] && j-i+1 > ans.size ()) ans = s.substr (i, 2 ); } for (bias=2 ; bias<n; ++bias) { for (int i=0 ; i+bias<n; ++i) { int j = i + bias; P[i][j] = (s[i] == s[j]) && P[i+1 ][j-1 ]; if (P[i][j] && j-i+1 > ans.size ()) ans = s.substr (i, j-i+1 ); } } return ans; } };
72.编辑距离
72. 编辑距离 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution {public : int minDistance (string word1, string word2) { int n1 = word1.size (), n2 = word2.size (); vector<vector<int >> dp (n1+1 , vector <int >(n2+1 , 0 )); for (int i=0 ; i<=n1; ++i) dp[i][0 ] = i; for (int j=0 ; j<=n2; ++j) dp[0 ][j] = j; for (int i=1 ; i<=n1; ++i) { for (int j=1 ; j<=n2; ++j) { if (word1[i-1 ] == word2[j-1 ]) dp[i][j] = dp[i-1 ][j-1 ]; else dp[i][j] = min (min (dp[i][j-1 ], dp[i-1 ][j]), dp[i-1 ][j-1 ]) + 1 ; } } return dp[n1][n2]; } };
数的划分
数的划分 | nowcoder
这题要求将整数n分成k份,并且需要去重(115、151、511视为一种方案),我们可以按照从小到大的顺序对k份数进行排序,以保证唯一性。
例如n=7,k=3,考虑
我们要保证遍历所有的情况,并且不能有重复
数字是递增的(严格说是非减的)
第一个数从1开始增加到n/k (不能为0,也不能超过n/k)
k数字的和为n
使用递归
1 f (n, k) = f (n-1 , k-1 ) + f (n-k, k)
其中f(n-1, k-1)
为第一个位置为1的情况,剩下的n-1分到第二到第k位置,对应 115, 124, 133
;
f(n-k, k)
为第一个数不为1的情况,此时所有的数都至少为1(因为要求非减),等价于将n-k分到1-k个位置即可,对应 223
。
还可以考虑动态规划,递推公式是类似的
1 dp[n][k] = dp[n-1 ][k-1 ] + dp[n-k][k]
放苹果
放苹果 | nowcoder
考虑 7 个苹果分到 3 个盘子的情况, 考虑去重, 苹果的数量按照从小到大的顺序排列
1 2 007, 016, 025, 034, 115, 124, 133, 223 \____存在空盘子___/ \____没有空盘子___/
按照上面的情况去划分, 列出递推公式, dp[m][n]
表示将 m 个苹果放入 n 个盘子的情况数
1 dp[m][n] = dp[m][n-1] + dp[m-n][n], (m >= n)
其中 dp[m][n-1]
表示存在空盘子的情况, 将 m 个苹果放入 n-1 个盘子; dp[m-n][n]
表示不存在空盘子的情况, 将 m 个苹果先拿出 n 个放入每个盘子 (每个盘子放 1 个苹果), 然后将剩下的 m-n 个苹果再放入 n 个盘子.
上面递推公式的前提是 m >= n, 当 m < n 时, 即苹果数量 m 小于盘子数量 n 时, 一定存在空盘子, 此时的递推公式是
1 dp[m][n] = dp[m][n-1] = ... = dp[m][m+1] = dp[m][m], (m < n)
dp[m][m]
又可以按照上面的递推公式进行递推.
打家劫舍系列
198.打家劫舍
198. 打家劫舍 | leetcode & 代码随想录
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int rob (vector<int >& nums) { int n = nums.size (); vector<int > dp (n+2 , 0 ) ; for (int i=2 ; i<n+2 ; i++) { int num = nums[i-2 ]; dp[i] = max (dp[i-1 ], dp[i-2 ] + num); } return dp.back (); } };
213.打家劫舍 II
213. 打家劫舍 II | leetcode & 代码随想录
分别"掐头"和"去尾"将环拆成两种链进行考虑
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : int rob (vector<int >& nums) { int n = nums.size (); if (n==1 ) return nums[0 ]; vector<int > dp (n+2 -1 , 0 ) ; for (int i=2 ; i<n+2 -1 ; i++) { int num = nums[i-2 ]; dp[i] = max (dp[i-1 ], dp[i-2 ] + num); } int dp0 = dp.back (); dp = vector <int >(n+2 , 0 ); for (int i=3 ; i<n+2 ; i++) { int num = nums[i-2 ]; dp[i] = max (dp[i-1 ], dp[i-2 ] + num); } int dp1 = dp.back (); return max (dp0, dp1); } };
337.打家劫舍 III
337. 打家劫舍 III | leetcode & 代码随想录
买卖股票的最佳时机系列
区间覆盖问题
1024. 视频拼接 | leetcode
数组划分类型
410.分割数组的最大值
410. 分割数组的最大值 | leetcode
这个代码没用使用前缀, 是为了方便阅读, 显示地将求和公式表示出来
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution {public : int splitArray (vector<int >& nums, int k) { int n = nums.size (); vector<vector<int >> dp (n+1 , vector <int >(k+1 , INT32_MAX)); for (int i=1 ; i<=n; ++i) { dp[i][1 ] = accumulate (nums.begin (), nums.begin ()+i, 0 ); } for (int j=2 ; j<=k; ++j) { for (int i=j; i<=n; ++i) { for (int k=i-1 ; k>=j-2 ; --k) { int sumk2i = accumulate (nums.begin ()+k, nums.begin ()+i, 0 ); dp[i][j] = min (dp[i][j], max (dp[k][j-1 ], sumk2i)); } } } return dp[n][k]; } };
下面的代码使用前缀和, 通过全部用例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution {public : vector<int > accumu; void getAccumu (const vector<int >& nums, int & n) { accumu = vector <int >(n+1 , 0 ); for (int i=1 ; i<=n; ++i) { accumu[i] = accumu[i-1 ] + nums[i-1 ]; } } int splitArray (vector<int >& nums, int k) { int n = nums.size (); getAccumu (nums, n); vector<vector<int >> dp (n+1 , vector <int >(k+1 , INT32_MAX)); for (int i=1 ; i<=n; ++i) { dp[i][1 ] = accumu[i]; } for (int j=2 ; j<=k; ++j) { for (int i=j; i<=n; ++i) { for (int k=i-1 ; k>=j-2 ; --k) { int sumk2i = accumu[i] - accumu[k]; dp[i][j] = min (dp[i][j], max (dp[k][j-1 ], sumk2i)); } } } return dp[n][k]; } };
状态压缩dp
1879.两个数组最小的异或值之和
1879. 两个数组最小的异或值之和 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution {public : int minimumXORSum (vector<int >& nums1, vector<int >& nums2) { int n = nums1.size (); vector<int > f (1 <<n, INT_MAX) ; f[0 ] = 0 ; for (int mask=1 ; mask<(1 <<n); ++mask) { int count = __builtin_popcount(mask); for (int i=0 ; i<n; ++i) { if ((mask & (1 <<i)) != 0 ) { f[mask] = min (f[mask], f[mask^(1 <<i)] + (nums1[count-1 ] ^ nums2[i])); } } } return f[(1 << n) -1 ]; } };
2172.数组的最大与和
2172. 数组的最大与和 | leetcode
图论
并查集
小美的朋友关系
美团2024春招第一场第4题:小美的朋友关系 | nowcoder
深搜 dfs 超时
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include <iostream> #include <vector> #include <unordered_set> using namespace std;bool friendship = false ;unordered_set<int > visited; void dfs (vector<unordered_set<int >> & relation, int src, int des) { visited.insert (src); if (friendship == true ) return ; if (src == des) {friendship = true ; return ;} for (int i : relation[src]) { if (visited.find (i) == visited.end ()) dfs (relation, i, des); } return ; } int main () { int n, m, q; cin >> n >> m >> q; vector<unordered_set<int >> relation (n+1 , unordered_set <int >()); for (int i = 0 ; i < m; i++) { int u, v; cin >> u >> v; relation[u].insert (v); relation[v].insert (u); } for (int i = 0 ; i < q; i++) { int op, u, v; cin >> op >> u >> v; if (op == 1 ) { relation[u].erase (v); relation[v].erase (u); } else { dfs (relation, u, v); if (friendship == true ) cout << "Yes" << endl; else cout << "No" << endl; friendship = false ; visited.clear (); } } return 0 ; }
寻找图中是否存在路径
1971. 寻找图中是否存在路径 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution {private : vector<int > father; public : void joint (int u, int v) { int rootu = find (u); int rootv = find (v); if (rootu == rootv) return ; father[rootv] = rootu; } int find (int u) { if (father[u] == u) return u; else { father[u] = find (father[u]); return father[u]; } } bool validPath (int n, vector<vector<int >>& edges, int source, int destination) { father = vector <int >(n); for (int i = 0 ; i < n; i++) father[i] = i; for (auto uv : edges) { int u = uv[0 ], v = uv[1 ]; joint (u, v); } int rootu = find (source); int rootv = find (destination); return rootu == rootv; } };
冗余连接
684. 冗余连接
685. 冗余连接 II
最小生成树
最小生成树
NC159. 最小生成树 | nowcoder
连接所有点的最小费用
1584. 连接所有点的最小费用 | leetcode
最短路径
郊区春游
郊区春游 | nowcoder
拓扑排序
课程表
207. 课程表 | Leetcode Hot100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution {public : bool canFinish (int numCourses, vector<vector<int >>& prerequisites) { vector<int > indegree (numCourses, 0 ) ; vector<vector<int >> nextCourses (numCourses, vector <int >()); for (auto & aibi : prerequisites) { int ai = aibi[0 ], bi = aibi[1 ]; indegree[ai]++; nextCourses[bi].push_back (ai); } queue<int > indeg_zero; for (int i=0 ; i<numCourses; i++) { if (indegree[i] == 0 ) indeg_zero.push (i); } int counts = 0 ; while (!indeg_zero.empty ()) { int course = indeg_zero.front (); indeg_zero.pop (); counts++; for (int nextcorse : nextCourses[course]) { indegree[nextcorse]--; if (indegree[nextcorse] == 0 ) indeg_zero.push (nextcorse); } } return counts == numCourses; } };
农场杂务
P1113 杂务 | luogu
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std;int main () { int n; cin >> n; vector<vector<int >> pre2nxt (n+1 , vector <int >()); vector<int > indegree (n+1 , 0 ) , times (n+1 ) , accumu_time (n+1 , 0 ) ; queue<int > indegree_zero; for (int i=1 ; i<=n; ++i) { int idx; cin >> idx; cin >> times[idx]; while (true ) { int pre; cin >> pre; if (pre != 0 ) { pre2nxt[pre].push_back (idx); ++indegree[idx]; } else { break ; } } } for (int idx=1 ; idx<=n; ++idx) { if (indegree[idx]==0 ) { indegree_zero.push (idx); accumu_time[idx] = times[idx]; } } while (!indegree_zero.empty ()) { int idx = indegree_zero.front (); indegree_zero.pop (); for (int nxt : pre2nxt[idx]) { accumu_time[nxt] = max (accumu_time[nxt], accumu_time[idx]+times[nxt]); if (--indegree[nxt]==0 ) indegree_zero.push (nxt); } } cout << *max_element (accumu_time.begin (), accumu_time.end ()) << endl; return 0 ; }
回溯
全排列
46. 全排列 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution {public : vector<vector<int >> ans; void backtrace (vector<int >& nums, int idx) { if (idx == nums.size ()) {ans.push_back (nums); return ;} for (int i=idx; i<nums.size (); ++i) { swap (nums[idx], nums[i]); backtrace (nums, idx+1 ); swap (nums[idx], nums[i]); } } vector<vector<int >> permute (vector<int >& nums) { backtrace (nums, 0 ); return ans; } };
方法二, 使用两个集合
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : vector<int > temp; vector<vector<int >> ans; void backtrace (unordered_set<int >& numset) { if (numset.empty ()) { ans.push_back (temp); return ; } for (auto num : numset) { unordered_set<int > tempset (numset) ; tempset.erase (num); temp.push_back (num); backtrace (tempset); temp.pop_back (); } } vector<vector<int >> permute (vector<int >& nums) { unordered_set<int > numset (nums.begin(), nums.end()) ; backtrace (numset); return ans; } };
全排列II
47. 全排列 II | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution {public : vector<int > temp; vector<vector<int >> ans; void backtrace (vector<int >& nums, int idx) { if (temp.size () == nums.size ()) { ans.push_back (temp); return ; } unordered_set<int > used; for (int i=idx; i<nums.size (); i++) { if (used.find (nums[i]) != used.end ()) continue ; used.insert (nums[i]); temp.push_back (nums[i]); swap (nums[idx], nums[i]); backtrace (nums, idx+1 ); swap (nums[idx], nums[i]); temp.pop_back (); } return ; } vector<vector<int >> permuteUnique (vector<int >& nums) { backtrace (nums, 0 ); return ans; } };
78.子集
78. 子集 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution {public : vector<int > temp; vector<vector<int >> ans; void backtrace (vector<int >& nums, int idx) { ans.push_back (temp); for (int i=idx; i<nums.size (); ++i) { temp.push_back (nums[i]); backtrace (nums, i+1 ); temp.pop_back (); } } vector<vector<int >> subsets (vector<int >& nums) { backtrace (nums, 0 ); return ans; } };
39.组合总和
39. 组合总和 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution {public : int tempsum = 0 ; vector<int > temp; vector<vector<int >> ans; void backtrace (vector<int >& candidates, int target, int idx) { if (tempsum > target) return ; if (tempsum == target) { ans.push_back (temp); return ; } for (int i = idx; i < candidates.size (); ++i) { temp.push_back (candidates[i]); tempsum += candidates[i]; backtrace (candidates, target, i); tempsum -= candidates[i]; temp.pop_back (); } } vector<vector<int >> combinationSum (vector<int >& candidates, int target) { backtrace (candidates, target, 0 ); return ans; } };
40.组合总和II
40. 组合总和 II | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 class Solution {public : vector<vector<int >> ans; vector<int > temp; int tempsum = 0 ; void backtrace (vector<int >& candidates, int target, int idx) { if (tempsum > target) return ; if (tempsum == target) { ans.push_back (temp); return ; } for (int i = idx; i < candidates.size (); ++i) { if (i-1 >= idx && candidates[i] == candidates[i-1 ]) continue ; temp.push_back (candidates[i]); tempsum += candidates[i]; backtrace (candidates, target, i+1 ); tempsum -= candidates[i]; temp.pop_back (); } } vector<vector<int >> combinationSum2 (vector<int >& candidates, int target) { sort (candidates.begin (), candidates.end ()); backtrace (candidates, target, 0 ); return ans; } };
22.括号生成
22. 括号生成 | leetcode-hot100
回溯法
1 2 3 4 5 0: ( 1: (( () 2: ((( (() ()( 3: (((( ((() (()( (()) ()(( ()() ... number of '(' >= number of ')' ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution {public : vector<string> ans; string temp; void backtrace (int n, int open, int close) { if (open < close) return ; if (open > n) return ; if (close == n) {ans.push_back (temp); return ;} temp.push_back ('(' ); backtrace (n, open+1 , close); temp.pop_back (); temp.push_back (')' ); backtrace (n, open, close+1 ); temp.pop_back (); } vector<string> generateParenthesis (int n) { backtrace (n, 0 , 0 ); return ans; } };
131.分割回文串
131. 分割回文串 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution {public : vector<vector<bool >> palindrome; void initialize_palindrome (string& s) { int n = s.size (); palindrome = vector<vector<bool >>(n, vector <bool >(n, true )); int bias = 1 ; for (int i=0 ; i+bias<n; ++i) { int j = i + bias; palindrome[i][j] = s[i] == s[j]; } for (; bias<n; ++bias) { for (int i=0 ; i+bias<n; ++i) { int j = i + bias; palindrome[i][j] = (s[i]==s[j]) && (palindrome[i+1 ][j-1 ]); } } } vector<string> temp; vector<vector<string>> ans; void backtrace (string& s, int left) { int n = s.size (); if (left == n) {ans.push_back (temp); return ;} for (int right=left; right<n; ++right) { if (palindrome[left][right] == false ) continue ; temp.push_back (s.substr (left, right-left+1 )); backtrace (s, right+1 ); temp.pop_back (); } } vector<vector<string>> partition (string s) { int n = s.size (); initialize_palindrome (s); backtrace (s, 0 ); return ans; } };
51.N皇后
51. N 皇后 | leetcode-hot100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution {public : unordered_set<int > occupied_col, occupied_antidiag, occupied_diag; vector<vector<string>> ans; vector<string> solu; void backtrace (int n, int r) { if (r == n) { ans.push_back (solu); return ; } string temprow (n, '.' ) ; for (int c=0 ; c<n; c++) { if (occupied_col.count (c)!=0 || occupied_antidiag.count (r-c)!=0 || occupied_diag.count (r+c)!=0 ) continue ; occupied_col.insert (c); occupied_antidiag.insert (r-c); occupied_diag.insert (r+c); temprow[c] = 'Q' ; solu.push_back (temprow); backtrace (n, r+1 ); solu.pop_back (); temprow[c] = '.' ; occupied_col.erase (c); occupied_antidiag.erase (r-c); occupied_diag.erase (r+c); } return ; } vector<vector<string>> solveNQueens (int n) { backtrace (n, 0 ); return ans; } };
491.非递减子序列
491. 非递减子序列 | leetcode
世界杯积分问题
世界杯积分问题 | 科大讯飞23校招研发类第2题 | nowcoder
回溯法遍历, 一共 3^10 种可能. 并通过将 vector<int>
转换成 string
, 从而借助 unorder_set<string>
进行去重和查找
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include <iostream> #include <numeric> #include <vector> #include <algorithm> #include <unordered_set> using namespace std;vector<vector<int >> rowcol = {{0 ,1 },{0 ,2 },{0 ,3 },{0 ,4 }, {1 ,2 },{1 ,3 },{1 ,4 }, {2 ,3 },{2 ,4 }, {3 ,4 }}; vector<vector<int >> gain = {{0 ,3 }, {1 ,1 }, {3 ,0 }}; vector<vector<int >> scorematrix (5 , vector <int >(5 , 0 )); vector<int > finalscore (5 , 0 ) ;unordered_set<string> scoreset; string vec2str (vector<int > & vec) { string str; for (int i : vec) { str.push_back ((char )(i + '0' )); } return str; } void backtrace (int idx) { if (idx == 10 ) { for (int i=0 ; i<5 ; i++) { finalscore[i] = accumulate (scorematrix[i].begin (), scorematrix[i].end (), 0 ); } sort (finalscore.begin (), finalscore.end (), greater<>()); string scorestr = vec2str (finalscore); scoreset.insert (scorestr); } if (idx >= 10 ) return ; int row = rowcol[idx][0 ]; int col = rowcol[idx][1 ]; for (auto & score : gain) { scorematrix[row][col] = score[0 ]; scorematrix[col][row] = score[1 ]; backtrace (idx+1 ); scorematrix[row][col] = 0 ; scorematrix[col][row] = 0 ; } return ; } int main () { backtrace (0 ); int totalnum = scoreset.size (); int inputnum; cin >> inputnum; totalnum == inputnum ? cout << "yes " : cout << "no " ; vector<int > inputscore (5 , 0 ) ; for (int i=0 ; i<5 ; i++) cin >> inputscore[i]; string inputstr = vec2str (inputscore); scoreset.find (inputstr) != scoreset.end () ? cout << "yes" : cout << "no" ; return 0 ; }
二分查找
35.搜索插入位置
35. 搜索插入位置 | leetcode-hot100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution {public : int searchInsert (vector<int >& nums, int target) { int left=0 , right=nums.size ()-1 ; while (left <= right) { int mid = (left + right) / 2 ; if (nums[mid] == target) return mid; if (nums[mid] < target) left = mid + 1 ; if (target < nums[mid]) right = mid - 1 ; } return left; } };
34.在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution {public : vector<int > searchRange (vector<int >& nums, int target) { int lbound = -1 , rbound = -1 ; int left = 0 , right = nums.size () - 1 ; while (left <= right) { int mid = (left + right) / 2 ; if (nums[mid] == target) lbound = mid; if (nums[mid] < target) { left = mid + 1 ; } else { right = mid - 1 ; } } left = 0 , right = nums.size () - 1 ; while (left <= right) { int mid = (left + right) / 2 ; if (nums[mid] == target) rbound = mid; if (nums[mid] <= target) { left = mid + 1 ; } else { right = mid - 1 ; } } return vector <int >({lbound, rbound}); } };
4.寻找两个正序数组的中位数
4. 寻找两个正序数组的中位数 | leetcode-hot100
双指针法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution {public : double findMedianSortedArrays (vector<int >& nums1, vector<int >& nums2) { int n1 = nums1.size (), n2 = nums2.size (); int midIdx1 = (n1 + n2 - 1 ) / 2 ; int midIdx2 = (n1 + n2 - 1 ) / 2 + (n1 + n2 - 1 ) % 2 ; int idx1 = 0 , idx2 = 0 ; double mid1=0 , mid2=0 ; bool finish = false ; while (true ) { if (idx2 >= n2 || idx1 < n1 && nums1[idx1] <= nums2[idx2]) { if ((idx1 + idx2) == midIdx1) mid1 = nums1[idx1]; if ((idx1 + idx2) == midIdx2) {mid2 = nums1[idx1]; break ;} idx1++; } if (idx1 >= n1 || idx2 < n2 && nums2[idx2] <= nums1[idx1]) { if ((idx1 + idx2) == midIdx1) mid1 = nums2[idx2]; if ((idx1 + idx2) == midIdx2) {mid2 = nums2[idx2]; break ;} idx2++; } } return (mid1 + mid2) / 2 ; } };
栈
单调栈
84.柱状图中最大的矩形
84. 柱状图中最大的矩形 | leetcode-hot100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution {public : int largestRectangleArea (vector<int >& heights) { int n = heights.size (); vector<int > left (n) , right (n) ; stack<int > mono_stack; for (int idx=0 ; idx<n; idx++) { while (!mono_stack.empty () && heights[mono_stack.top ()] >= heights[idx]) mono_stack.pop (); left[idx] = mono_stack.empty () ? -1 : mono_stack.top (); mono_stack.push (idx); } mono_stack = stack <int >(); for (int idx=n-1 ; idx>=0 ; idx--) { while (!mono_stack.empty () && heights[mono_stack.top ()] >= heights[idx]) mono_stack.pop (); right[idx] = mono_stack.empty () ? n : mono_stack.top (); mono_stack.push (idx); } int maxarea = 0 ; for (int idx=0 ; idx<n; idx++) { maxarea = max (maxarea, (right[idx] - left[idx] - 1 ) * heights[idx]); } return maxarea; } };
位运算
477.汉明距离总和
477. 汉明距离总和 | leetcode
136.只出现一次的数字
136. 只出现一次的数字 | leetcode-hot100
技巧&其它
31.下一个排列
31. 下一个排列 | leetcode-hot100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution {public : void nextPermutation (vector<int >& nums) { int lessidx = -1 , greateridx = -1 ; for (int i=nums.size ()-2 ; i>=0 ; i--) { if (nums[i] < nums[i+1 ]) { lessidx = i; break ; } } if (lessidx == -1 ) { reverse (nums.begin (), nums.end ()); return ; } for (int i=nums.size ()-1 ; i>lessidx; i--) { if (nums[i] > nums[lessidx]) { greateridx = i; break ; } } swap (nums[lessidx], nums[greateridx]); reverse (nums.begin ()+lessidx+1 , nums.end ()); return ; } };
组合数的和
现有n个人, 要从这n个人中选任意数量的人组成一只队伍, 再在这些人中选出一名队长, 求不同的方案数对 10^9+7
取模的结果. 如果两个方案选取的人的集合不同或选出的队长不同, 则认为这两个方案是不同的.
a n s = 1 × C n 1 + 2 × C n 2 + ⋯ + n × C n n ( i C n i = n C n − 1 i − 1 ) = n × ( C n − 1 0 + C n − 1 1 + ⋯ + C n − 1 n − 1 ) = n × 2 n − 1 \begin{split}
ans &= 1 × C_n^1 + 2 × C_n^2 + \cdots + n × C_n^n\\
(iC_n^i = nC_{n-1}^{i-1})
&= n × (C_{n-1}^0 + C_{n-1}^1 + \cdots + C_{n-1}^{n-1})\\
&= n × 2^{n-1}
\end{split}
an s ( i C n i = n C n − 1 i − 1 ) = 1 × C n 1 + 2 × C n 2 + ⋯ + n × C n n = n × ( C n − 1 0 + C n − 1 1 + ⋯ + C n − 1 n − 1 ) = n × 2 n − 1
1 2 long long ans = n;ans = ans << (n-1 ) % 1000000007 ;
i × C n i = i × n ! ( n − i ) ! i ! = n × ( n − 1 ) ! ( n − i ) ! ( i − 1 ) ! = n × C n i i×C_n^i = i × \frac{n!}{(n-i)!i!} = n × \frac{(n-1)!}{(n-i)!(i-1)!} = n × C_n^i
i × C n i = i × ( n − i )! i ! n ! = n × ( n − i )! ( i − 1 )! ( n − 1 )! = n × C n i
475.供暖器
475. 供暖器 | leetcode
134.加油站
134. 加油站 | leetcode
189.轮转数组
189. 轮转数组 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : void rotate (vector<int >& nums, int k) { if (k == 0 ) return ; int n = nums.size (); int period = lcm (n, k); int elems = period / k; int numOfPeriods = n / elems; for (int i = 0 ; i < numOfPeriods; i++) { int temp = nums[i]; int cur = i; do { cur = (cur + k) % n; swap (temp, nums[cur]); } while (cur != i); } } };
54.螺旋矩阵
54. 螺旋矩阵 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution {public : vector<int > spiralOrder (vector<vector<int >>& matrix) { int rows = matrix.size (), cols = matrix.back ().size (); int row = 0 , col = -1 ; vector<int > ans; while (cols > 0 && rows > 0 ) { for (int i=0 ; i<cols; ++i) {ans.push_back (matrix[row][++col]);} --rows; for (int i=0 ; i<rows; ++i) {ans.push_back (matrix[++row][col]);} --cols; if (cols <= 0 || rows <= 0 ) break ; for (int i=0 ; i<cols; ++i) {ans.push_back (matrix[row][--col]);} --rows; for (int i=0 ; i<rows; ++i) {ans.push_back (matrix[--row][col]);} --cols; } return ans; } };
48.旋转图像
48. 旋转图像 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : void rotate (vector<vector<int >>& matrix) { int n = matrix.size (); for (int i = 0 ; i < (n+1 )/2 ; i++) { for (int j = 0 ; j < n/2 ; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[n-1 -j][i]; matrix[n-1 -j][i] = matrix[n-1 -i][n-1 -j]; matrix[n-1 -i][n-1 -j] = matrix[j][n-1 -i]; matrix[j][n-1 -i] = temp; } } } };
43.字符串相乘
43. 字符串相乘 | leetcode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution {public : string multiply (string num1, string num2) { int n1 = num1.size (), n2 = num2.size (); vector<vector<int >> products; for (int i=0 ; i<n2; ++i) { char ch2 = num2[n2-1 -i]; int carry = 0 ; vector<int > product (i,0 ) ; for (int j=0 ; j<n1; ++j) { char ch1 = num1[n1-1 -j]; int num = (ch2-'0' )*(ch1-'0' ) + carry; product.push_back (num % 10 ); carry = num / 10 ; } if (carry != 0 ) product.push_back (carry); products.push_back (product); } vector<int > product = products[0 ]; for (int i=1 ; i<n2; ++i) { int carry = 0 ; for (int j=0 ; j<product.size (); ++j) { int num = product[j] + products[i][j] + carry; product[j] = num % 10 ; carry = num / 10 ; } for (int j=product.size (); j<products[i].size (); ++j) { int num = products[i][j] + carry; product.push_back (num % 10 ); carry = num / 10 ; } if (carry != 0 ) product.push_back (carry); } if (product.back () == 0 ) return "0" ; string ans; for (int i=product.size ()-1 ; i>=0 ; --i) { ans.push_back (product[i]+'0' ); } return ans; } };