上海企业免费网站建设,网站管理员怎么联系,欣宝儿在什么网站做直播,wordpress 搭建教程1382 用迭代遍历把1382又做了一遍 中序遍历树再记一遍
这次的中序遍历总结#xff1a;重点在curr不是每次pop的时候更新 而是要作为一个全局变量记录
while里面都用if else 不要再用while
容易出现的bug是 在左节点遍历完之后#xff0c;在vec加入中节点时又去判断左节点的…1382 用迭代遍历把1382又做了一遍 中序遍历树再记一遍
这次的中序遍历总结重点在curr不是每次pop的时候更新 而是要作为一个全局变量记录
while里面都用if else 不要再用while
容易出现的bug是 在左节点遍历完之后在vec加入中节点时又去判断左节点的问题 - 放到vec之后只看右节点 所以要用if else把这两种隔开 加入到vec之后就让currcurr-right
如果有左就一直放 currcurr-left
class Solution {
private:vectorint vec;void traversal(TreeNode* root) {stackTreeNode* stack;TreeNode* curr root;while (curr!nullptr || !stack.empty()) {if (curr!nullptr) {stack.push(curr);curr curr-left;}else {curr stack.top();stack.pop();vec.push_back(curr-val);curr curr-right;}}/* for (int i0; ivec.size(); i) {coutvec[i] ;} */}TreeNode* get_tree(vectorint vec, int start, int end) {if (startend) return nullptr;int mid (startend)/2;TreeNode* root new TreeNode(vec[mid]);root-left get_tree(vec, start, mid);root-right get_tree(vec, mid1, end);return root; }
public:TreeNode* balanceBST(TreeNode* root) {traversal(root);TreeNode* balanced_BST get_tree(vec, 0, vec.size());return balanced_BST;}
}; 100 用递归写 先比较是否为空同时为空/其中一个为空/都不为空都不为空时返回root-val相等且左右树same
class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {if (pnullptr qnullptr) return true;if (p !q) return false;if (!p q) return false;return p-val q-val isSameTree(p-left, q-left) isSameTree(p-right, q-right);}
};
用迭代写 用queue 层序遍历 一个一个节点比较
class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {if (pnullptr qnullptr) return true;if (!p || !q) return false;queueTreeNode* que;que.push(p);que.push(q);while (!que.empty()) {TreeNode* curr_p que.front();que.pop();TreeNode* curr_q que.front();que.pop();if (curr_p-val!curr_q-val) return false;//leftif (!curr_p-left !curr_q-left) {}else if (!curr_p-left || !curr_q-left) return false;else {que.push(curr_p-left);que.push(curr_q-left);}//rightif (!curr_p-right !curr_q-right) {}else if (!curr_p-right || !curr_q-right) return false;else {que.push(curr_p-right);que.push(curr_q-right);}}return true;}
};
116 用层序遍历 queue来写 count记录每一层的个数 挨个遍历 连next 再放入左右节点
class Solution {
public:Node* connect(Node* root) {queueNode* que;if (root!NULL) que.push(root);while (!que.empty()) {int count que.size();Node* pre NULL;for (int i0; icount; i) {Node* curr que.front(); que.pop();if (curr-left) que.push(curr-left);if (curr-right) que.push(curr-right);if (pre) pre-next curr;pre curr;} }return root;}
};
52 N皇后 回溯写 虽然是困难题但是用回溯模版思路很清晰
回溯时一排一排的放 排数是传递的值 所以遍历所有的列 能放check函数判断的就先放着然后准备放下一行 如果放不了就撤回当前
终止条件是已经放完所有行 说明已经完美放完 此时只需要计数就好
class Solution {
private: int count0;bool canPut (vectorvectorint board, int x, int y) {int n board.size();//check this columnfor (int i0; ix; i) {if (board[i][y]1) return false;} for (int i0; ix; i) {//check 45 degreeif (yin board[x-i][yi]1) return false;//check 135 degreeif (y-i0 board[x-i][y-i]1) return false;}return true;}void backtracking(vectorvectorint board, int row) {if (rowboard.size()) {count;return;}for (int i0; iboard[0].size(); i) {if (canPut(board, row, i)) {board[row][i]1;backtracking(board, row1);board[row][i]0;}}}
public:int totalNQueens(int n) {vectorvectorint board(n, vectorint(n,0));backtracking(board, 0);return count;}
}; 649 题意很绕 一开始没看清楚题
禁止任意一名参议员的权利 使之在这一轮和随后的几轮中丧失所有的权利
class Solution {
public:string predictPartyVictory(string senate) {int count_D0;int count_R0;for (int i0; isenate.size(); i) {if (senate[i]D) count_D;if (senate[i]R) count_R;}for (int i0; count_D0 count_R0; i) {if (isenate.size()) i0;if (senate[i]R) {int ji1;while (senate[j%senate.size()]!D) j;senate[j%senate.size()] ;count_D--;}else if (senate[i]D) {int ji1;while(senate[j%senate.size()]!R) j;senate[j%senate.size()] ;count_R--;}}if (count_D0) return Radiant;return Dire;}
};
1221 贪心算法 遇到L和R数量相同时就计数1
class Solution {
public:int balancedStringSplit(string s) {int result 0;int count0;for (int i0; is.size(); i) {if (s[i]R) count;else count--;if (count0) result;}return result;}
};
5 回文子串用动态规划
dp数组 pal[i][j] 表示从i到j这段substr是否是回文子串
初始化是所有i和j相等时的pal为true
递归公式是当 i 和 j 所指相同时 pal[i][j]pal[i1][j-1] 考虑特殊情况 j-i1
遍历顺序是i从后往前 j从前往后 始终保持ji
class Solution {
public:string longestPalindrome(string s) {vectorvectorbool pal(s.size(), vectorbool(s.size(), false));for (int i0; is.size(); i) pal[i][i]true;int longest_len1;string result string(1,s[0]);for (int is.size()-2; i0; i--) {for (int ji1; js.size(); j) {if (s[i]s[j] (ji1 || pal[i1][j-1]true)) {pal[i][j]true;if (j-i1longest_len) {longest_lenj-i1;result s.substr(i, j-i1);}} }}return result;}
};
