【LeetCode】2020-04 每日一题

8. 字符串转换整数 (atoi)（中等）

【分类】：模拟、正则表达式

【题解】：

解法1：直接模拟，但是在判断INT_MAX和INT_MIN上需要注意，因为直接判断会超出范围，所以可以将式子转换一下，本来是num * 10 + str[i] - '0' > MAX，可以转换为(MAX - (stri[i] - '0')) / 10 < num。

解法2：不得不说正则表达式真的牛逼啊啊啊啊！！！

'^[+-]?d+', s.lstrip()

 让我们来分析一下这个关键部分！

^x：表示匹配以字符串x为开头的字符串

[+-]?：匹配+或-或者什么也没有（？表示将前面的字符匹配0或1次）

d：表示数字

+：表示前面的字符一次或无数次

s.lstrip(a)：将字符串前面连续的a字符去除，默认为‘ ’

肯定有人要问最前面的*是什么意思了！！这个是解包，可以将findall返回的列表组成一个字符串。

【代码】：

C++（解法1）：

class Solution {
public:
    int myAtoi(string str) {
        int i = 0, f = 0;
        for (i = 0; i < str.size() && str[i] == ' '; i++);
        if (str[i] == '-')f = -1, i++;
        else if (str[i] == '+') f = 1, i++;
        else if(isdigit(str[i]))f = 1;
        if (f == 0)return 0;
        int num = 0, f2 = 0;
        int MAX = 2147483647, MIN = -2147483648;
        for (; i < str.size() && isdigit(str[i]); i++)
        {
            if (num > ((MAX - (str[i] - '0')) / 10 ))
            {
                if (f == 1)return MAX;
                else return MIN;
            }
            num = num * 10 + (str[i] - '0');
        }
        if (f == 1)return num;
        else return -num;
    }
};

Python3（解法2）：

class Solution:
    def myAtoi(self, s: str) -> int:
        return max(min(int(*re.findall('^[+-]?d+', s.lstrip())), 2**31 - 1), -2**31)

11. 盛最多水的容器（中等）

【分类】：双指针

【题解】：将指针l、r分别位于两端，比较两端元素大小，假如说左端大，那么易得以右端为端点已经取到了最大值（因为元素间距离不能再大了），我们接下来可以看看以左端为端点还能不能更大，所以要把右指针往左移，此时如果右端大，那么以左端为端点已经取得了最大值，依次类推。

【代码】：

C++：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0, l = 0, r = height.size() - 1;
        while(l <= r)
        {
            ans = max(ans, min(height[l], height[r]) * (r - l));
            if (height[l] > height[r])r--;
            else l++;
        }
        return ans;
    }
};

Python3：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans = 0
        l = 0
        r = len(height) - 1
        while l <= r:
            ans = max(ans, min(height[l], height[r]) * (r - l))
            if (height[l] > height[r]): r -= 1
            else: l += 1
        return ans

22. 括号生成（中等）

【分类】：dfs、动态规划

【题解】：

解法1：回溯法，l为剩余左括号数量，r为剩余右括号数量，先考虑递归出口，也就是l=0&r=0的时候return（没有剩余括号啦）。然后只要l还有剩余我们就可以一直递归下去，那么右括号什么情况可以递归呢，必须当r > l时才可以，比如n=2我现在是()，后面肯定不能再加)啦。

解法2：考虑n个括号的情况可以由n-1个括号的情况得到，假设第n个括号的左括号在最左，那么n个括号的情况就是这样了()a，(a)，a就是前n-1个括号的情况。所以也可以统一为(p)q，p = [0, n - 1]，q = n - 1 - p即可涵盖上述情况。

【代码】：

C++（解法1）：

class Solution {
public:
    vector<string>ans;
    vector<string> generateParenthesis(int n) {
        dfs("", n, n);
        return ans;
    }
    void dfs(string s, int l, int r)
    {
        if (l == 0 && r == 0)
        {
            ans.push_back(s);
            return;
        }
        if (l > 0)
            dfs(s + "(", l - 1, r);
        if (r > l)
            dfs(s + ")", l, r - 1);
        return;
    }
};

Python3（解法2）：

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        dp = []
        dp.append([""])
        for i in range(1, n + 1):
            cur = []
            for j in range(i):
                l = dp[j]
                r = dp[i - 1 -j]
                for ll in l:
                    for rr in r:
                        s = "(" + ll + ")" + rr
                        cur.append(s)
            dp.append(cur)
        return dp[n]

55. 跳跃游戏（中等）

【分类】：贪心

【题解】：

解法1：因为每个位置除0外最小能跳的距离为1，实际上只要考虑每个0的位置能否跳过即可，所以每当遍历到0的时候，再往前遍历查找是否有一个位置能够跳过0，只要能跳过所有的0位置，就一定能跳到终点。

解法2：维护一个当前可以跳到的最大距离值。

【代码】：

C++（解法1）：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        for (int i = 0; i < nums.size() - 1; i++)
        {
            if (nums[i] == 0)
            {
                int f = 0;
                int t = i + 1, j = i - 1;
                while(j >= 0)
                {
                    if (nums[j] >= t - j)
                    {
                        f = 1;
                        break;
                    }
                    j--;
                }
                if (!f)return false;
            }
        }   
        return true;
    }
};

