1. 剑指 Offer 04. 二维数组中的查找


重点思想：从左下角或右上角开始，这样就能将二维数组转换成二叉树

1
2
3
4
5
6
7
8
9
10
class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        left,right = len(matrix)-1,0
        while(left>-1 and right<len(matrix[0])):
            if target>matrix[left][right]:
                right+=1
            elif target<matrix[left][right]:
                left-=1
            else:return True
        return False

2. 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        if len(nums)==0:return nums
        left,right = 0,len(nums)-1
        while(left<right):
            while(nums[left]%2==1 and left<len(nums)-1):
                left+=1
            while(nums[right]%2==0 and right>0):
                right-=1
            if left<right:
                tmp = nums[left]
                nums[left]=nums[right]
                nums[right]=tmp
                left+=1
                right-=1
        return nums

3. 剑指 Offer 29. 顺时针打印矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def spiralOrder(self, matrix:[[int]]) -> [int]:
        if not matrix: return []
        l, r, t, b, res = 0, len(matrix[0]) - 1, 0, len(matrix) - 1, []
        while True:
            for i in range(l, r + 1): res.append(matrix[t][i]) # left to right
            t += 1
            if t > b: break
            for i in range(t, b + 1): res.append(matrix[i][r]) # top to bottom
            r -= 1
            if l > r: break
            for i in range(r, l - 1, -1): res.append(matrix[b][i]) # right to left
            b -= 1
            if t > b: break
            for i in range(b, t - 1, -1): res.append(matrix[i][l]) # bottom to top
            l += 1
            if l > r: break
        return res

另一个神奇的做法,zip将二维矩阵行列进行转换
用*让matrix转换成多个参数

1
2
3
4
5
6
7
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res += matrix.pop(0)
            matrix = list(zip(*matrix))[::-1]
        return res

4. 剑指 Offer 45. 把数组排成最小的数

思路：

  • 本质上是个排序问题
  • 先将所有元素转换为字符串
  • 对于字符串a,b 定义比较函数，若 a+b < b+a 则a < b
  • 按此定义进行升序排序，然后拼接到一起
  • 此题对比较函数的定义比较困难，其他部分正常，应该练习排序方法，偷懒了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def compare(x,y):
            if x+y<y+x:
                return -1
            elif x+y>y+x:
                return 1
            else:return 0
        nums_str = [str(num) for num in nums]
        nums_str.sort(key=cmp_to_key(compare))
        # 也可以用lambda生成匿名函数
        #  nums_str.sort(key=cmp_to_key(lambda x,y: int(str(x) + str(y)) - int(str(y) + str(x))))
        print(nums_str)
        return ''.join(nums_str)

5. 剑指 Offer 53 - I. 在排序数组中查找数字 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 左边界：数组中小于target的元素个数,即返回第一个大于等于target的元素index
        # 右边界：数组中小于等于target的元素个数,即返回第一个大于target的元素index
        # 1,2,3,4是互相影响的，记住一种框架就行
        # 这种框架思路如下：
        # 先确定循环条件left<=right,即最后跳出循环时left>right (#2)
        # 所以right初始化不能为len(nums)，不然在target大于最大值时会出现nums[len(nums)]而报错，只能为len(nums)-1 (#1)
        # 再确定返回值为left (#4)
        # 若求左边界，即找第一个大于等于target的元素index，所以只要nums[mid]<target,left(目标返回值)就从mid向右移一位 (#3)
        # 若求右边界，即找第一个大于target的元素index，所以只要nums[mid]<=target,left(目标返回值)就从mid向右移一位 (#3)  

        def left_boundary(tar):
            left,right = 0,len(nums)-1          #1
            while left<=right:                  #2
                mid = (left+right)//2
                if nums[mid]<tar:left=mid+1     #3
                else:right = mid-1
                print(left,mid,right)
            return left                         #4
        def right_boundary(tar):
            left,right = 0,len(nums)-1
            while left<=right:
                mid = (left+right)//2
                if nums[mid]<=tar:left=mid+1
                else:right = right-1
            return left 

        return right_boundary(target)-left_boundary(target)
        # return right_boundary(target)-right_boundary(target-1)
        # return left_boundary(target+1)-left_boundary(target)

6. 剑指 Offer 53 - II. 0～n-1中缺失的数字

