第一题
这个构造可以说是非常考验硬编码能力了
- 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,31,3,2
- 3,2,11,2,3
- 1,1,51,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);
- }
- };
来源: http://www.jianshu.com/p/3e1f52d9f646