leetcode刷题记录(2)

第一题

这个构造可以说是非常考验硬编码能力了。

public class Solution {
    public int[][] generateMatrix(int n) {
       int[][] a = new int[n][n];
       int len = n;
       int off = 0;
       int cnt = 1;
       int index = 0;
       while (len >= 1) {
           for (int j = off; j < len ; j++) {
               a[off][j] = cnt++;
           }//ok
           for (int i = off +1; i < len  ; i++) {
               a[i][len -1] = cnt++;
           }//ok
           for (int j = len - 2; j >= off; j--) {
               a[len  - 1][j] = cnt++;
           }
           for (int i = len  - 2; i >= 1 + off; i--) {
               a[i][off] = cnt++;
           }
           len-=1;
           off++;
       }
        return a;
    }
}

第二题

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int [][]ans = new int[m][n];
        ans[0][0] = grid[0][0];
        for(int i = 1;i < m;i++) {
            ans[i][0] = ans[i-1][0] + grid[i][0]; 
        }
        for(int i = 1;i < n; i++) {
            ans[0][i] = ans[0][i-1] + grid[0][i];
        }
        for(int i = 1;i < m; i++) {
            for(int j = 1; j < n; j++) {
                ans[i][j] = Math.min(ans[i-1][j]+grid[i][j],ans[i][j-1]+grid[i][j]);
            }
        }
        return ans[m-1][n-1];
    }
}

第三题

nextPermutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3→1,3,2
3,2,1→1,2,3
1,1,5→1,5,1

(mmp这题在头条面试的时候没有做出来，思路确实好难想啊，最后的reverse没有想到，欢声笑语打出GG，我还会回来的！！)

void nextPermutation(vector<int> &num) {
    if (num.size() < 2) return;
    int length = num.size();
    int i, j;
    for ( i = length-2; i >= 0; i--) {
        if (num[i] < num[i + 1]) break;
    }
    for (j = length - 1; j > i; j--) {
        if (num[i] < num[j]) break;
    }
    if (i >= 0) swap(num[i], num[j]);
    reverse(num.begin() + i + 1, num.end());
}

第四题

class Solution {
public:
    void dfs(int n,int left, int right,string s,vector<string> &ans) {
        if(left == n && right == n) {
            ans.push_back(s);
            return ;
        }
        if(left < n)
            dfs(n,left+1,right,s+'(',ans);
        if(right < n&&left>right) {
            dfs(n,left,right+1,s+')',ans);
        }
    }
    
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        dfs(n,0,0,"",ans);
        return ans;
    }
};

第五题

image.png

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetricTree(TreeNode* p, TreeNode* q) {
        if(p == NULL || q == NULL) return (p == q);
        return (p->val == q->val && isSymmetricTree(p->left, q->right) && isSymmetricTree(p->right, q->left));
    }
    bool isSymmetric(TreeNode *root) {
        if(root == nullptr) return true;
         return isSymmetricTree(root->left, root->right);
    }
};