Python3（解法2）：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        rightmost = 0
        for i in range(len(nums)):
            if rightmost >= i:
                rightmost = max(rightmost, i + nums[i])
            else:
                return False
        return True

56. 合并区间（中等）

【分类】：贪心

【题解】：每个区间按照左端点进行排序，然后遍历所有区间，当下一个区间的左端点大于当前区间的右端点说明这段区间不重合，反之说明重合，所以更新重合区间的右端点。

【代码】：

C++：

struct Node{
    int x, y;
};
class Solution {
public:
    static bool cmp(Node a, Node b)
    {
        return a.x != b.x ? a.x < b.x : a.y < b.y; 
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<Node>v;
        vector<vector<int> > ans;
        for (int i = 0; i < intervals.size(); i++)
            v.push_back({intervals[i][0], intervals[i][1]});    
        if (v.size() == 0)return ans;
        sort(v.begin(), v.end(), cmp);
        int l = v[0].x, r = v[0].y;
        for (int i = 1; i < v.size(); i++)
        {
            if (v[i].x <= r) r = max(v[i].y, r);
            else
            {
                vector<int>t;
                t.push_back(l);
                t.push_back(r);
                ans.push_back(t);
                l = v[i].x;
                r = v[i].y;
            }
        }
        vector<int>t;
        t.push_back(l);
        t.push_back(r);
        ans.push_back(t);
        return ans;
    }
};

Python3：

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 0:
            return []
        res = []
        intervals.sort(key=lambda x: x[0])  
        for inter in intervals:
            if len(res) == 0 or res[-1][1] < inter[0]:  
                res.append(inter)
            else:  
                res[-1][1] = max(res[-1][1], inter[1])
        return res

151. 翻转字符串里的单词（中等）

【分类】：字符串

【题解】：这种字符串的题用Python简直不要方便太多！！C++的话根据题意老老实实模拟就好啦。

【代码】：

C++：

class Solution {
public:
    string reverseWords(string s) {
        vector<string>v;
        string ss = "";
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] != ' ')ss = ss + s[i];
            else
            {
                if (ss != "")
                {
                    v.push_back(ss);
                    ss = "";
                }
            }
        }
        if (ss != "")v.push_back(ss);
        if (v.size() == 0)return "";
        ss = "";
        reverse(v.begin(), v.end());
        for (int i = 0; i < v.size() - 1; i++)
            ss = ss + v[i] + " ";
        ss = ss + v[v.size() - 1];
        return ss;
    }
};

Python3：

class Solution:
    def reverseWords(self, s: str) -> str:
        ls = s.split(' ') # 按空格分隔单词
        ls = list(filter(None, ls)) # 去除列表中的空字符串
        ls.reverse() # 将列表倒序
        ans = " ".join(ls)
        return ans

199. 二叉树的右视图（中等）

【分类】：dfs、bfs、二叉树

【题解】：

解法1：bfs，维护一个数组d，d[i]表示深度为i的节点值，因为bfs是从左往右层序遍历，所以遍历过程中每个深度最后保存的值就是右视图看过去的值。

解法2：dfs，先遍历右子树，更新在每一层最先出现的元素即可。

【代码】：

C++（解法1）：

