leetcode刷题记录

记录一下安全菜鸡学开发的过程

Posted by X1ng on May 18, 2021

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

1. 两数之和

执行用时: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;
    }
};