Array 问题编程

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

• Python Code
  • 计算二维数组行列数
  • 调整数组顺序使奇数位于偶数前面
  • 有效的数独

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 个数独格子，第 i 行 j 列元素对应的格子是使用 计算到的。