python中的动态数组!

手写动态数组

  1. 初始化
  2. 返回是否为空
  3. 数组size
  4. 添加
  5. 删除
  6. 清空
  7. 获取指定位置元素
import ctypes

class DynamicArray:
    # init,call func make_array() to apply space in mem
    def __init__ (self):
        'Create an empty array.'
        self._n = 0 #size
        self._capacity = 10
        self._A = self._make_array(self._capacity)
        
    # len(list)
    def __len__ (self):
        return self._n
    
    def is_empty(self):
        return self._n == 0
    
    # O(1)
    def __getitem__ (self, k):
        if not 0 <= k < self._n:
            raise ValueError('invalid index') 
        return self._A[k]
       
    # O(1) 
    def append(self, obj):
        if self._n == self._capacity:
            self._resize(2 * self._capacity)
        self._A[self._n] = obj    
        self._n += 1
        
    def _make_array(self, c):
        return (c * ctypes.py_object)( )
    
    def _resize(self, c):
        B = self._make_array(c)
        for k in range(self._n):
            B[k] = self._A[k]
        self._A = B
        self._capacity = c   

    # O(n)
    def insert(self, k, value):
        if self._n == self._capacity:
            self._resize(2 * self._capacity)
        for j in range(self._n, k, -1):
            self._A[j] = self._A[j-1]
        self._A[k] = value
        self._n += 1
     
    # O(n)    
    def remove(self, value):
        for k in range(self._n):
            if self._A[k] == value:
                for j in range(k, self._n - 1):
                    self._A[j] = self._A[j+1]
                self._A[self._n - 1] = None
                self._n -= 1
                return
        raise ValueError( 'value not found' )
    
    def _print(self):
        for i in range(self._n):
            print(self._A[i], end = ' ')
        print()

生成一个扫雷游戏

输入参数 M,N,p(行、列、是雷的概率)

