刷题链接

LeetCode 热题 100

LeetCode 经典面试题 150

牛客 竞赛题库

洛谷 题目列表

OnlineJudge IO 练习

OJ在线编程常见输入输出练习场 | nowcoder

逗号分隔的输入

字符串排序(3) | nowcoder

cpp
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) { // get the whole line
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<>()); // sort

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

cpp
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

cpp
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; // left是index,left+1是size
}
};

删除有序数组中的重复项 II

80. 删除有序数组中的重复项 II | leetcode-hot150

cpp
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; // slow是index,slow+1是size
}
};

Hash

三数之和

15. 三数之和 | leetcode

cpp
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 > i + 1 && nums[j] == nums[j-1]) continue;
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(.)

cpp
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(.).

cpp
1
2
3
if(j + 1 < nums.size() && nums[j] == nums[j+1]) {
numset.insert(nums[j]); continue;
}

使用 multiset (超时)

cpp
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());
// cout << "nums: "; for (auto i : nums) cout << i << ","; cout << endl;
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());
// cout << "numvec: "; for(int i : numvec) cout << i << ","; cout << endl;
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());
// cout << "numset: "; for(int i : numset) cout << i << ","; cout << endl;
if(numset.find(res) != numset.end())
ans.push_back({min, mid, res});
}
}
return ans;
}
};

字符串

反转每对括号间的子串

1190. 反转每对括号间的子串 | leetcode

cpp
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) {
// (ed(et(oc))el)
// reverse("ed" + reverse("et" + reverse("oc")) + "el")
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 { // alphabet
str += ch;
}
}
return str;
}
};

滑动窗口

3.无重复字符的最长子串

3. 无重复字符的最长子串 | leetcode

cpp
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); // num of char in ascii
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

cpp
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);
// initialization
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);
// (i+0), [i+1, ..., i+plen-1, (i+plen)], i+plen+1
for(int i=0; i+plen<slen; ++i) {
// 滑动窗口, 删掉 s[i] 增加 s[i+plen]
--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

cpp
1
2
主串: ABABABCAA
子串: ABABC

前缀表

plaintext
1
2
    模式串: A B A B C
部分匹配表: 0 0 1 2 0
cpp
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);
// for(int i : next) cout << i << ", "; cout << endl;
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

使用递归

cpp
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
/**
* 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) {}
* };
*/
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;
}
};

使用栈

cpp
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
/**
* 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) {}
* };
*/
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>> 数据结构来记录层数

cpp
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
/**
* 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) {}
* };
*/
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

cpp
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
/**
* 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) {}
* };
*/
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); // nullptr 用于分隔 layer
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

cpp
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
/**
* 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) {}
* };
*/
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

cpp
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
/**
* 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) {}
* };
*/
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

cpp
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
/**
* 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) {}
* };
*/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
int size = nums.size();
if(size == 0) return nullptr;
// [0, size/2), size/2, [size/2+1, end]
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

cpp
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
/**
* 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) {}
* };
*/
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()+1+leftInorder.size(), preorder.end());
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

回溯法遍历树的每条分支

cpp
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
/**
* 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) {}
* };
*/
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;
// 注意hashmap检索与更新的先后
if(sum2count.find(cursum - target) != sum2count.end())
ans += sum2count[cursum - target]; // 先
sum2count.find(cursum) == sum2count.end() ?
sum2count[cursum] = 1 : sum2count[cursum]++; // 后
backtrace(root->left);
// sum2count[cursum]--;
// cursum -= root->val;
// cursum += root->val;
// sum2count[cursum]++;
backtrace(root->right);
sum2count[cursum]--;
cursum -= root->val;
}

int pathSum(TreeNode* root, int targetSum) {
target = targetSum;
backtrace(root);
return ans;
}
};

使用 multiset 可以简化代码

cpp
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
/**
* 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) {}
* };
*/
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;
// tempsum - x = targetsum;
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

cpp
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
/**
* 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) {}
* };
*/
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

递归是回溯的思想

cpp
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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// if find "p" or "q" or reach "nullptr", then return root;
if(root == nullptr || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);

