KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode 133 Clone Graph

Given a reference of a node in a connected#Connected_graph) undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List neighbors;
}

Test case format:

For simplicity sake, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val = 1, the second node with val = 2, and so on. The graph is represented in the test case using an adjacency list.

Adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Example 1:

**Input:** adjList = [[2,4],[1,3],[2,4],[1,3]]
**Output:** [[2,4],[1,3],[2,4],[1,3]]
**Explanation:** There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:

**Input:** adjList = [[]]
**Output:** [[]]
**Explanation:** Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3:

**Input:** adjList = []
**Output:** []
**Explanation:** This an empty graph, it does not have any nodes.

Example 4:

**Input:** adjList = [[2],[1]]
**Output:** [[2],[1]]

Constraints:

  • 1 <= Node.val <= 100
  • Node.val is unique for each node.
  • Number of Nodes will not exceed 100.
  • There is no repeated edges and no self-loops in the graph.
  • The Graph is connected and all nodes can be visited starting from the given node.

题目大意：

深度复制图。注意要复制所有邻接节点。

算法I解题思路(推荐)：

三步走。分开写逻辑会显得清晰点。

  1. BFS搜索所有节点，变成邻接表节点列表。
  2. 复制节点。旧新节点映射存在dict中
  3. 根据node.neighbors复制边。

注意事项：

  1. 空节点判断Line 2-3
  2. BFS访问是收集节点列表，并不是变成邻接表。如果是含循环的图，由于用了visited，所以邻接表只能复制一半的边，不能用邻接表

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
def cloneGraph(self, node: 'Node') -> 'Node':
	if not node:
		return None
	di = {}
	node_list = self.bfs(node)
	for n in node_list:
		di[n] = Node(n.val)
	for n in node_list:
		for n2 in n.neighbors:
			di[n].neighbors.append(di[n2])
	return di[node]

def bfs(self, input):
	queue = deque([input])
	visited = {input}
	# graph = collections.defaultdict(list)
	res = []
	while queue:
		node = queue.popleft()
		# graph[node] = []
		res.append(node)
		for neighbor in node.neighbors:
			if neighbor in visited:
				continue
			queue.append(neighbor)
			visited.add(neighbor)
			# graph[node].append(neighbor)
	return res

Java代码：

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
37
// another bfs3 method uses 3 steps, convert graph to adjacent list by bfs (flatten the graph), 
//clone vertices, clone edges
public void bfs3(UndirectedGraphNode node, HashMap<UndirectedGraphNode, UndirectedGraphNode> map) {
	ArrayList<UndirectedGraphNode> nodes = getNodes(node);
	
	// Copy vertices
	for(UndirectedGraphNode old : nodes) {
		UndirectedGraphNode newNode = new UndirectedGraphNode(old.label);
		map.put(old, newNode);
	}
	
	// Copy edges
	for(UndirectedGraphNode old : nodes) {
		for(UndirectedGraphNode neighbor : old.neighbors) {
			map.get(old).neighbors.add(map.get(neighbor));
		}
	}
}

public ArrayList<UndirectedGraphNode> getNodes(UndirectedGraphNode node) {
	Queue<UndirectedGraphNode> q = new LinkedList<>();
	Set<UndirectedGraphNode> result = new HashSet<>();
	q.offer(node);
	result.add(node); // Use result set so we can save the visited set
	while(!q.isEmpty()) {
		UndirectedGraphNode n = q.poll();
		for(UndirectedGraphNode neighbor : n.neighbors) {
			if(result.contains(neighbor))
				continue;
			q.offer(neighbor);
			result.add(neighbor);
		}
	}
	ArrayList<UndirectedGraphNode> reList = new ArrayList<UndirectedGraphNode>();
	reList.addAll(result);
	return reList;
}

算法II解题思路：

不分开三步写

Java代码：

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
public UndirectedGraphNode cloneGraph2(UndirectedGraphNode node) {
	if(node == null)
		return null;
	
	HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
	bfs(node, map);
	return map.get(node);
}

public void bfs(UndirectedGraphNode node, HashMap<UndirectedGraphNode, UndirectedGraphNode> map) {
	Queue<UndirectedGraphNode> q = new LinkedList<>();
	q.offer(node);
	map.put(node, new UndirectedGraphNode(node.label));
	while(!q.isEmpty()) {
		UndirectedGraphNode head = q.poll();
		for(UndirectedGraphNode neighbor : head.neighbors) {
			if(!map.containsKey(neighbor)) {
				q.offer(neighbor);
				// Clone children's vertex
				map.put(neighbor, new UndirectedGraphNode(neighbor.label));
			}
			// Clone edge
			map.get(head).neighbors.add(map.get(neighbor));
		}
	}
}

