leetcode刷题记录(2)
【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(mmp这题在头条面试的时候没有做出来,思路确实好难想啊,最后的reverse没有想到,欢声笑语打出GG,我还会回来的!!)
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
void nextPermutation(vector &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 &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 generateParenthesis(int n) {
vector 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);
}
};
推荐阅读
- 20170612时间和注意力开销记录
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 【剽悍读书营成长记录】2018年我收获了什么|【剽悍读书营成长记录】2018年我收获了什么 3357-小松
- 记录iOS生成分享图片的一些问题,根据UIView生成固定尺寸的分享图片
- 课后分享记录
- 二叉树路径节点关键值和等于目标值(LeetCode--112&LeetCode--113)
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器(Swift)
- 感赏15+投射
- LeetCode(03)Longest|LeetCode(03)Longest Substring Without Repeating Characters