KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Special binary strings are binary strings with the following two properties:

The number of 0‘s is equal to the number of 1‘s. Every prefix of the binary string has at least as many 1‘s as 0‘s.

You are given a special binary string s.

A move consists of choosing two consecutive, non-empty, special substrings of s, and swapping them. Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string.

Return the lexicographically largest resulting string possible after applying the mentioned operations on the string.

Example 1:

Input: s = “11011000”
Output: “11100100”
Explanation: The strings “10” [occuring at s[1]] and “1100” [at s[3]] are swapped.
This is the lexicographically largest string possible after some number of swaps.


Example 2:

Input: s = “10”
Output: “10”


Constraints:

1 <= s.length <= 50 s[i] is either '0' or '1'.
* s is a special binary string.

题目大意：

Special string由0和1组成，数目一样且每个前缀1的数目大于等于0的数目。可以交换其内部的子特别字符串，让其数值最大

解题思路：

一开始考虑用统计presum的方法LeetCode 696 Count Binary Substrings，然后如果后者1的数目大于前者0的数目，表示可以交换。但这里只考虑到相邻特别子串的关系，并没有考虑特别字串的内部也是需要排序的。

此题特别串是含有递归定义，所以考虑DFS。首先，一个特别字符串是由多个特别子串连续组成，所以需要找出它们，且进行排序
第二，更难的是每个字串内部特别字串也需要重新排序比如11011000中的10和1100就需要互换。这个串不是直接由内部特殊字串组成而是1+特殊串+0组成(递归式). 根据特殊串定义，是以1开头0结束，类似于统计左右括号数，这点规律比较难找。

总结而已，这题是catalan递归但不是递归两边是，多边。且每个递归都是由总结出来的规律获得1+f(s[start+1:i])获得

解题步骤：

N/A

注意事项：

  1. 如果遇到0，count要减一
  2. 倒序排序：parts.sort(reverse=True)

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def makeLargestSpecial(self, s: str) -> str:
	parts = []
	count = 0
	start = 0
	for i in range(len(s)):
		if s[i] == '1':
			count += 1
		else:
			count -= 1 #attn
		if count == 0:
			sorted_part = '1'+ self.makeLargestSpecial(s[start+1:i]) + '0'
			parts.append(sorted_part)
			start = i + 1
	parts.sort(reverse=True) #attn
	return ''.join(parts)

算法分析：

next时间复杂度为O(n^2)，空间复杂度O(n)

错误的做法，只考虑到相互关系，没考虑内部关系

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def makeLargestSpecial(self, s: str) -> str:
	count, presum = 1, []
	for i in range(1, len(s)):
		if s[i] == s[i-1]:
			count += 1
		else:
			presum.append(count)
			count = 1
	if count > 0:
		presum.append(count)
	print(presum)

	def move(presum):
		is_moved = False
		for i in range(2, len(presum), 2):
			if presum[i] > presum[i-1]:
				presum[i-2] += -presum[i-1] + presum[i]
				presum[i+1] += -presum[i] + presum[i-1]
				presum[i-1], presum[i] = presum[i], presum[i-1]
				print(presum)
				is_moved = True
		return is_moved
	
	move_res = True
	while move_res:
		move_res = move(presum)

	res, c = '', '1'
	for n in presum:
		res += c * n
		if c == '1':
			c = '0'
		else:
			c = '1'
	print(res)
	return res

Posted on Edited on Disqus:

LeetCode



Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal.

A subarray is a contiguous part of the array.

Example 1:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4
Explanation: The 4 subarrays are bolded and underlined below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]


Example 2:

Input: nums = [0,0,0,0,0], goal = 0
Output: 15


Constraints:

`1 <= nums.length <= 3 104*nums[i]is either0or1. *0 <= goal <= nums.length`

题目大意：

有0和1组成的字符串，求所有子数组的和等于goal的个数

解题思路Presum(推荐)：

求子数组和第一时间想到presum，然后就是presum-goal是否在hashmap中，类似于Two sum。

解题步骤：

N/A

注意事项：

  1. presum初始值为0，因为如果单元素数组，才能得到它的差值。
  2. val_to_freq的计算要在循环中，类似于Two sum，不能提前用Counter计算，否则会有重复，比如[0, 0], goal=0, 不应该为4.

Python代码：

1
2
3
4
5
6
7
8
9
10
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
	presum = [0]
	for i in range(len(nums)):
		presum.append(presum[-1] + nums[i])
	val_to_freq, res = collections.defaultdict(int), 0
	for i in range(len(presum)):
		if presum[i] - goal in val_to_freq:
			res += val_to_freq[presum[i] - goal]
		val_to_freq[presum[i]] += 1 #attn
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

