有些题目不好分类就放到其他里面了。主要包含了树的构造和遍历、二维数组的一些内容。
1. 树的构造和遍历
144 二叉树的前序遍历
非递归:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
vector<int> data;
while (root||!stk.empty())
{
if (root)
{
data.push_back(root->val);
stk.push(root);
root = root->left;
}
else
{
root = stk.top();
//中序就把push_back写在这里
stk.pop();
root = root->right;
}
}
return data;
}
递归:
注意递归前要先判断是否存在。
vector<int> preorderTraversal(TreeNode* root) {
vector<int> data;
if(!root) return data;
recursive(data,root);
return data;
}
void recursive(vector<int>& data,TreeNode* root)
{
data.push_back(root->val);
if(root->left) recursive(data,root->left);
if(root->right) recursive(data,root->right);
}
094 二叉树的中序遍历
vector<int> inorderTraversal(TreeNode* root) {
vector<int> data;
stack<TreeNode*> stk;
if(!root) return data;
while(root||!stk.empty())
{
if(root)
{
stk.push(root);
root=root->left;
}
else
{
root=stk.top();
data.push_back(root->val);
stk.pop();
root=root->right;
}
}
return data;
}
145 二叉树的后序遍历
因为前面两道题前序和中序分别占据了if-else的其中一个,所以后序没得用了。换种思路:前序遍历是:中-左-右,而后序是左-右-中,它是中-右-左的逆过程,
在前序遍历中我们将data.push_back()
塞到了if(root)
中,在这里我们只需要将容器栈放到这里即可。
vector<int> postorderTraversal(TreeNode* root) {
vector<int> data;
if(!root) return data;
stack<TreeNode*> stk;
while(root||!stk.empty()){
if(root){
data.push_back(root->val);
stk.push(root);
root=root->right;
}else{
root=stk.top();
stk.pop();
root=root->left;
}
}
reverse(data.begin(),data.end());
return data;
}
105 从前序与中序遍历构造二叉树
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
3
/ \
9 20
/ \
15 7
解答:
前序的第一个一定是root,假设位置为prei,找到其在中序的位置midi。此时中序左边是左子树所有的部分,右边是右子树所有的部分。那么左子节点就是prei+1,右子节点计算方法是:跳过所有左子树,下一个就是右子节点,prei+(midi-inorder_start)+1
TreeNode* generate(vector<int>& preorder, vector<int>& inorder,
int inorder_start, int inorder_end,
int pre_root_index)
{
if (inorder_start == inorder_end)
return new TreeNode(preorder[pre_root_index]);
if (inorder_start > inorder_end)
return NULL; //叶子节点
int value = preorder[pre_root_index];
TreeNode* root = new TreeNode(value);
int i = 0;
for (; i < inorder.size(); i++)
{
if (inorder[i] == value)
break;
}
root->left = generate(preorder, inorder,
inorder_start, i - 1,
pre_root_index + 1);
root->right = generate(preorder, inorder,
i + 1, inorder_end,
pre_root_index + (i- inorder_start+1));
return root;
}
106 从中序与后序遍历构造二叉树
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
3
/ \
9 20
/ \
15 7
解答:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return fun(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
}
TreeNode* fun(vector<int>& preorder, vector<int>& inorder,
int pre_start, int pre_end, int in_start, int in_end) {
if (pre_start > pre_end) {
return NULL;
}
int pre_first_result = preorder[pre_start];
int root_position = in_start;
for (; root_position < in_end; root_position++) {
if (inorder[root_position] == pre_first_result) {
break;
}
}
TreeNode* node = new TreeNode(pre_first_result);
int left_length = root_position - in_start;
int right_length = in_end - root_position;
node->left = fun(preorder, inorder, pre_start + 1, pre_start + left_length, in_start, root_position - 1);
node->right = fun(preorder, inorder, pre_end - right_length + 1, pre_end, root_position + 1, in_end);
return node;
}
2. 二维数组
036 有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。
- 数字
1-9
在每一行只能出现一次。 - 数字
1-9
在每一列只能出现一次。 - 数字
1-9
在每一个以粗实线分隔的3x3
宫内只能出现一次。
解答:
bool isValidSudoku(vector<vector<char>>& board) {
vector<set<int>> rows(9);
vector<set<int>> cols(9);
vector<set<int>> cell(9);
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
if(board[i][j]=='.') continue;
int val = board[i][j]-'0';
if(!rows[i].count(val)) rows[i].insert(val);
else return false;
if(!cols[j].count(val)) cols[j].insert(val);
else return false;
int index = cell_index(i,j);
if(!cell[index].count(val)) cell[index].insert(val);
else return false;
}
return true;
}
int cell_index(int i,int j)
{
return i/3+3*(j/3);
}
048 旋转图像
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵,使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
解答:
先沿副对角线交换,再沿中间水平线交换
void rotate(vector<vector<int>>& matrix) {
if (matrix.size() == 0) return;
int n = matrix.size();
//沿副对角线交换
for(int i=0;i<n;i++)
for (int j = 0; j < n-i; j++)
{
int tmp = matrix[i][j];
//n-1-j表示间隔距离,调换一下ij的间隔距离即可达到副对角线
matrix[i][j] = matrix[n - 1 - j][n - 1 - i];
matrix[n - 1 - j][n - 1 - i]=tmp;
}
for(int i=0;i<n/2;i++)
for (int j = 0; j < n; j++)
{
int tmp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - i][j];
matrix[n - 1 - i][j] = tmp;
}
}
054 旋转矩阵
题目:
给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。
示例:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
解答:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
if (matrix.size() == 0) return res;
int len1 = matrix.size();
int len2 = matrix[0].size();
int right = matrix[0].size() - 1;
int left = 0;
int up = 1;
int down = matrix.size() - 1;
int row = 0, col = 0, k = 0;
int dir[4][4] = { {1,0,-1,0} ,{0,1,0,-1} };//列行
for (int i = 0; i < len1 * len2; i++)
{
res.push_back(matrix[row][col]);
row += dir[1][k % 4];
col += dir[0][k%4];
switch (k % 4)
{
case 0:
if (col > right)
{
col = right;
row++;
right--;
k++;//转向
}
break;
case 1:
if (row > down)
{
row = down;
col--;
down--;
k++;
}
break;
case 2:
if (col < left)
{
col = left;
row--;
left++;
k++;
}
break;
case 3:
if (row < up)
{
row = up;
col++;
up++;
k++;
}
break;
}
}
return res;
}
059 旋转矩阵 II
题目:
给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
解答:
vector<vector<int>> generateMatrix(int n){
vector<vector<int>> res(n, vector<int>(n, 0));
if (n== 0) return res;
int len1 = n;
int len2 = n;
int right = n - 1;
int left = 0;
int up = 1;
int down = n - 1;
int row = 0, col = 0, k = 0;
int dir[4][4] = { {1,0,-1,0} ,{0,1,0,-1} };//列行
for (int i = 0; i < len1 * len2; i++)
{
res[row][col] = i + 1;
row += dir[1][k % 4];
col += dir[0][k % 4];
switch (k % 4)
{
case 0:
if (col > right)
{
col = right;
row++;
right--;
k++;//转向
}
break;
case 1:
if (row > down)
{
row = down;
col--;
down--;
k++;
}
break;
case 2:
if (col < left)
{
col = left;
row--;
left++;
k++;
}
break;
case 3:
if (row < up)
{
row = up;
col++;
up++;
k++;
}
break;
}
}
return res;
}
073 矩阵置零
题目:
给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。
输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
解答:
为了能使空间为$O(1)$,我们就不能令设参数来记录哪些行列应该为0,解决办法是用边界来记录。
![](https://bucket-1259555870.cos.ap-chengdu.myqcloud.com/20191224125238.png)
void setZeroes(vector<vector<int>>& matrix) {
bool row = false, col = false;
int m = matrix.size(), n = matrix[0].size();
for (int i = 0; i < m; ++i) { if (matrix[i][0] == 0) col = true; }
for (int i = 0; i < n; ++i) { if (matrix[0][i] == 0) row = true; }
for (int i = 1; i < m; ++i)
for (int j = 1; j < n; ++j)
{
if (matrix[i][j] == 0)
matrix[i][0] = 0, matrix[0][j] = 0;
}
for (int i = 1; i < m; ++i)
for (int j = 1; j < n; ++j)
{
if (matrix[i][0] == 0 || matrix[0][j] == 0)
matrix[i][j] = 0;
}
if (col)
{
for (int i = 0; i < m; ++i) matrix[i][0] = 0;
}
if (row)
{
for (int i = 0; i < n; ++i) matrix[0][i] = 0;
}
}
3. 其他
56 合并区间
给出一个区间的集合,请合并所有重叠的区间。
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
解答:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> res;
if(intervals.size()==0||intervals[0].size()==0)
return res;
auto lambda = [](vector<int>& vec1,vector<int>& vec2) {
return vec1[0] < vec2[0];
};
sort(intervals.begin(), intervals.end(), lambda);
res.push_back(intervals[0]);
for(int i=1;i<intervals.size();++i){
if(res.back()[1]>=intervals[i][0]){
res.back()[1]=max(res.back()[1],intervals[i][1]);
}else{
res.push_back(intervals[i]);
}
}
return res;
}
59 螺旋矩阵II
给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。
输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
解答:
vector<vector<int>> generateMatrix(int n) {
if(n==0) return {{}};
vector<vector<int> > res(n,vector<int>(n,0));
int down=0,up=n-1,left=0,right=n-1;
int itm=1;
while(left<=right && down<=up){
for(int i=left;i<=right;i++) res[down][i]=itm++;
for(int i=down+1;i<=up;i++) res[i][right]=itm++;
for(int i=right-1;i>=left;i--) res[up][i]=itm++;
for(int i=up-1;i>=down+1;i--) res[i][left]=itm++;
down++;
up--;
left++;
right--;
}
return res;
}