/**
 * 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:
    int ans[10005];
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*>q;
        queue<int>d;
        vector<int>v;
        if (root == NULL)return v;
        q.push(root);
        d.push(0);
        int maxdepth = 0;
        while(!q.empty())
        {
            TreeNode* t = q.front();
            q.pop();
            int dd = d.front();
            d.pop();
            ans[dd] = t->val;
            maxdepth = max(maxdepth, dd);
            if (t->left != NULL)
            {
                q.push(t->left);
                d.push(dd + 1);
            }
            if (t->right != NULL)
            {
                q.push(t->right);
                d.push(dd + 1);
            }
        }
        for(int i = 0; i <= maxdepth; i++)
            v.push_back(ans[i]);
        return v;
    }
};

Python3（解法2）：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def dfs(self, root, depth):
        if root == None: return
        if depth > len(self.ans):
            self.ans.append(root.val)
        self.dfs(root.right, depth + 1)
        self.dfs(root.left, depth + 1)
    def rightSideView(self, root: TreeNode) -> List[int]:
        self.ans = [] 
        self.dfs(root, 1)
        return self.ans

200. 岛屿数量（中等）

【分类】：dfs、bfs

【题解】：算是比较基础的搜索题吧，只写了dfs。一定要看清楚题目是字符啊！！我一直以为是数字，被坑了好久。

【代码】：

C++：

class Solution {
public:
    int dirx[4] = {0, 0, 1, -1};
    int diry[4] = {1, -1, 0, 0};
    void dfs(vector<vector<char>>& grid, int x, int y, int n, int m)
    {
        if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '0')
            return;
        grid[x][y] = '0';
        for(int i = 0; i < 4; i++)
            dfs(grid, x + dirx[i], y + diry[i], n, m);
        return;
    }
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size();
        if (n == 0)return 0;
        int m = grid[0].size();
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (grid[i][j] == '1')
                {
                    ans++;
                    dfs(grid, i, j, n, m);
                }
            }
        }
        return ans;
    }
};

Python3：

class Solution:
    def __init__(self):
        self.dire = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    def dfs(self, grid, x, y, n, m):
        if x < 0 or x >= n or y < 0 or y >= m or grid[x][y] == '0':
            return
        grid[x][y] = '0'
        for d in self.dire:
            self.dfs(grid, x + d[0], y + d[1], n, m)
    def numIslands(self, grid: List[List[str]]) -> int:
        n = len(grid)
        if n == 0: return 0
        m = len(grid[0])
        ans = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '1':
                    ans += 1
                    self.dfs(grid, i, j, n, m)
        return ans;

289. 生命游戏（中等）

【分类】：模拟、位运算

【题解】：

解法1：直接模拟，因为要求必须同时进行，所以只要将更新后的状态赋值给另一个数组，等更新完后再赋值回去就可以啦。

解法2：位运算。这个操作还是挺有意思的，反正我想不出来。现在我们用二进制表示每个格子细胞的状态（低位为之前的状态，高位为后来的状态）：

（0）00：表示刚开始死的，后来还是死的

（1）01：表示刚开始活的，后来死了

（2）10：表示刚开始死的，后来活了

（3）11：表示刚开始活的，后来还是活的

然后分析一下条件可以发现：

1、当细胞是活的，周围有2或3个活细胞时可以活，对应上面的第（3）种情况

2、当细胞是死的，周围有3个活细胞时可以活，对应上面的第（2）种情况

所以每当满足以上两个条件的时候，如果是活细胞就记为3，死细胞就记为2。那么怎样计数呢？由于之前的状态在低位，所以只要每个状态&1就是本身的状态。

由于后来的状态在高位，那么最后的答案就是所有状态右移一位啦。

【代码】：

C++：

class Solution {
public:
    int t[505][505];
    int dirx[8] = {0, 0, 1, 1, 1, -1, -1, -1};
    int diry[8] = {1, -1, 0, 1, -1, 0, 1, -1};
    void gameOfLife(vector<vector<int>>& board) {
        int n = board.size();
        if (n == 0)return;
        int m = board[0].size();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                int num1 = 0;
                for(int ii = 0; ii < 8; ii++)
                {
                    int x = i + dirx[ii];
                    int y = j + diry[ii];
                    if (x >= 0 &&  x < n && y >=0 && y < m && board[x][y])
                        num1++;
                }
                if (board[i][j] == 0)
                {
                    if(num1 == 3)t[i][j] = 1;
                    else t[i][j] = 0;
                }
                else
                {
                    if(num1 == 2 || num1 == 3)t[i][j] = 1;
                    else t[i][j] = 0;
                }
            }
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                board[i][j] = t[i][j];
    }
};

Python3：

class Solution:
    def __init__(self):
        self.dire = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    def gameOfLife(self, board: List[List[int]]) -> None:
        n = len(board)
        if n == 0: return
        m = len(board[0])
        for i in range(n):
            for j in range(m):
                num1 = 0
                for d in self.dire:
                    x = i + d[0]
                    y = j + d[1]
                    if x >= 0 and x < n and y >= 0 and y < m:
                        num1 += board[x][y] & 1
                if board[i][j] == 0 and num1 == 3:
                    board[i][j] = 2
                elif board[i][j] == 1 and num1 in [2, 3]:
                    board[i][j] = 3
        for i in range(n):
            for j in range(m):
                board[i][j] >>= 1
        

445. 两数相加 II（中等）

【分类】：栈、链表

【题解】：倒序首先就要想到栈啦，把两个链表的数据分别存入两个栈中，再依次取出相加即可，比忘了进位哦。

【代码】：

C++：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2;
        while(l1 != NULL)
        {
            s1.push(l1->val);
            l1 = l1->next;
        }
        while(l2 != NULL)
        {
            s2.push(l2->val);
            l2 = l2->next;
        }
        int c = 0;
        ListNode* ans = NULL;
        while(!s1.empty() || !s2.empty() || c != 0)
        {
            int t1 = s1.empty() ? 0: s1.top();
            int t2 = s2.empty() ? 0: s2.top();
            if(!s1.empty())s1.pop();
            if(!s2.empty())s2.pop();  
            int t = t1 + t2 + c;
            int now = t % 10;
            c = t / 10;
            ListNode* cur = new ListNode();
            cur->val = now;
            cur->next = ans;
            ans = cur;
        }
        return ans;
    }
};

Python3：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        s1 = []
        s2 = []
        while(l1):
            s1.append(l1.val)
            l1 = l1.next
        while(l2):
            s2.append(l2.val)
            l2 = l2.next
        c = 0
        ans = None
        while(s1 or s2 or c != 0):
            t1 = 0 if not s1 else s1.pop()
            t2 = 0 if not s2 else s2.pop()
            t = t1 + t2 + c
            now = t % 10
            c = t // 10
            cur = ListNode(now)
            cur.next = ans
            ans = cur
        return ans