leetcode --day12 Surrounded Regions & Sum Root to Leaf Numbers & Longest Consecutive Sequence
1、
Surrounded Regions
Given a 2D board containing
A region is captured by flipping all
For example,
After running your function, the board should be:
分析:この問題は多くの時間を費やして、最後にやっとどのようにするかを理解して、すべてOの点の上下左右がXで囲まれた領域かどうかを判断することを考え始めて、これは明らかに間違っています;次に、2次元マトリクスを遍歴し、要素がOであれば、Oが囲まれた領域であるか否かを判断し、ここでの値をXに変更し、ここでの値を別のフラグ「D」に変更しなければ、解くたびに点の上下左右によって判断できるが、右下角がOの場合は無視される.後にアルゴリズムを改良し、上の点と左の点を先に判断するように変更し、そのうちの1つが「D」であれば必ず囲まれず、右と下の点を判断し、「O」であれば右と下の点の和を解くように再帰し、タイムアウトした.
最後に、2次元マトリクスを巡回し、「O」点に遭遇するたびに、この点と同じ連通領域にある「O」を見つけ、それを「P」に置き換え、この連通領域に境界上の点があるかどうかを判断し、ある場合はすべての点を「D」に変換し、ない場合はすべての点を「X」に変換する方法を検索した.遍歴が終わったら、すべての'D'を'O'に変換します.
Acceptedコードは次のとおりです.
2、Sum Root to Leaf Numbers
Given a binary tree containing digits from
An example is the root-to-leaf path
Find the total sum of all root-to-leaf numbers.
For example,
The root-to-leaf path
Return the sum = 12 + 13 =
分析:この問題は簡単で、簡単な再帰です.
コードは次のとおりです.
3、Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example, Given
Your algorithm should run in O(n) complexity.
分析:まず複雑度を考慮しない時、連続数の長さを要求して、まず配列を並べ替えて、最初から、シーケンスの長さを見て、この時multisetを採用して実現することができます;しかし、O(n)の複雑さを見ると、setは赤黒ツリーで実現され、複雑度はO(nlogn)であるが、ハッシュテーブル構造はソートされていない.1つの値に遍歴する場合、この値より小さい値とそれより大きい値が存在するかどうかを判断する必要があり、存在しない場合は継続的に遍歴し、前の値を保存する必要があり、複雑でhash_mapはC++標準ライブラリになく、ずっと'hash_を表示しています.multimap' was not declared in this scope
そこでmultisetを採用し,結果はAcceptedであるが,内部構造から言えば時間複雑度はO(nlogn)である.
コードは次のとおりです.
Surrounded Regions
Given a 2D board containing
'X' and 'O' , capture all regions surrounded by 'X' . A region is captured by flipping all
'O' s into 'X' s in that surrounded region. For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X分析:この問題は多くの時間を費やして、最後にやっとどのようにするかを理解して、すべてOの点の上下左右がXで囲まれた領域かどうかを判断することを考え始めて、これは明らかに間違っています;次に、2次元マトリクスを遍歴し、要素がOであれば、Oが囲まれた領域であるか否かを判断し、ここでの値をXに変更し、ここでの値を別のフラグ「D」に変更しなければ、解くたびに点の上下左右によって判断できるが、右下角がOの場合は無視される.後にアルゴリズムを改良し、上の点と左の点を先に判断するように変更し、そのうちの1つが「D」であれば必ず囲まれず、右と下の点を判断し、「O」であれば右と下の点の和を解くように再帰し、タイムアウトした.
最後に、2次元マトリクスを巡回し、「O」点に遭遇するたびに、この点と同じ連通領域にある「O」を見つけ、それを「P」に置き換え、この連通領域に境界上の点があるかどうかを判断し、ある場合はすべての点を「D」に変換し、ない場合はすべての点を「X」に変換する方法を検索した.遍歴が終わったら、すべての'D'を'O'に変換します.
Acceptedコードは次のとおりです.
class Solution {
public:
void solve(vector<vector<char>> &board) {
int rows = board.size();
if(rows <= 2){
return;
}
int cols = board[0].size();
if(cols <= 2){
return;
}
for(int i=0; i<rows; ++i){
for(int j=0; j<cols; ++j){
if(board[i][j] == 'O'){
bool isSurr = isSurround(board,i,j);
replaceSurround(board,isSurr);
}
}
}
// D O
for(int i=0; i<rows; ++i){
for(int j=0; j<cols; ++j){
if(board[i][j] == 'D'){
board[i][j] = 'O';
}
}
}
}
// (m,n) ， (m,n) 'P'
bool isSurround(vector<vector<char>> &board,int m,int n){
bool hasPath = false;
board[m][n] = 'P';
int rows = board.size();
int cols = board[0].size();
for(int i=0; i<rows; ++i){
for(int j=0; j<cols; ++j){
if(board[i][j] == 'P'){
if(i == 0){
hasPath = true;
//return false;
}else{
if(board[i-1][j] == 'O'){
board[i-1][j] = 'P';
i -= 2; // i=i-2, (i-1,j) , (i-2,j)
break; // break, i ， j
}
}
if(j == 0){
hasPath = true;
//return false;
}else{
if(board[i][j-1] == 'O'){
board[i][j-1] = 'P';
j -= 2;
continue;
}
}
if(i == rows-1){
hasPath = true;
//return false;
}else{
if(board[i+1][j] == 'O'){
board[i+1][j] = 'P';
}
}
if(j == cols-1){
hasPath = true;
//return false;
}else{
if(board[i][j+1] == 'O'){
board[i][j+1] = 'P';
}
}
}
}
}
return hasPath ? false:true;
}
// P ， X, D
void replaceSurround(vector<vector<char>> &board,bool isSurrounded){
for(int i=0; i<board.size(); ++i){
for(int j=0; j<board[i].size(); ++j){
if(board[i][j] == 'P'){
if(isSurrounded){
board[i][j] = 'X';
}else{
board[i][j] = 'D';
}
}
}
}
}
};2、Sum Root to Leaf Numbers
Given a binary tree containing digits from
0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path
1->2->3 which represents the number 123 . Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path
1->2 represents the number 12 . The root-to-leaf path 1->3 represents the number 13 . Return the sum = 12 + 13 =
25 . 分析:この問題は簡単で、簡単な再帰です.
コードは次のとおりです.
class Solution {
public:
int sumNumbers(TreeNode *root) {
int sum = 0;
allSum = 0;;
path(root,sum);
return allSum;
}
void path(TreeNode* root,int sum){
if(root == NULL){
return;
}else{
sum = sum*10 + root->val;
if(!root->left && !root->right){
allSum += sum;
return;
}
if(root->left){
path(root->left,sum);
}
if(root->right){
path(root->right,sum);
}
}
}
int allSum;
};
3、Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example, Given
[100, 4, 200, 1, 3, 2] , The longest consecutive elements sequence is [1, 2, 3, 4] . Return its length: 4 . Your algorithm should run in O(n) complexity.
分析:まず複雑度を考慮しない時、連続数の長さを要求して、まず配列を並べ替えて、最初から、シーケンスの長さを見て、この時multisetを採用して実現することができます;しかし、O(n)の複雑さを見ると、setは赤黒ツリーで実現され、複雑度はO(nlogn)であるが、ハッシュテーブル構造はソートされていない.1つの値に遍歴する場合、この値より小さい値とそれより大きい値が存在するかどうかを判断する必要があり、存在しない場合は継続的に遍歴し、前の値を保存する必要があり、複雑でhash_mapはC++標準ライブラリになく、ずっと'hash_を表示しています.multimap' was not declared in this scope
そこでmultisetを採用し,結果はAcceptedであるが,内部構造から言えば時間複雑度はO(nlogn)である.
コードは次のとおりです.
class Solution {
public:
int longestConsecutive(vector<int> &num) {
if(num.size() <= 1){
return num.size();
}
multiset<int> numSet;
for(int i=0; i<num.size(); ++i){
numSet.insert(num[i]);
}
int maxLen = 1;
for(multiset<int>::iterator iter=numSet.begin(); iter!=numSet.end(); ){
int tempLen = 1;
while(iter!=numSet.end()){
int nextVal = *iter , curVal = *iter;
while(curVal == nextVal){
curVal = *iter;
if(++iter == numSet.end()){
if(tempLen > maxLen){
maxLen = tempLen;
}
return maxLen;
}
nextVal = *iter;
}
--iter;
curVal = *iter;
++iter;
if(curVal+1 == nextVal){
++tempLen;
}else{
break;
}
}
if(tempLen > maxLen){
maxLen = tempLen;
}
}
return maxLen;
}
};