leetcode51-100

0053

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        long long sum = -10000000000, maxsum = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (maxsum < 0) maxsum = nums[i];
            else maxsum += nums[i]; 
            sum = max(sum, maxsum);
        }
        return sum;
    }
};

0054

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        if(matrix.empty())return ans;
        int n = matrix.size(), m = matrix[0].size(), i = 0, j = 0;
        int endi = n - 1, endj = m - 1, si = 0, sj = 0;
        if(n==1)return matrix[0];
        if(m==1){
            while(i<=endi)ans.push_back(matrix[i++][j]);
            return ans;
        }
        while (1) {
            if (endi == si && endj == sj) { ans.push_back(matrix[si][sj]); return ans; }
            while (j != endj) {ans.push_back(matrix[i][j++]);if (ans.size() == n * m) return ans;}
            while (i != endi) {ans.push_back(matrix[i++][j]);if (ans.size() == n * m) return ans;}
            while (j != sj) {ans.push_back(matrix[i][j--]);if (ans.size() == n * m) return ans;}
            while (i != si) {ans.push_back(matrix[i--][j]);if (ans.size() == n * m) return ans;}
            if (ans.size() == n * m) return ans;
            endi--, endj--, si++, sj++;
            i = si, j = sj;
        }
    }
};

0055

int vis[100010];
class Solution {
public:
    bool bfs(vector<int>nums) {
        int n = nums.size();
        for(int i=0;i<=n;i++)vis[i]=0;
        queue<pair<int, int>>q;
        q.push(make_pair(nums[0], 0));
        vis[0] = 1;
        while (!q.empty()) {
            pair<int, int> cur = q.front();
            q.pop();
            for (int i = cur.second; i <= cur.first + cur.second; i++) {
                if (!vis[i] && i < n) {
                    vis[i] = 1;
                    q.push(make_pair(nums[i], i));
                    if (i == n - 1)return true;
                }
            }
        }
        return false;
    }
    bool canJump(vector<int>& nums) {
        if(nums.size()==1)return true;
        else return bfs(nums);
    }
};

0056

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>>ans;
        if (intervals.empty())return ans;
        else if (intervals.size() == 1)return intervals;
        sort(intervals.begin(), intervals.end(), [](vector<int>&a, vector<int>&b) {return a[0] < b[0]; });
        int i;
        for (i = 1; i < intervals.size(); i++) {
            vector<int>&pre = intervals[i - 1], &cur = intervals[i];
            if ((cur[0] >= pre[0] && cur[0] <= pre[1]) || (cur[1] <= pre[1])) { cur[0] = min(cur[0], pre[0]); cur[1] = max(cur[1], pre[1]); }
            else ans.push_back(pre);
        }
        --i;
        if (ans.empty())ans.push_back(intervals[0]);
        vector<int>last = intervals[i], &ans_last = ans[ans.size() - 1];
        if ((last[0] >= ans_last[0] && last[0] <= ans_last[1]) || (last[1] <= ans_last[1])) { ans_last[0] = min(last[0], ans_last[0]); ans_last[1] = max(last[1], ans_last[1]); }
        else ans.push_back(last);
        return ans;
    }
};

0058

class Solution {
public:
    int lengthOfLastWord(string s) {
        int cnt = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            if (s[i] != ' ') cnt++;
            else {
                if (!cnt)continue;
                else break;
            }
        }
        return cnt;
    }
};

0059

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>>ans;
        vector<int>tmp;
        if (!n)return ans;
        else if (n == 1) { tmp.push_back(1); ans.push_back(tmp); return ans; }
        for (int i = 0; i < n; i++)tmp.push_back(0);
        for (int i = 0; i < n; i++)ans.push_back(tmp);
        int num = 1, i = 0, j = 0, sti = 0, stj = 0, endi = n - 1, endj = n - 1;
        while (num < n*n) {
            while (i == sti && j != endj)ans[i][j++] = num++;
            while (i != endi && j == endj)ans[i++][j] = num++;
            while (i == endi && j != stj)ans[i][j--] = num++;
            while (i != sti && j == stj)ans[i--][j] = num++;
            endi--, endj--, sti++, stj++;
            i = sti, j = stj;
            if (endi == sti && endj == stj)ans[endi][endj] = num;
        }
        return ans;
    }
};

