Python数据结构-数组(Array)

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 先上下进行 行反转 然后进行 对角线元素反转
        row = len(matrix)
        col = len(matrix[0])       # 列元素
        # 行反转 matrix[0][0], matrix[2][0] = matrix[2][0], matrix[0][0]
        for i in range(row//2):
            for j in range(col):
                matrix[i][j], matrix[row-i-1][j] = matrix[row-i-1][j], matrix[i][j]
        # 对角线元素反转
        for i in range(row):
            for j in range(i):   # 注意：只需要反转单侧对角线
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        return matrix

面试题 01.08. 零矩阵

输入：
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出：
[
[1,0,1],
[0,0,0],
[1,0,1]
]

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        row = len(matrix)
        col = len(matrix[0])

        flag_row = False
        flag_col = False

        # 判断第一行是否存在 0，并进行标记
        for i in range(row):
            if matrix[i][0] == 0:
                flag_col = True
                break
        # 判断第一列是否存在 0，并进行标记
        for j in range(col):
            if matrix[0][j] == 0:
                flag_row = True
                break
        # 遍历除了第一行和第一列的元素，使用数组的第一行、第一列对应位置来存储 0 的标记。
        for i in range(1, row):
            for j in range(1, col):
                if matrix[i][j] == 0:
                    matrix[i][0] = matrix[0][j] = 0
        # 遍历除了第一行和第一列的元素，对第一行、第一列对应位置标记为 0 的元素对应的所有行列元素置为 0       
        for i in range(1, row):
            for j in range(1, col):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        # 最后检查第一行和第一列
        if flag_col:      
            for i in range(row):
                matrix[i][0] = 0
        if flag_row:
            for j in range(col):
                matrix[0][j] = 0

73. 矩阵置零

给定一个 m* x *n 的矩阵，如果一个元素为 **0 **，则将其所在行和列的所有元素都设为 0 。请使用 [原地]算法。

• 相比上一道题目的解题思路，比较简单，便于理解

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        row = len(matrix)
        col = len(matrix[0])
        # 1 通过遍历查找包括 0 的行和列的位置
        locRow = set()
        locCol = set()
        for i in range(row):
            for j in range(col):
                if matrix[i][j] == 0:
                    locRow.add(i)
                    locCol.add(j)
        # 2 将包括0的行和列所有元素置为0
        for i in range(row):
            for j in range(col):
                if i in locRow or j in locCol:
                    matrix[i][j] = 0

283：移动零元素

输入：[1,2,0,0,3]
输出：[1,2,3,0,0] 保持原先的元素相对位置不变,不使用额外的空间

a = [1,2,0,0,3]
index = 0
for i in a:
    if i != 0:
        a[index] = i
        index += 1
for j in range(index+1, len(a)):
    a[j] = 0
print(a)

变位词
输入：'python', 'typhon'
输出：true

方法1：逐字检查

def anagramSolution(s1, s2):
    pos1 = 0
    stillOk = True
    alist = list(s2)                       # 将s2转变为列表，方便标记
    while pos1 < len(s1) and stillOk:      # 循环遍历s1
        pos2 = 0
        found = False
        while pos2 < len(s2) and not found: # 循环遍历s2
            if s1[pos1] == alist[pos2]:
                found = True
            else:
                pos2 += 1
        if found:
            alist[pos2] = None
        else:
            stillOk = False
        pos1 += 1

    return stillOk

s1 = 'abcde'
s2 = 'abde'
print(anagramSolution(s1, s2))

时间复杂度：两层循环O(n**2)

方法2：排序法

def compareStr(s1, s2):
    list1 = list(s1)
    list2 = list(s2)
    list1.sort() 
    list2.sort()
    pos = 0
    match = True
    while pos < len(s1) and match:
        if list1[pos] == list2[pos]:
            pos += 1
        else:
            match = False

    return match

print(compareStr('abc', 'ac'))

时间复杂度：主要是排序算法O(nlogn)

方法3：计数比较

# 总共有26个小写字母
def compareStr(s1, s2):
    c1 = [0]*26
    c2 = [0]*26
    for i in range(len(s1)):
        pos = ord(s1[i]) - ord('a')   # ASCII
        c1[pos] += 1
    for j in range(len(s2)):
        pos = ord(s1[j]) - ord('a')
        c2[pos] += 1
    # 计数结果比较
    k = 0
    match = True
    while k < 26 and match:
        if c1[k] == c2[k]:
            k += 1
        else:
            match = False
    return match
print(compareStr('abc', 'acb'))

时间复杂度：2n+26