1
2
3
4
5
6
7
8
9
10
# 有了前面的框架就可以很简单写出这题，目标为返回第一个元素index不等于元素值的元素index
# 所以只要nums[mid] == mid,left(目标返回值)就从mid向右移一位 (#3)
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        left,right = 0,len(nums)-1
        while(left<=right):
            mid = (left+right)//2
            if nums[mid] == mid:left = mid+1
            else:right = mid-1
        return left

7.剑指 Offer 57. 和为s的两个数字

算法流程：

  1. 初始化： 双指针 $i , j$ 分别指向数组 $nums$ 的左右两端 （俗称对撞双指针）。
  2. 循环搜索： 当双指针相遇时跳出；
    1. 计算和 $s = nums[i] + nums[j]$；
    2. 若 $s > targets$ ，则指针 $j$ 向左移动，即执行 $j = j - 1$ ；
    3. 若 $s < targets$ ，则指针 $i$ 向右移动，即执行 $i = i + 1$ ；
    4. 若 $s = targets$ ，立即返回数组 $[nums[i], nums[j]]$；
  3. 返回空数组，代表无和为 $target$ 的数字组合。


1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        i, j = 0, len(nums) - 1
        while i < j:
            s = nums[i] + nums[j]
            if s > target: j -= 1
            elif s < target: i += 1
            else: return nums[i], nums[j]
        return []

原文链接

8.剑指 Offer 57 - II. 和为s的连续正数序列


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        i,j,s,out = 1,2,3,[]
        
        while(i<j):
            print(i,j,s)
            if s<target:
                j+=1
                s+=j # j先加1,然后s再加上j
            elif s>=target:
                s-=i
                i+=1 # s先加上i,然后i再加1
            if s==target:
                out.append(list(range(i,j+1)))
        return out

9. 剑指 Offer 58 - I. 翻转单词顺序

说明：
如果一开始不用strip()函数除去两边空格的话，需要加判断i,j是否相等，不然可能会添加空字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def reverseWords(self, s: str) -> str:
        i = j = len(s)-1
        out = []
        while(i>=0):
            # 找单词结尾
            while(i>=0 and s[i] == ' '):i-=1 
            j=i
            # 找单词开头
            while(i>=0 and s[i] !=' '):i-=1
            # 如果i,j不相等则该单词存在，保留
            if i<j:out.append(s[i+1:j+1])

        return ' '.join(out)
        # return ' '.join(s.strip().split()[::-1]) #过于简单，面试时不推荐

10. 剑指 Offer 61. 扑克牌中的顺子

说明：
计算最小值可以按图示计算0的个数$joker$，$nums[joker]$就代表最小值，也可以像代码一样直接找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        nums.sort()
        min_num = 0
        pre = 0
        for num in nums:
            if num != 0 :
                if min_num == 0:
                    min_num = num
                if num == pre:
                    return False
                pre = num
        
        return nums[-1]-min_num < 5

11. 剑指 Offer 66. 构建乘积数组


1
2
3
4
5
6
7
8
9
10
class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
        b,tmp = [1]*len(a),1
        for i in range(1,len(a)):
            b[i]=b[i-1]*a[i-1]
        for i in range(len(a)-2,-1,-1):
            tmp*=a[i+1]
            b[i]*=tmp
        return b

12. 剑指 Offer 67. 把字符串转换成整数


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def strToInt(self, str: str) -> int:
        str = str.strip() # 去掉两端空字符
        if not str :return 0 # 若剩余字符为空，则返回0，因为后面会用上str[0],所以要提前判断
    
        sign = -1 if str[0]=='-' else 1 # 确定符号
        if str[0] in ['+','-'] :str = str[1:] # 开头有符号的话也去掉

        # 边界值，最大最小值
        boundry,int_max,int_min = 2**31//10,2**31 - 1,-2**31 
        res = 0
        for c in  str:
            if c < '0' or c > '9':break  # 遇到非数字直接退出
            # 遇到越界根据符号返回对应最值
            if res>boundry or res == boundry and c>'7':return int_max if sign==1 else int_min
            res=10*res+ord(c)-ord('0') # 用ascii(c)-ascii('0')就可将str的数字字符转换成数值
        return sign*res # 返回值