算法II解题思路Sliding Window：

此法虽然空间复杂度较优，但较难想。求字串的和可以考虑用Two pointers两边夹。这里求所有可能性，比如0011100, goal=3, 必须包括前缀0和后缀0，所以用Two pointers最长串的模板
类似于LeetCode 340 Longest Substring with At Most K Distinct Characters，不满足条件为窗口和大于goal，所以满足条件为小于等于goal(类似于at most k)。
所以要用at_most(goal) - at_most(goal - 1)才能得到最后结果。
计算的时候，是i-left+1代表窗口和<=subgoal的以nums[i]为结尾的子数组个数，比如10101, i指向最后一个1, left指向第一个0, res是4个，对应1, 01, 101, 0101

注意事项：

  1. 模板满足条件在内循环外，所以计算结果在内循环结束后。
  2. subgoal如果小于0，返回0。比如goal为0，nums=[0,0]

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
	def at_most(subgoal):
		if subgoal < 0: #attn
			return 0
		window_sum, left, res = 0, 0, 0
		i = 0
		for i in range(len(nums)):
			window_sum += nums[i]
			while window_sum > subgoal:
				window_sum -= nums[left]
				left += 1
			res += i - left + 1 # ending with nums[i]
		return res

	return at_most(goal) - at_most(goal - 1)

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

Posted on Disqus:

LeetCode



Koko loves to eat bananas. There are n piles of bananas, the i<sup>th</sup> pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4


Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30


Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23


Constraints:

1 <= piles.length <= 10<sup>4</sup> piles.length <= h <= 10<sup>9</sup>
* 1 <= piles[i] <= 10<sup>9</sup>

题目大意：

猴子吃n堆香蕉，要在h小时内吃完，求每小时吃的最少k根才能在限定时间内全部吃完。

解题思路：

枚举法，如果对于[3,6,7,11], k=3, 怎么算出多少小时呢? 数组每个数除以k向上取整求和即可，O(n)完成。怎么可以更快找到答案呢，很明显是二分法logn找答案，每次用O(n)算实际吃了多少小时。总的复杂度是O(nlogn).
所以此题是数值二分法，我也曾想过排序，但排序只能影响计算小于k值的小时数，不能优化后半段的，所以不用排序，而且数值二分法也不要求排序。

解题步骤：

数值二分法模板

注意事项：

  1. start是从1开始，不是min(piles)。最大值取max(piles)因为跟取整型最大值是一样的。这样也可以避免单独处理单元素数组。
  2. epsilon取0.5. 一般整数题都取0.5
  3. mid是除2获得不是//2
  4. mid作为参数输入到get_hours()要去int(mid)与题目一致，因为题目的k是整数
  5. 模板中h==hours时，不能return，要继续在左半区找，因为要达到误差epsilon内才会停止。类似于first_position

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def minEatingSpeed(self, piles: List[int], h: int) -> int:
	#if len(piles) == 1: # attn
	 #   return math.ceil(piles[0] / h)
	# piles.sort()
	
	def get_hours(piles, k):
		return sum([math.ceil(n / k) for n in piles])


	# start, end = piles[0], piles[-1] # 3, 4
	start, end = 1, max(piles) # attn: 1 rather than min(piles)
	while start + 0.5 < end: # attn: use 0.5
		mid = start + (end - start) / 2 # attn /2 not // 2 | 7, 5, 4            
		hours = get_hours(piles, int(mid))  # attn: int(mid) | 5, 8, 8
		if h >= hours: # eat slower, attn 8 > 5
			end = mid # end=7, 5, 4
		else:
                start = mid

算法分析：

next时间复杂度为O(nlogn)，空间复杂度O(n)

Posted on Disqus:

LeetCode



You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>), where u<sub>i</sub> is the source node, v<sub>i</sub> is the target node, and w<sub>i</sub> is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:



Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2


Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1


Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1


Constraints:

1 <= k <= n <= 100 1 <= times.length <= 6000
times[i].length == 3 1 <= u<sub>i</sub>, v<sub>i</sub> <= n
u<sub>i</sub> != v<sub>i</sub> 0 <= w<sub>i</sub> <= 100
All the pairs (u<sub>i</sub>, v<sub>i</sub>) are *unique. (i.e., no multiple edges.)

题目大意：

求从某一个点出发的所有能到达的点中的最短时间。若不能都到达返回-1

解题思路：

单源最短路径的最大值，如果有点不能到达返回-1.用BFS+Heap的模板

解题步骤：

N/A

