基础-模拟.md

模拟

Problems

• LeetCode 0005 最长回文子串 (中等, 2021-10)
• LeetCode 0143 重排链表 (中等, 2022-01)
• LeetCode 0352 将数据流变为多个不相交区间 (困难, 2021-10)
• LeetCode 0859 亲密字符串 (简单, 2021-11)
• LeetCode 0915 分割数组 (中等, 2022-01)
• 剑指Offer 2900 顺时针打印矩阵（3种思路4个写法） (中等, 2021-11)
• 剑指Offer 3900 数组中出现次数超过一半的数字（摩尔投票） (简单, 2021-12)
• 剑指Offer 4300 1～n整数中1出现的次数 (困难, 2021-12)
• 剑指Offer 4400 数字序列中某一位的数字 (中等, 2021-12)
• 剑指Offer 6100 扑克牌中的顺子 (简单, 2022-01)
• 剑指Offer 6200 圆圈中最后剩下的数字（约瑟夫环问题） (中等, 2022-01)
• 剑指Offer 6300 买卖股票的最佳时机 (中等, 2022-01)
• 剑指Offer 6700 把字符串转换成整数（atoi） (中等, 2022-01)
• 牛客 0001 大数加法 (中等, 2022-01)
• 牛客 0007 买卖股票的最好时机(一) (简单, 2022-01)
• 牛客 0010 大数乘法 (中等, 2022-01)
• 牛客 0017 最长回文子串 (中等, 2022-01)
• 牛客 0038 螺旋矩阵 (中等, 2022-03)
• 牛客 0057 反转数字 (简单, 2022-03)
• 牛客 0063 扑克牌顺子 (简单, 2022-03)

---

LeetCode 0005 最长回文子串 (中等, 2021-10)

问题简述

给你一个字符串 s，找到 s 中最长的回文子串。

5. 最长回文子串 - 力扣（LeetCode）

详细描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
    输入：s = "babad"
    输出："bab"
    解释："aba" 同样是符合题意的答案。
示例 2：
    输入：s = "cbbd"
    输出："bb"
示例 3：
    输入：s = "a"
    输出："a"
示例 4：
    输入：s = "ac"
    输出："a"

提示：
    1 <= s.length <= 1000
    s 仅由数字和英文字母（大写和/或小写）组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：动态规划

• 状态定义：dp[i][j] := 子串 s[i:j] 是否为回文串；
• 状态转移方程：dp[i][j] := dp[i+1][j-1] == True 且 s[i] == s[j]；
• 初始状态
  • 单个字符：dp[i][j] := True 当 i == j
  • 两个连续相同字符：dp[i][j] := True 当 j == i + 1 && s[i] == s[j]

注意：

• 动态规划并不是最适合的解，这里仅提供一个思路；
• 如果要使用动态规划解本题，如何循环是关键，因为回文串的特点，从“双指针”的角度来看，需要从中心往两侧遍历，这跟大多数的 dp 问题略有不同；

C++

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();

        vector<vector<int>> dp(n, vector<int>(n, 0));
        int max_len = 1;    // 保存最长回文子串长度
        int start = 0;      // 保存最长回文子串起点

        // 初始状态1：子串长度为 1 时，显然是回文子串
        for (int i = 0; i < n; i++)
            dp[i][i] = 1;

        //for (int j = 1; j < n; j++)         // 子串结束位置
        //    for (int i = 0; i < j; i++) {   // 子串起始位置
        // 上述循环方式也是可以的，但在 “最长回文子序列” 一题中会有问题
        // 下面的循环方式在两个问题中都正确，这个遍历思路比较像“中心扩散法”
        for (int j = 1; j < n; j++)             // 子串结束位置
            for (int i = j - 1; i >= 0; i--) {  // 子串开始位置
                if (j == i + 1)  // 初始状态2：子串长度为 2 时，只有当两个字母相同时才是回文子串
                    dp[i][j] = (s[i] == s[j]);
                else  // 状态转移方程：当上一个状态是回文串，且此时两个位置的字母也相同时，当前状态才是回文串
                    dp[i][j] = (dp[i + 1][j - 1] && s[i] == s[j]);

                // 保存最长回文子串
                if (dp[i][j] && max_len < (j - i + 1)) {
                    max_len = j - i + 1;
                    start = i;
                }
            }

        return s.substr(start, max_len);
    }
};

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        n = len(s)
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = 1
        
        start = 0
        length = 1
        for j in range(1, n):  # 子串的结束位置
            for i in range(j - 1, -1, -1):  # 子串的开始位置
                if i == j - 1:
                    dp[i][j] = 1 if s[i] == s[j] else 0
                else:
                    dp[i][j] = 1 if dp[i + 1][j - 1] and s[i] == s[j] else 0

                if dp[i][j]:
                    if j - i + 1 > length:
                        length = j - i + 1
                        start = i

        return s[start: start + length]

思路2：模拟-中心扩散（推荐）