算法II解题思路：

DFS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
	HashMap<Integer, UndirectedGraphNode> map = new HashMap<Integer, UndirectedGraphNode>();
	return cloneGraphR(node, map);
}

public UndirectedGraphNode cloneGraphR(UndirectedGraphNode node,
		HashMap<Integer, UndirectedGraphNode> map) {
	if (node == null)
		return node;
	if (map.containsKey(node.label))
		return map.get(node.label);

	UndirectedGraphNode result = new UndirectedGraphNode(node.label);
	map.put(node.label, result);
	for (UndirectedGraphNode child : node.neighbors) {
		result.neighbors.add(cloneGraphR(child, map));
	}
	return result;
}

算法分析：

时间复杂度为O(# of results)，空间复杂度O(lengh(high))。

Posted on Edited on Disqus:

LeetCode 126 Word Ladder



Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

Return an empty list if there is no such transformation sequence. All words have the same length.
All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

Output:
[
  [“hit”,”hot”,”dot”,”dog”,”cog”],
  [“hit”,”hot”,”lot”,”log”,”cog”]
]


Example 2:

Input:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

Output: []

*Explanation: The endWord “cog” is not in wordList, therefore no possibletransformation.


题目大意：

给定一个字典和两个单词。每次变换一个字母的得到新单词且该词要在字典中。求所有最少的变换路径。

解题思路：

更难于Leetcode 127，BFS用于找最短路径而DFS找路径，此题正是贯彻这一思想，先用BFS找出最短路径，
然后根据最短路径值找出所有路径。找BFS解的同时建图用邻接表表示Map>(这是
部分图，与解相关的图)和解集合Map(从始点到不同节点的最短距离)，这两个信息正是
Dijkistra的图输入和解。DFS从始点开始遍历邻接节点，确保沿着最短路径走，最短路径为
map.get(cur)+1=map.get(next)表示当前节点到始点距离+1=儿节点到始点距离，终止条件为找到目标节点。

  1. 在遍历所有邻接节点的时候，如果不加筛选对所有邻接节点都做DFS会造成LTE。关键是要利用BFS中所有
    节点到单源的最短路径来剪枝。只需DFS最短路径上的节点，否则跳过。
  2. 利用了单源最短路径映射表distance后，不需要记录visited，因为重复的节点不会在最短路劲上。
  3. Cache nextWords的结果。

解题步骤：

这题是最短路径题，第一时间想到BFS。这是一条典型的单源最短路径问题。

  1. 建字典。
  2. BFS访问，得到图和单源最短路径Map，以及最短路径距离。同时建立邻接表graph[word] = neighbors，DFS时候不用再次找相邻单词
  3. DFS求路径，按最短路径剪枝dict[neighbor] == dict[startWord] + 1。

注意事项：

  1. 注意题目条件，开始词不在字典中(终结词默认在，否则无结果），要将它加入字典中且距离为1且要加入到path，Line 10。
  2. 建图的邻接表，对没有边的节点也要加到邻接表，所以先对所有点赋空列表，再根据边更新值，Line 29。用defaultdict(list)可解决
  3. DFS模板中去掉visited部分，因为用了最短距离distance的map来指导访问路径，所以不会存在循环的情况(否则不会是最短距离)
    而且如果有visited会存在丢解，因为如果一个节点不在最短路径上先被访问就会被标记为visited，真正到最短路径上时就会返回。
    DFS模板中加入if dict[neighbor] == dict[startWord] + 1来剪边。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[int]]:
	if not beginWord or not endWord:
		return 0
	distance, graph = {}, defaultdict(list)
	for word in wordList:
		distance[word] = 0
	distance[beginWord] = 1
	self.bfs(beginWord, endWord, distance, graph, set())
	result = []
	self.dfs(graph, beginWord, endWord, [beginWord], result, distance) # remember [beginWord]
	return result

def dfs(self, graph, startWord, endWord, path, res, dict):
	if startWord == endWord:
		res.append(list(path))
		return
	'''if startWord in visited: # remember
		return
	visited.add(startWord)'''
	for neighbor in graph[startWord]:
		if dict[neighbor] == dict[startWord] + 1:
			path.append(neighbor)
			self.dfs(graph, neighbor, endWord, path, res, dict)
			path.pop()

def bfs(self, beginWord, endWord, dict, graph, visited):
	queue = deque([beginWord])
	visited.add(beginWord)
	# for key in dict.keys():  # remember
	#    graph[key] = []
	while queue:
		word = queue.popleft()
		if word == endWord:
			return dict[word]

		neighbors = self.get_next_words(word, dict)
		graph[word] = neighbors
		for neighbor in neighbors:
			if neighbor not in visited:
				queue.append(neighbor)
				visited.add(neighbor)
				dict[neighbor] = dict[word] + 1
	return 0

def get_next_words(self, word, dict):
	res = []
	for i in range(len(word)):
		for c in string.ascii_lowercase: # or use 'abcdefghijklmnopqrstuvwxyz'
			if c == word[i]:
				continue
			new_word = word[:i] + c + word[i + 1:]
			if new_word in dict:
				res.append(new_word)
	return res

Java代码：

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
	List<String> path = new ArrayList<>();
	List<List<String>> res = new ArrayList<>();
	if(beginWord == null || endWord == null)
		return res;
	
	// This is a dict and also keeps track of distance
	Map<String, Integer> dict = getDict(wordList);
	// Make sure endWord is in the dict and can be the next word 
	//dict.put(endWord, 0);
	dict.put(beginWord, 1);
	HashMap<String, List<String>> graph = new HashMap<String, List<String>>();
	ladderLength(beginWord, endWord, dict, graph);
	path.add(beginWord);
	dfs(beginWord, endWord, dict, graph, path, res);
	return res;
}

