有些题目不好分类就放到其他里面了。主要包含了树的构造和遍历、二维数组的一些内容。

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，解决办法是用边界来记录。

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;
}

Leetcode题目总结11-其他

2019-09-07
算法

Leetcode题目总结11-其他

1. 树的构造和遍历

144 二叉树的前序遍历

094 二叉树的中序遍历

145 二叉树的后序遍历

105 从前序与中序遍历构造二叉树

106 从中序与后序遍历构造二叉树

2. 二维数组

036 有效的数独

048 旋转图像

054 旋转矩阵

059 旋转矩阵 II

073 矩阵置零

3. 其他

56 合并区间

59 螺旋矩阵II

Leetcode题目总结11-其他

1. 树的构造和遍历

144 二叉树的前序遍历

094 二叉树的中序遍历

145 二叉树的后序遍历

105 从前序与中序遍历构造二叉树

106 从中序与后序遍历构造二叉树

2. 二维数组

036 有效的数独

048 旋转图像

054 旋转矩阵

059 旋转矩阵 II

073 矩阵置零

3. 其他

56 合并区间

59 螺旋矩阵II

感谢支持！