2020.11.09
100
Runtime: 4 ms, faster than 51.00% of C++ online submissions for Same Tree.
Memory Usage: 10.4 MB, less than 51.00% of C++ online submissions for Same Tree.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p != nullptr && q != nullptr){
if(p->val == q->val) {
if(isSameTree(p->left, q->left))
if(isSameTree(p->right, q->right))
return true;
else
return false;
else
return false;
}
else
return false;
}
else if(p == nullptr && q == nullptr)
return true;
else
return false;
}
};
101
Runtime: 4 ms, faster than 89.80% of C++ online submissions for Symmetric Tree.
Memory Usage: 16.8 MB, less than 81.25% of C++ online submissions for Symmetric Tree.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p != nullptr && q != nullptr){
if(p->val == q->val) {
if(isSameTree(p->left, q->right))
if(isSameTree(p->right, q->left))
return true;
else
return false;
else
return false;
}
else
return false;
}
else if(p == nullptr && q == nullptr)
return true;
else
return false;
}
bool isSymmetric(TreeNode* root) {
if(root != nullptr){
if(root->left != nullptr && root->right != nullptr){
TreeNode *p = root->left, *q = root->right;
if(root->left->val == root->right->val){
return isSameTree(p,q);
}
else
return false;
}
else if(root->left == nullptr && root->right == nullptr)
return true;
else
return false;
}
else
return true;
}
};
104
Runtime: 12 ms, faster than 66.30% of C++ online submissions for Maximum Depth of Binary Tree.
Memory Usage: 19.3 MB, less than 22.55% of C++ online submissions for Maximum Depth of Binary Tree.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int go(TreeNode *node, int &deepth, int &max){
if(node != nullptr){
deepth ++;
go(node->left, deepth, max);
go(node->right, deepth, max);
if(deepth > max)
max = deepth;
deepth --;
}
return 0;
}
int maxDepth(TreeNode* root) {
int deepth = 0;
int max = 0;
if(root != nullptr)
go(root, deepth, max);
return max;
}
};
107
Runtime: 4 ms, faster than 85.05% of C++ online submissions for Binary Tree Level Order Traversal II.
Memory Usage: 14 MB, less than 22.42% of C++ online submissions for Binary Tree Level Order Traversal II.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void go(TreeNode* node, vector<int> *a, int &deepth)
{
deepth ++;
if(node->left != nullptr && node->right != nullptr){
go(node->left, a, deepth);
go(node->right, a, deepth);
a[deepth].push_back(node->left->val);
a[deepth].push_back(node->right->val);
}
else if(node->left != nullptr && node->right == nullptr){
go(node->left, a, deepth);
a[deepth].push_back(node->left->val);
}
else if(node->left == nullptr && node->right != nullptr){
go(node->right, a, deepth);
a[deepth].push_back(node->right->val);
}
deepth --;
return;
}
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> out;
vector<int> a[751];
int deepth = 0;
if(root!=nullptr){
go(root, a, deepth);
a[deepth].push_back(root->val);
for(int i = 0; i<=750; i++){
if(!(a[750-i].empty()))
out.push_back(a[750-i]);
}
}
return out;
}
};
2021.04.08
面试题 17.12. BiNode
并没有想出来，学习评论区大佬的解法
执行用时：60 ms, 在所有 C++ 提交中击败了97.96%的用户
内存消耗：30.8 MB, 在所有 C++ 提交中击败了38.69%的用户
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* convertBiNode(TreeNode* root) {
if(root==nullptr) return nullptr;
convertBiNode(root->left);
pre->right = root;
root->left = nullptr;
pre = pre->right;
convertBiNode(root->right);
return m_root1->right;
}
private:
TreeNode* m_root1 = new TreeNode(-1);
TreeNode* pre = m_root1;
};
2021.04.09
执行用时：8 ms, 在所有 C++ 提交中击败了59.67%的用户
内存消耗：8.5 MB, 在所有 C++ 提交中击败了93.60%的用户
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
for(int i = 0; i<nums.size(); i++){
for(int j = i+1; j<nums.size(); j++){
if(nums[i]+nums[j]==target){
ret.push_back(i);
ret.push_back(j);
goto end;
}
}
}
end:
return ret;
}
};
2021.04.10
20. 有效的括号
执行用时：4 ms, 在所有 C++ 提交中击败了39.18%的用户
内存消耗：6.2 MB, 在所有 C++ 提交中击败了73.13%的用户
class Solution {
public:
char stack[10000];
bool isValid(string s) {
char *p = (char *)s.c_str();
int i = 0;
while(*p){
if(*p=='('){
if(*p+1==*(p+1))
p += 2;
else if(i<10000)
stack[i++] = *p++;
else
goto error;
}
else if(*p=='[' || *p=='{'){
if(*p+2==*(p+1))
p += 2;
else if(i<10000)
stack[i++] = *p++;
else
goto error;
}
else if(*p==')'){
if(i>0){
if(stack[--i]+1 == *p){
p += 1;
}
else
goto error;
}
else
goto error;
}
else if(*p==']' || *p=='}'){
if(i>0){
if(stack[--i]+2 == *p){
p += 1;
}
else
goto error;
}
else
goto error;
}
}
if(i==0)
return true;
error:
return false;
}
};
2021.04.11
21. 合并两个有序链表
执行用时：8 ms, 在所有 C++ 提交中击败了83.13%的用户
内存消耗：14.4 MB, 在所有 C++ 提交中击败了40.05%的用户
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* L = new ListNode(-1);
ListNode* l = L;
while(l1 && l2){
if(l1->val < l2->val){
l->next = l1;
l1 = l1->next;
}
else{
l->next = l2;
l2 = l2->next;
}
l = l->next;
}
if(l1!=nullptr)
l->next = l1;
else
l->next = l2;
return L->next;
}
};
26. 删除有序数组中的重复项
执行用时：328 ms, 在所有 C++ 提交中击败了5.20%的用户
内存消耗：13.4 MB, 在所有 C++ 提交中击败了15.79%的用户
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
vector<int>::iterator i,j,k;
for(i = nums.begin(); i!=nums.end(); i++){
int times=0;
for(j = i+1; j!= nums.end(); j++){
if(*i != *j)
break;
times++;
}
for(k = i+1; j!=nums.end(); k++,j++){
*k = *j;
}
for(int z = 0; z<times; z++)
nums.pop_back();
}
return nums.size();
}
};
写复杂了，学习评论区大佬的写法
int removeDuplicates(vector<int>& nums) {
if (nums.size() < 2) return nums.size();
int j = 0;
for (int i = 1; i < nums.size(); i++)
if (nums[j] != nums[i]) nums[++j] = nums[i];
return ++j;
}
2021.04.12
53. 最大子序和
只会超时的暴力枚举
class Solution {
public:
int max = 0x80000000;
int maxSubArray(vector<int>& nums) {
int sum;
for(int i = 1; i<=nums.size(); i++){
for(int j = 0; j+i<=nums.size(); j++){
sum = 0;
for(int k = 0; k<i; k++){
sum += nums[j+k];
}
max = sum > max ? sum : max;
}
}
return max;
}
};
学习动态规划解法
初始化：dp[0] = nums[0]
状态转移方程： dp[i] = max(dp[i - 1] + nums[i], nums[i])（dp[i]表示到当前位置 i 的最大子序列和）
class Solution {
public:
int max(int n1, int n2){
return n1 > n2 ? n1 : n2;
}
int maxSubArray(vector<int>& nums) {
if(nums.size()==1) return nums[0];
int currMaxSum = nums[0], MaxSum = nums[0];
for(int i = 1; i<nums.size(); i++){
currMaxSum = max(currMaxSum + nums[i], nums[i]);
MaxSum = max(currMaxSum, MaxSum);
}
return MaxSum;
}
};
2021.05.18
207. 课程表
BFS+拓扑排序写了个贼慢的方法
执行用时：84 ms, 在所有 C++ 提交中击败了8.13%的用户
内存消耗：12.5 MB, 在所有 C++ 提交中击败了97.93%的用户
class Solution {
public:
vector<int> a[5000];
int rd[10000];
queue<int> qu;
int num = 0;
int visited[10000];
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
for(int i = 0; i<prerequisites.size(); i++){
a[prerequisites[i][1]].push_back(prerequisites[i][0]);
rd[prerequisites[i][0]]++;
}
for(int i = 0; i<numCourses; i++){
if(rd[i]==0){
visited[i] = 1;
qu.push(i);
}
}
int temp;
while(!qu.empty()){
temp = qu.front();
num++;
for(int j = 0; j<a[temp].size(); j++){
rd[a[temp][j]]--;
}
qu.pop();
for(int i = 0; i<numCourses; i++){
if(!rd[i] && !visited[i]){
visited[i] = 1;
qu.push(i);
}
}
}
if(num<numCourses){
return false;
}
else{
return true;
}
}
};
210. 课程表 II
BFS+拓扑排序
执行用时：68 ms, 在所有 C++ 提交中击败了7.52%的用户
内存消耗：12.9 MB, 在所有 C++ 提交中击败了94.63%的用户
class Solution {
public:
queue<int> qu;
int rd[5000];
int num = 0;
vector<int> a[5000];
int visited[5000];
vector<int> out;
vector<int> findOrder(int numCourses, vector<vector<int> >& prerequisites) {
for(int i = 0; i<prerequisites.size(); i++){
a[prerequisites[i][1]].push_back(prerequisites[i][0]);
rd[prerequisites[i][0]]++;
}
for(int i = 0; i<numCourses; i++){
if(rd[i]==0){
visited[i] = 1;
qu.push(i);
}
}
int temp;
while(!qu.empty()){
temp = qu.front();
num++;
out.push_back(temp);
for(int i = 0; i<a[temp].size(); i++){
rd[a[temp][i]]--;
}
qu.pop();
for(int i = 0; i<numCourses; i++){
if(rd[i]==0 && visited[i]==0){
visited[i] = 1;
qu.push(i);
}
}
}
if(num<numCourses){
vector<int> nu;
return nu;
}
else{
return out;
}
}
};
329. 矩阵中的最长递增路径
DFS暴力搜索超时
class Solution {
public:
int visited[200][200];
int m, n;
int max = 0;
vector<vector<int> > map;
void dfs(int x, int y, int step) {
if(x+1<m && !visited[x+1][y] && map[x+1][y]>map[x][y]){
visited[x+1][y] = 1;
dfs(x+1, y, step+1);
visited[x+1][y] = 0;
}
if(x-1>=0 && !visited[x-1][y] && map[x-1][y]>map[x][y]){
visited[x-1][y] = 1;
dfs(x-1, y, step+1);
visited[x-1][y] = 0;
}
if(y+1<n && !visited[x][y+1] && map[x][y+1]>map[x][y]){
visited[x][y+1] = 1;
dfs(x, y+1, step+1);
visited[x][y+1] = 0;
}
if(y-1>=0 && !visited[x][y-1] && map[x][y-1]>map[x][y]){
visited[x][y-1] = 1;
dfs(x, y-1, step+1);
visited[x][y-1] = 0;
}
if(step>max){
max = step;
}
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
if(matrix.empty()){
return max;
}
m = matrix.size();
n = matrix[0].size();
map = matrix;
for(int i = 0; i<m; i++){
for(int j = 0; j<n; j++){
visited[i][j] = 1;
dfs(i, j, 1);
visited[i][j] = 0;
}
}
return max;
}
};
学习评论区大佬的写法，DFS+记忆化
dfs找到的最大值通过返回值传递，并用visited数组存储以该节点为起点的最长增长序列的长度
执行用时：40 ms, 在所有 C++ 提交中击败了97.91%的用户
内存消耗：15.7 MB, 在所有 C++ 提交中击败了43.30%的用户
class Solution {
public:
int visited[200][200];
int m, n;
vector<vector<int> > map;
int dfs(int x, int y) {
if(visited[x][y]>0){
return visited[x][y];
}
int l=0, r=0, u=0, d=0;
if(x+1<m && map[x+1][y]>map[x][y]){
r = dfs(x+1, y);
}
if(x-1>=0 && map[x-1][y]>map[x][y]){
l = dfs(x-1, y);
}
if(y+1<n && map[x][y+1]>map[x][y]){
d = dfs(x, y+1);
}
if(y-1>=0 && map[x][y-1]>map[x][y]){
u = dfs(x, y-1);
}
visited[x][y] = 1 + max(max(l, r), max(u, d));
return visited[x][y];
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
int maxNum = 0;
if(matrix.empty()){
return maxNum;
}
m = matrix.size();
n = matrix[0].size();
map = matrix;
for(int i = 0; i<m; i++){
for(int j = 0; j<n; j++){
maxNum = max(maxNum, dfs(i, j));
}
}
return maxNum;
}
};
45. 跳跃游戏 II
没想出来，学习贪心算法
每次循环遍历到当前位置到可达的最大位置，并更新下一次遍历的最大位置
执行用时：4 ms, 在所有 C++ 提交中击败了52.80%的用户
内存消耗：7.9 MB, 在所有 C++ 提交中击败了54.24%的用户
class Solution {
public:
int jump(vector<int>& nums) {
if(nums.size()==1) return 0;
int nextMaxPos = 0, curMaxPos = 0;
int ret = 0;
int cur = 0;
while(nextMaxPos<nums.size()-1){
curMaxPos = nextMaxPos;
for(int i = cur; i<=curMaxPos; i++){
nextMaxPos = max(nextMaxPos, nums[i]+i);
}
cout << curMaxPos<< " ";
cur = curMaxPos+1;
ret++;
}
return ret;
}
};