0060

class Solution {
public:
    string getPermutation(int n, int k) {
        char ans[10];
        int cnt = 0;
        for (int i = 1; i <= n; i++)ans[cnt++] = ('0' + i);
        ans[cnt] = '\0';
        while (--k)next_permutation(ans, ans + n);
        return ans;
    }
};

0061

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        int cnt = 1;
        ListNode*h = head;
        if(h == nullptr)return head;//这样例就nm离谱
        while(h->next)h = h->next, cnt++;
        h->next = head;
        k %= cnt;
        cnt -= k;
        h = head;
        if(!cnt)return head;
        while(cnt > 1){
            h = h->next;
            cnt--;
        }
        ListNode*new_h = h->next;
        h->next = nullptr;
        return new_h;
    }
};

0062

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[110][110];
        for (int i = 0; i < m; i++)dp[i][0] = 1;
        for (int i = 0; i < n; i++)dp[0][i] = 1;
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m - 1][n - 1];
    }
};

0063

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid.empty())return 0;
        long dp[110][110];
        int m=obstacleGrid.size(),n=obstacleGrid[0].size();
        memset(dp,0,sizeof(dp));
        if (obstacleGrid[m-1][n-1])return 0;
        dp[0][0]=!obstacleGrid[0][0]?1:0;
        for (int i = 1; i < m; i++)dp[i][0] = (dp[i - 1][0] && !obstacleGrid[i][0]) ? 1 : 0;
        for (int i = 1; i < n; i++)dp[0][i] = (dp[0][i - 1] && !obstacleGrid[0][i]) ? 1 : 0;
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                dp[i][j] = !obstacleGrid[i][j]?dp[i - 1][j] + dp[i][j - 1]:0;
        return dp[m - 1][n - 1];
    }
};

0064

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.empty())return 0;
        int dp[210][210], m = grid.size(), n = grid[0].size();
        memset(dp, 0x4f4f4f4f, sizeof(dp));
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++)dp[i][0] = dp[i - 1][0] + grid[i][0];
        for (int i = 1; i < n; i++)dp[0][i] = dp[0][i - 1] + grid[0][i];
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                dp[i][j] = min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
        return dp[m - 1][n - 1];
    }
};

0066

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        if (digits[digits.size() - 1] + 1 == 10) {
            digits[digits.size() - 1] = 0;
            for (int i = digits.size() - 2; i >= 0; i--) {
                digits[i]++;
                if (digits[i] == 10)digits[i] = 0;
                else break;
            }
            if (!digits[0])digits.insert(digits.begin(), 1);
        }
        else digits[digits.size() - 1]++;
        return digits;
    }
};

0067

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return str(bin(int(a,2)+int(b,2)))[2:]

0069

class Solution {
public:
    int mySqrt(int x) {
        return sqrt(x);
    }
};

0070

class Solution {
public:
    int climbStairs(int n) {
        long long a = 0, b = 1;
        while (n--) {
            long long tmp = b;
            b += a;
            a = tmp;
        }
        return b;
    }
};

0072

class Solution {
public:
    int dp[510][510];
    int minDistance(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        for (int i = 1; i <= n; i++) dp[i][0] = i;
        for (int i = 1; i <= m; i++) dp[0][i] = i;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (s1[i - 1] != s2[j - 1])
                    dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
                else dp[i][j] = dp[i - 1][j - 1];
        return dp[n][m];
    }
};

0073

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!matrix[i][j]) {
                int tmpi = i, tmpj = j;
                while (tmpi >= 0 && tmpi <= i)if (matrix[tmpi][j])matrix[tmpi--][j] = -1e4; else tmpi--;
                tmpi = i;
                while (tmpi < n && tmpi >= i)if (matrix[tmpi][j])matrix[tmpi++][j] = -1e4; else tmpi++;
                while (tmpj >= 0 && tmpj <= j)if (matrix[i][tmpj])matrix[i][tmpj--] = -1e4; else tmpj--;
                tmpj = j;
                while (tmpj < m && tmpj >= j)if (matrix[i][tmpj])matrix[i][tmpj++] = -1e4; else tmpj++;
                }
            }
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (matrix[i][j] == -1e4)matrix[i][j] = 0;
    }
};

0074