void dfs(String cur, String endWord, Map<String, Integer> distance,
		HashMap<String, List<String>> graph, List<String> path, List<List<String>> res) {
	if(endWord.equals(cur)) {
		res.add(new ArrayList<>(path));
		return;
	}
	for(String word : graph.get(cur)) {
		path.add(word);
		if(distance.get(word) - 1 == distance.get(cur)) // use distance, resolve LTE the most important
			dfs(word, endWord, distance, graph, path, res);
		path.remove(path.size() - 1);
	}
}

// cache getNextWords
int ladderLength(String beginWord, String endWord, Map<String, Integer> dict, Map<String, List<String>> graph) {
	Set<String> visited = new HashSet<>();
	Queue<String> q = new LinkedList<>();
	q.offer(beginWord);
	visited.add(beginWord);
	for(String s : dict.keySet()) {// remember
		graph.put(s, new ArrayList<>());
	}
	while(!q.isEmpty()) {
		String word = q.poll();
		if(endWord.equals(word))
			return dict.get(word);
		
		List<String> nextWords = getNextWords(word, dict);
		graph.put(word, new ArrayList<>(nextWords));
		for(String s : nextWords) {
			if(visited.contains(s))
				continue;
			
			q.offer(s);
			visited.add(s);
			dict.put(s, dict.get(word) + 1);
		}
	}
	return 0;
}

Map<String, Integer> getDict(List<String> wordList) {
	Map<String, Integer> map = new HashMap<>();
	for(String word : wordList) {
		map.put(word, 0);
	}
	return map;
}

List<String> getNextWords(String word, Map<String, Integer> dict) {
	List<String> result = new ArrayList<>();
	for(int i = 0; i < word.length(); i++) {
		for(int j = 0; j < 26; j++) { 
			char newChar = (char)('a' + j);
			if(word.charAt(i) == newChar) // exclude itself
				continue;
			String newWord = word.substring(0, i) + 
					newChar + word.substring(i + 1, word.length());
			if(dict.containsKey(newWord))
				result.add(newWord);
			
		}
	}
	return result;
}

算法分析：

getNextWords是L26L=O(L2)产生新字符串需要L
时间复杂度为O(nL2 + mk)，空间复杂度O(n)，m为答案个数, k为最短路径值，n为单词数。

Posted on Edited on Disqus:

LeetCode 368 Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:

Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

**Input:** [1,2,3]
**Output:** [1,2] (of course, [1,3] will also be ok)

Example 2:

**Input:** [1,2,4,8]
**Output:** [1,2,4,8]

题目大意：

一个数组，让我们求这样一个子集合，集合中的任意两个数相互取余均为0。

解题思路：

由于知道子问题有助于求解考虑用DP。它就是LIS的翻版。这道题还需要打印DP路径。

  1. 定义dp[i]为num[i-1]这个数对应的最大可整除子集合个数。
  2. 递归式为dp[i] = max{dp[j-1] + 1}, 0<j<i, 若num[i-1]可被num[j-1]整除
  3. 方向为从左到右。初始值为dp = 1。
  4. path数组记录解的下标+1，每求得一个解dp[i] = dp[j] + 1就记录对应上一层解的下标，也就是到此解的路径。

注意事项：

  1. 初始值dp = 1。

