KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]


Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]


Constraints:

n == nums.length 1 <= n <= 300
nums[i] is either 0, 1, or 2.

*Follow up: Could you come up with a one-pass algorithm using only constant extra space?

题目大意：

排序3值数组

算法思路：

类似于Quicksort的partition，但有三种值，需要有三个指针: left, i, right

注意事项：

  1. 三个指针: left, i, right. 循环不是for每个元素，而是i <= right
  2. nums[2]的时候，right要往前移
  3. 和partition一样： nums[i] == 0，left和i都移动，nums[i] == 1只移动i

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def sortColors(self, nums: List[int]) -> None:
	left, i, right = 0, 0, len(nums) - 1
	while i <= right: # remember
		if nums[i] == 0:
			nums[left], nums[i] = nums[i], nums[left]
			left += 1
			i += 1
		elif nums[i] == 1:
			i += 1
		else:
			nums[i], nums[right] = nums[right], nums[i]
			right -= 1 # remember

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void sortColors(int[] nums) {
	int middleStart = 0, middleEnd = nums.length-1, i=0;
	while(i<=middleEnd){
		if(nums[i]==2)
			swap(nums,i,middleEnd--);//no i++ coz 2,0,2,2, swap 2,2 and i can't +1
		else if(nums[i]==0)
			swap(nums,i++,middleStart++);
		else
			i++;
	}
			
}