bool binary_s(vector<int>::iterator b,vector<int>::iterator e,int t){
    auto l = b, r = e;
    while (l != r) {
        auto m = l + (r - l) / 2;
        if (*m == t)return true;
        else if (*m > t)r = m;
        else l = m + 1;
    }
    return false;
}

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()||matrix[0].empty())return false;
        int n = matrix.size();
        for (int i = 0; i < n; i++) {
            if (matrix[i][0] < target) {
                if (binary_s(matrix[i].begin(), matrix[i].end(), target))return true;
                else continue;
            }
            else if(matrix[i][0]==target)return true;
            else return false;
        }
        return false;
    }
};

0075

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int col[3];
        for(auto i:nums)col[i]++;
        for(auto&i:nums){
            if(col[0]){i=0,col[0]--;}
            else if(col[1]){i=1;col[1]--;}
            else if(col[2]){i=2;col[2]--;}
        }
    }
};

0077

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        deque<vector<int>>pipe;
        vector<vector<int>>ans;
        for (int i = 1; i <= n; i++) {
            vector<int>t{ i };
            pipe.push_back(t);
        }
        while (1) {
            vector<int>tmp = pipe.front();
            if (tmp.size() == k)break;
            else {
                pipe.pop_front();
                int t = *(--tmp.end());
                for (int i = t + 1; i <= n; i++) {
                    vector<int>newtmp = tmp;
                    newtmp.push_back(i);
                    pipe.push_back(newtmp);
                }
            }
        }
        while (!pipe.empty()) {
            ans.push_back(pipe.front());
            pipe.pop_front();
        }
        return ans;
    }
};

0078

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>>ans=;
        vector<int>tmp;
        for(auto num:nums){
            int n=ans.size();
            for(int i = 0;i < n;i++){
                ans.push_back(ans[i]);
                ans.back().push_back(num);
            }
        }
        return ans;
    }
};

0079

class Solution {
public:

    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    set<pair<int, int>>st;

    bool dfs(vector<vector<char>>& board, string&word, int x, int y, int n, int m, char c, int pos) {
        if (c != word[pos])return false;
        else if (pos == word.size() - 1 && c == word[pos])return true;        
        else {
            for (int i = 0; i < 4; i++) {
                int tmpx = x + dx[i], tmpy = y + dy[i];
                if (tmpx >= 0 && tmpx < n&&tmpy >= 0 && tmpy < m&&st.find({ tmpx,tmpy }) == st.end()) {
                    st.insert({ tmpx,tmpy });
                    if (dfs(board, word, tmpx, tmpy, n, m, board[tmpx][tmpy], pos + 1))return true;
                    st.erase({ tmpx,tmpy });
                }
            }
            return false;
        }
    }

    bool exist(vector<vector<char>>& board, string word) {
        char s = word[0];
        int n = board.size(), m = board[0].size();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (board[i][j] == s) {
                    st.insert({ i,j });
                    if (dfs(board, word, i, j, n, m, s, 0))return true;
                    st.erase({ i, j });
                }
        return false;
    }
};

0080

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0;
        for (int num : nums)if (i < 2 || num > nums[i - 2])nums[i++] = num;
        return i;
    }
};

0081

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int maxv = -1, minv = 1000000, maxpos = -1, minpos = -1, tmppos = -1, n = nums.size();
        if(!n)return false;
        for (int i = 0; i < n; i++)if (nums[i] > maxv)maxpos = i, maxv = nums[i];
        tmppos = maxpos;
        while (nums[maxpos] == maxv) {
            maxpos = (maxpos + 1) % n;
            if (nums[maxpos] != maxv || maxpos == tmppos) { minpos = maxpos, minv = nums[maxpos]; break; }
        }
        int l = 0, r = n;
        while (l < r) {
            int m = (l + r) / 2;
            if (nums[(m + minpos) % n] == target)return true;
            else if (nums[(m + minpos) % n] < target)l = m + 1;
            else r = m;
        }
        return false;
    }
};

