Array 问题编程
weigaochen 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
代码解析:
- 其中的 k 是为了记录当前已经排好序的奇数的个数
- 然后循环找到一个奇数,交换这个奇数和前面元素的位置,注意到交换的次数和当前奇数的下标与已经排好奇数的数量有关
- 已经排序好的奇数数量加 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 表示第几个九宫格)
- 每个数属于哪个 box 只取决于纵坐标(也就是用
这个问题是一个很好的操作二维数组的例子,虽然同时也结合了 hash 表,但是主要还是确定数独的格子。
在一个 i
行 j
列元素对应的格子是使用