public void swap(int[] a,int i,int j){
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:



Input: root = [2,1,3]
Output: true


Example 2:



Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node’s value is 5 but its right child’s value is 4.


Constraints: The number of nodes in the tree is in the range [1, 10<sup>4</sup>].
* -2<sup>31</sup> <= Node.val <= 2<sup>31</sup> - 1

题目大意：

验证BST

算法思路：

N/A

注意事项：

  1. 用min, max法

Python代码：

1
2
3
4
5
6
7
8
9
10
def isValidBST(self, root: TreeNode) -> bool:
	return self.dfs(root, float('-inf'), float('inf'))

def dfs(self, root, min_val, max_val):
	if not root:
		return True
	if min_val >= root.val or root.val >= max_val:
		return False
	return self.dfs(root.left, min_val, root.val) and \
		   self.dfs(root.right, root.val, max_val)

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
// Recommended method: use min max and devide & conquer
public boolean isValidBST2(TreeNode root) {
	return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

// val can be Integer.Min so use long
public boolean isValid(TreeNode root, long min, long max) {
	if(root == null)
		return true;
	
	if(min >= root.val || max <= root.val)
		return false;
	
	return isValid(root.left, min, root.val) && 
			isValid(root.right, root.val, max);
}

// Method 2: use isVisited
TreeNode lastVisited = null;
public boolean isValidBST(TreeNode root){
	if(root==null)
		return true;
	
	if(!isValidBST(root.left))
		return false;
	
	if(lastVisited!=null && lastVisited.val>=root.val)
		return false;
	
	lastVisited = root;//in-order traversal
			
	if(!isValidBST(root.right))
		return false;
	
	return true;
}

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.


Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.


Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.


Constraints:

n == nums.length 1 <= n <= 5000
-5000 <= nums[i] <= 5000 All the integers of nums are unique.
* nums is sorted and rotated between 1 and n times.

算法思路：

二分法

注意事项：

  1. 如果nums[start] > nums[mid]或nums[mid] > nums[end]都将会是min所在的区间。但是由于无位移数组的min在左边，所以优先判断后半区间nums[mid] > nums[end]，否则若用nums[start] > nums[mid] + else会忽略无位移情况。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def findMin(self, nums: List[int]) -> int:
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if nums[mid] > nums[end]:
			start = mid
		else:
			end = mid
	if nums[start] < nums[end]:
		return nums[start]
	else:
		return nums[end]

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int findMin(int[] nums) {
	if(nums == null || nums.length == 0)
		return -1;
	
	int start = 0, end = nums.length - 1;
	while(start + 1 < end) {
		int mid = start + (end - start) / 2;
		if(nums[start] > nums[end]) {
			if (nums[mid] < nums[end])
				end = mid;
			else
				start = mid;
		} 
		else 
			return nums[start];
	}
	if(nums[start] < nums[end])
		return nums[start];
	else
		return nums[end];
}

算法分析：

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

Posted on Edited on Disqus:

LeetCode 316 Remove Duplicate Letters

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

题目大意：

给定一个只包含小写字母的字符串，从中移除重复字母使得每个字母只出现一次。你必须确保结果的字典序最小。

解题思路：

这题是保持原顺序输出结果，所以考虑用递减栈(递增栈，从栈底递增，求最小即用递增，如求k个最大用最小堆一样)。先看例子bcabc->abc，a入栈倒逼
bc出栈，可解此题。因为既然bc在栈外还有，就可以出栈，保证第一个字母最小（题目要求）。再看cbacdcbc，acd时候b入栈，不能倒逼cd出栈
因为d是唯一一个，所以还要维护一个hashMap来记录每个字母的词频。所以入栈条件为准入栈元素小于栈顶元素且栈顶元素为最后一个（频数>0）。
hashMap作用有两个，第一个为统计词频，第二个为记录未入栈的字母的频数。
resultSet记录stack中所有唯一元素，用于判断是否需要入栈。这是难点，对于已在栈中的重复元素不需要再入栈，因为它在栈中的位置已经是目前
最小的位置，如果要出现更小的结果只能通过非栈内元素倒逼产生新结果。如acabc，第二个a不需要逼c出来，b可以做到这一点，a已在最小位置。

注意事项：

  1. 已在栈内的重复元素不入栈，也不倒逼任何元素出栈，也就是直接忽略它，只要将其频数减一即可，表示已处理。比如abacb，第二个a不能倒逼b。用两个数据结构：set保证不重复加入到栈内，map保证外面还有元素可入栈
  2. 进入循环后频数立刻减一，不要出列时候才做，参见BFS。
  3. 出栈条件：栈不为空，准入栈元素小于栈顶元素，栈顶元素频数>0（表示栈外还有元素可以入栈）。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def removeDuplicateLetters(self, s: str) -> str:
	char_to_count = collections.Counter(s)
	stack, stack_set = [], set()
	for i in range(len(s)):
		char_to_count[s[i]] -= 1
		if s[i] in stack_set:
			continue
		while stack and s[i] < stack[-1] and char_to_count[stack[-1]] > 0:
			stack_set.remove(stack[-1])
			stack.pop()
		stack.append(s[i])
		stack_set.add(s[i])
	return ''.join(stack)

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 String removeDuplicateLetters(String s) {
	Stack<Character> stack = new Stack<Character>();
	Map<Character, Integer> map = new HashMap<Character, Integer>();
	Set<Character> result = new HashSet<Character>();
	
	for(int i=0;i<s.length();i++){
		Character c = s.charAt(i);
		if(map.containsKey(c))
			map.put(c, map.get(c)+1);
		else
			map.put(c, 1);
	}
	
	for(int i=0;i<s.length();i++){
		Character c = s.charAt(i);
		map.put(c, map.get(c)-1);
		
		//Stack已经有c就不加入
		if(result.contains(c))
			continue;
		
		while(!stack.isEmpty() && c<stack.peek() && map.get(stack.peek())>0){
			result.remove(stack.peek());
			stack.pop();
		}
		stack.push(c);
		result.add(c);
	}
	
	StringBuilder sb = new StringBuilder();
	while(!stack.isEmpty())
		sb.append(stack.pop());
	return sb.reverse().toString();  	
}

算法分析：

所有元素入栈出栈最多一次，所以时间复杂度为O(n)，空间复杂度O(n)。

Posted on Edited on Disqus:

LeetCode



You are given a 2D array of integers envelopes where envelopes[i] = [w<sub>i</sub>, h<sub>i</sub>] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Example 1:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).


Example 2:

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1


Constraints:

1 <= envelopes.length <= 5000 envelopes[i].length == 2
* 1 <= w<sub>i</sub>, h<sub>i</sub> <= 10<sup>4</sup>

题目大意：

信封套信封，能套上的条件是内信封的宽度和高度均小于外信封。求最多有多少个信封能套在一次

算法思路：

类似于LIS，先排序宽度，高度就变成LIS问题。

注意事项：

  1. 宽度和高度都是严格递增，所以排序envelopes的时候，先顺序排序宽度，再逆序排高度，逆序是防止同一宽度但高度不同的信封成为合法结果，如[3, 4], [3, 5], 高度LIS变成[4, 5]但不合法。还要注意Python语法：envelopes.sort(key=lambda x: (x[0], -x[1]))
  2. 用bisect_left因为，若高度相等，原地替换并不往后加。

Python代码：

1
2
3
4
5
6
7
8
9
10
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
	envelopes.sort(key=lambda x: (x[0], -x[1])) # remember format and reversed order
	sorted_height = []
	for i in range(len(envelopes)):
		index = bisect.bisect_left(sorted_height, envelopes[i][1]) # remember left
		if index < len(sorted_height):
			sorted_height[index] = envelopes[i][1]
		else:
			sorted_height.append(envelopes[i][1])
	return len(sorted_height)

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
public int maxEnvelopes(int[][] envelopes) {
	if(envelopes == null || envelopes.length == 0 || 
			envelopes[0] == null || envelopes[0].length != 2) // remember for 2d array
		return 0;
	Arrays.sort(envelopes, new Comparator<int[]>() {
		public int compare(int[] a, int[] b) {
			if(a[0] == b[0])
				return b[1] - a[1]; // remember the reverse order for [4,5], [4,6] case must strictly increasing for width and height
			else
				return a[0] - b[0];
		}
	});
	int len = 0;
	int[] lis = new int[envelopes.length];
	for(int[] e : envelopes) {
		int index = Arrays.binarySearch(lis, 0, len, e[1]);
		if(index < 0) {
			index = -index - 1;
			lis[index] = e[1];
		}
		else
			lis[index] = e[1];
		if(index == len)
			len++;
	}

	return len;
}

算法分析：

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

Free mock interview