Java代码：

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
public List<Integer> largestDivisibleSubset(int[] nums) {
	List<Integer> res = new ArrayList<>();
	if(nums == null || nums.length == 0)
		return res;
	if(nums.length == 1)
		return Arrays.asList(nums[0]);
	Arrays.sort(nums);
	int max = Integer.MIN_VALUE;
	int maxPos = -1;
	int[] dp = new int[nums.length + 1];
	int[] path = new int[nums.length + 1];
	for(int i = 0; i < dp.length; i++) // remember to init to 1
		dp[i] = 1;
	for(int i = 1; i < dp.length; i++) {
		for(int j = 1; j < i; j++) {
			if(nums[i-1] % nums[j-1] == 0 && dp[j] + 1 > dp[i]) {
				dp[i] = dp[j] + 1;
				path[i] = j;
			}
		}
		if(dp[i] > max) { // the biggest value might not be the last one, keep track of the start pos for the path
			max = dp[i];
			maxPos = i;
		}
	}
	int pos = maxPos;
	for(int i = 0; i < dp[maxPos]; i++) {
		res.add(nums[pos-1]);
		pos = path[pos];
		
	}
	Collections.sort(res);
	return res;
}

算法分析：

时间复杂度为O(n2)，空间复杂度O(n2)。

Posted on Edited on Disqus:

LeetCode 312 Burst Balloons

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

    nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
   coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

题目大意：

给定n个气球，下标为0到n-1。每个气球上都标有一个数字，用数组nums表示。你被要求扎破所有气球。扎破第i个气球可以获得nums[left] × nums[i] × nums[right]枚硬币。这里left和right是与i相邻的下标。扎破气球以后，left和right就变成相邻的了。
寻找最优策略下可以获得的硬币数。

注意：
(1) 你可以假设nums[-1] = nums[n] = 1. 它们并非真实的因此不能扎破。
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

解题思路：

  1. 此题遍历所有可能性，所以考虑用DP
  2. 因为一个参数不足以描述问题，因为并不能固定nums左端或右端，所以考虑二元DP，左右边界为参数。DP流程一：定义函数f(i,j)为nums[i..j]之间的最大硬币数。
  3. 下一步写递归式，由于这是二元DP，参考Floyd和矩阵链乘法算法，一遍要定义一个k，二分法得到两个子问题的解f(i,k)和f(k,j)，求解它们的关系是难点。先写几个例子培养下思路：
    2,3,4
    f([2,4])=2×3×4同时消去了3变成[2,4],再写一个
    2,3,4,5,6,7,8
    k=5, 数组变成[2,5,8]所以我们定义中忽略了一个重要事实，修改为f(i,j)为nums[i..j]之间的最大硬币数及其它们之间的元素已经消去。
    这样的话，关系就很明朗了，只要消去5就可以得到f([2,8])，k的定义要可以清晰了：最后一个消去的元素。
    f(i,j)=max{f(i,m)+ nums[i]×nums[m]×nums[j] +f(m,j)}, i<m<j，m为整数
  4. 我们还要试试nums为单元素和双元素情况下是否适用。比如单元素5，根据题目意思首先前后补1
    1,5,1 -> f(1,5)+1×5×1+f(5,1)=5这是正确的因为f(x,y)默认为0.
    1,5,3,1, k=5, f(1,5)+1×5×1+f(5,1)=0+5+(5×3×1)=20 | k=3, f(1,3)+1×3×1+f(3,1)=(1×5×3)+3+0=18.所以也是正确，且f(x,y)默认为0没问题。

  5. 遍历顺序。一开始我用i,j,m三重循环，但结果不对。主要因为这个计算过程与演算过程不一致，我们刚才的演算过程是先计算所有i和j之间的值。例如，
    1, 5, 3, 1
    i        j
    i            j
        i        j

    在第二次循环的时候f(i,j)已经计算出来很显然是不对的。