• 按照回文串的定义，遍历每个字符作为中点，向两边扩散；
• 官方题解从 DP 的转移方程解释了为什么中心扩散可以得到正确答案（虽然这个结论非常直观），观察状态转移方程，可以看到所有状态在转移时的可能性都是唯一的：dp[i][j] <- dp[i+1][j-1] <- dp[i+2][j-2] <- ...，也就是说，从每一种边界情况开始「扩展」，都可以得出所有状态对应的答案。

  最长回文子串 - 力扣官方题解

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:

        n = len(s)
        self.ret = s[0]

        # 从 s[l:r] 开始向两侧扩散，开始时，l==r 或者，l+1==r
        def process(l, r):
            tmp = ''
            while l >= 0 and r < n:
                if s[l] != s[r]:
                    break
                tmp = s[l: r + 1]
                l -= 1
                r += 1

            if len(tmp) > len(self.ret):
                self.ret = tmp

        for l in range(n - 1):
            process(l, l)
            process(l, l + 1)

        return self.ret

---

LeetCode 0143 重排链表 (中等, 2022-01)

问题简述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
    L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
    L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

详细描述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
    L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
    L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：
    输入：head = [1,2,3,4]
    输出：[1,4,2,3]
示例 2：
    输入：head = [1,2,3,4,5]
    输出：[1,5,2,4,3]

提示：
    链表的长度范围为 [1, 5 * 104]
    1 <= node.val <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：模拟

1. 先找到中间节点 mid；
2. 将链表 mid 反转；
3. 然后合并 head 和 mid；

Python：写法1

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
    
        def  get_mid(p):
            lp, fp = p, p

            while fp and fp.next:
                lp = lp.next
                fp = fp.next.next
            
            return lp
        
        def reverse(p):
            cur, pre = p, None
            while cur:
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
            
            return pre
        
        mid = get_mid(head)  # 注意此时还没有断开两个链表
        mid = reverse(mid)

        # merge
        l, r = head, mid
        while True:
            l_nxt, r_nxt = l.next, r.next
            if not r_nxt:  # 这是一种写法，另一种写法是在获得 mid 后将 mid 与原链表断开（后移一个节点，结果也是正确的，见写法2）
                break
            l.next, r.next = r, l_nxt
            l, r = l_nxt, r_nxt

Python：写法2

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
    
        def  get_mid(p):
            lp, fp = p, p

            while fp and fp.next:
                lp = lp.next
                fp = fp.next.next
            
            return lp
        
        def reverse(p):
            cur, pre = p, None
            while cur:
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
            
            return pre
        
        mid = get_mid(head)
        mid.next, mid = None, mid.next  # 写法2）提前断开 mid
        # mid, mid.next = mid.next, None  # err
        mid = reverse(mid)

        # merge
        l, r = head, mid
        while r:
            l_nxt, r_nxt = l.next, r.next
            # if not r_nxt:
            #     break
            l.next, r.next = r, l_nxt
            l, r = l_nxt, r_nxt

---

LeetCode 0352 将数据流变为多个不相交区间 (困难, 2021-10)

问题描述

给你一个由非负整数 a1, a2, ..., an 组成的数据流输入，请你将到目前为止看到的数字总结为不相交的区间列表。

实现 SummaryRanges 类：
    SummaryRanges() 使用一个空数据流初始化对象。
    void addNum(int val) 向数据流中加入整数 val 。
    int[][] getIntervals() 以不相交区间 [starti, endi] 的列表形式返回对数据流中整数的总结。

进阶：如果存在大量合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

“进阶”：在插入过程中完成合并操作；

示例

输入：
    ["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
输出：
    [null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

解释：
    SummaryRanges summaryRanges = new SummaryRanges();
    summaryRanges.addNum(1);      // arr = [1]
    summaryRanges.getIntervals(); // 返回 [[1, 1]]
    summaryRanges.addNum(3);      // arr = [1, 3]
    summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]]
    summaryRanges.addNum(7);      // arr = [1, 3, 7]
    summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]]
    summaryRanges.addNum(2);      // arr = [1, 2, 3, 7]
    summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]]
    summaryRanges.addNum(6);      // arr = [1, 2, 3, 6, 7]
    summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]

提示：
    0 <= val <= 10^4
    最多调用 addNum 和 getIntervals 方法 3 * 10^4 次

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

法1）Python：暴力求解

• 每次 getIntervals 时，先对数组排序，然后依次找出每个不相交的区间；

class SummaryRanges:

    def __init__(self):
        self.ls = []

    def addNum(self, val: int) -> None:
        """"""
        self.ls.append(val)

    def getIntervals(self) -> List[List[int]]:
        """"""
        ls = sorted(self.ls)
        ret = []
        l = ls[0]
        for i in range(1, len(ls)):
            if ls[i] - ls[i-1] > 1:  # 判断是否需要合并
                ret.append([l, ls[i-1]])
                l = ls[i]
        
        ret.append([l, ls[-1]])

        return ret

法2）Python：模拟，分情况讨论

• 明确每次 addNum 时，区间会发生那些变化：

  • 情况1：存在一个区间 [l, r] 满足 l <= val <= r；
  • 情况2：存在一个区间 [l, r] 满足 r + 1 == val；
  • 情况3：存在一个区间 [l, r] 满足 l - 1 == val；
  • 情况4：存在两个个区间 [l0, r0] 和 [l1, r1] 满足 r0 + 1 == val == l1 - 1，即加入 val 后，会合并为一个区间 [l0, r1]
  • 情况5：以上均不满足，加入后 val 单独成为一个区间；

