LeetCodeブラシ記録
文書ディレクトリ 1. LeetCode 113-パス合計II 2. LeetCode 236-二叉木の最近の共通祖先 3. LeetCode 289-ライフゲーム 4. LeetCode 91-二叉木の中序遍歴 1.LeetCode 113-パス合計II
1、二叉木の先順遍歴は深さ探索と理解することができ、まず最も左の葉ノードを探索し、経路のすべてのノードの値を得ることができる.さらに、遍歴中に木全体の左から右の各葉ノードの経路(ルートノードから葉ノードまでのすべてのノード)を検索(葉ノードが必ずしも同じ層にあるとは限らない)し、深さ検索に相当する;2、vectorはstackを実現し、push_back()はスタックに相当し、pop_back()はポップアップスタックトップ要素に相当し、スタックの機能(検索パスが得られ、ヘッダ要素がルートノードであるスタックベースであり、この問題の出力要求に合致する)を逆出力することもできるし、スタックの要素(ベースからトップまで)を逆出力することもでき、両端キュー列のように考えてもこの機能を実現することができる.
2.LeetCode 236-二叉木の最近の共通祖先
1、核心的な考え方は両ノードに共通のルートノードから最も遠い祖先がいる場合、この2つのノードの探索経路(それぞれpathPとpathQとして表される)では、この祖先以前の探索経路は同じであり、すなわち経路pathPとpathQの先頭は全く同じであり、最初の異なる経路ノードが現れた場合、前のノードは最近の共通の祖先である(つまりルートノードから最も遠い共通の祖先);2、それでは問題を解く構想は1とあまり違わないで、先に二叉木の遍歴アルゴリズムを通じて2つのノードの経路を求めて、それから経路を比較して、経路はvectorで記憶することができて、比較しやすいです;3、書く過程の中で1つのBUGに出会って、result配列でその場で探した経路を保存していないならば、関数のためです再帰の問題では,上位再帰関数は,最後の行コード
3.LeetCode 289-ライフゲーム
1、テーマがちょっと長いですが、実は意味がはっきりしています.まとめてみると、1つの点に対して8近傍の値を1元素の総和(1は生細胞)とし、現在の元素からその元素を1にするか0にするかを判断する.2、従来の解法では、画像のボリュームに相当し、各近傍で結果を求めて新しい配列を開いて結果を格納する(そうでなければ元の配列の更新に問題があり、同時に更新する必要があるため)、最後に元の配列に値を割り当てます.3、主にこの8隣接領域のクエリー思想を記録しましょう.配列の下のラベルが境界を越えているかどうかを判断するには、最初は2つのネストforサイクルだけで行と列を循環しifでインデックスが境界を越えているかどうかを判断したいと思っていましたが、後で発見状況が複雑だと書いていました.判断
1、二叉木の先順遍歴は深さ探索と理解することができ、まず最も左の葉ノードを探索し、経路のすべてのノードの値を得ることができる.さらに、遍歴中に木全体の左から右の各葉ノードの経路(ルートノードから葉ノードまでのすべてのノード)を検索(葉ノードが必ずしも同じ層にあるとは限らない)し、深さ検索に相当する;2、vectorはstackを実現し、push_back()はスタックに相当し、pop_back()はポップアップスタックトップ要素に相当し、スタックの機能(検索パスが得られ、ヘッダ要素がルートノードであるスタックベースであり、この問題の出力要求に合致する)を逆出力することもできるし、スタックの要素(ベースからトップまで)を逆出力することもでき、両端キュー列のように考えてもこの機能を実現することができる.
2.LeetCode 236-二叉木の最近の共通祖先
1、核心的な考え方は両ノードに共通のルートノードから最も遠い祖先がいる場合、この2つのノードの探索経路(それぞれpathPとpathQとして表される)では、この祖先以前の探索経路は同じであり、すなわち経路pathPとpathQの先頭は全く同じであり、最初の異なる経路ノードが現れた場合、前のノードは最近の共通の祖先である(つまりルートノードから最も遠い共通の祖先);2、それでは問題を解く構想は1とあまり違わないで、先に二叉木の遍歴アルゴリズムを通じて2つのノードの経路を求めて、それから経路を比較して、経路はvectorで記憶することができて、比較しやすいです;3、書く過程の中で1つのBUGに出会って、result配列でその場で探した経路を保存していないならば、関数のためです再帰の問題では,上位再帰関数は,最後の行コード
path.pop_back()が本来保存していたアドレスをポップアップしているため,プログラムはルートノードのみを記録する./**
* 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 {
// node key ， path
// result ， path ， pop_back()
void searchPath(TreeNode* node, TreeNode* key, vector<TreeNode*> &path, vector<TreeNode*> &result, int &flag)
{
//
if(!node || flag){
return;
}
//
// ， key
path.push_back(node);
if(node == key){
flag = 1;
result = path;
return;
}
searchPath(node->left, key, path, result, flag);
searchPath(node->right, key, path, result, flag);
path.pop_back();
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//
vector<TreeNode*> pathP, resultP;
vector<TreeNode*> pathQ, resultQ;
int finP = 0, finQ = 0;
searchPath(root, p, pathP, resultP, finP);
searchPath(root, q, pathQ, resultQ, finQ);
TreeNode* publicNode = NULL;
for(int i = 0, n=min(resultQ.size(), resultP.size()); i<n; i++){
if(resultP[i]==resultQ[i])
publicNode = resultQ[i];
else
break;
}
return publicNode;
}
};
3.LeetCode 289-ライフゲーム
1、テーマがちょっと長いですが、実は意味がはっきりしています.まとめてみると、1つの点に対して8近傍の値を1元素の総和(1は生細胞)とし、現在の元素からその元素を1にするか0にするかを判断する.2、従来の解法では、画像のボリュームに相当し、各近傍で結果を求めて新しい配列を開いて結果を格納する(そうでなければ元の配列の更新に問題があり、同時に更新する必要があるため)、最後に元の配列に値を割り当てます.3、主にこの8隣接領域のクエリー思想を記録しましょう.配列の下のラベルが境界を越えているかどうかを判断するには、最初は2つのネストforサイクルだけで行と列を循環しifでインデックスが境界を越えているかどうかを判断したいと思っていましたが、後で発見状況が複雑だと書いていました.判断
row>=0/row=0/col ， （ if/else ）， ， （ 8 ， 4 ， dx/dy ）， 8 if ， ！ if !(i==1&&j==1)という は、 (つまり が な )が み られないようにすることを としています.class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
vector<vector<int>> res(board);
int neighbors[3] = {1, 0, -1};
int rows = board.size(), cols = board[0].size();
for(int row = 0; row<rows; row++){
for(int col = 0; col<cols; col++){
// ，
int count = 0;
for(int i = 0; i<3; i++){
for(int j=0; j<3; j++){
int dr = row + neighbors[i];
int dc = col + neighbors[j];
//
if(dr>=0 && dr<rows && dc>=0 && dc<cols && !(i==1&&j==1) && board[dr][dc]==1)
count++;
}
}
//
if(board[row][col]==1){
if(count<2) res[row][col]=0;
else if(count==2 || count==3) res[row][col]=1;
else res[row][col]=0;
}
else{
if(3==count) res[row][col]=1;
else res[row][col]=0;
}
}
}
board = res;
}
};
4.LeetCode 91-ツリーの
と を し, はスタックを し, に の を した./**
* 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:
//
/*vector inorderTraversal(TreeNode* root) {
vector res;
inorder(res, root);
return res;
}
void inorder(vector &res, TreeNode* node){
if(node==nullptr) return;
inorder(res, node->left);
res.push_back(node->val);
inorder(res, node->right);
}*/
//
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> sinorder;
TreeNode* p=root;
// p ，
while(p!=nullptr || !sinorder.empty()){
// p
//
if(p==nullptr){
//
p=sinorder.top();
sinorder.pop();
res.push_back(p->val);
//
p=p->right;
}
// p
else {
sinorder.push(p);
p=p->left;
}
}
return res;
}
};