leetcode-数组1

– 到最近的人的最大距离

方法一:从左到右遍历找0和1的差值,只考虑右边的差。
从右到左遍历找0和1的差值,并与上一步的值进行比较,小的就是最近的人。
在最近的人数组中找到距离max

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):                                                                 
def maxDistToClosest(self, seats):
ans = [0]*len(seats)
for i in range(len(seats)):
if seats[i]==1:
index = i
else:
ans[i] = abs(i-index)
for i in range(len(seats)-1,-1,-1):
if seats[i]==1:
index = i
else:
ans[i] = min( abs(i-index), ans[i])
return max(ans)

方法二:找到连续0的个数,考虑两个1中间的0 和首尾的0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):                                                                 
def maxDistToClosest(self, seats):
"""
:type seats: List[int]
:rtype: int
"""
count = 0
ans = []
for i in seats:
if i==0:
count+=1
else:
ans.append(count)
count=0
ans.append(count)
max_1 = max(ans)
if max_1%2 == 0:
max_1 = max_1 / 2
else:
max_1 = max_1 / 2 +1
return max(max_1,ans[0], ans[-1])
第二种方法在内存和耗时上效果更好。

– 转置矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def transpose(self, A):
"""
:type A: List[List[int]]
:rtype: List[List[int]]
"""
n=len(A)
m = len(A[0])
B=[[0]*n for k in range(m)]
for i in range(n):
for j in range(m):
B[j][i] = A[i][j]
return B

– 公平的糖果交换

A[i] 是爱丽丝拥有的第 i 块糖的大小,B[j] 是鲍勃拥有的第 j 块糖的大小。

因为他们是朋友,所以他们想交换一个糖果棒,这样交换后,他们都有相同的糖果总量。

返回一个整数数组 ans,其中 ans[0] 是爱丽丝必须交换的糖果棒的大小,ans[1] 是 Bob 必须交换的糖果棒的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def fairCandySwap(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: List[int]
"""
sum1=sum(A)
sum2=sum(B)
c = set(B)
d = (sum1-sum2)//2
for i in A:
if i-d in c:
return[i,i-d]

尽量循环里少计算

– 单调数列

如果数组是单调递增或单调递减的,那么它是单调的。

如果对于所有 i <= j,A[i] <= A[j],那么数组 A 是单调递增的。 如果对于所有 i <= j,A[i]> = A[j],那么数组 A 是单调递减的。

当给定的数组 A 是单调数组时返回 true,否则返回 false。

我的思路是对单调的元素个数计数。耗时较大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def isMonotonic(self, A):
"""
:type A: List[int]
:rtype: bool
"""
count1 = 0
count2 = 0
for i in range(1,len(A)):
if A[i]<=A[i-1]:
count1+=1
if A[i]>=A[i-1]:
count2+=1
if count1==len(A)-1 or count2==len(A)-1:
return bool(1)
else:
return bool(0)
先根据第一个和最后一个定单调减还是单调加。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def isMonotonic(self, A):
"""
:type A: List[int]
:rtype: bool
"""
flag = A[-1] - A[0] # 定基调
#如果是加 ,for循环查看中间是否有小于的
if flag > 0:
for i in range(len(A) - 1):
if A[i + 1] - A[i] < 0:
return False
#如果是减 ,for循环查看中间是否所有有大于的
else:
for i in range(len(A) - 1):
if A[i + 1] - A[i] > 0:
return False
return True