// When p and q are not found in the left either right subtrees:
if(left == nullptr && right == nullptr) return nullptr;
// When p and q exist only in the right subtree
if(left == nullptr && right != nullptr) return right;
// When p and q exist only in the left subtree
if(left != nullptr && right == nullptr) return left;
// When p and q are found in the left and right subtrees respectively:
// In this case, root is the lowest common ancestor of p and q.
return root; // if(left != nullptr && right != nullptr)
}
};

208.前缀树 Trie (26叉树)

208. 实现 Trie (前缀树)

cpp
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
// 26叉树

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;
}
};

/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/

动态规划

背包问题

背包问题:给定一组物品,每种物品都有自己的重量、价格以及数量。再给定一个最多能装重量为 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

cpp
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:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* 计算01背包问题的结果
* @param V int整型 背包的体积
* @param n int整型 物品的个数
* @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
* @return int整型
*/
int knapsack(int V, int n, vector<vector<int>>& vw) {
// write code here
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

cpp
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);
// positive - negative = target; negative = sum - positive;
// => positive = (sum + target) / 2
int positive = (sum + target) / 2;

if((sum + target) % 2 == 1) return 0;
if(sum < abs(target)) return 0;

// dp[j]表示nums中和为j的表达式个数
// dp[j]一共会迭代nums.size()次
vector<int> dp(positive + 1, 0);
// positive = 0, 即target = -sum, 此时只有一种表达式——全为负号
dp[0] = 1;
// 开始遍历nums中的元素
for(int i=0; i<nums.size(); i++) {
int num = nums[i];
// 因为我们用的是一维的dp,注意更新dp[j]要从高位往低位更新。这样我们在这一轮更新dp中,
// 更新高位的dp[j]时取到的低位的dp[j-num]还是上一轮的值,而不是这一轮新更新的值
for(int j=dp.size()-1; j>=num; j--) {
dp[j] = dp[j] + dp[j-num];
}
}
return dp[positive];
}
};

回溯法

cpp
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++;
// return; 这里不能return因为还有0的情况
}

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);
// positive - negative = target; negative = sum - positive;
// => positive = (sum + target) / 2
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

cpp
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
/*
nums = [1,5,11,5], sum = 22, target = 11
: [0];
---------------------------------------------------------------------------
1: [0], [1];
---------------------------------------------------------------------------
5: [0], [1], [0,5], [1,5];
---------------------------------------------------------------------------
11: [0], [1], [0,5], [1,5], [0,11], [1,11], [0,5,11], [1,5,11];
---------------------------------------------------------------------------
5: [0], [1], [0,5], [1,5], [0,11], [1,11], [0,5,11], [1,5,11],
[0,5], [1,5], [0,5,5], [1,5,5], [0,11,5], [1,11,5], [0,5,11,5], [1,5,11,5].
*/
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

cpp
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) {
// 二维的dp数组,其中dp[i][j]表示numof0<=i, numof1<=j的最大子集长度
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];
}
};

回溯法(超时)

cpp
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;
}
};

完全背包问题

完全背包问题

完全背包问题 | 有道小图灵

cpp
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() {
// process input
int M, N; cin >> M >> N;
int W[N], C[N];
for(int i=0; i<N; ++i) cin >> W[i] >> C[i];
// dp recursion
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

cpp
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
/*
s = "applepenapple", wordDict = ["apple", "pen"]
0 : "";
1 : "apple", "pen";
2 : "appleapple", "applepen", "penapple", "penpen";
3 : "appleappleapple", "applepenapple", "penappleapple", "penpenapple",
"appleapplepen", "applepenpen", "penapplepen", "penpenpen";
......
*/
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. 组合总和 Ⅳ

cpp
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;
// 外层对dp中的元素进行遍历
for(int i=0; i<=target; i++) {
// 内层对nums中元素进行遍历
for(int num : nums) {
if(i - num < 0) continue;
// if(dp[i] + dp[i - nums] > INT_MAX) continue;
if(dp[i] > INT_MAX - dp[i - num]) continue; // int类型overflow了
dp[i] = dp[i] + dp[i - num];
}
}
return dp[target];
}
};

322.零钱兑换

322. 零钱兑换

