0%

Self-Learned Algorithms - 01

Posted on Edited on In

Self-Learned Algorithms - 01

This is my learning note about algorithms.

Reference

350.两个数组的交集·2

https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/

题解

  • 简单的求交集的映射类题目，一开始想错的点就在于说明中的“输出结果中每个元素出现的次数”，而不是简单的出现元素。映射关系为<元素，出现次数>。
  • 进阶中“如果给定的数组已经排好序”是一个很大的提示，我们可以先给数组排序，再进行计算。

解法

  • 暴力解法：直接枚举
1
2
3
4
5
6
7
8
9
10
if len(nums2) < len(nums1):
  nums1, nums2 = nums2, nums1
output = []
for i in nums1:
  for j in nums2:
    if i == j:
      output.append(i)
      nums2.remove(j)
      break
return output
  • 哈希表
1
2
3
4
5
6
7
8
from collections import Counter
c1 = Counter(nums1)
ans = []
for n in nums2:
  if n in c1 and c1[n] > 0:
    ans.append(n)
    c1[n] -= 1
return ans

第5行中还可以用(count := hs.get(num, 0)) > 0进行判断。

  • 排序双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
nums1.sort()
nums2.sort()
r = []
left, right = 0, 0
while left < len(nums1) and right < len(nums2):
  if nums1[left] < nums2[right]:
    left += 1
  elif nums1[left] == nums2[right]:
    r.append(nums1[left])
    left += 1
    right += 1    
  else:
    right += 1
return r

或者可以不用新建数组，而是使用一个index将需要输出的数字替换到nums1[index]，最终输出nums1[:index]即可。（实际空间复杂度相同，但时间会增加）

  • 一个一行解法
1
return sum(([i] * j for i, j in (collections.Counter(nums1) & collections.Counter(nums2)).items()), [])

对于两个 Counter 对象，&操作意味着取两者都有的key, value取小的那一个。

14.最长公共前缀

https://leetcode-cn.com/problems/longest-common-prefix/

题解

解法

  • 水平扫描
1
2
3
4
5
6
7
if len(strs) == 0:
	return ''
s = strs[0]
for i in range(1, len(strs)):
	while strs[i].find(s) != 0 :
		s = s[:-1]
return s
  • 垂直扫描
1
2
3
4
5
6
7
8
if len(strs) == 0:
	return ''
for i in range(len(strs[0])):
	c = strs[0][i]
	for j in range(1,len(strs)):
		if i == len(strs[j]) or strs[j][i] != c:
			return strs[0][0:i]
return strs[0]
  • 最大和最小字符串的公共前缀
1
2
3
4
5
6
7
8
if not strs: 
  return ""
str0 = min(strs)
str1 = max(strs)
for i in range(len(str0)):
	if str0[i] != str1[i]:
		return str0[:i]
return str0

min()和max()是找到数组中字典序最小和最大的字符串。一个很新奇的思路。（时间减少，内存消耗增加）

  • zip迭代
1
2
3
4
5
6
7
s = ""
for i in zip(*strs):
	if len(set(i)) == 1:
		s += i[0]
	else:
		break           
return s

zip 打包成元素列表，同时利用set()函数的不重复性。

官方文档对zip(*iteration)的解释：创建一个聚合了来自每个可迭代对象中的元素的迭代器。 返回一个元组的迭代器，其中的第 i 个元组包含来自每个参数序列或可迭代对象的第 i 个元素。 当所输入可迭代对象中最短的一个被耗尽时，迭代器将停止迭代。 当只有一个可迭代对象参数时，它将返回一个单元组的迭代器。 不带参数时，它将返回一个空迭代器。

（但时间和内存消耗都比水平扫描要多）

122.买卖股票的最佳时机·2

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

题解

  • 不能参与多笔交易。换句话讲，我们只能在手上没有股票的时候买入
  • 尽可能地多进行交易。把握住机会，在每一次涨跌的时候，低价卖入高价卖出，就可以使利益达到最大化

解法

  • 线性规划：第i天只有两种状态，不持有或持有股票，当天不持有股票的状态可能来自昨天卖出或者昨天也不持有，同理，当天持有股票的状态可能来自昨天买入或者昨天也持有中，取最后一天的不持有股票状态就是问题的解
1
2
3
4
5
6
7
8
9
10
if not prices:
	return 0
n = len(prices)
dp = [[0]*2 for _ in range(n)]
# dp[i][0]表示第i天不持有股票, dp[i][1]表示第i天持有股票
dp[0][0], dp[0][1] = 0, - prices[0]
for i in range(1, n):
	dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
	dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
return dp[n-1][0]