• 这里使用了 SortedDict 降低了代码难度，也可以使用一个有序数组来模拟；

• 时间复杂度: addNum O(NlgN)、getIntervals O(N)；

• 空间复杂度: O(N)；

from sortedcontainers import SortedDict
from bisect import bisect_right, bisect_left

class SummaryRanges:

    def __init__(self):
        self.ret = SortedDict()  # {l: r}
        # 加入首尾两个哨兵，防止区间不存在的情况，这样会徒增很多判断
        self.ret[-10] = -10
        self.ret[10010] = 10010

    def addNum(self, val: int) -> None:
        ret = self.ret
        L = list(self.ret.keys())
        R = list(self.ret.values())

        # 二分找出 val 的相邻区间
        idx = bisect_left(L, val)  # idx = ret.bisect_left(val)
        pre = L[idx - 1], R[idx - 1]
        nxt = L[idx], R[idx]

        if pre[0] <= val <= pre[1] or nxt[0] <= val <= nxt[1]:  # 情况1
            pass
        elif pre[1] + 1 == val == nxt[0] - 1:  # 情况4
            ret.pop(nxt[0])
            ret[pre[0]] = nxt[1]
        elif pre[1] + 1 == val:  # 情况2
            ret[pre[0]] = val
        elif nxt[0] - 1 == val:  # 情况3
            ret.pop(nxt[0])
            ret[val] = nxt[1]
        else:  # 情况5
            ret[val] = val

    def getIntervals(self) -> List[List[int]]:
        return list(self.ret.items())[1:-1]  # 去除两个哨兵

• 上面的代码中用到了 SortedDict，示例：

>>> d = SortedDict()
>>> d[3] = 33
>>> d[2] = 22
>>> d[4] = 44
>>> d[6] = 66
>>> d[7] = 77
>>> d
SortedDict({2: 22, 3: 33, 4: 44, 6: 66, 7: 77})
>>> d.bisect_left(4)  # 二分查找返回的是插入位置
2
>>> d.bisect_right(4)  # left 和 right 的区别是如果插入值已存在，则 left 会插到前面，right 会插到后面
3

---

LeetCode 0859 亲密字符串 (简单, 2021-11)

问题简述

给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false。

例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。

详细描述

给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。

交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。

例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。
 

示例 1：
    输入：s = "ab", goal = "ba"
    输出：true
    解释：你可以交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 相等。
示例 2：
    输入：s = "ab", goal = "ab"
    输出：false
    解释：你只能交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 不相等。
示例 3：
    输入：s = "aa", goal = "aa"
    输出：true
    解释：你可以交换 s[0] = 'a' 和 s[1] = 'a' 生成 "aa"，此时 s 和 goal 相等。
示例 4：
    输入：s = "aaaaaaabc", goal = "aaaaaaacb"
    输出：true
 

提示：
    1 <= s.length, goal.length <= 2 * 10^4
    s 和 goal 由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/buddy-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：分情况讨论

• 当 len(s) != len(goal) 时：False

• 当 len(s) == len(goal) 时：

  • 当 s != goal 时：当且仅当不同的字符数量等于 2，且交换后满足条件；
  • 当 s == goal 时：s 中存在出现至少 2 次的字符；

• s == goal 的情况比较容易被忽略；

Python：模拟

class Solution:

    def buddyStrings(self, s: str, goal: str) -> bool:
        """"""
        if len(s) != len(goal):
            return False

        dif = []
        cs = set()
        for i, c in enumerate(s):
            cs.add(c)
            if s[i] != goal[i]:
                dif.append(i)

        # 存在字符出现过 2 次
        if s == goal and len(cs) < len(s):
            return True

        # 只存在两个位置字符不同，且交换后满足条件
        if len(dif) == 2 and (s[dif[0]], s[dif[1]]) == (goal[dif[1]], goal[dif[0]]):
            return True

        return False

---

LeetCode 0915 分割数组 (中等, 2022-01)

问题简述

给定整数数组 nums，将其划分为 left 和 right 两部分，要求：
    1. left 中的每个元素都小于或等于 right 中的每个元素；
    2. left 的长度要尽可能小。
返回 left 的长度，题目保证 left 和 right 都非空；

要求：
    时间复杂度 O(n)
    空间复杂度 O(n) 或 O(1)

915. 分割数组 - 力扣（LeetCode）

思路1

• 记 lmax[i] 表示 nums[:i] 中的最大值，rmin[i] 表示 nums[i:] 中的最小值；
• 返回使 lmax[i - 1] <= rmin[i] 的最小 i；

  这里要 <=，否则意味着所有相同的最小值会被分到 left，不符合题意；

Python

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        
        n = len(nums)

        # 计算 lmax
        lmax = [float('-inf')] * n
        lmax[0] = nums[0]
        for i in range(1, n):
            lmax[i] = max(lmax[i - 1], nums[i])
        
        # 计算 rmin
        rmin = [float('inf')] * n
        for i in range(n - 2, -1, -1):
            rmin[i] = min(rmin[i + 1], nums[i])
        
        for i in range(1, n):
            if lmax[i - 1] <= rmin[i]:  # 注意这里要 <=；如果是 <，意味着所有相同的最小值会分到 left，不符合题意
                return i
        
        return -1

