dq买一送一：石器时代 —— Leetcode刷题日记 （三 面试题相关） 2024-05-06 12:11:53 0 0 随机刷题 vivo2020 算法题B卷 运矿石每次可以挖到多个矿石，每个矿石的重量都不一样，挖矿结束后需要通过一款平衡矿车运送下山；平衡矿车有左右2个车厢，中间只有1个车轮沿着导轨滑到山下，且矿车只有在2个车厢重量完全相等且矿石数量相差不超过1个的情况下才能成功运送矿石，否则在转弯时可能出现侧翻假设小v挖到了n（n<100）个矿石，每个矿石重量不超过100，为了确保一次性将n个矿石都运送出去，一旦矿车的车厢重量不一样就需要购买配重砝码。请问小v每次最少需要购买多少重量的砝码呢? （假设车厢足够放下这些矿石和砝码，砝码重量任选）思路：恰好装满的01背包问题的变形，多了一个且矿石数量相差不超过1个条件！#include <stdio.h>#include <stdlib.h>#include <string.h>#include <iostream>#include <vector>#include <limits.h> // INT_MINusing namespace std;#define MAX_NUM 101int solution(int n, int weight[]) { int sum = 0, h_sum, h_n = (n + 1) / 2; for (int i = 0; i < n; i++) sum += weight[i]; h_sum = sum / 2; vector<vector<int>> dp(h_sum + 1, vector<int>(h_n + 1, INT_MIN)); for (int i = 0; i <= h_sum; i++) dp[i][0] = 0; for (int i = 0; i < n; i++) { auto tmp = dp; // 避免覆盖！ for (int j = weight[i]; j <= h_sum; j++) { for (int k = 1; k <= h_n; k++) tmp[j][k] = max(tmp[j][k], dp[j-weight[i]][k-1]+weight[i]); } dp = tmp; } if (n % 2) return sum - 2 * max(dp[h_sum][h_n], dp[h_sum][h_n-1]); else return sum - 2 * dp[h_sum][h_n];}int main(){ string str("");getline(cin, str);int a[MAX_NUM];int i = 0;char *p;int count = 0;const char* strs = str.c_str();p = strtok((char *)strs, " ");while(p) {a[i] = atoi(p);count++;p = strtok(NULL, " ");i++;if(i >= MAX_NUM)break;}int result = solution(count, a);cout << result << endl;return 0;} 报数将N（N<10000）个人排成一排，从第1个人开始报数；如果报数是M的倍数就出列，报到队尾后则回到队头继续报，直到所有人都出列；按照出列顺序为每个人依次分配工号#include <stdio.h>#include <stdlib.h>#include <iostream>#include <string.h>#include <vector>using namespace std;typedef struct _node{ int num; struct _node * next;}node;void solution(int N, int M){if (N < 1 || M < 1) return; vector<int> rows(N, 0); for (int i = 0; i < N; i++) rows[i] = i + 1; int pos = 0; while (rows.size() > 0) { pos += M - 1; pos %= rows.size(); cout << rows[pos] << " "; rows.erase(rows.begin() + pos); } cout << endl;}int main(){int N;int M;string str("");getline(cin, str);char *p;const char* strs = str.c_str();p = strtok((char *)strs, " ");N = atoi(p);p = strtok(NULL, " ");M = atoi(p);solution(N, M);return 0;} 跳盒子有n个盒子排成了一行，每个盒子上面有一个数字a[i]，表示在该盒子上的人最多能向右移动a[i]个盒子（比如当前所在盒子上的数字是3，则表示可以一次向右前进1个盒子，2个盒子或者3个盒子）小v从左边第一个盒子上开始体验游戏，请问最少需要移动几次能到最后一个盒子上？思路：贪心，Leetcode45；但是不一定是能到达最后的盒子！#include <iostream>#include <stdlib.h>#include <string.h>using namespace std;int solution(int a[], int N){ int pre = 0, cur = 0; int steps = 0; for (int i = 0; i < N - 1; i++) { cur = max(cur, i+a[i]); if (pre == i) { pre = cur; steps++; if (cur >= N - 1) break; } } return pre >= N - 1 ? steps : -1;}int main(){string str("");getline(cin, str);int a[2000];int i = 0;char *p;int count = 0;const char* strs = str.c_str();p = strtok((char *)strs, " ");while(p){a[i] = atoi(p);count++;p = strtok(NULL, " ");i++;if(i >= 2000)break;}int num = solution(a, count);cout << num << endl;return 0;} VIVO2020 算法题A卷 服务部署三维背包问题！//write code herevector<vector<vector<int>>> dp(countOfApp + 1,vector<vector<int>>(disk+1,vector<int>(mem+1)));for(int i = 1; i <= countOfApp; i++){ for(int j = disk; j > 0; j--){ for(int k = mem; k > 0; k--){ if(j >= disks[i-1] && k >= mems[i-1]){ dp[i][j][k] = max(dp[i - 1][j][k],dp[i - 1][j - disks[i-1]][k - mems[i-1]]+ users[i-1]); }else{ dp[i][j][k] = dp[i - 1][j][k]; } } }}return dp[countOfApp][disk][mem]; 消消乐就是L546移除盒子int dfs(int boxs[], int N, int start, int end, int k, vector<vector<vector<int>>>& dp) { if (start > end) return 0; if (dp[start][end][k] > 0) return dp[start][end][k]; for (int i = start; i < end; i++) { if (boxs[start] != boxs[i + 1]) break; k++; start++; } int res = dfs(boxs, N, start + 1, end, 0, dp) + (k + 1) * (k + 1); for (int i = start + 1; i <= end; i++) { if (boxs[i] != boxs[start]) continue; res = max(res, dfs(boxs, N, start + 1, i - 1, 0, dp) + dfs(boxs, N, i, end, k + 1, dp)); } return dp[start][end][k] = res;} 拆礼盒(()(()((()(0))))) > 5(((0))) > 3int solution(string str){ int left = 0, right = 0; for (int i = 0; i < str.size(); i++) { if (str[i] == '0') break; if (str[i] == '(') left++; if (str[i] == ')') left--; } for (int i = str.size() - 1; i>= 0; i--) { if (str[i] == '0') break; if (str[i] == ')') right++; if (str[i] == '(') right--; }return min(left, right);} 牛客网上的IO代码 如 1,2,3#include <vector>#include <string>vector<int> inputArray1() {string inputs;cin >> inputs;// splitsvector<string> splits;int start = 0;for (size_t i = 0; i < inputs.size(); i++) {if (inputs[i] == ',') {splits.push_back(inputs.substr(start, i - start));start = i + 1;}}if (start != (int)inputs.size()) {splits.push_back(inputs.substr(start));}vector<int> res;for (string s : splits) {res.push_back(std::stoi(s));// cout << res.back() << " ";}return res;} 如 1 2 3 … \n输入无限长度的数据，数据之间用空格分开，回车结束vector<int> inputArray2() {vector<int> inputs;int a;do {cin >> a;inputs.push_back(a);// cout << a << " ";} while (getchar() != '\n');return inputs;} 如 size + 1 2 3 (1D)先输入数组大小，然后输入数据，中间以空格或者’\n’字符隔开vector<int> inputArray3() {int size = 0;cin >> size;vector<int> inputs;for (int i = 0; i < size; i++) {int tmp;cin >> tmp;cout << tmp << " ";inputs.push_back(tmp);}return inputs;} 如 size + 1 2 3 (2D)先输入矩阵高宽，再输入数据vector<vector<int>> inputMatrix() {int m, n;cin >> m >> n;vector<vector<int>> matrix(m, vector<int>(n, 0));for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int a;cin >> a;matrix[i][j] = a;}}return matrix;} 整数翻转 输入: 123 输出: 321class Solution {public: int reverse(int x) { int res = 0; while (x != 0) { if (abs(res)>INT_MAX/10) return 0; res = res*10+(x); x/=10; } return res; }}; 二叉树中序遍历的下一个节点 后序遍历的下一个元素，不知道对不对！// 这是后序遍历时的下一个节点 // Pa(X).right.最左 - 同层右节点的最左节点 if (!pNode) return NULL; if (!pNode->next) return NULL; TreeLinkNode *root = pNode->next; if (!root->right || root->right == pNode) return root; root = root->right; while (root->left) root = root->left; return root; 以此为启发！ 先序遍历的下一个节点：存在左子节点，下一个节点为左子节点不存在左子节点，下一个节点为从同层向上第一个父子关系为右的节点，如果遍历到右节点，则其左节点和右节点都被遍历到了！ 中序遍历的下一个节点：该节点存在右子节点，则下一个节点是右子树的最左节点。该节点不存在右子节点，则下一个节点是该节点的第一个父子关系为左的祖先节点中的父节点， 因为如果遍历的节点是父节点的右节点说明父节点已遍历过了 后序遍历的下一个节点：该节点同层且同父节点的右节点为根节点的子树的最左节点若没有，则下一个节点为父节点！ 对称二叉树 层次遍历class Solution {private: bool loopJudge(vector<int>& seq) { int left = 0, right = seq.size() - 1; while (left < seq.size() && right >= 0 && left < right) { if (seq[left++] != seq[right--]) return false; } return true; }public: bool isSymmetrical(TreeNode* pRoot) { if (!pRoot) return true; queue<TreeNode*> que; que.push(pRoot); while (!que.empty()) { int sz = que.size(); vector<int> seq; for (int i = 0; i < sz; i++) { auto x = que.front(); que.pop(); if (!x) seq.push_back(INT_MIN); else seq.push_back(x->val); if (x) { que.push(x->left); que.push(x->right); } } if (!loopJudge(seq)) return false; } return true; }}; 或者用两个que，一个保存左子树的左右子节点，一个保存右子树的右左子节点，注意顺序！刷题日记（1）里面就是！ 而如何写递归？ 1 观察是否有递归结构 2 处理递归子结构（如该题就是一个高度为3的二叉树的处理结果！） 递归class Solution {public: bool isSymmetrical(TreeNode* pRoot) { if (!pRoot) return true; return dfs(pRoot->left, pRoot->right); } bool dfs(TreeNode* left, TreeNode* right) { if (!left) return !right; if (!right) return !left; return (left->val == right->val) && dfs(left->left,right->right) && dfs(left->right,right->left); }}; 之字形打印二叉树 1 用双栈，一个先left再right堆入，一个先right再left堆入，两个栈交叠进行 2 用双端队列，分奇偶左右导出！ 剑指offer OJ链接 1约瑟夫环 题解 链接class Solution {public: int lastRemaining(int n, int m) { if (n == 1) return 0; return (lastRemaining(n-1,m) + m) % n; }}; 表示数值的字符串 使用有限状态机做 … if-else之流的太蛋疼了 先设定开始状态(未处理时)为0 再确定有几种状态：1点状态类似于" . "2正负号类似于" + "3整数类似于"132"4浮点数类似于"3.2"5科学计数类似于"5e3"6数加e状态类似于"5e"7数加e加正负状态类似于"5e+"8额外状态以便处理尾空格情况 转移图（无8）如下： class Solution {public: bool isNumber(string s) { // 状态x操作 // 状态:0起始状态 1点 2正负 3整数 4浮点数 5科学计数 6数+"e" 7数+”正负"+"e" // 中间状态1/2/6/7 // 完美状态3/4/5 // 操作:0数 1空 2点 3正负 4e // 添一个空状态8 以处理尾部空格 s += ' '; // 添上一个尾部空格 vector<vector<int>> State { {3, 0, 1, 2,-1}, {4,-1,-1,-1,-1}, {3,-1, 1,-1,-1}, {3, 8, 4,-1, 6}, {4, 8,-1,-1, 6}, {5, 8,-1,-1,-1}, {5,-1,-1, 7,-1}, {5,-1,-1,-1,-1}, {-1,8,-1,-1,-1} }; vector<int> legalState {3,4,5,8}; int sta = 0; for (auto& c : s) { if (c >= '0' && c <= '9') sta = State[sta][0]; else if (c == ' ') sta = State[sta][1]; else if (c == '.') sta = State[sta][2]; else if (c == '+' || c == '-') sta = State[sta][3]; else if (c == 'e') sta = State[sta][4]; else sta = -1; if (sta == -1) return false; } for (auto& ls : legalState) if (sta == ls) return true; return false; }}; 126. 单词接龙 II DFSTLE!最短路径不适合使用DFS来算，需要很多复杂的剪枝才能ac …class Solution {private: int minL;public: vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) { if (find(wordList.begin(), wordList.end(), endWord) == wordList.end()) return {}; minL = INT_MAX; vector<vector<string>> res; vector<string> tmp; tmp.push_back(beginWord); backstrck(beginWord, endWord, wordList, res, tmp); return res; } void backstrck(string& be, string& en, vector<string>& dict, vector<vector<string>>& res, vector<string>& tmp) { if (be == en) { if (minL > tmp.size()) { res.clear(); minL = tmp.size(); res.push_back(tmp); } else if (minL == tmp.size()) { res.push_back(tmp); } return; } if (tmp.size() >= minL) return; for (int i = 0; i < dict.size(); i++) { auto x = dict[i]; if (find(tmp.begin(), tmp.end(), x) != tmp.end() || !oneChanged(be, x)) continue; tmp.push_back(x); backstrck(x,en,dict,res,tmp); tmp.pop_back(); } } bool oneChanged(string& beginWord, string& curWord) { int count = 0; for (int i = 0; i < beginWord.length(); i++) { if (beginWord[i] != curWord[i]) count++; if (count == 2) return false; } return count == 1; }}; BFSclass Solution {public: //判断两个单词能否互相转换 bool check_transform(string &word1, string &word2){ int difference = 0; for(int i = 0; i < word1.length() && difference < 2; i++){ if(word1[i] != word2[i]) difference++; } return difference == 1; } vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) { unordered_map<string, int> wordId; //word->ID的映射 vector<string> idWord; //ID->word的映射 vector<vector<int>> edges; //构造图 int id = 0; for(int i = 0; i < wordList.size(); i++){ if(!wordId.count(wordList[i])){ wordId[wordList[i]] = id++; idWord.push_back(wordList[i]); } } if(!wordId.count(endWord)) return {}; //不存在结束单词，返回空 if(!wordId.count(beginWord)){ wordId[beginWord] = id++; //加入起始单词 idWord.push_back(beginWord); } //构造图 edges.resize(id); for(int i = 0; i < idWord.size(); i++){ for(int j = i + 1; j < idWord.size(); j++){ if(check_transform(idWord[i], idWord[j])){ edges[i].push_back(j); edges[j].push_back(i); //构造两条有向边 } } } int endWord_id = wordId[endWord]; vector<vector<string>> res; queue<vector<int>> q; q.push(vector<int>{wordId[beginWord]}); //起始单词作为一个路径入队 //cost[id]：从起始单词出发，转换到id所代表的单词所需的次数(代价) vector<int> cost(id, INT_MAX); cost[wordId[beginWord]] = 0; while(!q.empty()){ vector<int> now_path = q.front(); q.pop(); int last_word_id = now_path.back(); //当前路径最后一个为结束单词时 if(last_word_id == endWord_id){ vector<string> temp; for(int i = 0; i < now_path.size(); i++){ temp.push_back(idWord[now_path[i]]); } res.push_back(temp); } else { for(int i = 0; i < edges[last_word_id].size(); i++){ //路径最后一个单词的连接单词 int next = edges[last_word_id][i]; if(cost[last_word_id] + 1 <= cost[next]){ cost[next] = cost[last_word_id] + 1; //更新转换次数 vector<int> temp(now_path.begin(), now_path.end()); temp.push_back(next); q.push(temp); } } } } return res; }};参考 猿辅导2020校招笔试(算法岗一) Q1：击鼓传花过10%，比如3,4 -> 0，OJ认为不对，得是6，但是击鼓传花只能相邻左右传，为啥会等于6，姑且认为是测试数据集有问题！#include <iostream>#include <vector>using namespace std;int main() {long long n, k; // n次击鼓传花 k个人cin >> n >> k;vector<vector<long long>> dp(n + 1, vector<long long>(k));dp[0][0] = 1;for (int i = 1; i <= n; i++) {for (int j = 0; j < k; j++) {dp[i][j] = (dp[i - 1][(j - 1 + k) % k] +dp[i - 1][(j + 1) % k]) % 1000000007;}}cout << dp[n][0] << endl;return 0;} Q2：走迷宫AC#include <iostream>#include <vector>#include <algorithm>using namespace std;int dx[4] = { 0, 1, 0, -1 };int dy[4] = { 1, 0, -1, 0 };int dfs_dp(int y, int x, int k, vector<vector<int>>& mat, vector<vector<vector<int>>>& dp) {int N = dp.size(), M = dp[0].size(), K = dp[0][0].size();if (dp[y][x][k] != -1) return dp[y][x][k];dp[y][x][k] = 1;for (int i = 0; i < 4; i++) {int ny = y + dy[i];int nx = x + dx[i];if (nx < 0 || nx >= N || ny < 0 || ny >= M)continue;if (mat[y][x] < mat[ny][nx])dp[y][x][k] = max(dp[y][x][k], dfs_dp(ny, nx, k, mat, dp) + 1);if (mat[y][x] >= mat[ny][nx] && k > 0)dp[y][x][k] = max(dp[y][x][k], dfs_dp(ny, nx, k - 1, mat, dp) + 1);}return dp[y][x][k];}int main() {int n, m, k;cin >> n >> m >> k;// 迷宫vector<vector<int>> mat(n, vector<int>(m));for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)cin >> mat[i][j];// 迷宫中(n,m)按k次走的最多步vector<vector<vector<int>>> dp(n,vector<vector<int>>(m, vector<int>(k+1, -1)));int max_res = 0;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)max_res = max(max_res,dfs_dp(i, j, k, mat, dp));cout << max_res << endl;return 0;} Q3：字符串解压缩从Leetcode 394题上修改的 …我反向遍历字符串，再在3A和3(A)这两种情况下多考虑了一些 …AC#include <iostream>#include <vector>#include <string>#include <algorithm>#include <stack>using namespace std;string reverse(string str1) {int left = 0, right = str1.size() - 1;while (left < right)swap(str1[left++], str1[right--]);return str1;}string dfs(string& s, int& pos) {string res = "";while (pos >= 0 && s[pos] != '(') {// 反转后: '()' -> ')('if (s[pos] < '0' || s[pos] > '9') // 字母res.push_back(s[pos--]);else {int times = 1, num = 0;while (s[pos] >= '0' && s[pos] <= '9') {num += (s[pos--] - '0') * times;times *= 10;}string t;if (s[pos] == ')') { // "3)ABC("pos--; // 跳过 [t = dfs(s, pos);pos--; // 跳过 ]} else t = s[pos--]; // "3ABC"for (int i = 0; i < num; i++) res += t;}}return res;}int main() {int len = -1;cin >> len;for (int i = 0; i < len; i++) {string in_str;cin >> in_str;int pos = in_str.size() - 1;cout << reverse(dfs(in_str, pos)) << endl;}return 0;} 猿辅导2020校招笔试(算法岗二) Q1： Q2： Q3： 猿辅导2020校招笔试(算法岗三) Q1：逆时针打印数组#include <iostream>#include <vector>using namespace std;int main() {int n, m;cin >> n >> m;vector<vector<int>> arr(n, vector<int>(m));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {int t;cin >> t;arr[i][j] = t;}}// Handlevector<vector<int>> dirs{ { 1,0 },{ 0,1 },{ -1,0 },{ 0, -1 } };int dir = 0;int y = -1, x = 0;m--;while (m >= 0 && n >= 0) {int looptime = (dir % 2) ? m-- : n--;for (int i = 0; i < looptime; i++) {y += dirs[dir][0];x += dirs[dir][1];cout << arr[y][x] << " ";}dir = (dir + 1) % 4;}return 0;} Q2： Q3：最长连续的没有触发报警的课程数量#include <iostream>#include <vector>#include <algorithm>using namespace std;int main() {int n, s;cin >> n >> s;vector<int> v;for (int i = 0; i < n; i++) {int t;cin >> t;v.push_back(t);}// Handleint left = 0, right = 0;int sum = 0, mlen = 0;while (right < n) {sum += v[right];right++;while (sum > s) {sum -= v[left];left++;}mlen = max(mlen, right - left);}cout << mlen << endl;return 0;} 猿辅导高频算法题整理 - 牛客网链接 L86 分割链表一个未排序的单向链表给一个链表中存在的值 V输出保证：小于V的节点在 大于等于V节点的前面代码如下：class Solution {public: ListNode* partition(ListNode* head, int x) { ListNode* dummy1 = new ListNode(-1); ListNode* dummy2 = new ListNode(-1); ListNode *p1 = dummy1, *p2 = dummy2; while (head) { if (head->val < x) { p1->next = head; p1 = p1->next; } else { p2->next = head; p2 = p2->next; } head = head->next; } p2->next = NULL; p1->next = dummy2->next; return dummy1->next; }}; L445 两数相加II两个单向链表表示两个数越靠近头部的节点的值在高位输出两个链表相加之和的链表7 2 4 3 + 5 6 4 = 7 8 0 7 (尾节点对齐)代码如下： 递归DFS/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: int len(ListNode* pNode) { int length = 0; while (pNode) { pNode = pNode->next; length++; } return length; } void dfs(ListNode* l1, ListNode* l2, ListNode* pre, int len1, int len2) { if (!l1) return; if (len1 > len2) { dfs(l1->next, l2, l1, len1-1, len2); } else { dfs(l1->next, l2->next, l1, len1-1, len2-1); l1->val += l2->val; } int p = l1->val / 10; pre->val += p; l1->val %= 10; } ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int len1 = len(l1), len2 = len(l2); ListNode* node = new ListNode(0); if (len1 > len2) { dfs(l1, l2, node, len1, len2); node->next = l1; } else { dfs(l2, l1, node, len2, len1); node->next = l2; } return node->val ? node : node->next; }}; 栈一般逆序问题，都要考虑能不能用栈/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { stack<int> s1, s2; while (l1) { s1.push(l1->val); l1 = l1->next; } while (l2) { s2.push(l2->val); l2 = l2->next; } ListNode* out = new ListNode(0); while (!s1.empty() || !s2.empty()) { int num = 0; if(!s1.empty()) { num += s1.top(); s1.pop(); } if (!s2.empty()) { num += s2.top(); s2.pop(); } int sum_num = (out->val + num); out->val = sum_num % 10; ListNode* tmp = new ListNode(sum_num / 10); tmp->next = out; out = tmp; } return out->val ? out : out->next; }};还有反转链表和原地计算两个思路 L543 二叉树的直径二叉树定义二叉树的直径为树中任意两个节点路径长度的最大值class Solution {public: int diameterOfBinaryTree(TreeNode* root) { if (!root) return 0; int dia = 0; dfs(root, dia); return dia; } int dfs(TreeNode* root, int& dia) { if (!root) return 0; int L = dfs(root->left, dia); int R = dfs(root->right, dia); dia = max(dia, L + R); return max(L, R) + 1; }}; L83 删除排序链表中的重复元素单向链表 去重 递归class Solution {public: ListNode* deleteDuplicates(ListNode* head) { if (!head || !head->next) return head; head->next = deleteDuplicates(head->next); if (head->val == head->next->val) head = head->next; return head; }}; 迭代class Solution {public: ListNode* deleteDuplicates(ListNode* head) { if (!head) return head; ListNode *out = head; while (head && head->next) { if (head->val == head->next->val) head->next = head->next->next; else head = head->next; } return out; }}; 面试题03.05 栈排序把排好序的栈，拆成两个栈 class SortedStack {private: stack<int> s1, s2; // 前者三角形 后者倒三角 二合一是排好序的public: SortedStack() {} void push(int val) { while (!s1.empty() && s1.top() < val) { s2.push(s1.top()); s1.pop(); } while (!s2.empty() && s2.top() > val) { s1.push(s2.top()); s2.pop(); } s1.push(val); } void pop() { while (!s2.empty()) { s1.push(s2.top()); s2.pop(); } if (!s1.empty()) s1.pop(); } int peek() { while (!s2.empty()) { s1.push(s2.top()); s2.pop(); } if (!s1.empty()) return s1.top(); else return -1; } bool isEmpty() { return s1.empty() && s2.empty(); }}; 1254 统计封闭岛屿的数目二维数组 4连通域 检测0表示陆地，1表示水域递归 深度搜索class Solution {public: int closedIsland(vector<vector<int>>& grid) { int cnt = 0; for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[0].size(); j++) { if (grid[i][j] == 0 && dfs(grid, i, j)) cnt++; } } return cnt; } bool dfs(vector<vector<int>>& grid, int y, int x) { if (y < 0 || y >= grid.size() || x < 0 || x >= grid[0].size()) return false; if (grid[y][x] == 0) grid[y][x] = -1; else return true; bool up = dfs(grid, y - 1, x); bool dw = dfs(grid, y + 1, x); bool lt = dfs(grid, y, x - 1); bool rt = dfs(grid, y, x + 1); return up && dw && lt && rt; }}; 剑指22 链表倒数第k个节点无序单链表后序遍历class Solution {private: ListNode* out = NULL;public: ListNode* getKthFromEnd(ListNode* head, int k) { dfs(head, k); return out; } void dfs(ListNode* head, int& k) { if (!head) return; dfs(head->next, k); if (--k== 0 && !out) out = head; }};或者采用双指针 L847 访问所有节点的最短路径无向连通图输出邻接链表i行表示i节点，表示和i连通的其他节点标注[[1,2,3],[0],[0],[0]]：0-1；0-2；0-3； DFS：状态转移图：状态2^N，操作N个class Solution {private: struct State { int cover; int i; State(int _cover, int _i) : cover(_cover), i(_i) {} };public: int shortestPathLength(vector<vector<int>>& adj) { const int N = adj.size(); const int END = (1 << N) - 1; vector<State> currs; vector<vector<int>> dist(1 << N, vector<int>(N, 0)); // 标记是否已遍历 // 从所有点（同时）出发BFS for (int i = 0; i < N; ++i) { currs.push_back(State(1 << i, i)); dist[1 << i][i] = 0; } // 层次遍历 for (int level = 0; !currs.empty(); ++level) { vector<State> nexts; for (auto curr : currs) { for (int j : adj[curr.i]) { int v = curr.cover | (1 << j); if (v == END) return level + 1; // 终点 if (!dist[v][j]) { dist[v][j] = 1; nexts.push_back(State(v, j)); } } } currs = nexts; } return 0; }}; DP：cover 表示一条路径上访问过的节点集合，head 表示当前节点。dist[cover][head] 存储路径 (cover, head) 的长度。class Solution {public: int shortestPathLength(vector<vector<int>>& graph) { int N = graph.size(); int target = (1 << N) - 1; vector<vector<int>> dp(target+1, vector<int>(N, N * N)); for (int i = 0; i < N; i++) dp[1 << i][i] = 0; for (int i = 0; i <= target; i++) { bool repeat = true; while (repeat) { repeat = false; for (int j = 0; j < N; j++) { int dist = dp[i][j]; for (auto next : graph[j]) { int x = i | (1 << next); if (dist + 1 < dp[x][next]) { dp[x][next] = dist + 1; if (x == i) repeat = true; } } } } } int out = N * N; for (auto x : dp[target]) out = min(out, x); return out; }}; L1293 网格中得最短路径二维网格，0空 1障碍最多可消除k个障碍物求(0,0)到(m-1,n-1)的最短路径，最多经过k个障碍物定义三元组（x，y，rest），位置 + 障碍物grid[0][0] == grid[m-1][n-1] == 0 BFS 广搜class Solution {private: struct State { int y, x; int e; State(int _y, int _x, int _e) : x(_x), y(_y), e(_e) {} }; int delta_yx[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};public: int shortestPath(vector<vector<int>>& grid, int k) { int N = grid.size(), M = grid[0].size(); if (N == 1 && M == 1) return 0; k = min(k, N + M - 2); bool visited[N][M][k+1]; memset(visited, false, sizeof(visited)); queue<State> q; q.emplace(0, 0, k); visited[0][0][k] = true; int steps = 0; while (!q.empty()) { int len = q.size(); steps++; for (int i = 0; i < len; i++) { auto cur_s = q.front(); q.pop(); for (int j = 0; j < 4; j++) { int yd = cur_s.y + delta_yx[j][0]; int xd = cur_s.x + delta_yx[j][1]; if (yd < 0 || xd < 0 || yd >= N || xd >= M) continue; if (grid[yd][xd] == 0 && !visited[yd][xd][cur_s.e]) { if (yd == N - 1 && xd == M - 1) return steps; visited[yd][xd][cur_s.e] = true; q.emplace(yd, xd, cur_s.e); } else if (grid[yd][xd] == 1 && cur_s.e > 0 && !visited[yd][xd][cur_s.e-1]) { visited[yd][xd][cur_s.e-1] = true; q.emplace(yd, xd, cur_s.e - 1); } } } } return -1; };}; DFS 深度优先搜索TODO L25 K 个一组翻转链表反转链表大集合 L206 反转链表 L92 反转链表II 反转m~n号节点之间的链表 L25 K个一组反转链表/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* reverseL(ListNode* left, ListNode* right) { if (left == right) return left; ListNode* pre = NULL, *cur = left; while (cur != right) { ListNode* next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; } ListNode* reverseKGroup(ListNode* head, int k) { if (!head) return NULL; ListNode *x = head, *y = head; for (int i = 0; i < k; i++) { if (!y) return head; y = y->next; } ListNode* last = reverseL(x, y); x->next = reverseKGroup(y, k); return last; }}; L189 旋转数组一维数组循环右移k[1,2,3,4,5,6,7] 和 k = 3[5,6,7,1,2,3,4]三次反转class Solution {public: void rotate(vector<int>& nums, int k) { int len = nums.size(); if (len < 2) return; k = k % len; int left = 0, right = len - k - 1; while (left < right) swap(nums[left++], nums[right--]); left = len - k, right = len - 1; while (left < right) swap(nums[left++], nums[right--]); left = 0, right = len - 1; while (left < right) swap(nums[left++], nums[right--]); }}; 剑指27 二叉树镜像二叉树左子树和右子树互换从底向上遍历比较符合class Solution {public: TreeNode* mirrorTree(TreeNode* root) { if (!root) return root; TreeNode* left = mirrorTree(root->left); TreeNode* right = mirrorTree(root->right); root->left = right; root->right = left; return root; }}; L113 路径总和 II二叉树路径：根节点到叶节点保存路径和等于k的所有路径回溯算法class Solution {public: vector<vector<int>> pathSum(TreeNode* root, int sum) { if (!root) return {}; vector<vector<int>> out; vector<int> tmp; tmp.push_back(root->val); backtrack(root, tmp, out, root->val, sum); return out; } void backtrack(TreeNode* node, vector<int>& tmp, vector<vector<int>>& out, int sum, int S) { if (node && !node->right && !node->left) { // leaf node if (sum == S) out.push_back(tmp); } if (node->left) { tmp.push_back(node->left->val); backtrack(node->left, tmp, out, sum + node->left->val, S); tmp.pop_back(); } if (node->right) { tmp.push_back(node->right->val); backtrack(node->right, tmp, out, sum + node->right->val, S); tmp.pop_back(); } }}; L1 两数之和一维数组搜素两数之和等于k的下标！class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> m; for (int i = 0; i < nums.size(); i++) { int rest = target - nums[i]; if (m.count(rest) != 0) return {m[rest], i}; m[nums[i]] = i; } return {-1, -1}; }}; L74 搜素二维矩阵二维数组每行升序，每列升序每行起始整数大于前一行最后整数 matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]] target = 3class Solution {public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty()) return false; int N = matrix.size(), M = matrix[0].size(); int y = N - 1, x = 0; while (y >= 0 && y < N && x >= 0 && x < M) { if (matrix[y][x] == target) return true; else if (matrix[y][x] > target) y--; else if (matrix[y][x] < target) x++; } return false; }}; L110 平衡二叉树二叉树平衡：每个节点的左右子树的高度差的绝对值不超过1class Solution {public: bool balanced = true; bool isBalanced(TreeNode* root) { het_count(root); return balanced; } int het_count(TreeNode* node) { if (!node) return 0; if (!balanced) return -1; //剪枝 int lt = het_count(node->left); int rt = het_count(node->right); if (abs(lt - rt) > 1) balanced = false; return max(lt, rt) + 1; }}; L222 完全二叉树的节点数二叉树完全二叉树：长这个样子1 / \ 2 3 / \ /4 5 6其实就是满二叉树节点计算 + 普通的计算 > O(lgn*lgn)class Solution {public: int countNodes(TreeNode* root) { int left = 0, right = 0; TreeNode* node = root; while (node) { left++; node = node->left; } node = root; while (node) { right++; node = node->right; } if (left == right) return pow(2, left) - 1; else return 1 + countNodes(root->left) + countNodes(root->right); }}; 剑指36 二叉搜索树与双向链表二叉搜索树：左 < 根 < 右双向循环链表：前驱+后驱 指针把二叉搜索树 转换为 双向链表输出的双向链表，头节点head指向二叉搜索树的中的最小节点class Solution {private: Node *pre = NULL, *head = NULL;public: void dfs(Node* root) { if (!root) return; dfs(root->left); if (!head) { head = root; pre = root; } else { pre->right = root; root->left = pre; pre = root; } dfs(root->right); } Node* treeToDoublyList(Node* root) { if (!root) return root; dfs(root); head->left = pre; // cycle pre->right = head; return head; }}; L98 验证二叉搜索树二叉搜索树class Solution {private: bool isBST = true; TreeNode* pre = NULL;public: bool isValidBST(TreeNode* root) { if (!root || !isBST) return isBST; isValidBST(root->left); if (!pre) pre = root; else { if (root->val <= pre->val) isBST = false; else pre = root; } isValidBST(root->right); return isBST; }}; 215 数组中的第k大元素数组未排序找到第k大元素快排和堆排 快排思想class Solution {public: int findKthLargest(vector<int>& nums, int k) { int n = nums.size(); if (n < k) return -1; int left = 0, right = nums.size() - 1; while (true) { int pos = partition(nums, left, right); if (pos == k) return nums[k - 1]; else if (pos > k) right = pos - 1; else left = pos; } return nums[k - 1]; } int partition(vector<int>& nums, int left, int right) { if (left > right) return -1; if (left == right) return left + 1; int pivot = nums[left]; int c1 = left, c2 = right; while (c1 < c2) { while (c1 < c2 && nums[c2] <= pivot) c2--; if (c1 < c2) nums[c1++] = nums[c2]; while (c1 < c2 && nums[c1] > pivot) c1++; if (c1 < c2) nums[c2--] = nums[c1]; } nums[c1] = pivot; return c1 + 1; }}; 推排思想class Solution {public: int findKthLargest(vector<int>& nums, int k) { int n = nums.size(); for (int i = n / 2 - 1; i >= 0; i--) { heapBuild(nums, i, n); } for (int i = n - 1; i >= n - k + 1; i--) { swap(nums[0], nums[i]); heapBuild(nums, 0, i); } return nums[0]; } void heapBuild(vector<int>& nums, int root, int end) { int left = 2 * root + 1; if (left >= end) return; int right = left + 1; int maxIdx = ((right < end) && (nums[right] > nums[left]))?right:left; if (nums[maxIdx] < nums[root]) return; swap(nums[maxIdx], nums[root]); heapBuild(nums, maxIdx, end); }}; 十大排序算法Github - 7个排序算法 L7 整数反转123 > 321class Solution {public: int reverse(int x) { string str = to_string(x); bool sgn = (str[0] != '-'); if (!sgn) str.erase(str.begin()); int left = 0, right = str.size() - 1; while (left < right) swap(str[left++], str[right--]); long out = stol(str); if (!sgn) out = -1 * out; if (out < INT_MIN || out > INT_MAX) return 0; return out; }};优雅点的class Solution {public: int reverse(int x) { string str = to_string(x); bool sgn = (str[0] != '-'); if (!sgn) str.erase(str.begin()); int left = 0, right = str.size() - 1; while (left < right) swap(str[left++], str[right--]); long out = stol(str); if (!sgn) out = -1 * out; if (out < INT_MIN || out > INT_MAX) return 0; return out; }}; L102 二叉树层次遍历 DFS写法class Solution {public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; levelInsertDFS(root, 0, res); return res; } void levelInsertDFS(TreeNode* node, int level, vector<vector<int>>& res) { if (!node) return; if (res.size() == level) res.push_back({}); res[level].push_back(node->val); if (node->left) levelInsertDFS(node->left,level+1,res); if (node->right) levelInsertDFS(node->right,level+1,res); }}; BFS写法class Solution {public: vector<vector<int>> levelOrder(TreeNode* root) { if (!root) return {}; vector<vector<int>> out; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int sz = q.size(); vector<int> tmp; for (int i = 0; i < sz; i++) { auto x = q.front(); q.pop(); tmp.push_back(x->val); if (x->left) q.push(x->left); if (x->right) q.push(x->right); } out.push_back(tmp); } return out; }}; L562 矩阵中最长的连续1线段二维矩阵水平，垂直，左上和右下四个方向找最长连续1线段不能之间DFS，因为不是路径，线段是直的！ 暴力class Solution {public: int record(vector<vector<int>>& M, int y, int x, int dy, int dx) { int H = M.size(), W = M[0].size(); int out = 0, maxV = 0; while (!(y < 0 || y >= H || x < 0 || x >= W)) { if (M[y][x]) maxV = max(maxV, ++out); else out = 0; y += dy; x += dx; } return maxV; } int longestLine(vector<vector<int>>& M) { if (M.empty()) return 0; int H = M.size(), W = M[0].size(); int out = INT_MIN; for (int i = 0; i < H; i++) { out = max(out, record(M, i, 0, 0, 1)); out = max(out, record(M, i, 0, 1, 1)); out = max(out, record(M, i, W - 1, 1, -1)); } for (int i = 0; i < W; i++) { out = max(out, record(M, 0, i, 1, 0)); out = max(out, record(M, 0, i, 1, 1)); out = max(out, record(M, 0, i, 1, -1)); } return out; }}; 1维DP 2维DP L41 缺失的第一个正数未排序的一维数组找出没有出现在其中的最小正整数！class Solution {public: int firstMissingPositive(vector<int>& nums) { int N = nums.size(); if (N == 0) return 1; for (int i = 0; i < N; i++) { while (nums[i] > 0 && nums[i] < N && nums[i] != nums[nums[i] - 1]) swap(nums[i], nums[nums[i] - 1]); } for (int i = 0; i < N; i++) if (nums[i]!= i + 1) return i + 1; return N + 1; }}; L448 找到所有数组中消失的数字一维数组1 <= x <= size找到消失的数字class Solution {public: vector<int> findDisappearedNumbers(vector<int>& nums) { int n = nums.size(); vector<int> out; for (int i = 0; i < n; i++) { int pos = abs(nums[i]) - 1; if (nums[pos] >= 0) nums[pos] *= -1; } for (int i = 0; i < n; i++) if (nums[i] > 0) out.push_back(i + 1); return out; }}; L82 删除排序链表中的重负元素 II已排序链表含有重复数组，把重复的节点都删去！ 递归class Solution {public: ListNode* deleteDuplicates(ListNode* head) { if (!head) return head; if (head->next && head->next->val == head->val) { while (head->next && head->next->val == head->val) head = head->next; return deleteDuplicates(head->next); } else head->next = deleteDuplicates(head->next); return head; }}; 迭代 快慢指针class Solution {public: ListNode* deleteDuplicates(ListNode* head) { if (!head || !head->next) return head; ListNode *dummy = new ListNode(-1); dummy->next = head; ListNode *slow = dummy, *fast = head; while (fast) { while (fast->next && fast->val == fast->next->val) fast = fast->next; if (slow->next == fast) slow = slow->next; else slow->next = fast->next; fast = fast->next; } return dummy->next; }}; L94 二叉树中序遍历二叉树中序遍历 递归class Solution {public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res = {}; if (!root) return res; inorder(root, res); return res; } void inorder(TreeNode* root, vector<int>& res) { if (!root) return; if (root->left) inorder(root->left, res); res.push_back(root->val); if (root->right) inorder(root->right, res); }}; 栈 TODO L257 二叉树的所有路径路径：二叉树根节点到叶节点的所有节点class Solution {public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> out; if (!root) return out; dfs(root, out, to_string(root->val)); return out; } void dfs(TreeNode* root, vector<string>& out, string tmp) { if (!root->left && !root->right) { if (!tmp.empty()) out.push_back(tmp); return; } if (root->left) dfs(root->left, out, tmp + "->" + to_string(root->left->val)); if (root->right) dfs(root->right, out, tmp + "->" + to_string(root->right->val)); }}; L124. 二叉树中的最大路径和路径：定义为经过任意节点的序列class Solution {private: int maxV = INT_MIN;public: int maxPathSum(TreeNode* root) { dfs(root); return maxV; } int dfs(TreeNode* root) { if (!root) return 0; int leftV = max(dfs(root->left), 0); int rightV = max(dfs(root->right), 0); maxV = max(maxV, leftV + rightV + root->val);//记录root为根节点的路径 return max(leftV, rightV) + root->val;//返回经过该点的较大路径 }}; L450. 删除二叉搜索树中的节点二叉搜素树 左节点值 < 根节点值 < 右节点值注意二叉搜索树的某个节点的前继节点(predecessor)和后继节点(successor)int successor(TreeNode* node) { // 相邻较大值 node = node->right; while (node && node->left) node = node->left; return node->val;}int predecessor(TreeNode* node) { // 相邻较小值 node = node->left; while (node && node->right) node = node->right; return node->val;}代码class Solution {public: TreeNode* deleteNode(TreeNode* root, int key) { if (!root) return root; if (root->val > key) root->left = deleteNode(root->left, key); else if (root->val < key) root->right = deleteNode(root->right, key); else if (root->val == key) { if (!root->right && !root->left) root = NULL; else if (root->right) { root->val = successor(root); root->right = deleteNode(root->right, root->val); } else { root->val = predecessor(root); root->left = deleteNode(root->left, root->val); } } return root; }}; 40. 组合总和 II一维数组找出所有和为k的数字序列主要看数组中的数字能不能重复取用数组无重复 + 能重复取用= 39题：class Solution {public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<int> tmp; vector<vector<int>> res; backtrack(candidates, res, tmp, 0, target); return res; } void backtrack(vector<int>& cand, vector<vector<int>>& res, vector<int>& tmp, int pos, int tar) { if (tar < 0) return; if (tar == 0) {res.push_back(tmp); return;} for (int i = pos; i < cand.size(); i++) { tmp.push_back(cand[i]); backtrack(cand, res, tmp, i, tar - cand[i]); tmp.pop_back(); } }};数组含重复 + 不能重复取用= 40题class Solution {private: vector<bool> visits; // Label 1public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { vector<int> tmp; vector<vector<int>> res; visits.resize(candidates.size(), false); // Label 2 sort(candidates.begin(), candidates.end()); // Label 3 backtrack(candidates, res, tmp, 0, target); return res; } void backtrack(vector<int>& cand, vector<vector<int>>& res, vector<int>& tmp, int pos, int tar) { if (tar < 0) return; if (tar == 0) {res.push_back(tmp); return;} for (int i = pos; i < cand.size(); i++) { if (visits[i]) continue; // 保证不重复取用 Label 4 if ((i > pos && cand[i] == cand[i - 1]) && !visits[i - 1]) continue; // 重复数字不能在同层 Label 5 tmp.push_back(cand[i]); visits[i] = true; backtrack(cand, res, tmp, i, tar - cand[i]); tmp.pop_back(); visits[i] = false; } }}; 658. 找到 K 个最接近的元素一维升序数组找和X最近的k个元素当和X距离相同，把较小的数字放在前面！ STL自带排序class Solution {public: vector<int> findClosestElements(vector<int>& arr, int k, int x) { int n = arr.size(); sort(arr.begin(), arr.end(), [x](int a, int b){ bool flag = false; if (abs(a-x) < abs(b-x)) flag = true; else if (abs(a-x) == abs(b-x)) flag = a < b; return flag; }); vector<int> out; for (int i = 0; i < min(n, k); i++) out.push_back(arr[i]); sort(out.begin(), out.end()); return out; }}; 双指针数组已排序，使用左右双指针class Solution {public: vector<int> findClosestElements(vector<int>& arr, int k, int x) { int n = arr.size(); if (n <= k) return arr; int left = 0, right = arr.size() - 1; while (right >= left && right - left + 1 > k) { int d_left = x - arr[left]; int d_right = arr[right] - x; if (d_left == d_right) { if (arr[left] < arr[right]) right--; else left++; } else if (d_left > d_right) left++; else right--; } vector<int> out(arr.begin()+left, arr.begin()+right+1); return out; }}; 二分查找数组是升序，用二分查找找左边界left就行left + k确定出区间class Solution {public: vector<int> findClosestElements(vector<int>& arr, int k, int x) { int n = arr.size(); if (n <= k) return arr; int left = 0, right = n - k; while (left < right) { int mid = left + (right - left) / 2; if (x - arr[mid] > arr[mid+k] - x) { left = mid + 1; } else right = mid; } vector<int> out(arr.begin()+left, arr.begin()+left+k); return out; }}; 316. 去除重复字母原则：两个相同位数的数字大小关系取决于第一个不同的数的大小字典序：ASCII表上面的字母先后顺序不打乱字符的相对位置 贪心class Solution {public: string removeDuplicateLetters(string s) { if (s.empty()) return ""; int lookup[26] = {0}; for (auto& c : s) lookup[c-'a']++; int pos = 0; for (int i = 0; i < s.size(); i++) { if (s[i] < s[pos]) pos = i; if (--lookup[s[i]-'a'] == 0) break; } char c = s[pos]; s = s.substr(pos + 1); s.erase(remove(s.begin(), s.end(), c), s.end()); return c + removeDuplicateLetters(s); }}; 单调栈class Solution {public: string removeDuplicateLetters(string s) { unordered_map<char, int> last_occur;//最后出现的位置 unordered_set<char> seen;//保证不重复 vector<char> st; for (int i = 0; i < s.size(); i++) last_occur[s[i]] = i; for (int i = 0; i < s.size(); i++) { char c = s[i]; if (seen.count(c)) continue; while (!st.empty() && c < st.back() && last_occur[st.back()] > i) { seen.erase(st.back()); st.pop_back(); } seen.insert(s[i]); st.push_back(s[i]); } return string(st.begin(), st.end()); }}; 剑指22 链表中倒数第k个节点单链表取倒数k节点class Solution {private: ListNode* out = NULL;public: ListNode* getKthFromEnd(ListNode* head, int k) { if (k < 1 || !head) return head; dfs(head, k); return out; } void dfs(ListNode* head, int& k) { if (!head) return; dfs(head->next, k); if (k == 1) out = head; k--; }}; 560. 和为K的子数组一维数组元素有正有负用sum大于k来作为缩小窗口的标准 枚举class Solution {public: int subarraySum(vector<int>& nums, int k) { int out = 0; for (int i = 0; i < nums.size(); i++) { int sum = 0; for (int j = i; j >= 0; j--) { sum += nums[j]; if (sum == k) out++; } } return out; }}; 前缀和优化枚举复杂度使用前缀和/累积数组使用map记录前面有多少是"可以的"值 pre - kclass Solution {public: int subarraySum(vector<int>& nums, int k) { unordered_map<int, int> record; int pre = 0, out = 0; record[0] = 1; for (int i = 0; i < nums.size(); i++) { pre += nums[i]; if (record.count(pre - k)) out += record[pre - k]; record[pre]++; } return out; }}; 442. 数组中重复的数据一维数组1 <= x <= size有出现1次和2次的找出所有出现2次的 MAPclass Solution {public: vector<int> findDuplicates(vector<int>& nums) { unordered_map<int, int> m; vector<int> out; for (int i = 0; i < nums.size(); i++) { m[nums[i]]++; if (m.count(nums[i]) && m[nums[i]] == 2) out.push_back(nums[i]); } return out; }}; 标记class Solution {public: vector<int> findDuplicates(vector<int>& nums) { vector<int> out; for (int i = 0; i < nums.size(); i++) { if (nums[abs(nums[i]) - 1] > 0) nums[abs(nums[i]) - 1] *= -1; else out.push_back(abs(nums[i])); } return out; }}; 1325. 删除给定值的叶子节点二叉树删除给定值的叶子节点需要后序遍历class Solution {public: TreeNode* removeLeafNodes(TreeNode* root, int target) { if (!root) return root; root->left = removeLeafNodes(root->left, target); root->right = removeLeafNodes(root->right, target); if (!root->left && !root->right && root->val == target) return NULL; // 叶节点 return root; }}; 剑指25. 合并两个排序的链表两个链表升序合并 递归法class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; if (l1->val < l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l1, l2->next); return l2; } }}; 迭代法 TODO 240. 搜索二维矩阵 II二维数组每行的元素从左到右升序排列。每列的元素从上到下升序排列。和L74用相同的代码都能过！class Solution {public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty()) return false; int N = matrix.size(), M = matrix[0].size(); int y = N - 1, x = 0; while (y >= 0 && y < N && x >= 0 && x < M) { if (matrix[y][x] == target) return true; else if (matrix[y][x] > target) y--; else if (matrix[y][x] < target) x++; } return false; }}; 958. 二叉树的完全性检验二叉树完全二叉树，只有最后一层节点集中在左侧，上面各层都是满二叉树class Solution {public: bool isCompleteTree(TreeNode* root) { if (!root) return false; queue<TreeNode*> q; q.push(root); TreeNode* pre = root; while (!q.empty()) { auto cur = q.front(); q.pop(); if (!pre && cur) return false; if (cur) { q.push(cur->left); q.push(cur->right); } pre = cur; } return true; }}; 239. 滑动窗口最大值一维数组滑动窗长k步长1移动记录每个窗口中的最大值class Solution {public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { if (k > nums.size()) return {}; deque<int> dq; // 单减栈 vector<int> res; for (int i = 0; i < nums.size(); i++) { while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back(); dq.push_back(i); if (i >= k - 1) { // 长度到了，可以记录了 res.push_back(nums[dq.front()]); if (!dq.empty() && dq.front() == i - k + 1) dq.pop_front(); // 删去窗口左边界 } } return res; }}; 208. 实现 Trie (前缀树)前缀树：多叉树模型，子节点26个(字母)class Trie {private: bool isEnd; Trie* next[26];public: /** Initialize your data structure here. */ Trie() { isEnd = false; memset(next, 0, sizeof(next)); } /** Inserts a word into the trie. */ void insert(string word) { Trie* cur = this; for (auto& c : word) { if (!cur->next[c-'a']) cur->next[c-'a'] = new Trie(); cur = cur->next[c-'a']; } cur->isEnd = true; } /** Returns if the word is in the trie. */ bool search(string word) { Trie* cur = this; for (auto& c : word) { cur = cur->next[c-'a']; if (!cur) return false; } return cur->isEnd; } /** Returns if there is any word in the trie that starts with the given prefix. */ bool startsWith(string prefix) { Trie* cur = this; for (auto& c : prefix) { cur = cur->next[c-'a']; if (!cur) return false; } return true; }}; 99. 恢复二叉搜索树二叉搜索树有两个节点互换了，找到并恢复class Solution {private: TreeNode *pre = NULL, *n1 = NULL, *n2 = NULL;public: void inorder(TreeNode *node) { if (!node) return; inorder(node->left); if (pre && !n1 && node->val < pre->val) n1 = pre; if (n1 && node->val < pre->val) n2 = node; pre = node; inorder(node->right); } void recoverTree(TreeNode* root) { inorder(root); if (n1 && n2) swap(n1->val, n2->val); }}; 56. 合并区间二维数组，Nx2重叠头和尾接触class Solution {public: vector<vector<int>> merge(vector<vector<int>>& intervals) { if (intervals.empty()) return {}; vector<vector<int>> out; sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){ return a[0] < b[0]; }); int startx = intervals[0][0]; int endx = intervals[0][1]; for (int i = 1; i < intervals.size(); i++) { if (intervals[i][0] <= endx) { endx = max(endx, intervals[i][1]); } else { out.push_back({startx, endx}); startx = intervals[i][0]; endx = intervals[i][1]; } } out.push_back({startx, endx}); return out; }}; 199. 二叉树的右视图二叉树右视图：从右往左看class Solution {public: vector<int> rightSideView(TreeNode* root) { if (!root) return {}; vector<int> out; dfs(root, out, 0); return out; } void dfs(TreeNode *node, vector<int>& out, int depth) { if (!node) return; if (depth == out.size()) out.push_back(node->val); dfs(node->right, out, depth+1); dfs(node->left, out, depth+1); }};BFS TODO 面试题 02.05. 链表求和两个单向链表头节点为个位class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *dummy = new ListNode(-1); dummy->next = l1; ListNode *p = dummy; int up = 0; while (l1 && l2) { int sum = up + l1->val + l2->val; p->next = new ListNode(sum % 10); up = sum / 10; l1 = l1->next; l2 = l2->next; p = p->next; } if (l2) swap(l1, l2); while (l1) { int sum = l1->val + up; p->next = new ListNode(sum % 10); up = sum / 10; l1 = l1->next; p = p->next; } if (up) p->next = new ListNode(up); return dummy->next; }}; 105. 从前序与中序遍历序列构造二叉树两个一维数组class Solution {private: unordered_map<int, int> m;public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int n = inorder.size() - 1; for (int i = 0; i <= n; i++) m[inorder[i]] = i; return dfs_build(preorder, 0, n, inorder, 0, n); } TreeNode* dfs_build(vector<int>& pre, int s1, int e1, vector<int>& ino, int s2, int e2) { if (s1 > e1 || s2 > e2) return NULL; int root_val = pre[s1]; int root_idx = m[root_val]; int left_len = root_idx - s2; int right_len = e2 - root_idx; TreeNode *node = new TreeNode(root_val); node->left = dfs_build(pre, s1 + 1, s1 + left_len, ino, s2, root_idx - 1); node->right = dfs_build(pre, s1 + left_len + 1, e1, ino, root_idx + 1, e2); return node; }}; 674. 最长连续递增序列一维数组找到最长递增子序列长度class Solution {public: int findLengthOfLCIS(vector<int>& nums) { if (nums.size() < 2) return nums.size(); int st = 0, i = 1, out = INT_MIN; for (i = 1; i < nums.size(); i++) { if (nums[i] <= nums[i-1]) { out = max(out, i - st); st = i; } } return max(out, i - st); }}; 剑指46. 把数字翻译成字符串一个整数0~25 翻译成 a~z判断这串数字最多几种方法class Solution {public: int translateNum(int num) { string s = to_string(num); int n = s.size(); vector<int> dp(n + 1, 1); for (int i = 2; i <= n; i++) { int tmp = stoi(s.substr(i-2, 2)); if (tmp < 26 && tmp > 9) dp[i] = dp[i-1] + dp[i-2]; else dp[i] = dp[i-1]; } return dp.back(); }}; 557. 反转字符串中的单词 III字符串保留空格和单词的初始顺序class Solution {public: void reverse(string& strs, int start, int end) { if (start >= strs.size()) return; while (start < end) swap(strs[start++], strs[end--]); } string reverseWords(string s) { vector<int> x; int start = 0; for (int i = 0; i < s.size(); i++) if (s[i] == ' ') x.push_back(i); for (auto& z : x) { reverse(s, start, z - 1); start = z + 1; } reverse(s, start, s.size() - 1); return s; }}; 153. 寻找旋转排序数组中的最小值升序数组循环右移（旋转）二分查找class Solution {public: int findMin(vector<int>& nums) { int left = 0, right = nums.size(); while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums.back()) left = mid + 1; else right = mid; } return nums[left]; }}; 剑指32 - III. 从上到下打印二叉树 III二叉树层次遍历打印class Solution {public: vector<int> levelOrder(TreeNode* root) { if (!root) return {}; vector<int> level; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int sz = q.size(); for (int i = 0; i < sz; i++) { auto x = q.front(); q.pop(); level.push_back(x->val); if (x->left) q.push(x->left); if (x->right) q.push(x->right); } } return level; }};分层打印2class Solution {public: vector<vector<int>> levelOrder(TreeNode* root) { if (!root) return {}; vector<vector<int>> out; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int sz = q.size(); vector<int> level; for (int i = 0; i < sz; i++) { auto x = q.front(); q.pop(); level.push_back(x->val); if (x->left) q.push(x->left); if (x->right) q.push(x->right); } out.push_back(level); } return out; }};之字形打印class Solution {public: vector<vector<int>> levelOrder(TreeNode* root) { if (!root) return {}; vector<vector<int>> out; queue<TreeNode*> q; q.push(root); int dir = 1; while (!q.empty()) { int sz = q.size(); vector<int> level; for (int i = 0; i < sz; i++) { auto x = q.front(); q.pop(); if (dir > 0) level.push_back(x->val); else level.emplace(level.begin(), x->val); if (x->left) q.push(x->left); if (x->right) q.push(x->right); } out.push_back(level); dir *= -1; } return out; }}; 剑指29. 顺时针打印矩阵二维数组从外到里顺时针打印数字class Solution {public: vector<int> spiralOrder(vector<vector<int>>& matrix) { if (matrix.empty()) return {}; vector<int> res; vector<vector<int>> dirs {{0,1},{1,0},{0,-1},{-1,0}}; int y = 0, x = -1, n = matrix.size() - 1, m = matrix[0].size(); int dir = 0; while (n >= 0 && m >= 0) { int loop = (dir % 2) ? n-- : m--; for (int i = 0; i < loop; i++) { y += dirs[dir][0]; x += dirs[dir][1]; res.push_back(matrix[y][x]); } dir = (dir + 1) % 4; } return res; }}; 179. 最大数输入一组非负整数重排成一个最大整数（字符串）class Solution {public: string largestNumber(vector<int>& nums) { vector<string> strs; string out = ""; for (auto& n : nums) strs.push_back(to_string(n)); sort(strs.begin(), strs.end(), [](const string& a, const string& b) { return (a + b) > (b + a); // 这里加上=会报错 }); if (strs[0] == "0") return "0"; for (auto& s : strs) out += s; return out; }}; 628. 三个数的最大乘积一维数组找到乘积最大的三个数元素有正有负找到 最大的三个数以及最小的两个数 即可这里就使用sortclass Solution {public: int maximumProduct(vector<int>& nums) { int N = nums.size(); if (N < 3) return -1; sort(nums.begin(), nums.end()); int n1 = nums[N - 1] * nums[N - 2] * nums[N - 3]; int n2 = nums[N - 1] * nums[0] * nums[1]; return max(n1, n2); }}; 328. 奇偶链表单向链表奇偶这里指的是节点序号的奇偶奇节点放在前面，偶节点放在后面其余顺序不变使用双指针class Solution {public: ListNode* oddEvenList(ListNode* head) { if (!head || !head->next) return head; ListNode *oddN = head, *eveN = head->next; ListNode *eveNHead = eveN; while (eveN && eveN->next) { oddN->next = eveN->next; oddN = oddN->next; eveN->next = oddN->next; eveN = eveN->next; } oddN->next = eveNHead; return head; }}; 剑指54. 二叉搜索树的第k大节点二叉搜素树右中左，得到降序左中右，得到升序class Solution {private: int out = INT_MIN;public: int kthLargest(TreeNode* root, int k) { dfs(root, k); return out; } void dfs(TreeNode *node, int& k) { if (!node) return; dfs(node->right, k); if (--k == 0) out = node->val; dfs(node->left, k); }}; 80. 删除排序数组中的重复项 II升序数组重复次数会出现超过2次输出数组重复次数限制在2次class Solution {public: int removeDuplicates(vector<int>& nums) { if (nums.empty()) return 0; int idx = 0, cnt = 0; for (int i = 1; i < nums.size(); i++) { if (nums[i] == nums[idx]) cnt++; else cnt = 0; if (cnt < 2) nums[++idx] = nums[i]; } for (int i = idx + 1; i < nums.size(); i++) nums.pop_back(); return idx + 1; }}; class Solution {public: int removeDuplicates(vector<int>& nums) { if (nums.size() < 2) return nums.size(); int idx = 1; for (int i = 2; i < nums.size(); i++) { if (nums[i] != nums[idx - 1]) // 容许2元素 nums[++idx] = nums[i]; } // for (int i = idx + 1; i < nums.size(); i++) // nums.pop_back(); return idx + 1; }}; 236. 二叉树的最近公共祖先最深的公共祖先节点class Solution {public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root || root->val == p->val || root->val == q->val) return root; auto a = lowestCommonAncestor(root->left, p, q); auto b = lowestCommonAncestor(root->right, p, q); if (!a) return b; if (!b) return a; return root; }}; 234. 回文链表判断是不是回文链表前序和后序比较class Solution {public: bool isPalindrome(ListNode* head) { ListNode *tmp = head; return postOrder(head, tmp); } bool postOrder(ListNode* node, ListNode*& head) { if (!node) return true; if (!head) return true; bool flag = postOrder(node->next, head); bool flag2 = true; if (head->val != node->val) flag2 = false; head = head->next; return flag && flag2; }};快慢指针 或 栈，TODO 662. 二叉树最大宽度二叉树宽度：每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。使用BFS记录每个节点的序号，根节点1时，左节点序号为2x，右节点2x+1这道题得 使用到无符号长长整型 8字节typedef unsigned long long ull;class Solution {public: int widthOfBinaryTree(TreeNode* root) { if (!root) return NULL; queue<TreeNode*> q; deque<ull> dq; q.push(root); dq.push_back(1); ull out = 1; while (!q.empty()) { int sz = q.size(); for (int i = 0; i < sz; i++) { auto t = q.front(); q.pop(); ull x = dq.front(); dq.pop_front(); if (t->left) { q.push(t->left); dq.push_back(2 * x); } if (t->right) { q.push(t->right); dq.push_back(2 * x + 1); } } if (dq.size() > 1) out = max(out, dq.back() - dq.front() + 1); } return out; }}; 518. 零钱兑换 II无限硬币和为Kclass Solution {public: int change(int amount, vector<int>& coins) { int N = coins.size(); vector<int> dp(amount+1, 0); dp[0] = 1; for (auto& c : coins) { for (int i = c; i <= amount; i++) { dp[i] += dp[i - c]; } } return dp.back(); }}; L1143 最长公共子序列两个字符串子序列：不改变字符的相对顺序的 部分数据找最长子序列的最大长度class Solution {public: int longestCommonSubsequence(string text1, string text2) { if (text1.empty() || text2.empty()) return 0; int N = text1.size(), M = text2.size(); vector<vector<int>> dp(N+1, vector<int>(M+1, 0)); for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { if (text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } return dp.back().back(); }}; + 剑指offer + DP 猿辅导2020算法笔试 区间最多重叠数 网易互联网2020CV岗 一维数组，最少抛弃多少能等分二份回溯，三叉树#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>using namespace std;const int N = 20;int T, n, ret;int w[N];int a, b, c;void dfs(int u) { if (u == n) { if (a == b) ret = min(ret, c); return; } a += w[u]; dfs(u + 1); a -= w[u]; b += w[u]; dfs(u + 1); b -= w[u]; c += w[u]; dfs(u + 1); c -= w[u];}int main() { cin >> T; while (T -- ) { cin >> n; ret = 0; for (int i = 0; i < n; i ++ ) cin >> w[i], ret += w[i]; dfs(0); cout << ret << endl; } return 0;} 排队时间问题自己买耗时a，和前面的人一起买耗时b （单位秒）8::00::00 am 开售#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>using namespace std;const int N = 2010;int T, n;int a[N], b[N], f[N];int main() { cin >> T; while (T -- ) { cin >> n; for (int i = 1; i <= n; i ++ ) cin >> a[i]; for (int i = 1; i <= n - 1; i ++ ) cin >> b[i]; f[1] = a[1]; for (int i = 2; i <= n; i ++ ) f[i] = min(f[i - 1] + a[i], f[i - 2] + b[i - 1]); int &t = f[n]; int h = t / 3600 + 8, m = t % 3600 / 60, s = t % 60; bool status = true; if (h > 12) h -= 12, status = false; printf("d:d:d %s\n", h, m, s, status ? "am" : "pm"); } return 0;} 收藏（0）