但dp的运行时间和内存消耗都要大。

  • 贪心：算法题（×） 脑筋急转弯题( √ ），只要今天价格小于明天价格就在今天买入然后明天卖出
1
2
3
4
5
ans = 0
for i in range(1, len(prices)):
	if prices[i] > prices[i-1]:
		ans += prices[i] - prices[i-1]
return ans

189.旋转数组

https://leetcode-cn.com/problems/rotate-array/

题解

  • 要求使用空间复杂度为 O(1) 的原地算法。（限制了直接拼接构造新数组sad不过还是有trick可以的）
  • 至少有三种不同的方法可以解决这个问题。

解法

  • 一行切片：按着切片下标修改值，而不是nums修改的地址重新指向右边的临时地址（不写切片无法AC，因为不是原地）
1
nums[:] = nums[-k % len(nums):] + nums[:-k % len(nums)]

或者（空间O(1)，速度提升）

1
nums[:] = (nums[i] for i in range(-(k % len(nums)), len(nums) - k % len(nums)))

k%n是为了简化计算，比如数组长度为 7，旋转 8 位其实就相当于旋转 1 位，这样减少了循环次数

  • 三次反转：反转前n-k个，反转后k个，反转全部
1
2
3
4
5
6
7
8
9
10
11
12
13
n = len(nums)
k = k % n
if n < 2:
	pass
else:
	def reverse(nums, t, s):
		while t < s:
			nums[t], nums[s] = nums[s], nums[t]
			t += 1
			s -= 1
  reverse(nums, 0, n-1)
  reverse(nums, 0, k-1)
  reverse(nums, k, n-1)

（时间和空间上都比一行切片要优秀）

1
2
3
4
5
6
7
8
9
10
count,index,temp = 0,0,nums[0]
done_index = [0]
while count < len(nums):
  count,target = count+1, (index + k) % len(nums)
  temp,nums[target] = nums[target],temp
  if target not in done_index:
  	index = target
  elif target + 1 < len(nums):
  	index,temp = target + 1,nums[target + 1]
  done_index.append(index)

27.原地删除

https://leetcode-cn.com/problems/remove-element/

题解

  • 没什么好说的，只能说python天下第一吧（？）

解法

  • 很暴力
1
2
3
while val in nums:
	nums.remove(val)
return len(nums)
  • 倒序遍历：在正向遍历的过程中，删除list的多个元素，index值不能变，比较麻烦。反向遍历就不会存在这个问题。
1
2
3
4
for i in range(len(nums)-1, -1, -1):
  if(nums[i] == val):
  	nums.pop(i)
return len(nums)
  • 双指针
1
2
3
4
5
6
7
i = 0
for j in range(0, len(nums)):
	# 如果nums[j]不等于val, 则将nums[j]赋值给nums[i]即可, i自增
	if nums[j] != val:
		nums[i] = nums[j]
		i += 1
return i

类似题目

26.删除排序数组中的重复项

283.移动O

66.加一

https://leetcode-cn.com/problems/plus-one/

题解

  • 看起来很简单的题目，只要考虑两种情况：9和其他数字就可以了

解法

  • 一次遍历：遍历是否为9，是9变0，不是9返回即可
1
2
3
4
5
6
7
for i in range(1,len(digits)+1):
  if digits[-i] != 9:
    digits[-i] += 1
    return digits
  digits[-i] = 0
digits.insert(0,1)
return digits
  • python抖机灵法
1
2
3
a = [i *10**index for index,i in enumerate(digits[::-1])]
num = sum(a) + 1
return [int(x) for x in str(num)]
1
2
3
4
5
6
7
8
9
nums_str = ""
for i in digits:
	nums_str =nums_str+str(i)

nums_int = int(nums_str)+1
res = []
for i in str(nums_int):
	res.append(int(i))
return res

（抖机灵法2的内存消耗居然更少呢）

1.两数之和

https://leetcode-cn.com/problems/two-sum/

题解

  • 可以暴力解，但是有没有更好的办法呢？

解法

  • 暴力解法：最简单的暴力解法就是两层循环，两数相加再判断是否为目标值，但其实一层循环寻找target - x就可以了
1
2
3
4
5
6
7
n = len(nums)
  for x in range(n):
    a = target - nums[x]
    if a in nums:
      y = nums.index(a) 
      if x != y: 
      	return x,y
  • 哈希表：如果有重复值字典也会刷新
1
2
3
4
5
dct = {}
for i, n in enumerate(nums):
  if target - n in dct:
  	return [dct[target - n], i]
  dct[n] = i

如果先把数组转化成字典的话，target-n的值很有可能会等于n，所以放在后面更新字典。（哈希解法的速度比暴力快20倍）