优化：计算 lmax 和比较的过程都是顺序遍历，可以合并到一起，节省部分空间；

Python：优化1

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        
        n = len(nums)
        rmin = [float('inf')] * n
        for i in range(n - 2, -1, -1):
            rmin[i] = min(rmin[i + 1], nums[i])
        
        # 合并计算 lmax 和比较过程
        lmax = nums[0]
        for i in range(1, n):
            if lmax <= rmin[i]:
                return i
            lmax = max(lmax, nums[i])
        
        return -1

思路2

【贪心法】 - 分割数组 - qwf

时间复杂度 O(n)，空间复杂度 O(1)

• 使用 lmax 记录已划分 left 中的最大值；
  • 根据题意，left 的中至少会存在一个元素，因此可以初始化 lmax=nums[0]；
• 使用 amax 记录遍历过程中的最大值；
• 当 nums[i] < lmax 时，说明需要扩充 left，即需要把 i 之前的所有元素都添加到 left；同时更新 lmax=amax；

以 nums=[3,4,1,5,6] 为例，下面是：

初始化：
    amax = 3
    lmax = 3
    ret = 1

for i in range(1, len(nums)):

    i  amax  lmax  ret
    1  3     3     1
    2  4     3     1
    3  5     4     3
    4  6     4     3

返回：
    ret = 3

Python

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:

        lmax = amax = nums[0]
        ret = 1
        for i in range(1, len(nums)):
            amax = max(amax, nums[i])
            if nums[i] < lmax:
                ret = i + 1
                lmax = amax
        
        return ret

---

剑指Offer 2900 顺时针打印矩阵（3种思路4个写法） (中等, 2021-11)

问题简述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

详细描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：
    输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
    输出：[1,2,3,6,9,8,7,4,5]
示例 2：
    输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
    输出：[1,2,3,4,8,12,11,10,9,5,6,7]

限制：
    0 <= matrix.length <= 100
    0 <= matrix[i].length <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：螺旋遍历

• 循环遍历 4 个方向的路线，中间做好边界判断（虽然思路简单，但是写起来很容易出错）；

Python：写法1（更朴素）

class Solution:
    def spiralOrder(self, matrix: [[int]]) -> [int]:
        """"""        
        ret = []
        if not matrix or not matrix[0]:
            return ret

        m, n = len(matrix), len(matrix[0])  # m行n列
        # 设置左、右、上、下边界
        l, r, t, b, = 0, n - 1, 0, m - 1

        while True:
            # 依次遍历 4 个方向
            # 因为最后一趟遍历哪个方向都有可能，所以需要 4 个 break

            # left to right, top+=1
            for i in range(l, r + 1):
                ret.append(matrix[t][i])
            t += 1
            if t > b:
                break

            # top to bottom, right-=1
            for i in range(t, b + 1):
                ret.append(matrix[i][r])
            r -= 1
            if l > r:
                break

            # right to left, bottom-=1
            for i in range(r, l - 1, -1):  # 逆序
                ret.append(matrix[b][i])
            b -= 1
            if t > b:
                break

            # bottom to top, left+=1
            for i in range(b, t - 1, -1):  # 逆序
                ret.append(matrix[i][l])
            l += 1
            if l > r:
                break

        return ret

• 写法 1 的逻辑足够清晰，但不够通用（优雅），比如要遍历 8 个方向时；
• 另一种写法会预先定义各方向的 step，详见代码；

Python：写法2（更优雅）

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []

        # 4 个方向的 step
        steps = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        m, n = len(matrix), len(matrix[0])

        # 法1）使用一个 set 或矩阵记录已经访问过的位置
        # visited = set()
        # visited = [[False] * n for _ in range(m)]  # m行n列
        # 法2）直接在 matrix 上修改访问过的位置
        visited = 10001

        ret = []
        i, j = 0, 0  # 记录当前访问的位置
        k = 0  # 已经访问过的位置数量
        d = 0  # 方向标记
        while k < m * n:
            ret.append(matrix[i][j])
            matrix[i][j] = visited
            # visited.add((i, j))
            # visited[i][j] = True
            k += 1

            # 下一个位置
            nxt_i, nxt_j = i + steps[d][0], j + steps[d][1]
            # 判断下一个位置是否合法，或是否访问过
            if not 0 <= nxt_i < m or not 0 <= nxt_j < n or matrix[nxt_i][nxt_j] == visited:
                # 如果不合法或已经访问过，进入下一个方向
                d = (d + 1) % 4
                nxt_i, nxt_j = i + steps[d][0], j + steps[d][1]
            i, j = nxt_i, nxt_j

        return ret

思路2：层层递归

• 每次遍历完最外圈后，递归遍历下一圈；

Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        """"""
        def dfs(M):
            # 注意：这里除了要判断 M，还要判断 M[0]，因为之后代码中的切片操作可能会使行数据为空列表 []
            if not M or not M[0]: return []

            m, n = len(M), len(M[0])

            # 如果最内圈是一行或一列，那么该行/列的遍历方向一定是 左→右 或 上→下
            if m == 1:
                return M[0]
            if n == 1:
                return [row[0] for row in M]

            # 最外一圈的数据
            ret = M[0] \
                + [row[-1] for row in M[1:]] \
                + M[-1][-2::-1] \
                + [row[0] for row in M[-2:0:-1]]

            return ret + dfs([row[1:-1] for row in M[1:-1]])

        return dfs(matrix)

