python刷题笔记怎么改_数组-Python刷题笔记

在一个二维数组中(每个一维数组的长度相同)，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

逐行逐列包里查找

# -*- coding:utf-8 -*-

class Solution:

# array 二维列表

def Find(self, target, array):

# write code here

if not array:

return

for i in range(row):

for j in range(col):

if array[i][j]==target:

return True

return False

# -*- coding:utf-8 -*-

class Solution:

# array 二维列表

def Find(self, target, array):

# write code here

if not array:

return

for row in array:

if target in row:

return True

return False

每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。所以左上是最小，右下是最大。从左下角开始搜索或者右上角开始会比较简单处理。如果使用左下角开始，逐个对比，比目标小就右移，比目标大就上移。直到找到目标。

# -*- coding:utf-8 -*-

class Solution:

# array 二维列表

def Find(self, target, array):

# write code here

if not array:

return

row=len(array)

col=len(array[0])

i = row - 1

j = 0

while (i >= 0 and j <= col-1) :

if array[i][j] == target:

return True

elif array[i][j] < target:

j += 1

elif array[i][j] > target:

i -= 1

return False

【tips】：

while loop 边界条件

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

逐个读取储存至列表，如果出现重复直接输出

# -*- coding:utf-8 -*-

class Solution:

# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]

# 函数返回True/False

def duplicate(self, numbers, duplication):

# write code here

record = []

for i in numbers:

if i in record:

duplication[0] = i

return True

else:

record.append(i)

return False

【tips】：

需要不断用 in 查询，整体复杂度较高 O(n2)

Counter

# -*- coding:utf-8 -*-

import collections

class Solution:

# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]

# 函数返回True/False

def duplicate(self, numbers, duplication):

# write code here

flag=False

c=collections.Counter(numbers)

for k,v in c.items():

if v>1:

duplication[0]=k

flag=True

break

return flag

【tips】：

>>> from collections import *

>>> c = Counter()

>>> c

Counter()

>>> c = Counter("gallahad")

>>> c

Counter({'a': 3, 'l': 2, 'g': 1, 'h': 1, 'd': 1})

>>> b = Counter({'red':4,'blue':2})

>>> b

Counter({'red': 4, 'blue': 2})

>>> a = Counter(cats = 4,dogs = 8)

>>> a

Counter({'dogs': 8, 'cats': 4})

Counter 对象常见操作

>>> c

Counter({'a': 5, 'b': 4, 'd': 2, 'c': -3})

>>> sum(c.values())# 统计所有的数目

>>> list(c)# 列出所有唯一的元素

['a', 'c', 'b', 'd']

>>> set(c)# 转换为set

set(['a', 'c', 'b', 'd'])

>>> dict(c)# 转换为常规的dict

{'a': 5, 'c': -3, 'b': 4, 'd': 2}

>>> c.items()# 转换为(elem,cnt)对构成的列表

[('a', 5), ('c', -3), ('b', 4), ('d', 2)]

>>> c.most_common()[:-4:-1]# 输出n个数目最小元素

[('c', -3), ('d', 2), ('b', 4)]

>>> c += Counter()# 删除数目为0和为负的元素

>>> c

Counter({'a': 5, 'b': 4, 'd': 2})

>>> Counter(dict(c.items()))# 从(elem,cnt)对构成的列表转换为counter

Counter({'a': 5, 'b': 4, 'd': 2})

>>> c.clear()# 清空counter

>>> c

Counter()

>>> c = Counter(a=3,b=1,c=-2)

>>> d = Counter(a=1,b=2,c=4)

>>> c+d#求和

Counter({'a': 4, 'b': 3, 'c': 2})

>>> c-d#求差

Counter({'a': 2})

>>> c & d#求交集

Counter({'a': 1, 'b': 1})

>>> c | d#求并集

Counter({'c': 4, 'a': 3, 'b': 2})

items

列表的形式返回可以遍历的值

voc2 = {'name':'xin','sex':'male','job':'AI'}

output = voc2.items()

print(type(output))

#

print(output)

# dict_items([('name', 'xin'), ('sex', 'male'), ('job', 'AI')])

for k,v in output:

print(k,v)

# name xin

# sex male

# job AI

【Q】：

Counter 返回值中是按照出现次序降序排列，但是在遍历 items 时却是按原有出现顺序遍历。

Why？

长度为n的数组里的所有数字都在0到n-1的范围内，所以可以利用现有数组设置标志，不需要额外数组或者 hash table.

# -*- coding:utf-8 -*-

class Solution:

# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]

# 函数返回True/False

def duplicate(self, numbers, duplication):

# write code here

length = len(numbers)

for i in range(length):

val = numbers[i]

if val >= length:

val -= length

if numbers[val] >= length:

duplication[0] = val

return True

numbers[val] = numbers[val] + length

return False

类似3的思路，但是更方便。

遍历一次，依次把对应位上数字变负，重复见到的时候对应位会负负得正的，直接输出

# -*- coding:utf-8 -*-

class Solution:

# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]

# 函数返回True/False

def duplicate(self, numbers, duplication):

# write code here

for i in range(len(numbers)):

val = abs(numbers[i])

numbers[val] = -numbers[val]

if numbers[val] > 0:

duplication[0] = val

return True

return False

给定一个数组A[0,1,...,n-1],

请构建一个数组B[0,1,...,n-1],

其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。

不能使用除法。

注意：规定

B[0] = A[1] * A[2] * ... * A[n-1]，

B[n-1] = A[0] * A[1] * ... * A[n-2];

按照题目，两次遍历完成

# -*- coding:utf-8 -*-

class Solution:

def multiply(self, A):

# write code here

Alength = len(A)

B = [None]*Alength

for x in range(Alength):

val = 1

for y in range(Alength):

if y != x:

val *= A[y]

B[x] = val

return B

B[i] 的值可以看作下图的矩阵中每行的乘积。

下三角用连乘可以很容求得，上三角，从下向上也是连乘。

先算下三角中的连乘: B[i] = B[i-1] * A[i-1]

然后倒过来按上三角中的分布规律，把另一部分也乘进去。

B0

1

A1

A2

...

A n-2

A n-1

B1

A0

1

A2

...

A n-2

A n-1

B2

A0

A1

1

...

A n-2

A n-1

...

...

...

...

...

...

...

Bn-3

A0

A1

...

1

A n-2

A n-1

B n-2

A0

A1

...

A n-3

1

A n-1

B n-1

A0

A1

...

A n-3

A n-2

1

# -*- coding:utf-8 -*-

class Solution:

def multiply(self, A):

# write code here

if not A:

return []

Alength = len(A)

B = [None] * Alength

# 左下角乘一遍 后一项比前一项多一个也就是说

#B[i] = B[i-1] * A[i-1]

B[0] = 1

for i in range(1,Alength):

B[i] = B[i-1] * A[i-1]

# 右上角同理，不过需要反着来

print(B)

tmp = 1

for i in range(Alength-2, -1, -1):

B[i] = B[i+1] * A[i+1]

return B

【Q】：

后半段计算如果写成：

for i in range(Alength-2, -1, -1):

B[i] = B[i+1] * A[i+1]

return B

结果不对，为什么？怎么改

Reference