0082

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        int flag = 1;
        ListNode inf(0x3f3f3f3f);
        inf.next = head;
        ListNode tmp = inf;
        ListNode*cur = inf.next;
        ListNode*pre = &inf;
        while(cur&&flag){
            if(cur->next == nullptr){
                cur->next = (ListNode*)malloc(sizeof(ListNode));
                flag = 0;
            }
            if(cur->val != (cur->next)->val&&cur->val != pre->val&&cur->val != tmp.val){
                pre->next = cur;
                pre = pre->next;
                cur = cur->next;
            }
            else{
                tmp.val = cur->val;
                cur = cur->next;
            }
        }
        pre->next = nullptr;
        return inf.next;
    }
};

0083

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode*tmp = head;
        while (tmp) {
            while (tmp->next && tmp->val == tmp->next->val)
                tmp->next = tmp->next->next;
            tmp = tmp->next;
        }
        return head;
    }
};

0085

class Solution {
public:
    int l[210][210], r[210][210], up[210][210];
    int maximalRectangle(vector<vector<char>>& maze) {
        int n = maze.size(), ans = 0;
        if(!n)return 0;
        int m = maze[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < m; j++)
                if (maze[i][j] == '1' && maze[i][j - 1] == '1')l[i][j] = l[i][j - 1] + 1;
            for (int j = m - 1; j > 0; j--)
                if (maze[i][j - 1] == '1' && maze[i][j] == '1')r[i][j - 1] = r[i][j] + 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (maze[i][j] == '1') {
                    if (i >= 1 && maze[i - 1][j] == '1') {
                        l[i][j] = min(l[i][j], l[i - 1][j]), r[i][j] = min(r[i][j], r[i - 1][j]);
                        up[i][j] = up[i - 1][j] + 1;
                    }
                    else up[i][j] = 1;
                }
                ans = max(ans, (l[i][j] + r[i][j] + 1) * up[i][j]);
            }
        }
        return ans;
    }
};

0086

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        ListNode ans1(0);
        ListNode ans2(0);
        ListNode *p1 = &ans1, *p2 = &ans2;
        while (head) {
            if (head->val < x)p1 = p1->next = head;
            else p2 = p2->next = head;
            head = head->next;
        }
        p2->next = nullptr;
        p1->next = ans2.next;
        return ans1.next;
    }
};

0088

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int i = m, j = 0; i < m + n && j < n; i++, j++)nums1[i] = nums2[j];
        sort(nums1.begin(), nums1.end());
    }
};

0089

class Solution {
public:
    int num[10010], vis[10010];
    vector<int>ans;
    int cnt = 1;
    bool dfs(int *tmp,int n) {
        if (cnt == pow(2, n))return true;
        for (int i = 0; i < n; i++) {
            int tmp_ans = 0;
            tmp[i] = !tmp[i];
            for (int j = 0; j < n; j++)tmp_ans += tmp[j] * (pow(2, n - j - 1));
            if (!vis[tmp_ans]) {
                vis[tmp_ans] = 1, cnt++;
                if (dfs(tmp,n)) { ans.push_back(tmp_ans); return true; }
                vis[tmp_ans] = 0, cnt--;
            }
            tmp[i] = !tmp[i];
        }
        return false;
    }
    vector<int> grayCode(int n) {
        ans.push_back(0);
        vis[0] = 1;
        dfs(num,n);
        return ans;
    }
};

0090

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>>ans;
        set<vector<int>>tmp_ans;
        tmp_ans.insert(vector<int>());
        sort(nums.begin(), nums.end());
        for(auto &i : nums){
            vector<vector<int>>tmp;
            for(auto j : tmp_ans){
                j.push_back(i);
                tmp.push_back(j);
            }
            for(auto &j : tmp)tmp_ans.insert(j);
        }
        for(auto &i : tmp_ans)ans.push_back(i);
        return ans;
    }
};

0091

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        int dp[100000];
        memset(dp, 0, sizeof(dp));
        dp[0] = (s[0] != '0');
        dp[1] = (s[0] != '0' && s[1] != '0');
        for(int i = 2; i <= n; i++){
            if(s[i] != '0'){
                dp[i] = dp[i - 1];
                int tmp = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
                if(tmp <= 26 && s[i - 1] != '0')dp[i] += dp[i - 2];
                else if(tmp <= 26 && s[i - 1] =='0')dp[i] = dp[i - 2];
            }
            else dp[i] = 0;
        }
        return dp[n];
    }
};