思路3：“削苹果”

• 每次“削去”矩阵的第一层，然后将矩阵逆时针旋转 90 度，循环削去第一层；
• 而逆时针旋转的操作在 python 中可以用一行代码完成！

Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ret = []
        while matrix:
            ret += list(matrix.pop(0))  # zip 后的结果是一个元组，这里转成 list，不过实际上不转换也可以；

            # 核心操作，逆时针旋转 90 度
            matrix = list(zip(*matrix))[::-1]
        
        return ret

# 图解 `list(zip(*matrix))[::-1]` 这一步做了什么：

# 假设已经 pop 了第一行，此时矩阵剩余的部分是：
[4 5 6]  # 记为 l1
[7 8 9]  # 记为 l2，如果有 n 行，则记为 ln

# zip(*matrix) 包含了两个知识点：一个是 zip() 函数，一个是 * 号的作用；
# zip(*matrix) 实际上等价于 zip(l1, l2, ..., ln)
# 经过这一步 matrix 将转化为（相当于做了一次转置）
[4 7]
[5 8]
[6 9]

# 这时再将 matrix 做一次逆序，就得到了逆时针旋转 90 度的结果
[6 9]
[5 8]
[4 7]

---

剑指Offer 3900 数组中出现次数超过一半的数字（摩尔投票） (简单, 2021-12)

问题简述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

详细描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:
    输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
    输出: 2
限制：
    1 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：排序

• 排序后，数组中间位置的数一定满足题意；
• 时间复杂度 O(NlogN)；