cpp
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; // 初始化为0
for(int i=0; i<=amount; i++) {
for(int coin : coins) {
if(i-coin < 0) continue;
// dp[i]表示当前凑成i最少的硬币个数
// dp[i-coin]+1表示当前凑成i-coin最少的硬币个数+1(在i-coin的基础上再加一个coin)
dp[i] = min(dp[i], dp[i-coin]+1);
}
}
return dp[amount] == INT16_MAX ? -1 : dp[amount];
}
};

518.零钱兑换 II

518. 零钱兑换 II | leetcode

cpp
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; // amount=0时要初始化为1
for(int coin : coins) {
// 这里要从小到大进行更新,这样一个coin可以反复使用
// 因为这样,dp[i-coin]中的值就是这轮更新的新值(加了coin后)
// 比如coints = [1,2,5], amount=5, 初始dp = [1, 0, 0, 0, 0, 0]
// 使用coin=1去更新dp, dp = [1, 1, 1, 1, 1, 1]
// 例如在更新dp[2]的时候, dp[2] = dp[2] + dp[2-coin], 其中的" + dp[2-coin]"表示加入coin能够新增的次数
// 由于dp[2-coin]在dp[2]之前已经使用coin更新了, 所以上面的操作相当于重复使用了coin
for(int i=coin; i<=amount; i++) {
dp[i] = dp[i] + dp[i-coin];
}
}
return dp[amount];
}
};

300.最长递增子序列

300. 最长递增子序列 | leetcode

cpp
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

cpp
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
/*
P[i][j]表示s[i]...s[j]是否为回文串
初始化:
P[0][0] = P[1][1] = ... = P[n-1]P[n-1] = 1
P[0][1] = (s[0]==s[1]) ... P[n-2][n-1] = (s[n-2]==s[n-1])
递推公式:
P[i][j] = (s[i]==s[j]) && P[i+1]P[j-1]

b a b a d b a b a d b a b a d b a b a d b a b a d
b T | T F | T F T | T F T F | T F T F F
a T | T F | T F T | T F T F | T F T F
b T | T F | T F F | T F F | T F F
a T | T F | T F | T F | T F
d T | T | T | T | T
*/

class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
// int maxlen = 1, left = 0, right = 0;
string ans(1, s[0]);
// initialization, bias = 0
vector<vector<bool>> P(n, vector<bool>(n, true));
// initialization, bias = 1
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);
}
// update
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

cpp
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();
// dp[i][j] 表示 w1[0]...w1[i-1] 到 w2[0]...w2[j-1] 的最短编辑距离
// i=0 和 j=0 时分别表示 word1 为空串和 word2 为空串
vector<vector<int>> dp(n1+1, vector<int>(n2+1, 0));
// initialization
for(int i=0; i<=n1; ++i) dp[i][0] = i;
for(int j=0; j<=n2; ++j) dp[0][j] = j;
// recursion
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,考虑

plaintext
1
2
3
4
1,1,5
1,2,4
1,3,3
2,2,3

我们要保证遍历所有的情况,并且不能有重复

  • 数字是递增的(严格说是非减的)
  • 第一个数从1开始增加到n/k (不能为0,也不能超过n/k)
  • k数字的和为n

使用递归

cpp
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

还可以考虑动态规划,递推公式是类似的

cpp
1
dp[n][k] = dp[n-1][k-1] + dp[n-k][k]

放苹果

放苹果 | nowcoder

考虑 7 个苹果分到 3 个盘子的情况, 考虑去重, 苹果的数量按照从小到大的顺序排列

plaintext
1
2
007, 016, 025, 034, 115, 124, 133, 223
\____存在空盘子___/ \____没有空盘子___/

按照上面的情况去划分, 列出递推公式, dp[m][n] 表示将 m 个苹果放入 n 个盘子的情况数

plaintext
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 时, 一定存在空盘子, 此时的递推公式是

plaintext
1
dp[m][n] = dp[m][n-1] = ... = dp[m][m+1] = dp[m][m], (m < n)

dp[m][m] 又可以按照上面的递推公式进行递推.

打家劫舍系列

198.打家劫舍

198. 打家劫舍 | leetcode & 代码随想录

cpp
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 & 代码随想录

分别"掐头"和"去尾"将环拆成两种链进行考虑

cpp
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

这个代码没用使用前缀, 是为了方便阅读, 显示地将求和公式表示出来