import random
def minesweeper(m,n,p):
    #in order to ignore Border judgment,init (n+2)*(m+2) top bot left and right plus 1 
    board = [[None]*(n + 2) for i in range(m + 2)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            r = random.random()
            board[i][j] = -1 if r < p else 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            print("*",end = " ") if board[i][j] == -1 else print("." , end = " ")
        print()
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if(board[i][j] != -1):
                for ii in range(i - 1, i + 2):
                    for jj in range(j -1 ,j + 2):
                        if(board[ii][jj] == -1):
                            board[i][j]+=1
    print()
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            print("*",end = " ") if board[i][j] == -1 else print(board[i][j] , end = " ")
        print()
    


矩阵0变换

给定一个mxn矩阵,如果一个元素为0,则把该行、该列变为0.

最典型的错误:第一次遍历找0时,就直接将一行变为0。显然这样做会修改后续还没有遍历到的值的判断!

def zero(matrix):
    for x in matrix:
        print(x, sep=" ")
    
    m=[None]*len(matrix)
    n=[None]*len(matrix[0])
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == 0:
                m[i] = 1
                n[j] = 1
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if(m[i] == 1 or n[j] == 1):
                matrix[i][j] = 0
                
    print()
    
    for x in matrix:
        print(x, sep=" ")
    
    

九宫图

规则:用1到n*n个数填充,每行每列和相同。

九宫格填写有如下规律:

def magic_squ(n):
    magic=[[0] * n for i in range(n)]
    row=n-1
    col=n//2
    magic[row][col] = 1
    for i in range(2, n * n + 1):
        try_row = (row + 1) % n
        try_col = (col +1 ) % n
        
        if(magic[try_row][try_col] == 0):
            row = try_row
            col = try_col
        else:
            row = (row -1 +n) % n
        magic[row][col] = i 
    for x in magic:
        print(x, sep = " ")
    

验证数独是否正确

预备知识:

  • 按行(列)检查时,我们需要记录该数是否出现过,当然用set可行!

以本题9为例子。
初始一个9个0的数(res=000000000),用这个对应的位置记录某个数是否出现过。
1->000000001
1、2->000000011
……
那么来一个数怎么判断是否已经在里面了?
我们知道&操作有如下性质
1&1=1,1&0=0,0&0=0,因此来一个数,将1入这个数对应的位置做&操作即可。

比如现在res=000000110(记录了2,3),来了一个3,做000000110&000000100。这样除了第三位其他位最终操后都是0,仅第三位关系到结果。
0000001001<<2,即1<<(3-1)得到。
这样就知道怎么判断一个数是否已经出现了!

来了一个数,已经判断没有出现,那么怎么标记为出现,以下次做判断呢?
同样,|操作有如下性质
1|1=1,1|0=1,0|0=0,因此来一个数,在确定没有出现过(即res对应位置为0),那么我们可以用|1的操作将其置位。

因此我们在代码中有了关键的一段,来判断是否出现过,若没有将其标记

if ((result_blk & (1 << (tmp-1))) == 0):
    result_blk = result_blk | (1<<(tmp - 1))

  • 如何用一次二重循环即检查行,又检查列?
for i in range(n):
    for j in range(n):
        #a[i][j]是按行遍历
        #a[j][i]是按列遍历
  • 如何用二重循环中的一层循环遍历到一个block(子数独)?
    遍历第1行时,需要将第1行9个数通过变换(即f(x))转换为第1块子数独

遍历第2行时,需要将第2行9个数通过变换(即f(x))转换为第2块子数独
……
因此可以做出下面的映射:

1->(1,1)
2->(1,2)
3->(1,3)
4->(2,1)
5->(2,2)
6->(2,3)
7->(3,1)
8->(3,2)
9->(3,3)

为了方便用(i,j)--->(m,n)表示映射关系;
每一块子数独都有3行,因此通过(i,j)映射到子数独应该为:

  • 首先由i决定映射到的行起始位置(i//3)*3,0-2为0,3-5为3,6-8为6
  • j每多3个,映射关系就换行!
  • 得到映射到的row为(i//3)*3+j//3

同理,列的映射关系为:

  • 首先由i决定子数独所在的块(知道块,比如第(2,3)块,列前面就要加6) 即i%3*3
  • 由j每去掉一个3都是放到前面的子数独中,剩下的放到自己映射的子数独上,即j%3

最终得到映射后的子数独位置为:
idx_row = (i//3) * 3 + j//3idx_col = (i%3) * 3 + j%3

最终代码为:

def sudoku(matrix):
    n = len(matrix)
    for i in range(n):
        result_row = result_col = result_blk = 0
        for j in range(n):   
            ## check row
            tmp = matrix[i][j]
            if ((result_row & (1 << (tmp-1))) == 0):
                result_row = result_row | (1<<(tmp - 1))
            else:
                print("row: " , i ,j)
                return False
            
            ## check col
            tmp = matrix[j][i]
            if ((result_col & (1 << (tmp-1))) == 0):
                result_col = result_col | (1<<(tmp - 1))
            else:
                print("col: " , j ,i)
                return False
            
            ## check block
            idx_row = (i//3) * 3 + j//3
            idx_col = (i%3) *3 + j%3
            tmp=matrix[idx_row][idx_col]
            if ((result_blk & (1 << (tmp-1))) == 0):
                result_blk = result_blk | (1<<(tmp - 1))
            else:
                print("blk: " , idx_row ,idx_col)
                return False
            
    return True
    

LeetCode(36.有效的数独)



class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        n = len(board)
        result_row = result_col = result_blk = 0
        for i in range(n):
            result_row = result_col = result_blk = 0
            for j in range(n):
                ## check row
                tmp = board[i][j]
                if(tmp!='.'):
                    tmp=int(tmp)
                    if ((result_row & (1 << (tmp-1))) == 0):
                        result_row = result_row | (1<<(tmp-1))
                    else:
                        print("row: ", i, j)
                        return False

                ## check column
                tmp = board[j][i]
                if(tmp!='.'):
                    tmp=int(tmp)
                    if ((result_col & (1 << (tmp-1))) == 0):
                        result_col = result_col | (1<<(tmp-1))
                    else:
                        print("col: ", j, i)
                        return False

                ## check block
                idx_row = (i//3) * 3 + j//3
                idx_col = (i%3)  * 3 + j%3
                tmp = board[idx_row][idx_col]
                if(tmp!='.'):
                    tmp=int(tmp)
                    if ((result_blk & (1 << (tmp-1))) == 0):
                        result_blk = result_blk | (1<<(tmp-1))
                    else:
                        print("block: ", idx_row, idx_col)
                        return False
        return True

旋转数组

def rotate(matrix):
    n = len(matrix)
    result = [[0] * (n) for i in range(n)]
    
    for i in range(n):
        for j in range(n):
            result[j][n-1-i] = matrix[i][j]
    
    for x in result:
        print(x, sep=" ")

上述算法空间复杂度O(n)


in-place
LeetCode(48)旋转图像
原地转换,只需要确定旋转时,四个点即可!

def ratoate_in_place(nums):
    n = len(nums)
    #按圈旋转,从最外圈--->向最内圈扩展,只需n//2即可!
    for layer in range(n//2):
        first = layer
        last = n-1-first
        for i in range(first , last ):
            offset = i-first;
            # 保存左上角
            top = nums[first][i]
            
            # 左下角->左上角
            nums[first][i]=nums[last-offset][first]
            
            # 右下角->左下角
            nums[last-offset][first] = nums[last][last-offset]
            
            # 右上角->右下角
            nums[last][last-offset]=nums[i][last]
            
            nums[i][last] = top
    for x in nums:
        print(x,sep = " ")
        

反转字符串

def reverse2(s):
    l = list(s)
    begin, end = 0, len(l) - 1
    while begin <= end
        l[begin], l[end] = l[end], l[i]
    return ''.join(l)

双指针即可!

最长连续子串

def find_consecutive_ones(nums):
    local = maximum = 0
    for i in nums:
        local = local + 1 if i==1 else 0
    maximum=max(maximum,local)
    return maximum

最大数

数组中有一个最大数,判断这个最大数是不是其他数的2倍,是返回索引。
本题无需逐个比较,仅需比较最大和第二大即可!

# O(n) time
# O(1) space
def largest_twice(nums):
    maximum = second = idx = 0
    for i in range(len(nums)):
        if (maximum < nums[i]):
            second = maximum
            maximum = nums[i]
            idx = i
        elif second < nums[i]:
            second = nums[i]
    return idx if (maximum >= second * 2) else -1

查找缺失的数

给定一个数组,长度为n,内部元素均在[1,n]之间,部分数重复,部分数不存在,求不存在的数?

LeetCode(448)找到所有数组中消失的数字

input:[4,3,2,7,8,2,3,1] output:[5,6]

本题用到了一个技巧,用数组的下标记录另一个数!
对于4,将a[3](第4个位置)置为负数
一轮下来,若某个数大于0,它对应的下标是不存在这个数组中的。

def findDisappearedNumbers2(nums):
    # For each number i in nums,
    # we mark the number that i points as negative.
    # Then we filter the list, get all the indexes
    # who points to a positive number
    for i in range(len(nums)):
        index = abs(nums[i]) - 1
        nums[index] = - abs(nums[index])

    return [i + 1 for i in range(len(nums)) if nums[i] > 0]


注意下面几个细节:

  • 本题和下面题的区别在于,本题所有数都大于0,不会出现0.且题目为注明数字只出现1次
  • 之前的遍历可能将后面的某个数变成了负数,因此遍历到这个负数时,要取其绝对值
  • 置负数时,需要-1,最后输出时加1。因为数组下标是从0开始的!

此题的变种题:
LeetCode(面试题17.04)消失的数字
此题用异或完成(利用一个数异或上本身为0)

class Solution {
    public int missingNumber(int[] nums) {
        int res=0;
        for(int i=0;i<nums.length;i++){
            res^=i;
            res^=nums[i];
        }
        res^=nums.length;
        return res;

    }
}
Last modification:April 22nd, 2020 at 02:03 am