注意事项：

  1. 用queue

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
	# build graph
	graph = collections.defaultdict(list)
	for e in times:
		graph[e[0]].append((e[1], e[2]))
	heap = [(0, k)] # weight, node
	visited = {k: 0}
	while heap:
		weight, node  = heapq.heappop(heap)
		for neighbor, _weight in graph[node]:
			if neighbor in visited and visited[neighbor] <= weight + _weight:
				continue
			heapq.heappush(heap, (weight + _weight, neighbor))
			visited[neighbor] = weight + _weight
	return max(visited.values()) if len(visited) == n else -1

算法分析：

next时间复杂度为O(V+E)，空间复杂度O(V)

Posted on Edited on Disqus:

算法思路：

图用邻接表为输入，思路用Queue实现, 还要一个机制记录节点访问过没有，可以用HashSet，同时它作为结果存储BFS访问结果。
BFS多用于找最短路径
DFS多用于快速发现底部节点和具体路劲问题（如路径和或打印路径）。

BFS优缺点：
同一层的所有节点都会加入队列，所以耗用大量空间
仅能非递归实现
相比DFS较快，空间换时间
适合广度大的图
找环的话需要用拓扑排序

DFS优缺点：
无论是系统栈还是用户栈保存的节点数都只是树的深度，所以空间耗用小
有递归和非递归实现
由于有大量栈操作（特别是递归实现时候的系统调用），执行速度较BFS慢
适合深度大的图
找环的话比较容易实现

如果BFS和DFS都可以用，建议用BFS，因为工业应用中，BFS不用有限的栈空间，可以利用到所有内存。
BFS题目问自己是否需要按层遍历，是否需要visited

注意事项：

  1. 坐标型BFS，注意输入为(i, j)时候，x = node[0] + _dx[0], 用x不要用输入的i
  2. deque([(start[0], start[1])]), set([(startx, starty)])
  3. board[x][y] == ‘+’ 注意矩阵的其他不能遍历的元素，如L200中的0

其他:

  1. 只要把节点放入队列立即标记其为访问，不要在出列的时候才标记。否则同一个节点会入列多次。
    比如下图, 入列顺序为1,2,3,4,4。4入列了两次。
  2. 矩阵的遍历用方向List: OFFSETS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

图遍历

只有是对所有节点BFS题型才需要将visited作为参数传入

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def bfs(self, graph, start) -> List[int]:
	queue, res = deque([start]), []
	visited = {start}
	while queue:
		node = queue.popleft()
		res.append(node)
		for neighbor in graph[node]:
			if neighbor in visited:
				continue
			queue.append(neighbor)
			visited.add(neighbor)
	return res

树模板只要把visited去掉，neighbor改成left和right

注意事项：

  1. visited = {start}不写set([start])
  2. if neighbor in visited在循环里，不是if node in visited
  3. 在bfs_layer2，res.append(level)

计算最短距离的图遍历(最常考的模板)

  • 只要加line 4和14
  • visited在函数内定义
  • 遇到target就返回最短距离，若离开循环返回-1，问清楚是否存在路径不存在的情况
  • 求距离公式不需要用min，因为这个遍历保证了最短距离了。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def bfs_layer(self, graph, start, target) -> int:
	queue = deque([start])
	visited = {start}
	distance = {start: 1}
	while queue:
		node = queue.popleft()
		if node == target:
			return distance[node]
		for neighbor in graph[node]:
			if neighbor in visited:
				continue
			queue.append(neighbor)
			visited.add(neighbor)
			distance[neighbor] = distance[node] + 1
	return -1

写法2

1
2
3
4
5
6
7
8
9
10
11
12
13
def bfs_layer_v2(self, graph, start, target) -> int:
	queue = deque([(start, 1)])
	visited = {start}
	while queue:
		node, distance = queue.popleft()
		if node == target:
			return distance
		for neighbor in graph[node]:
			if neighbor in visited:
				continue
			queue.append((neighbor, distance + 1))
			visited.add(neighbor)
	return -1

按层遍历

核心是加这一行for _ in range(len(queue))
具体还要加line 5, 6和14, 15. 二叉树不需要visited。能用distance dict就尽量不用此法，因为多了一个循环。

注意事项：

  1. 关键行： 多这一行for循环 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def bfs_layer2(self, graph, start) -> List[List[int]]:
	queue, res = deque([start]), []
	visited = {start}
	while queue:
		level = []
		for _ in range(len(queue)):
			node = queue.popleft()
			level.append(node)
			for neighbor in graph[node]:
				if neighbor in visited:
					continue
				queue.append(neighbor)
				visited.add(neighbor)
		res.append(level)
	return res

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
 * graph: 邻接表
 * visited: 记录已访问节点，避免重复访问
 * start: BFS的根节点
 */