cpp
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
/*
示例 nums = [7,2,5,10,8], k = 2
i\j 1 2
1 [7] [\]
2 [72] min{[7|2]}
3 [725] min{[7|25], [72|5]}
4 [7250] min{[7|250], [72|50], [725|0]}
5 [72508] min{[7|2508],[72|508],[725|08],[7250|8]}
*/

class Solution {
public:
int splitArray(vector<int>& nums, int k) {
int n = nums.size();
// dp[i][j] 表示将前 i 个数 (n[0]~n[i-1]) 分成 j 组的最小最大和
vector<vector<int>> dp(n+1, vector<int>(k+1, INT32_MAX));
// 初始化, j=1
for(int i=1; i<=n; ++i) {
dp[i][1] = accumulate(nums.begin(), nums.begin()+i, 0);
}
// 递推更新, j=2,3,...,k
for(int j=2; j<=k; ++j) {
// 已知分成 j-1 组的最小最大和, 求分成 j 组的最小最大和
for(int i=j; i<=n; ++i) {
// 计算 nums 前 i 个数 n[0] ~ n[i-1] 分成 j 组的最小最大和. 已知:
// 前 j-1 个数 n[0] ~ n[j-2] 分成 j-1 组的最小最大和, 可以计算 {n[0]~n[j-2]}|(n[j-1]~n[i-1])
// 前 j 个数 n[0] ~ n[j-1] 分成 j-1 组的最小最大和, 可以计算 {n[0]~n[j-1]}|(n[j] ~n[i-1])
// 。。。。。。
// 前 i-1 个数 n[0] ~ n[i-2] 分成 j-1 组的最小最大和, 可以计算 {n[0]~n[i-2]}|(n[i-1])
// 从其中选取 min, 即为将 n[0] ~ n[i-1] 分成 j 组的最小最大和
for(int k=i-1; k>=j-2; --k) {
int sumk2i = accumulate(nums.begin()+k, nums.begin()+i, 0); // sum{n[k],...,n[i-1]}
dp[i][j] = min(dp[i][j], max(dp[k][j-1], sumk2i));
}
}
}
return dp[n][k];
}
};

下面的代码使用前缀和, 通过全部用例

cpp
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:
// accumu[i] = accumulate(nums.begin(), nums.begin()+i, 0);
// = sum{n[0],...,n[i-1]}.
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);
// dp[i][j] 表示将前 i 个数 (n[0]~n[i-1]) 分成 j 组的最小最大和
vector<vector<int>> dp(n+1, vector<int>(k+1, INT32_MAX));
// 初始化, j=1
for(int i=1; i<=n; ++i) {
// dp[i][1] = accumulate(nums.begin(), nums.begin()+i, 0);
dp[i][1] = accumu[i];
}
// 递推更新, j=2,3,...,k
for(int j=2; j<=k; ++j) {
// 已知分成 j-1 组的最小最大和, 求分成 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); // sum{n[k],...,n[i-1]}
int sumk2i = accumu[i] - accumu[k]; // sum{n[0],...,n[i-1]} - sum{n[0],...,n[k-1]}
dp[i][j] = min(dp[i][j], max(dp[k][j-1], sumk2i));
}
}
}
return dp[n][k];
}
};

状态压缩dp

1879.两个数组最小的异或值之和

1879. 两个数组最小的异或值之和 | leetcode

cpp
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
/*
mask = 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, ...
f[mask] 表示从数组 nums2 中选择的元素状态为 mask 时,
并且选择了数组 nums1 的前 count(mask) 个元素的情况下,
可以组成的最小的异或值之和. 例如:
- f[0001] 表示 n2[0] 与 n1[0] 能够组成的最小异或值之和 = n1[0]^n2[0];
- f[0100] 表示 n2[2] 与 n1[0] 能够组成的最小异或值之和 = n1[0]^n2[2];
- f[0101] 表示 n2[0],n2[2] 与 n1[0],n1[1] 能够组成的最小异或值之和.
其中 f[0101] = min{f[0100] + n1[1]^n2[0], f[0001] + n1[1]^n2[2]}.
状态转移方程:
f[mask] = min{f[maks\i] + n1[c-1]^n2[i]}
*/