0092

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
    ListNode *h = new ListNode(0);
    ListNode *pre = h;
    h -> next = head;
    for (int i = 0; i < m - 1; i++)pre = pre -> next;
    ListNode *cur = pre -> next;
    for (int i = 0; i < n - m; i++) {
        ListNode* tmp = pre -> next;
        pre -> next = cur -> next;
        cur -> next = cur -> next -> next;
        pre -> next -> next = tmp;
    }
    return h -> next;
    }
};

0093

class Solution {
public:
    int stoi(string &s) {
        if ((s[0] == '0'&&s.size() > 1) || s.size() > 4)return 256;
        int ans = 0, l = s.size() - 1;
        for (auto &i : s) {
            ans += (i - '0') * std::pow(10, l);
            l--;
        }
        return ans;
    }

    bool judge(string &s1, string &s2, string &s3, string &s4) {
        return stoi(s1) <= 255 && stoi(s2) <= 255 && stoi(s3) <= 255 &&
            stoi(s4) <= 255;
    }

    vector<string> restoreIpAddresses(string s) {
        int n = s.size();
        vector<string> ans;
        if (n < 4 || n > 12)return ans;
        vector<int> tmp(n - 1);
        for (int i = 0; i < 3; i++) *(tmp.rbegin() + i) = 1;
        do {
            int d1 = -1, d2 = -1, d3 = -1;
            for (int i = 0; i < tmp.size(); i++) {
                if (tmp[i]) {
                    if (d1 < 0)d1 = i + 1;
                    else if (d2 < 0)d2 = i + 1;
                    else if (d3 < 0)d3 = i + 1;
                }
            }
            string t1(s.begin(), s.begin() + d1);
            string t2(s.begin() + d1, s.begin() + d2);
            string t3(s.begin() + d2, s.begin() + d3);
            string t4(s.begin() + d3, s.end());
            if (judge(t1, t2, t3, t4))ans.push_back(string(t1 + "." + t2 + "." + t3 + "." + t4));
        } while (next_permutation(tmp.begin(), tmp.end()));
        return ans;
    }
};

0094

class Solution {
public:
    void inorder(vector<int>&ans, TreeNode *cur){
        if(cur->left)inorder(ans, cur->left);
        ans.push_back(cur->val);
        if(cur->right)inorder(ans, cur->right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>ans;
        if(!root)return ans;
        inorder(ans, root);
        return ans;
    }
};

0095

很难过，这题我目前不会。

0096

class Solution {
public:
    int numTrees(int n) {
        long long k = 1;
        for (int i = 1; i <= n; i++) k = k * (4 * i - 2) / (i + 1);
        return k;
    }
};

0098

class Solution {
public:
    
    bool isValidBST_tmp(TreeNode* cur, TreeNode* minN, TreeNode* maxN){
        if(!cur)return true;
        if(minN && cur->val <= minN->val || maxN && cur->val >= maxN->val)return false;
        return isValidBST_tmp(cur->left, minN, cur) && isValidBST_tmp(cur->right, cur, maxN);
    }
    
    bool isValidBST(TreeNode* root) {
        return isValidBST_tmp(root, nullptr, nullptr);
    }
};

0100

class Solution {
public:
    
    bool bfs(TreeNode*r1, TreeNode*r2){
        queue<TreeNode*>q1, q2;
        q1.push(r1), q2.push(r2);
        if(r1->val != r2->val)return false;
        while(!q1.empty() && !q2.empty()){
            TreeNode*cur1 = q1.front(); q1.pop();            
            TreeNode*cur2 = q2.front(); q2.pop();
            int lv1 = cur1->left ? cur1->left->val : -1;            
            int lv2 = cur2->left ? cur2->left->val : -1;
            int rv1 = cur1->right ? cur1->right->val : -1;
            int rv2 = cur2->right ? cur2->right->val : -1;
            if(lv1 != lv2 || rv1 != rv2)return false;
            if(cur1->left)q1.push(cur1->left);            
            if(cur1->right)q1.push(cur1->right);
            if(cur2->left)q2.push(cur2->left);            
            if(cur2->right)q2.push(cur2->right);
        }
        if(!q1.empty() || !q2.empty())return false;
        else return true;
    }
    
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q)return true;
        else if(!p || !q)return false;
        else return bfs(p, q);
    }
};