Python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return sorted(nums)[len(nums) // 2]

思路2：计数

• 一次遍历，记录每个数出现的次数；
• 空间复杂度 O(N)；

Python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        from collections import defaultdict

        cnt = defaultdict(int)

        for x in nums:
            cnt[x] += 1
            if cnt[x] > len(nums) // 2:
                return x
        
        # return -1

思路3：“摩尔投票法”

数组中出现次数超过一半的数字（摩尔投票法，清晰图解）

• “摩尔投票法”的核心思想是一一抵消；
• 假设已知目标数为 x，遍历时若出现一次 x 记 +1 票，否则为 -1 票；
  • 推论1：最终票数和必大于 0；
  • 推论2：若前 n 个数的票数和为 0，那么剩余部分依然满足推论1，即目标数字依然为 x；

Python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:

        cnt = 0
        for x in nums:
            if cnt == 0:  # 当票数和为 0 时，假设当前值为目标值
                ret = x   # 如果这个数不是目标值，那么它迟早会因为不断 -1，被替换掉
                
            if x == ret:
                cnt += 1
            else:
                cnt -= 1
        
        return ret

思路4：分治

数组中出现次数超过一半的数字

• 本题使用分治在时间和空间上都不是最优，仅用于理解分治的思想；

Python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:

        def recur(lo, hi):  # [lo, hi] 闭区间
            if lo == hi:  # 当数组中只有一个元素时，这个数就是目标值
                return nums[lo]

            # 分治
            mid = (hi - lo) // 2 + lo
            l = recur(lo, mid)
            r = recur(mid + 1, hi)

            # 如果左右返回值相同时，显然这个值就是目标值
            if l == r:
                return l

            # 否则需要判断哪个出现的次数更多
            lc = sum(1 for i in range(lo, hi + 1) if nums[i] == l)
            rc = sum(1 for i in range(lo, hi + 1) if nums[i] == r)
            return l if lc > rc else r

        return recur(0, len(nums) - 1)

---

剑指Offer 4300 1～n整数中1出现的次数 (困难, 2021-12)

问题简述

剑指 Offer 43. 1～n 整数中 1 出现的次数 - 力扣（LeetCode）

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

详细描述

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：
    输入：n = 12
    输出：5
示例 2：
    输入：n = 13
    输出：6

限制：
    1 <= n < 2^31

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 找规律的题目，很费时，建议直接看：1～n 整数中 1 出现的次数（清晰图解） - Krahets

Python

class Solution:
    def countDigitOne(self, n: int) -> int:
        # 初始化一些变量
        digit, ret = 1, 0
        hi, cur, lo = n // 10, n % 10, 0

        while hi != 0 or cur != 0:
            if cur == 0:
                ret += hi * digit
            elif cur == 1:
                ret += hi * digit + lo + 1
            else:
                ret += (hi + 1) * digit
            lo += cur * digit
            cur = hi % 10
            hi //= 10
            digit *= 10
        return ret

---

剑指Offer 4400 数字序列中某一位的数字 (中等, 2021-12)

问题简述

剑指 Offer 44. 数字序列中某一位的数字 - 力扣（LeetCode）

数字以0123456789101112131415…的格式序列化到一个字符序列中，求任意第n位对应的数字。

详细描述

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

示例 1：
    输入：n = 3
    输出：3
示例 2：
    输入：n = 11
    输出：0
 
限制：
    0 <= n < 2^31

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：找规律

数字序列中某一位的数字（迭代 + 求整 / 求余，清晰图解）

Python：迭代+求整/求余

数字序列中某一位的数字（迭代 + 求整 / 求余，清晰图解）

class Solution:
    def findNthDigit(self, n: int) -> int:
        digit, start, cnt = 1, 1, 9
        
        while n > cnt:  # 1. 计算所属区间，如 1~9、10~99、100~999、... 等
            n -= cnt
            start *= 10
            digit += 1
            cnt = 9 * start * digit
        
        num = start + (n - 1) // digit  # 2. 计算属于区间中的哪个数字
        idx = (n - 1) % digit  # 3. 计算在该数字的第几位
        return int(str(num)[idx])  # 4. 返回结果

---

剑指Offer 6100 扑克牌中的顺子 (简单, 2022-01)

问题简述

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子；

详细描述

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1:
    输入: [1,2,3,4,5]
    输出: True
示例 2:
    输入: [0,0,1,2,5]
    输出: True

限制：
    数组长度为 5 
    数组的数取值为 [0, 13] .

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 排序后，统计 0 出现的次数，以及数组中的 max_x 和 min_x；
• 当最大值 - 最小值 < 5 时即可组成顺子；
• 若出现相同牌则提前返回 False；

Python

class Solution:
    def isStraight(self, nums: List[int]) -> bool:

        nums.sort()  # 排序
        # 如果不想排序需的话，就需要另外使用一些变量来记录最大、最小和已经出现过的牌

        cnt_0 = 0
        for i, x in enumerate(nums[:-1]):
            if x == 0:  # 记录 0 的个数
                cnt_0 += 1
            elif x == nums[i + 1]:
                return False
        
        # return nums[-1] - nums[cnt_0] == 4  # Error，因为 0 也可以用来作为最大或最小的牌
        return nums[-1] - nums[cnt_0] < 5

---

剑指Offer 6200 圆圈中最后剩下的数字（约瑟夫环问题） (中等, 2022-01)

问题简述

0 ~ n-1 这 n 个数字围成一个圆圈，从数字0开始，每次从这个圆圈里删除第 m 个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

详细描述

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：
    输入: n = 5, m = 3
    输出: 3
示例 2：
    输入: n = 10, m = 17
    输出: 2

限制：
    1 <= n <= 10^5
    1 <= m <= 10^6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：暴力解（超时）

Python

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:

        nums = list(range(n))
        idx = 0
        while len(nums) > 1:
            idx = (idx + m - 1) % len(nums)
            nums.pop(idx)
        
        return nums[0]

思路2：递推

• 虽然我们不知道这个最终的值是哪个，但是可以确定的是在最后一轮删除后，这个值在数组中的索引一定是 0（此时数组中只有一个值了）；
• 递推的目的就是每次还原这个值在上一轮所在的索引，直到第一轮，然后就可以根据索引从数组中找到这个值了；
• 记 f(i) 表示倒数第 i 轮时目标值所在的索引（i>=1），显然有 f(1) = 0；
• 递推公式：f(i) = (f(i-1) + m) % i（倒数第 i 轮，数组的长度也为 i，所以是对 i 取余）
  • (f(i-1) + m) % i
• 关于递推公式的具体解析可以参`考「换个角度举例解决约瑟夫环」

Python

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:

        # nums = list(range(n))  # 因为 nums = [0..n-1]

        idx = 0  # 因为最后一轮数组中只有一个值了，所以此时目标的索引一定是 0
        for i in range(2, n + 1):
            idx = (idx + m) % i  # 倒数第 i 轮时目标的索引
        
        # return nums[idx]
        return idx  # 因为 nums = [0..n-1]，所以 nums[idx] == idx

---

剑指Offer 6300 买卖股票的最佳时机 (中等, 2022-01)

问题简述

把某股票的价格按照时间顺序存储在数组中，求买卖一次的最大利润。
示例: 输入: [7,1,5,3,6,4]，输出: 5（在价格 1 时买入，价格 6 时卖出）

详细描述

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:
    输入: [7,1,5,3,6,4]
    输出: 5
    解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
        注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
    输入: [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
 

限制：
    0 <= 数组长度 <= 10^5
    0 <= 股票价格 <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

1. 遍历 prices，以 min_p 记录当前的最小值（非全局最小值）；
2. 用当前价格 p 减去 min_p，得到当天卖出的利润；
3. 使用 ret 记录遍历过程中的最大利润。

Python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        """"""
        ret = 0
        min_p = 10001
        for p in prices:
            min_p = min(p, min_p)
            ret = max(ret, p - min_p)
        
        return ret

---

剑指Offer 6700 把字符串转换成整数（atoi） (中等, 2022-01)

问题简述

写一个函数 strToInt(string s)，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

详细描述

写一个函数 strToInt(string s)，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：
    假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:
    输入: "42"
    输出: 42
示例 2:
    输入: "   -42"
    输出: -42
    解释: 第一个非空白字符为 '-', 它是一个负号。
         我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
    输入: "4193 with words"
    输出: 4193
    解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
    输入: "words and 987"
    输出: 0
    解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
        因此无法执行有效的转换。
示例 5:
    输入: "-91283472332"
    输出: -2147483648
    解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
         因此返回 INT_MIN (−231) 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 把字符串当做数组，依次遍历每个字符，根据题目要求执行每一步操作；
• 注意一些细节：如正负号、char 与 int 的互转、越界判断等，详见下方代码；
• PS：不同编程语言中字符串的实现细节；

C++

class Solution {
public:
    int strToInt(string str) {
        int n = str.length();
        if (n < 1) return 0;
        
        int ret = 0;
        int p = 0;      // 模拟指针
        int sign = 1;   // 正负
        int s_max = INT_MAX / 10;
        
        while (isspace(str[p])) 
            p++;  // 跳过前置空格

        // c++ 的字符串末尾有一个特殊字符，因此不需要做越界判断
        // if (p == n) return 0;
        
        if (str[p] == '-') sign = -1;
        if (str[p] == '-' || str[p] == '+') p++;
        
        while (str[p] >= '0' && str[p] <= '9') {
            if (ret > s_max || (ret == s_max && str[p] > '7')) {  // 越界判断
                return sign > 0 ? INT_MAX : INT_MIN;
            }
            ret = ret * 10 + (str[p] - '0');  // str[p] - '0' 必须括起来，否则顺序计算时会溢出
            p++;
        }
        
        return sign * ret;
    }
};

Python

class Solution:
    def strToInt(self, str: str) -> int:

        n = len(str)
        if n < 1: return 0

        INT_MAX = 2 ** 31 - 1
        INT_MIN = -2 ** 31

        ret = 0  # 保存结果
        sign = 1  # 记录符号
        p = 0  # 模拟指针

        # Python 字符串与 C++ 不同，时刻需要进行越界判断
        while p < n and str[p] == ' ':
            p += 1
        
        if p == n:  # 越界判断
            return ret
        
        if str[p] == '-':
            sign = -1
        if str[p] in ('-', '+'):
            p += 1
        
        while p < n and '0' <= str[p] <= '9':  # 注意越界判断
            ret = ret * 10 + int(str[p])
            p += 1
            if ret > INT_MAX:  # python 中不存在越界，因此直接跟 INT_MAX 比较即可
                return INT_MAX if sign == 1 else INT_MIN
        
        return ret * sign

Java

把字符串转换成整数（数字越界处理，清晰图解）

class Solution {
    public int strToInt(String str) {
        int res = 0, bndry = Integer.MAX_VALUE / 10;
        int i = 0, sign = 1, length = str.length();
        if(length == 0) return 0;
        while(str.charAt(i) == ' ')
            if(++i == length) return 0;
        if(str.charAt(i) == '-') sign = -1;
        if(str.charAt(i) == '-' || str.charAt(i) == '+') i++;
        for(int j = i; j < length; j++) {
            if(str.charAt(j) < '0' || str.charAt(j) > '9') break;
            if(res > bndry || res == bndry && str.charAt(j) > '7')
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            res = res * 10 + (str.charAt(j) - '0');
        }
        return sign * res;
    }
}

---

牛客 0001 大数加法 (中等, 2022-01)

问题简述

以字符串的形式读入两个数字，计算它们的和，以字符串形式返回。

大数加法_牛客题霸_牛客网

思路

• 把较短的字符串通过补前缀 0 使长度一致，此时只要处理好进位即可；

Python

class Solution:
    def solve(self , s: str, t: str) -> str:
        # write code here
        n, m = len(s), len(t)
        if n < m:  # 确保 n >= m
            s, t = t, s
            n, m = m, n
            
        t = '0' * (n - m) + t  # 补0
        
        ret = ''
        ex = 0  # 进位标志
        for i in range(n - 1, -1, -1):
            r = int(s[i]) + int(t[i]) + ex
            ret = str(r % 10) + ret
            ex = r // 10
            
        if ex:
            ret = '1' + ret
        
        return ret

---

牛客 0007 买卖股票的最好时机(一) (简单, 2022-01)

问题简述

给定一支股票的价格序列，返回买卖一次的最大值；

买卖股票的最好时机(一)_牛客题霸_牛客网

思路：动态规划

• 记 dp[i] 表示 prices[:i] 中的最小值；
• 则 ret = max(x - dp[i])；
• 实际可以用一个变量记录当前最小值，节省空间；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param prices int整型一维数组 
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        ret = 0
        min_p = prices[0]
        for x in prices[1:]:
            ret = max(ret, x - min_p)
            min_p = min(x, min_p)
        return ret

---

牛客 0010 大数乘法 (中等, 2022-01)

问题简述

以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。

http://

思路1：模拟

以 54 * 68 为例：

    54
  x 68
  -----

用 tmp 记录每一步的结果

8 * 4 = 32      tmp = [32]
8 * 5 = 40      tmp = [40, 32]
6 * 4 = 24      tmp = [40 + 24, 32]
6 * 5 = 30      tmp = [30, 40 + 24, 32]

得到 tmp 后做循环进位加法即可，详见代码；

• 示例中按照手算习惯是从低位开始算起的，实际因为各位之间互相独立，从高位开始也可以，详见代码；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 第一个整数
# @param t string字符串 第二个整数
# @return string字符串
#
class Solution:
    def solve(self , s: str, t: str) -> str:
        from collections import deque
        
        # write code here
        tmp = []
        # 从高位开始算起
        for i, a in enumerate(s):
            for j, b in enumerate(t):
                c = int(a) * int(b)
                if i + j == len(tmp):
                    tmp.append(c)
                else:
                    tmp[i + j] += c
        
        ret = deque()
        add = 0  # 进位
        for x in tmp[::-1]:  # 因为要考虑进位，所以从低位开始算起，即逆序遍历
            x += add
            add = x // 10
            ret.appendleft(str(x % 10))  # 这里也可以直接拼字符串，不过推荐用队列
        
        if add:
            ret.appendleft(str(add))
            
        return ''.join(ret)

---

牛客 0017 最长回文子串 (中等, 2022-01)

问题简述

求给定字符串中最长回文子串的长度。

最长回文子串_牛客题霸_牛客网

思路1：模拟中心扩散（推荐）

• 中心扩散直观，且不需要额外的空间，比动态规划的方法更好；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        n = len(A)
        
        def process(l, r):
            tmp = 1  # 使用一个变量保存已知的最大长度
            while l >= 0 and r < n:
                if A[l] != A[r]:
                    break
                tmp = r - l + 1
                l -= 1
                r += 1
            # return r - l + 1  # 直接返回有问题，无法判断最后一次是否匹配上
            return tmp
        
        ret = 1
        for i in range(len(A) - 1):
            # 同时处理 process(i, i), process(i, i + 1) 避免奇偶的讨论
            ret = max(ret, process(i, i), process(i, i + 1))
            
        return ret

思路2：动态规划

• DP 虽然能解，但是不够直观，且初始状态容易写错（相邻两个字符相同的情况）；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        n = len(A)
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = 1
        
        start = 0
        length = 1
        for j in range(1, n):  # 子串的结束位置
            for i in range(j - 1, -1, -1):  # 子串的开始位置
                if i == j - 1:
                    dp[i][j] = 1 if A[i] == A[j] else 0
                else:
                    dp[i][j] = 1 if dp[i + 1][j - 1] and A[i] == A[j] else 0

                if dp[i][j]:
                    if j - i + 1 > length:
                        length = j - i + 1
                        start = i

        return length

---

牛客 0038 螺旋矩阵 (中等, 2022-03)

问题简述

给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。

螺旋矩阵_牛客题霸_牛客网

思路

• 把矩阵及其元素看作坐标中的点，初始定义左上角和右下角两个点 (0, 0) 和 (m, n)；
• 然后根据要求，每次打印一圈，注意边界条件，详见代码；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 
# @return int整型一维数组
#
class Solution:
    def spiralOrder(self , M: List[List[int]]) -> List[int]:
        # write code here
        if not M: return []
        
        ret = []
        
        def dfs(a, b, c, d):
            
            # 打印一行 (a,b) -> (a, d)
            if a == c:
                t = b
                while t <= d:
                    ret.append(M[a][t])
                    t += 1
            # 打印一列 (a, d) -> (c, d)
            elif b == d:
                t = a
                while t <= c:
                    ret.append(M[t][b])
                    t += 1
            # 打印一圈
            else:
                # 左到右: (a,b) -> (a, d-1)
                t = b
                while t < d:
                    ret.append(M[a][t])
                    t += 1
                # 上到下: (a, d) -> (c-1, d)
                t = a
                while t < c:
                    ret.append(M[t][d])
                    t += 1
                # 右到左: (c, d) -> (c, b+1)
                t = d
                while t > b:
                    ret.append(M[c][t])
                    t -= 1
                # 下到上: (c, b) -> (a-1, b)
                t = c
                while t > a:
                    ret.append(M[t][b])
                    t -= 1
        
        a, b, c, d = 0, 0, len(M) - 1, len(M[0]) - 1
        while a <= c and b <= d:
            dfs(a, b, c, d)
            a, b = a + 1, b + 1
            c, d = c - 1, d - 1
        
        return ret

---

牛客 0057 反转数字 (简单, 2022-03)

问题简述

给定一个32位的有符号整数num，将num中的数字部分反转，最后返回反转的结果
1.只反转数字部分，符号位部分不反转
2.反转后整数num超过 32 位的有符号整数的范围 [−2^31,  2^31 − 1] ，返回 0

反转数字_牛客题霸_牛客网

思路

• 要点：越界判断；
  • Python 中不会越界，直接跟边界比较即可；

Python

class Solution:
    def reverse(self , x: int) -> int:
        sign = -1 if x < 0 else 1
        x = abs(x)
        
        ret = 0
        while x:
            c = x % 10
            ret = ret * 10 + c
            if ret > 2 ** 31 - 1:
                return 0
            x //= 10
        return ret * sign

---

牛客 0063 扑克牌顺子 (简单, 2022-03)

问题简述

现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
有如下规则：
1. A为1，J为11，Q为12，K为13，A不能视为14
2. 大、小王为 0，0可以看作任意牌
3. 如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。
4.数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]

扑克牌顺子_牛客题霸_牛客网

思路

• 不能有重复牌；
• 最大和最小之间的差小于等于 4；

Python

class Solution:
    def IsContinuous(self , arr: List[int]) -> bool:
        # write code here
        
        book = set()
        mx, mi, cnt0 = 1, 13, 0
        
        for x in arr:
            if x == 0:
                cnt0 += 1
                continue
            book.add(x)
            mx = max(mx, x)
            mi = min(mi, x)
        
        # 组成顺子的条件：没有重复牌，最大和最小的差小于等于 4
        return len(book) == 5 - cnt0 and mx - mi <= 4

---