Array 问题编程

9/17/2019 algorithmleetcode

遇到数组问题,一般是二维数组的问题,不要慌,这个文章就是为了总结几个基本的确定点,也可以说是原则,避免在紧张的时候不知所措。

# Python Code

# 计算二维数组行列数

在 Python 中,如果遇到二维数组的问题了,需要格外注意:计算二维数组的行列的时候绝对不能出错:

# 3 行 2 列
>>> alist = [[1, 2],[3, 4], [5, 6]]
"""
[
    [1, 2],
    [3, 4],
    [5, 6]
]
"""
>>> len(alist)
$ 3
>>> len(alist[0])
$ 2

所以一般的计算方式为:

# alist
rows = len(alist) # 行 i
cols = len(alist[0]) # 列 j

# 调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

要使得相对位置不变,可以使用下面的比较好的写法:

class Solution:
    def reOrderArray(self, array):
        k = 0
        for i in range(len(array)):
            if array[i] % 2 == 1:
                j = i
                while j > k:
                    array[j], array[j-1] = array[j-1], array[j]
                    j -= 1
                k += 1
        return array

代码解析:

  1. 其中的 k 是为了记录当前已经排好序的奇数的个数
  2. 然后循环找到一个奇数,交换这个奇数和前面元素的位置,注意到交换的次数和当前奇数的下标与已经排好奇数的数量有关
  3. 已经排序好的奇数数量加 1

# 有效的数独

代码如下:

# @lc app=leetcode.cn id=36 lang=python3
#
# [36] 有效的数独
# algorithm/array_1.py

# @lc code=start
class Solution:
    def isValidSudoku(self, board: 'List[List[str]]') -> bool:
        # row
        import collections
        rows = [{} for i in range(len(board))]
        cols = [{} for j in range(len(board[0]))]
        boxes = [{} for n in range(9)]  # 一共 9 个 box
        for i in range(len(board)):
            for j in range(len(board[0])):
                # 行是否存在重复,拿出每一行的数
                num = board[i][j]
                if num != '.':
                    # 先建 hash table
                    rows[i][num] = rows[i].get(num, 0) + 1
                    cols[j][num] = cols[j].get(num, 0) + 1
                    # 判断处于哪个 box 中,先要计算 box 的索引
                    box_index = j // 3 + (i // 3) * 3
                    boxes[box_index][num] = boxes[box_index].get(num, 0) + 1
                    # hash table 建立完成,现在开始判断
                    if rows[i][num] > 1 or cols[j][num] > 1 or boxes[box_index][num] > 1:
                        return False
        return True

这个问题的主要关键点有:

  • 不必非要按照行、列、各自的顺序来遍历并判断,只需要判断在行、列、格子中是否出现过即可,这样只需要一次遍历即可完成。
  • 对于是否在格子中出现过,可以使用该作者的思路,寻找规律:
    • 每个数属于哪个 box 只取决于纵坐标(也就是用 j / 3 即可计算出处于哪一列 box 中,共有 3 列)
    • j/3 + (i/3)*3 用于判断所当前的数字 board[i][j] 处于哪个 box 中(box 表示第几个九宫格)

这个问题是一个很好的操作二维数组的例子,虽然同时也结合了 hash 表,但是主要还是确定数独的格子。

在一个 的数独格子中,共有 9 个数独格子,第 ij 列元素对应的格子是使用 计算到的。

更新时间: 2021年9月24日星期五 23:04