public void bfs(HashMap<Integer, LinkedList<Integer>> graph, HashSet<Integer> visited, int start){
	int num=0;
	Queue<Integer> q=new LinkedList<>();
	q.offer(start);
	visited.add(start);
	while(!q.isEmpty()){
		int node = q.poll();
		LinkedList<Integer> children = graph.get(node);
		for(int child : children){
			if (!visited.contains(child)){
				q.offer(child);
				visited.add(child);
			}
		}
	}
}

错误算法：

问题是加入到queue里面的child没有去重，这样容易queue爆炸式增长。

1
2
3
4
5
6
7
8
9
10
11
12
13
public void bfs(HashMap<Integer, LinkedList<Integer>> graph, HashSet<Integer> visited, int start){
	Queue<Integer> q=new LinkedList<>();
	q.offer(start);
	while(!q.isEmpty()){
		int node = q.poll();
		visited.add(node);
		LinkedList<Integer> children = graph.get(node);
		for(int child : children){
			if (!visited.contains(child))
				q.offer(child);
		}
	}
}

按层次遍历：

第一个思路是三重循环，先queue，然后该层所有节点，最后该层每一个节点的儿子。关键在于size = q.size();

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void bfsByLayer3(HashMap<Integer, LinkedList<Integer>> graph, int start){
	Queue<Integer> q=new LinkedList<>();
	int layer = 1;
	q.offer(start);
	while(!q.isEmpty()){
		int size = q.size();
		for(int i = 0; i < size; i++) {// loop this layer
			int node = q.poll();
			System.out.println("node:"+node+" in layer "+ layer);
			LinkedList<Integer> children = graph.get(node);
			for(int child : children){// loop its children
				q.add(child);
			}
		}
		layer++;
	}
}

上述代码三重循环看似可读性不够好，所有可以用hashMap来记录每个点的距离从而减少第二重循环。
nodeToHeight.put(start, 1);
nodeToHeight.put(child, nodeToHeight.get(node) + 1);

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void bfsByLayer4(HashMap<Integer, LinkedList<Integer>> graph, int start){
	Queue<Integer> q = new LinkedList<>();
	q.offer(start);
	Map<Integer, Integer> nodeToHeight = new HashMap<>();
	nodeToHeight.put(start, 1);
	while(!q.isEmpty()){

		int node = q.poll();
		System.out.println("node:"+node+" in layer "+ nodeToHeight.get(node));
		LinkedList<Integer> children = graph.get(node);
		for(int child : children){// loop its children
			q.add(child);
			nodeToHeight.put(child, nodeToHeight.get(node) + 1);
		}
		
	}
}

  1. q.isEmpty() && !q2.isEmpty()

第三思路是用两个队列来实现：用第一个队列存储该层的节点，第二个队列存储第一个队列中节点的儿子节点，
也就是下一次的节点。此思路比较容易实现。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 假设不循环
 * graph: 邻接表
 * start: BFS的根节点
 */
public void bfsByLayer(HashMap<Integer, LinkedList<Integer>> graph, int start){
	Queue<Integer> q=new LinkedList<>();
	Queue<Integer> q2=new LinkedList<>();
	int layer = 1;
	q.offer(start);
	while(!q.isEmpty()){
		int node = q.poll();
		System.out.println("node:"+node+" in layer "+ layer);
		LinkedList<Integer> children = graph.get(node);
		for(int child : children){
			q2.offer(child);
		}
		if(q.isEmpty() && !q2.isEmpty()){
			q = q2;
			q2 = new LinkedList<>(); 
			layer++;
		}
	}
}

第四思路是只用一个队列来实现：层与层之间用结束符间隔，每遇到结束符，表示该层访问结束，下一层的节点也准备好
（不会再有新的节点加入到这一层），此时再往队列加入新的结束符。此思路对数据有一定限制，实现起来注意事项较多。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void bfsByLayer2(HashMap<Integer, LinkedList<Integer>> graph, int start){
	Queue<Integer> q=new LinkedList<>();
	int layer = 1;
	q.offer(start);
	q.offer(-1);
	while(!q.isEmpty()){
		int node = q.poll();
		if(node == -1){
			//确保有非结束符节点
			if(q.size()>0){
				q.offer(-1);
				layer++;
			}
			continue;
		}
		System.out.println("node:"+node+" in layer "+ layer);
		LinkedList<Integer> children = graph.get(node);
		for(int child : children){
			q.offer(child);
		}
	}
}

算法分析：

时间复杂度为O(n)，w为树的所有层里面的最大长度，空间复杂度O(w)。

Free mock interview