来源经典算法解题实战
整型数组二
Product of Array Exclude Itself
Given an integers array A.
Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], calculate B WITHOUT divide operation.
Example
For A=[1, 2, 3], return [6, 3, 2].
一般的想法
def solution(arr):
length = len(arr)
result = []
for i in range(length):
for j in range(length):
m = 1
if i != j:
m *= arr[j]
result.append(m)
return result
每个元素都需要重新累乘得到, 可以将累乘的结果保存到左右数组中
def solution(arr):
length = len(arr)
result = []
left_arr = [1 for i in range(length)]
right_arr = [1 for i in range(length)]
for i in range(length):
if i > 0:
left_arr[i] = left_arr[i -1] * arr[i - 1]
right_arr[length - i - 1] = right_arr[ length - i] * arr[length - i]
for i in range(length):
result.append(left_arr[i] * right_arr[i])
# result = [left_arr[i]* rigjt_arr[i] for i in range(length)]
return result
同时可以将结果代替其中一个数组, 以减少内存的使用
def solution(arr):
length = len(arr)
# 数组长度小于2时, 直接返回[]
if length < 2:
return []
result = [1 for i in range(length)]
for i in range(1, length):
result[i] = result[i - 1] * arr[i - 1]
m = 1
for i in range(length-2, -1, -1):
m *= arr[i + 1]
result[i] = m * result[i]
return result
索引变换的时候有点懵, 不知道为什么. ?
Partition Array
Given an array nums of integers and an int k, partition the array (i.e move the elements in "nums") such that:
All elements < k are moved to the left
All elements >= k are moved to the right
Return the partitioning index, i.e the first index i nums[i] >= k.
If nums = [3,2,2,1] and k=2, a valid answer is 1.
数列中小于某值放在左边, 剩下的自然在右边.
- 注意的是在某结果判断后, 再对其操作, 原先的判断失效(犯的错误)
def solution(arr, k):
right = 0
length = len(arr)
for i in range(length):
# 注意第二个条件, 避免对调换后的数组再进行判断
while arr[i] >= k and length -right -1 < i:
right += 1
temp = arr[i]
arr[i] = arr[length - right]
arr[length - right] = temp
return length - right
或者是下面这个方法更清晰
def solution(arr, k):
length = len(arr)
right = length -1
left = 0
i = 0
while left <= right:
print(arr[i], arr[left], arr[right])
if arr[i] < k:
arr[i], arr[left] = arr[left], arr[i]
left += 1
else:
# arr[i], arr[right] = arr[right], arr[i]加上这句就错了, 因为如果这样调换, 会将未知的元素换到i位上, i++,从而没有判断.将需要的换到左边, 剩下的自然在右边
right -= 1
i += 1
return left
First Missing Positive
Given an unsorted integer array, find the first missing positive integer.
Example
Given [1,2,0] return 3, and [3,4,-1,1] return 2.
Challenge
Your algorithm should run in O(n) time and uses constant space.
看题的时候没注意是正整数,可以得到第一个缺少的整数
- 基本的方法和计数排序一样
- 注意的是在自身上交换, 交换的判断条件是:1.索引(变换)和元素不相等 和 2.交换的两个元素值不等 ;3.注意因为交换到指定索引处, 首先还需判断索引是否越界
- 将每一个元素交换到正确的位置.
如果暂时没有满足的位置, 就不处理. 因为每一个元素都会交换到相应位置.如果该位置和元素不对应,则说明该位置没有相应的元素. - 还有就是在循环外使用target=arr[i] - min_n, 在循环中arr[i] 值已经变化, 又犯了这样的错误
def solution(arr):
# 判断第一个正整数就不需要找最小值
min_n = min(arr)
length = len(arr)
for i in range(length):
target = arr[i] - min_n
# 一直交换元素直至不满足条件
while target <= length - 1 and target != i and arr[i] != arr[target]:
arr[i], arr[target] = arr[target], arr[i]
# 这里需要注意, 循环中arr[i]发生了变化
target = arr[i] - min_n
for i in range(length):
if arr[i] -min_n != i:
return i + min_n
else:
return min_n + length - 1
sum
标记: ??
Given an array of integers, find two numbers such that they can add up to a specific target number.
the function twoSum should return indices of two numbers such that they add up to the target, where index1 must be less than index2. Please note that your answer is not zero-based
numbers=[2, 7, 11, 15], target=9
return [1, 2]
you may assume that each input may would have exactly one
可以将目标值减去列表中每个数的结果作为字典的键, 在碰到下一个元素检查字典中是否含有该键.如果有则找到正确的两个数
def solution(arr, target):
hashdict = {}
for k, val in enumerate(arr):
dict_k = target - val
if dict_k in hashdict:
return [hashdict[dict_k], k + 1]
else:
hashdict[dict_k] = k + 1
return []
另一个是先排序, 再找
3 sum
Given an array s of n integers, are there elements a, b, c in s such that a+b+c=0?
find all unique triplets in the array which gives the sum of zero.
Example
For example, given array S = {-1 0 1 2 -1 -4}, A solution set is:
(-1, 0, 1)
(-1, -1, 2)
Note
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
将3 sum的问题转为2 sum问题. 用一个列表存储第一个0减第一个数字的结果, 然后求剩余的元素2 sum问题
def solution(arr):
result = []
temp = []
# 列表排序, 使结果从小到大
arr.sort()
for i in arr:
temp.append(0-i)
# 将3 sum转换为 2 sum问题
for i in range(len(arr)-2):
if arr[i] in arr[:i]:
continue
hashdict = {}
for k, value in enumerate(arr):
if k <= i:
continue
target = temp[i] - value
if value in hashdict:
result.append((arr[i], arr[hashdict[value]], arr[k]))
else:
hashdict[target] = k
return result
2sum 中不用字典, 排序后用j 和k 指向两个索引, 索引处元素相加如果大于目标值, 则k前移, 小于目标值, 则j后移, 知道j>=k
def solution(arr):
# 无效的情况
length = len(arr)
if length < 3:
return []
result = []
arr.sort()
for i in range(length-2):
if arr[i] in arr[:i]:
continue
# 2 sum
j = i + 1
k = length - 1
while j < k:
sum_three = arr[i] + arr[j] +arr[k]
if sum_three ==0:
result.append((arr[i], arr[j], arr[k]))
# ...
j += 1
elif sum_three > 0:
k -= 1
else:
j += 1
return result
3 sum closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target.
Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
两根指针i,j是o和length -1 , 他们的和 位于所有两个数之后的某个位置, 从大于(小于)某个状态单调减少(增加)到另一个状态
def solution(arr, target):
result = 2**31 -1
length = len(arr)
if length < 3:
return result
arr.sort()
for i, item_i in enumerate(arr):
# 留两个位置
if i > length -3:
break
# 这是用来干什么的?判断最小的是否大于target值, 如果大于就不在循环下去
if item_i + arr[i+1] + arr[i +2] > target:
# 这里应该判断下result 和他的和大小
result = min(result, item_i, arr[i + 1], arr[i + 2])
break
start = i + 1
end = length - 1
# 接下来是在循环体之内用两根指针
while start < end:
#接下来是start += 1 or end -= 1
# 先立个flag, 作为大于小于标记, 初始有两个状态
flag = 0
# 用一个temp变量保存他们的和
temp = item_i + arr[start] + arr[end]
result = min(abs(result - target), abs(temp - target))
if temp > target:
# flag变为-1, 假设是从小于状态变来的
if flag == -1:
break
# 如果不是突变的, 则flag=1
end -= 1
flag = 1
elif temp < target:
if flag == 1:
break
flag = -1
start += 1
else:
return temp
return result
# 上面的错误
# 没有分清result 和 abs(temp-target)的关系
# 分支语句的冗余
def solution(arr, target):
length = len(arr)
if length < 3:
return
result = 2**31 -1
arr.sort()
for i in range(length - 2):
temp = arr[i] + arr[i + 1] + arr[i + 2]
if temp > target:
result = min(abs(temp - target), result)
break
start = i + 1
end = length - 1
flag = 0
while start < end:
temp = arr[i] + arr[start] + arr[end]
if temp > target:
if flag == -1:
break
flag = 1
end -= 1
elif temp < target:
if flag == 1:
break
flag = -1
start += 1
else:
return temp
# 每次循环后都保存当前的结果, 以备最终使用
last_temp = temp
# 当跳出循环后, 说明从一个状态到另一个状态, 即last_temp到temp或者last_temp和temp相等, 这时求得结果
result = min(abs(temp - target), result, abs(last_temp - target))
return result
