牛客网-刷题汇总（持续更新）
发布时间
阅读量：
阅读量
链表
树
数组
双指针
二分
贪心
动态规划
背包
其他DP
队列
栈
搜索
数组
- 双指针
1. 思路：三数之和如果按照o(n^3)遍历肯定会爆，所以需要将复杂度降低到o(n^2)，问题就来到了如何能完全枚举所有可能性结果呢；双指针（当value>target时，此时说明此处三数之和已经大于target，后面不需要进行遍历，故，先将nums进行排序之后进行双指针）
2. int ClosestSum(vector<int>& nums, int target) {
3. sort(nums.begin(), nums.end());
4. int min_value = INT_MAX;
5. int res = 0;
6. for (int i = 0; i < nums.size() - 2; i++) {
7. int left = i + 1, right = nums.size() - 1;
8. while (left < right) {
9. int value = nums[i] + nums[left] + nums[right];
10. if (abs(value - target) < min_value) {
11. res = value;
12. min_value = abs(value - target);
13. }
14. //次处不需要接else： 上述最接近3数之和处不知道是大于target还是小于target，所以不能直接进行left++或者right--操作； [-10,20,10,40], target=20
15. if (value > target) {
16. right -= 1;
17. } else {
18. left += 1;
19. }
20. }
21. }
22. return res;
23. } 1. //思路：双指针，由于2个数组都是有序的，故只需要二分判断即可；
2. int findKthNum(vector<int>& arr1, vector<int>& arr2, int target) {
3. // write code here
4. int arr1_left = 0, arr1_right = arr1.size() - 1;
5. int arr2_left = 0, arr2_right = arr2.size() - 1;
6. int arr1_idx = 0;
7. int arr2_idx = 0;
8. while (target != 1) {
9. // 取出一半元素的idx索引（索引需要-1）
10. int k = target / 2 - 1;
11. // 索引位置不能超出数组的长度，故去min
12. arr1_idx = min(arr1_left + k, arr1_right);
13. arr2_idx = min(arr2_left + k, arr2_right);
14. // 判断2个数组索引位置大小，如果小值的话，肯定不是需要的结果；
15. if (arr1[arr1_idx] < arr2[arr2_idx]) {
16. target = target - (arr1_idx - arr1_left + 1);
17. arr1_left = arr1_idx + 1;
18. } else {
19. target = target - (arr2_idx - arr2_left + 1);
20. arr2_left = arr2_idx + 1;
21. }
22. // 必须是大于，由于你上面target已经去掉了不可能答案，所以，剩下的数组一定满足答案；
23. // 如果是==的话，由于你上面加1，导致你idx已经到最后一个位置，直接返回的话就有问题；
24. if (arr1_left > arr1_right) {
25. return arr2[arr2_left + target - 1];
26. }
27. if (arr2_left > arr2_right) {
28. return arr1[arr1_left + target - 1];
29. }
30. }
31. return min(arr1[arr1_left], arr2[arr2_left]);
32. } 1. vector<int> reOrderArrayTwo(vector<int>& array) {
2. // write code here
3. int left = 0, right = array.size() - 1;
4. while (left < right) {
5. while (left < right && array[left] % 2 == 1) {
6. left += 1;
7. }
8. while (left < right && array[right] % 2 == 0) {
9. right -= 1;
10. }
11. if (left < right) {
12. swap(array[left], array[right]);
13. left += 1;
14. right -= 1;
15. }
16. }
17. return array;
18. } 1. bool editdistance(string s, string t) {
2. // write code here
3. if (s.size() < t.size()) {
4. swap(s, t);
5. }
6. if (s.size() - t.size() >= 2) {
7. return false;
8. }
9.
10. int i_left = 0, i_right = s.size() - 1;
11. int j_left = 0, j_right = t.size() - 1;
12. while (i_left < s.size() && j_left < t.size() && s[i_left] == t[j_left]) {
13. i_left += 1, j_left += 1;
14. }
15.
16. while (j_right > j_left && i_right > i_left && s[i_right] == t[j_right]) {
17. j_right -= 1;
18. i_right -= 1;
19. }
20.
21. if (i_right - i_left == 0 || j_right - j_left == 0) {
22. return true;
23. }
24. return false;
25. } 1. // 二分查找比现在大的数字的索引；由于是大于，所以nums[mid] == target的时候，也需要left++
2. int find(vector<int>& nums, int target) {
3. int left = 0, right = nums.size() - 1;
4. while (left < right) {
5. int mid = (left + right) / 2;
6. if (nums[mid] <= target) {
7. left = mid + 1;
8. } else {
9. right = mid;
10. }
11. }
12. return left;
13. }
14.
15. // 取出三角形两边进行寻找满足三角形最小的边，找到的idx和j之前的所有数字都满足条件
16. int validTriangleNumber(vector<int>& nums) {
17. sort(nums.begin(), nums.end());
18. int res = 0;
19. for (int i = nums.size() - 1; i >= 2; i--) {
20. for (int j = i - 1; j >= 1; j--) {
21. int idx = find(nums, nums[i] - nums[j]);
22. if (j > idx) {
23. res += (j - idx);
24. }
25. }
26. }
27. return res;
28. }原地置换
1. vector<int> findDisappearedNumbers(vector<int>& nums) {
2. // write code here
3. vector<int> res;
4. for (int i = 0; i < nums.size(); i++) {
5. //原地置换
6. while (i + 1 != nums[i] && nums[nums[i] - 1] != nums[i]) {
7. swap(nums[i], nums[nums[i] - 1]);
8. }
9. }
10. for (int i = 0; i < nums.size(); i++) {
11. if (nums[i] != i + 1) {
12. res.push_back(i + 1);
13. }
14. }
15. return res;
16. }贪心
1. string maximumSwap(string num) {
2. // write code here
3. unordered_map<char, int> un_mp;
4. // 记录每个位置最后位置，最后位置是为了保证前面的小数被排到最后
5. for (int i = 0; i < num.size(); i++) {
6. un_mp[num[i]] = i;
7. }
8. for (int i = 0; i < num.size(); i++) {
9. for (int j = 9; j >= 0; j--) {
10. char t = j + '0';
11. // 数字确实比较现在的值大，同时位置也偏后
12. if (un_mp[t] > i && t > num[i]) {
13. swap(num[i], num[un_mp[t]]);
14. return num;
15. }
16. }
17. }
18. return num;
19. }-
- 滑动窗口
1. // 区间个数不好求，转换为求l和r的结果，然后结果相减即可
2. int countSubarray(vector<int>& nums, int l, int r) {
3. // write code here
4. int res_left = 0;
5. int res_right = 0;
6. int min_left_start = 0;
7. int min_right_start = 0;
8. for (int i = 0; i < nums.size(); i++) {
9. if (nums[i] <= r) {
10. //由于区间之内都满足条件，所以满足子数组个数为本身长度（无序排列）
11. // [2,1,3] -> [2](2结尾) [1] [2,1]（1结尾） [3] [1,3] [2,1,3]（3结尾）
12. res_right += (i - min_right_start + 1);
13. } else {
14. min_right_start = i + 1;
15. }
16.
17. if (nums[i] < l) {
18. res_left += (i - min_left_start + 1);
19. } else {
20. min_left_start = i + 1;
21. }
22. }
23. return res_right - res_left;
24. } 1. // 乘积小于K的子数组，只需要确定子数组的left和right即可，典型的滑动窗口例子
2. int subarrayCnt(vector<int>& nums, int k) {
3. long sum = 1;
4. int start = 0;
5. int res = 0;
6. for (int i = 0; i < nums.size(); i++) {
7. sum = sum * nums[i];
8. // start <= i, 防止除到下一个nums[i+1]元素
9. while (sum >= k && start <= i) {
10. sum = sum / nums[start++];
11. }
12. res += (i - start + 1);
13. }
14. return res;
15. }树
1. 思路：左叶子节点，DFS和BFS都可以，BFS层次遍历即为模版，故不在写代码（只需要在倒数第二层判断即可）；DFS（1.确定递归参数；2.确定终止条件；3.单层循环体）
2. int res = 0;
3. int sumOfLeftLeaves(TreeNode* root) {
4. // write code here
5. if (root == NULL) {
6. return 0;
7. }
8. // 由于是累加和，故，不能return，需要用全局变量保存这个结果；
9. if (root->left && root->left->left == NULL && root->left->right == NULL) {
10. res += root->left->val;
11. }
12. // 上述res已经保存结果了，故每棵树返回结果可以忽略
13. sumOfLeftLeaves(root->left);
14. sumOfLeftLeaves(root->right);
15. return res;
16. } 1. class Solution {
2. public:
3. TreeNode* insertToBST(TreeNode* root, int val) {
4. // write code here
5. if (root == NULL) {
6. return new TreeNode(val);
7. }
8. //如果root节点大于val的话，说明插入值只能在left；
9. if (root->val > val) {
10. if (root->left == NULL) {
11. TreeNode* temp = new TreeNode(val);
12. root->left = temp;
13. } else {
14. root->left = insertToBST(root->left, val);
15. }
16. } else {
17. //如果root节点小于val的话，说明插入值只能在right；
18. if (root->right == NULL) {
19. TreeNode* temp = new TreeNode(val);
20. root->right = temp;
21. } else {
22. root->right = insertToBST(root->right, val);
23. }
24. }
25. return root;
26. }
27. }; 1. class Solution {
2. public:
3. TreeNode* deleteNode(TreeNode* root, int key) {
4. // write code here
5. if (root == NULL) {
6. return NULL;
7. }
8. if (root->val == key) {
9. if (root->left == NULL && root->right) {
10. return root->right;
11. }
12. if (root->right == NULL && root->left) {
13. return root->left;
14. }
15. if (root->left == NULL && root->right == NULL) {
16. return NULL;
17. }
18. if (root->left && root->right) {
19. TreeNode* temp = root->right;
20. while (temp->left) {
21. temp = temp->left;
22. }
23. temp->left = root->left;
24. TreeNode* t = root;
25. root = root->right;
26. delete t;
27. return root;
28. }
29. }
30.
31. if (root->val > key) {
32. root->left = deleteNode(root->left, key);
33. }
34. if (root->val < key) {
35. root->right = deleteNode(root->right, key);
36. }
37. return root;
38. }
39. }; 1. int numberOfTree(int n) {
2. // write code here
3. vector<long long> dp(n + 1, 0);
4. // 个数等于=左个数 * 右个数；
5. // 1的个数是1，左=1、右=0 ｜｜左=0、右=1； 故dp[1] = 1;
6. dp[0] = 1;
7. dp[1] = 1;
8. for (int i = 2;i <= n; i++) {
9. // 枚举左树个数
10. // 根节点保持1个节点，故需要右树i-j-1
11. for (int j = 0; j < i; j++) {
12. // 递归公式：dp[i] = dp[i左] * dp[i右]
13. dp[i] += (dp[j] * dp[i - j - 1]) % 1000000007;
14. dp[i] = dp[i] % 1000000007;
15. }
16. }
17. return dp[n];
18. }字符串
1. //可以解析为AEB; A->[+/-]C.D CD都是整形数判断可以放到一起
2. // A
3. bool scanInt(string s, int& idx) {
4. // +/-
5. if (s[idx] == '+' || s[idx] == '-') {
6. idx++;
7. }
8. return scanFloat(s, idx);
9. }
10. //C || D
11. bool scanFloat(string s, int& idx) {
12. int t = idx;
13. while (idx < s.size() && s[idx] >= '0' && s[idx] <= '9') {
14. idx++;
15. }
16. return idx > t;
17. }
18. bool isNumeric(string str) {
19. // write code here
20. if (str.size() == 0) {
21. return false;
22. }
23. int i = 0;
24. while (str[i] == ' ') {
25. i += 1;
26. }
27.
28. bool is_num = scanInt(str, i);
29. if (str[i] == '.') {
30. i++;
31. is_num = scanFloat(str, i) || is_num;
32. }
33.
34. if (str[i] == 'e' || str[i] == 'E') {
35. i += 1;
36. is_num = is_num && scanInt(str, i);
37. }
38. while (str[i] == ' ') {
39. i += 1;
40. }
41.
42. if (i == str.size() && is_num) {
43. return true;
44. }
45. return false;
46. }哈希
1. string rearrangestring(string str) {
2. vector<int> v(27, 0);
3. int max_num = 0;
4. for (int i = 0; i < str.size(); i++) {
5. v[str[i] - 'a'] += 1;
6. max_num = max(max_num, v[str[i] - 'a']);
7. }
8.
9. // 如果字符串超过一半以上的话，直接返回
10. if (max_num > (str.size() + 1) / 2) {
11. return "";
12. }
13.
14. string res = "";
15. int idx = 0;
16. //先排偶数位置，再排奇数位置
17. for (int j = 0; j < 26; j++) {
18. while (v[j]) {
19. str[idx] = j + 'a';
20. idx = idx + 2;
21. v[j] -= 1;
22. if (idx >= str.size()) {
23. idx = 1;
24. }
25. }
26. }
27. return str;
28. }搜索
- dfs
1. // DFS常规模版
2. vector<vector<int> > dir = {{-1,0}, {1,0}, {0,1}, {0,-1}};
3. bool res = 0;
4. void dfs(vector<vector<char> > matrix, vector<vector<int> > visited, string word, int x, int y, int start) {
5. if (start == word.size() - 1) {
6. res = true;
7. return;
8. }
9. for (int i = 0; i < 4; i++) {
10. int newx = x + dir[i][0];
11. int newy = y + dir[i][1];
12. if (newx >= 0 && newx < matrix.size()
13. && newy >= 0 && newy < matrix[0].size()
14. && visited[newx][newy] == 0
15. && matrix[newx][newy] == word[start + 1]) {
16. visited[newx][newy] = 1;
17. dfs(matrix, visited, word, newx, newy, start + 1);
18. visited[newx][newy] = 0;
19. }
20. }
21. }
22. bool hasPath(vector<vector<char> >& matrix, string word) {
23. // write code here
24. vector<vector<int> > visited(matrix.size(), vector<int>(matrix[0].size(), 0));
25. for (int i = 0; i < matrix.size(); i++) {
26. for (int j = 0; j < matrix[0].size(); j++) {
27. if (matrix[i][j] == word[0]) {
28. dfs(matrix, visited, word, i, j, 0);
29. if (res) {
30. return true;
31. }
32. }
33. }
34. }
35. return false;
36. }- BFS
1.
2. //BFS模板
3. int countPath(vector<vector<int> >& CityMap, int n, int m) {
4. // write code here
5. vector<vector<int> > dir = {{-1,0}, {1, 0}, {0, 1}, {0, -1}};
6. queue<pair<int,int> > q;
7. for (int i = 0; i < n; i++) {
8. for (int j = 0; j < m; j++) {
9. if (CityMap[i][j] == 1) {
10. q.push(make_pair(i, j));
11. break;
12. }
13. }
14. }
15. int res = 0;
16. while (res == 0 && !q.empty()) {
17. int length = q.size();
18. for (int i = 0; i < length; i++) {
19. int x = q.front().first;
20. int y = q.front().second;
21. q.pop();
22. for (int j = 0; j < 4; j++) {
23. int newx = dir[j][0] + x;
24. int newy = dir[j][1] + y;
25. if (newx >= 0 && newx < n && newy >= 0 && newy < m) {
26. if (CityMap[newx][newy] == 0) {
27. q.push(make_pair(newx, newy));
28. }
29. if (CityMap[newx][newy] == 2) {
30. res += 1;
31. }
32. }
33. }
34. }
35. }
36. return res;
37. }模拟
1. 分析：
2. int findNthDigit(int n) {
3. // write code here
4. if (n < 10) {
5. return n;
6. }
7. int num = 1; //数字的长度
8. long long value = 9; //1位数：1-9（9个）；2位数：10-99（90个）； 3位数：100-999（900个）
9. long long cur = 1; // 当前位数所表示最小值
10. while (n >= value) {
11. n -= value;
12. num += 1;
13. cur = cur * 10;
14. value = cur * num * 9;
15. }
16.
17. // 10-99，从0开始，故需要n-1
18. long t = cur + (n - 1) / num;
19. string temp = to_string(t);
20. // 取出对应的位置；
21. int tt = temp[(t - 1) % num] - '0';
22. return tt;
23. }栈
1. // 栈 + 贪心
2. string removeDuplicateLetters(string str) {
3. unordered_map<int, int> mp;
4. vector<int> visited(26, 0);
5. for (int i = 0; i < str.size(); i++) {
6. mp[str[i] - 'a'] += 1;
7. }
8.
9. string res = "";
10. for (int i = 0; i < str.size(); i++) {
11. if (visited[str[i] - 'a']) {
12. mp[str[i] - 'a'] -= 1;
13. continue;
14. }
15.
16. while (res.size() && res.back() > str[i] && mp[res.back() - 'a'] > 0) {
17. visited[res.back() - 'a'] = 0;
18. res.pop_back();
19. }
20. res += str[i];
21. mp[str[i] - 'a'] -= 1;
22. visited[str[i] - 'a'] = 1;
23. }
24. return res;
25. }全部评论 (0)
还没有任何评论哟~