class Solution {
public:
int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(); // 1 <= n <= 14
vector<int> f(1<<n, INT_MAX);
f[0] = 0; // f[0000] = 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 超时

cpp
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<vector<bool>> relation(n, vector<bool>(n, false));
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 { // op == 2
dfs(relation, u, v);
if(friendship == true)
cout << "Yes" << endl;
else
cout << "No" << endl;
friendship = false;
visited.clear();
}
}
return 0;
}
// 64 位输出请用 printf("%lld")

寻找图中是否存在路径

1971. 寻找图中是否存在路径 | leetcode

cpp
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;
// rootu <-- rootv
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) {
// initialization
father = vector<int>(n);
for(int i = 0; i < n; i++) father[i] = i;

// build unionfind
for(auto uv : edges) {
int u = uv[0], v = uv[1];
// u <-- v
joint(u, v);
}

// is source and destination on same union
int rootu = find(source);
int rootv = find(destination);
return rootu == rootv;
}
};

冗余连接

684. 冗余连接

685. 冗余连接 II

最小生成树

最小生成树

NC159. 最小生成树 | nowcoder

连接所有点的最小费用

1584. 连接所有点的最小费用 | leetcode

最短路径

郊区春游

郊区春游 | nowcoder

拓扑排序

课程表

207. 课程表 | Leetcode Hot100

cpp
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
// bfs
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

cpp
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>()); // pre -> nxt
vector<int> indegree(n+1, 0), times(n+1), accumu_time(n+1, 0);
queue<int> indegree_zero;

// get inputs
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 { // pre == 0
break;
}
}
}

// initialization
for(int idx=1; idx<=n; ++idx) {
if(indegree[idx]==0) {
indegree_zero.push(idx);
accumu_time[idx] = times[idx];
}
}

// topological sorting
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

cpp
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
/*
Input:nums = [1,2,3]

[1,2,3]
idx=0: [(1),2,3], [(2),1,3], [(3),2,1]
idx=1: [(1),[2],3], [(1),[3],2]; [(2),[1],3], [(2),[3],1]; [(3),[2],1], [(3),[1],2];
idx=2: [(1),[2],{3}], [(1),[3],{2}]; [(2),[1],{3}], [(2),[3],{1}]; [(3),[2],{1}], [(3),[1],{2}];
*/
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;
}
};

方法二, 使用两个集合

cpp
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

cpp
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; // 使用一个set记录当前层已经选过的元素
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

cpp
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
/*
nums = [0,1,2]
[ ]
| \ \
0 1 2
[0] [1] [2]
| \ |
1 2 2
[01] [02] [12]
|
2
[012]
*/
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

cpp
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
/*
candidates = [2,3,6,7]
[ ]____________________________________
| \ \ \
2 3 6 7
[2]_________ [3]_____ [6]_ [7]
| \ \ \ | \ \ | \ |
2 3 6 7 3 6 7 6 7 7
[22][23][26][27] [33][36][37] [66][67] [77]
|\\\|\\ |\ | |\\ |\ | |\ | |
... ...
*/
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

cpp
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
/*
candidates = [1,2,2,2,5]
[ ]_______________________________________________
| \ x x \
1 2 2 2 5
[1]_____________________________ [2] (2) (2) [5]
| x x \
2 2 2 5
[12]______________ (12)(12)[15]
| x \
2 2 5
[122]_ (122)[125]
| \
2 5
[1222][1225]
|
5
[12225]
*/
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

回溯法

