Ylin's Blog
0%

17:算法小练(1)

发表于 更新于 分类于

四月份还是三月份有蓝桥杯的算法比赛，加上一直对算法感兴趣。所以从现在开始稍微学一下。

每天会坚持做几题吧，因为不知道哪些比较重要，我就主要记一些我认为重要的内容和算法

数组

数组中心索引

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

当数组中一个索引右边的和等于左边和时，称这个索引为数组的中心索引

1
2
3
4
5
6
7
8
9
def midIndex(nums:List[int])->int:
    all = sum(nums)
    left = 0
    for i in range(len(nums)):
        if left*2+nums[i]==all:
            return i
        else:
            left += nums[i]
    return -1

大概的思路就是根据它的数值对称的思路来实现中心索引的寻找

二分法查找

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

这是一个经典的查找算法，相较于线性查找，它的时间复杂度更简单O(log_n)

1
2
3
4
5
6
7
8
9
10
11
def binary_search(nums:List[int],target:int)->int:
    left,right = 0,len(nums)-1
    while left<=right:
        mid = left + (right-left)//2	# 避免整数溢出
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid+1
        else:
            right = mid-1
    return -1

首先设置左右边界，然后判断目标在左区间还是右区间。如果在左区间，则更改右边界条件；在右区间，则更改左边界条件。直到找到目标数值，返回索引

区间合并

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给一个若干区间组成的数组，其区间含义为[start,end]，我们将其进行合并

1
2
3
4
5
6
7
8
9
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key= lambda x:x[0])
        rList = list()
        for interval in intervals:
            if not rList or rList[-1][-1]<interval[0]:
                rList.append(interval)
            else:
                rList[-1][-1] = max(rList[-1][-1],interval[1])
        return rList

首先根据区间的起始位置进行排序，然后创建一个新的列表，设置以下规则：

  • 当列表为空时，加入数组
  • 当列表中数组的最后一位小于当前数组的第一位，说明不重叠，加入数组
  • 当发生重叠时，比较两数组的最后一位，保留大的数字

二维数组

旋转矩阵

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个NXN矩阵表示的图像，其中每个像素大小为4字节，设计一种算法，将图像顺时针旋转90°

方法一：

使用一个额外的数组来辅助完成

1
2
3
4
5
6
7
8
def rotate(self,matrix: List[List[int]])->List[List[int]]:
    rlists = list()
    for j in range(len(matrix[0])):
        rlist = list()
        for i in range(len(matrix)-1,-1,-1):
            rlist.append(matrix[i][j])
            rlists.append(rlist)
    return rlists

这个实际上是通过更改读取顺序的方式，重新创建一个矩阵，但是不符合题目不额外使用空间的思想

方法二：

通过矩阵的几何特性来实现

1
2
3
4
5
6
7
8
9
def rotate(self,matrix: List[List[int]]):
    N = len(matrix)
    # 对角线互换
    for i in range(N):
        for j in range(i):	# 这里要仔细理解，因为接下来要进行互换，所以j要随i增大
            matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]
    # 水平互换
    for i in range(N):
        matrix[i][:] = matrix[i][::-1]

这里我们可以总结：

  • 顺时针旋转90°，先对角翻转，再水平翻转
  • 逆时针旋转90°，先水平翻转，再对角线翻转

零矩阵

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

数字0所在的行与列，在矩阵中全部置0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def setZeroes(self, matrix:List[List[int]]):
    M=len(matrix)
    N=len(matrix[0])
    line=[0]*M
    row=[0]*N
    for i in range(M):
        for j in range(N):
            if matrix[i][j]==0:
                line[i] = 1
                row[j] = 1
    for i in range(M):
        for j in range(N):
            if line[i]==1 or row[j]==1:
                matrix[i][j]=0

这个方法很直观，分别创建行和列的索引，并进行标记，当匹配到标记时，将数据置0

对角线遍历

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个大小mxn的矩阵mat，以对角线遍历的顺序，用一个数组返回

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
class Solution(object):
    def findDiagonalOrder(self, mat:List[List[int]])->List[int]:
        ans = []
        Xsize = len(mat)
        Ysize = len(mat[0])
        tot = Xsize + Ysize - 1
        x,y = 0,0
        for i in range(tot):
            if i%2==1:
                while y>=0 and x<Xsize:
                    ans.append (mat[x][y])
                    x += 1
                    y -= 1
                if x<Xsize:
                    y += 1
                else:
                    y += 2
                    x -= 1
            else:
                while x>=0 and y<Ysize:
                    ans.append (mat[x][y])
                    x -= 1
                    y += 1
                if y<Ysize:
                    x += 1
                else:
                    x += 2
                    y -= 1
        return ans

这道题目难在边界条件的处理，需要仔细分析（分类讨论）

注意：在观察二维数组时，一定要把索引与行列之间的关系理清除

这里附上一个很好的解答498. 对角线遍历 - 力扣（LeetCode）