注意事项：

  1. 二元DP([i,j],k的递归式)+二分法。 二元DP中k的引入参考Floyd按步长计算。nums[i] * nums[m] * nums[j]而不是nums[m-1] * nums[m] * nums[m+1]
  2. 原数组前后补1，这样巧妙地让递归式适用于一个元素的情况，避免特别处理。因此步长可以k=2开始，i<m<j不取等号。dp数组以新数组为边界
  3. 遍历顺序也类似于Floyd，先k(步长且至少为2)，再遍历矩阵i和j。特别注意i<n-k而不是i<n

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def maxCoins(self, nums: List[int]) -> int:
	ary = list(nums)
	ary.insert(0, 1)
	ary.append(1)
	N = len(ary)
	dp = [[0 for _ in range(N)] for _ in range(N)]
	for k in range(2, N):
		for i in range(0, N - k):
			j = i + k
			for m in range(i + 1, j):
				dp[i][j] = max(dp[i][j], dp[i][m] + ary[i] * ary[m] * ary[j] + dp[m][j])
	return dp[0][N - 1]

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int maxCoins(int[] nums) {
	int n = nums.length+2;
	int[] coins = new int[n];
	
	for(int i=0;i<nums.length;i++)
		coins[i+1]=nums[i];
	coins[0] = coins[n-1] = 1;
	
	int[][] dp = new int[n][n];
	for(int k=2;k<n;k++)
		for(int i=0;i<n - k;i++){
			int j = i+k;
			for(int m=i+1;m<j;m++)
				dp[i][j] = Math.max(dp[i][j], dp[i][m]+coins[i]*coins[m]*coins[j] + dp[m][j]);
				
		}
	return dp[0][n-1];
}

算法分析：

三重循环，时间复杂度为O(n3)，空间复杂度O(n2)。

Posted on Edited on Disqus:

LeetCode 2080 Range Frequency Queries

Design a data structure to find the frequency of a given value in a given subarray.

The frequency of a value in a subarray is the number of occurrences of that value in the subarray.

Implement the RangeFreqQuery class:

  • RangeFreqQuery(int[] arr) Constructs an instance of the class with the given 0-indexed integer array arr.
  • int query(int left, int right, int value) Returns the frequency of value in the subarray arr[left...right].

A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).

Example 1:

**Input**
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
**Output**
[null, 1, 2]

**Explanation**
RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
rangeFreqQuery.query(1, 2, 4); // return 1\. The value 4 occurs 1 time in the subarray [33, 4]
rangeFreqQuery.query(0, 11, 33); // return 2\. The value 33 occurs 2 times in the whole array.

Constraints:

  • 1 <= arr.length <= 10<sup>5</sup>
  • 1 <= arr[i], value <= 10<sup>4</sup>
  • 0 <= left <= right < arr.length
  • At most 10<sup>5</sup> calls will be made to query

题目大意：

设计数据结构，支持在指定的子数组中某target的频数。

解题思路：

这题有意思，有望成为经典题。第一种方法写用以每个字母为结尾的frequency_dict作为数据结构，query只需要用frequency_dict[right]-frequency_dict[left-1]，
空间复杂度为O(n2)得到TLE。第二种方法用bucket sort，就是将值作为key存到dict中，而value是下标List，query时候得到对应List，遍历
一次即可，但仍然得到TLE。第三种方法改进用Binary search得到下标List的左右界。二分法用greater_or_equal_position以及small_or_equal_position.
所以最终方案采取bucket sort + binary search

解题步骤：

  1. dict记录值到下标列表的映射
  2. 二分法找left和right的index从而求个数

注意事项：

  1. Binary search用greater_or_equal_position以及small_or_equal_position.

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class RangeFreqQuery:
	
    def __init__(self, arr: List[int]):
        self.frequency_dict = {}

        for i, n in enumerate(arr):
            if n not in self.frequency_dict:
                self.frequency_dict[n] = [i]
            else:
                self.frequency_dict[n].append(i)

    def query(self, left: int, right: int, value: int) -> int:
        if value not in self.frequency_dict:
            return 0
        index_list = self.frequency_dict[value]
        '''
        count = 0
        for index in index_list:
            if left <= index <= right:
                count += 1
        '''
        left_pos = self.greater_or_equal_position(index_list, left)
        right_pos = self.smaller_or_equal_position(index_list, right)
        if left_pos == -1 or right_pos == -1:
            return 0
        return right_pos - left_pos + 1

    def greater_or_equal_position(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if target > nums[mid]:
                start = mid
            elif target < nums[mid]:
                end = mid
            else:
                start = mid
        if nums[start] >= target:
            return start
        if nums[end] >= target:
            return end
        return -1

    def smaller_or_equal_position(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if target > nums[mid]:
                start = mid
            elif target < nums[mid]:
                end = mid
            else:
                end = mid
        if nums[end] <= target:
            return end
        if nums[start] <= target:
            return start
        return -1

用defaultdict(list)和bisect来优化程序

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def __init__(self, arr: List[int]):
	self.frequency_dict = collections.defaultdict(list)

	for i, n in enumerate(arr):
		self.frequency_dict[n].append(i)

def query(self, left: int, right: int, value: int) -> int:
	index_list = self.frequency_dict[value]
	left_pos = bisect.bisect(index_list, left - 1)
	right_pos = bisect.bisect(index_list, right)
	return right_pos - left_pos

算法分析：

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

Free mock interview