plaintext
1
2
3
4
5
0: (
1: (( ()
2: ((( (() ()(
3: (((( ((() (()( (()) ()(( ()()
... number of '(' >= number of ')' ...
cpp
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

cpp
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:
//palindrome[i][j]表示s[i]...s[j](s.substr(i, j-i+1))是否为回文串
vector<vector<bool>> palindrome;
void initialize_palindrome(string& s) {
int n = s.size();
// bias = 0
palindrome = vector<vector<bool>>(n, vector<bool>(n, true));
// bias = 1
int bias = 1;
for(int i=0; i+bias<n; ++i) {
int j = i + bias;
palindrome[i][j] = s[i] == s[j];
}
// bias = 2, 3, ..., n-1
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

cpp
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
/*
/反对角线的表示方法: i + j = 0, ..., n-1, ..., 2n-2
\ 对角线的表示方法: i - j = -(n-1), ..., 0, ..., n-1
diagonal anti-diagonal
/i + j/ | \i - j\
0 1 2 3 | 0 1 2 3
0 <0> (1) [2] {3} | 0 {0} [1] (2) <3>
1 (1) [2] {3} [4] | 1 [-1] {0} [1] (2)
2 [2] {3} [4] (5) | 2 (-2)[-1] {0} [1]
3 {3} [4] (5) <6> | 3 <-3>(-2)[-1] {0}
*/

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) { // row and column
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> 进行去重和查找

cpp
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();
// cout << totalnum << endl; // 355

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;
}
// 64 位输出请用 printf("%lld")

二分查找

35.搜索插入位置

35. 搜索插入位置 | leetcode-hot100

cpp
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
/*
m t (m<t) t m (t<m) t m
|i-1| i |i+1| ——> |i-1| i |i+1| ——> |i-1| i |i+1|
l r l r r l
————————————————————————————————————————————————
t m (t<m) t m (m<t) m t
|i-1| i |i+1| ——> |i-1| i |i+1| ——> |i-1| i |i+1|
l r l r r l
————————————————————————————————————————————————
m t (m<t) t m (t<m) t m
| i |i+1| ——> | i |i+1| ——> | i |i+1|
l r l r r l
*/
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. 在排序数组中查找元素的第一个和最后一个位置

cpp
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;

// left bound
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 { // target <= nums[mid]
right = mid - 1;
}
}

// right bound
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 { // target < nums[mid]
right = mid - 1;
}
}
return vector<int>({lbound, rbound});
}
};

4.寻找两个正序数组的中位数

4. 寻找两个正序数组的中位数 | leetcode-hot100

双指针法

cpp
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;
// vector<int> * nums;
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

cpp
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; // monotonic increasing stack
for(int idx=0; idx<n; idx++) { // left
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); // heights[mono_stack.top()] < heights[idx]
}
mono_stack = stack<int>(); // clear stack
for(int idx=n-1; idx>=0; idx--) { // right
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); // heights[mono_stack.top()] < heights[idx]
}

// calculate maximum area
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

cpp
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
/*
1 5 8 4 7 6 5 3 1
^ ^
1 5 8 5 7 6 4 3 1
\_______/
1. 将左边的一个[较小数]和右边一个[较大数]交换
2. [较小数]需要尽量靠右, [较大数]需要尽量小
3. 交换后需要将[较小数]右边的序列重新从小到大排序
a. 从右往左第一个下降的数就是[较小数]
b. 从右往左第一个大于[较小数]的数就是[较大数]
c. 交换前后[较小数]右边的序列都是降序, 所以将其reverse后就是升序排列
*/

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 取模的结果. 如果两个方案选取的人的集合不同或选出的队长不同, 则认为这两个方案是不同的.

ans=1×Cn1+2×Cn2++n×Cnn(iCni=nCn1i1)=n×(Cn10+Cn11++Cn1n1)=n×2n1\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}

cpp
1
2
long long ans = n;
ans = ans << (n-1) % 1000000007;

i×Cni=i×n!(ni)!i!=n×(n1)!(ni)!(i1)!=n×Cnii×C_n^i = i × \frac{n!}{(n-i)!i!} = n × \frac{(n-1)!}{(n-i)!(i-1)!} = n × C_n^i

475.供暖器

475. 供暖器 | leetcode

134.加油站

134. 加油站 | leetcode

189.轮转数组

189. 轮转数组 | leetcode

cpp
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); // k 和 n 的最小公倍数,表示两者相遇的周期
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

cpp
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
/*
example 1
o a a a | o | | | |
d e b | d e b | d e | d e | o e | o
c c b | c c b | c c o | o | |
----------------------------------------
example 2
o a a a a | o | | | | |
d e e b | d e e b | d e e | d e e | o e e | o |
c c c b | c c c b | c c c o | o | | |
*/
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

cpp
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++) { // ceil(n/2)
for(int j = 0; j < n/2; j++) { // floor(n/2)
// [i,j] -> [j, (n-1)-i]
// [j, (n-1)-i] -> [(n-1)-i, (n-1)-j]
// [(n-1)-i, (n-1)-j] -> [(n-1)-j, i]
// [(n-1)-j, i] -> [i, 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

cpp
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;
}
};