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



Given the root of a binary search tree, and an integer k, return the k<sup>th</sup> smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:



Input: root = [3,1,4,null,2], k = 1
Output: 1


Example 2:



Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3


Constraints:

The number of nodes in the tree is n. 1 <= k <= n <= 10<sup>4</sup>
0 <= Node.val <= 10<sup>4</sup>

*Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

题目大意：

求BST的第k个最小元素（k从1开始）

算法思路：

N/A

注意事项：

  1. 用返回值(count, 结果). 递归右节点，用k - 1 - left_count
  2. Line 9不能用if left_val，因为left_val可能是0，用is not None

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def kthSmallest(self, root: TreeNode, k: int) -> int:
	count, val = self.dfs(root, k)
	return val

def dfs(self, root, k):
	if not root:
		return 0, None

	left_count, left_val = self.dfs(root.left, k)
	if left_val is not None: # remember if left_val is wrong
		return 0, left_val
	if left_count + 1 == k:
		return 0, root.val
	right_count, right_val = self.dfs(root.right, k - left_count - 1) # remember k-1-left_count
    if right_val is not None:
		return 0, right_val
	return left_count + 1 + right_count, right_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
public int kthSmallest2(TreeNode root, int k) {
	return kthSmallest2R(root, k).result;
}

public ResultType kthSmallest2R(TreeNode root, int k) {
	if (root == null)
		return new ResultType(null, 0);
	ResultType leftResult = kthSmallest2R(root.left, k);

	Integer result = leftResult.result;
	if(result != null)
		return new ResultType(result, 0);
	if(leftResult.count + 1 == k)
		return new ResultType(root.val, 0);
	
	ResultType rightResult = kthSmallest2R(root.right, k - 1 - leftResult.count);
	result = rightResult.result;
	
	return new ResultType(result, leftResult.count + 1 + rightResult.count);
}

class ResultType {
	Integer result;
	int count;
	
	public ResultType(Integer r, int c) {
		result = r;
		count = c;
	}
}

算法分析：

时间复杂度为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



There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4


Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1


Example 3:

Input: nums = [1], target = 0
Output: -1


Constraints:

1 <= nums.length <= 5000 -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>
All values of nums are unique. nums is an ascending array that is possibly rotated.
* -10<sup>4</sup> <= target <= 10<sup>4</sup>

题目大意：

有序数组旋转了几位，求target的下标

算法思路：

N/A

注意事项：

  1. 四种情况： 左半有序且target在这个有序区间内，左边有序的所有其他情况，右半有序且target在这个有序区间，右半有序的所有其他情况

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def search(self, nums: List[int], target: int) -> int:
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if nums[start] < nums[mid] and nums[start] <= target <= nums[mid]:  # remember
			end = mid
		elif nums[start] < nums[mid]:
			start = mid
		elif nums[mid] < nums[end] and nums[mid] <= target <= nums[end]:
			start = mid
		else:
			end = mid
	if nums[start] == target:
		return start
	if nums[end] == target:
		return end
	return -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
public int search(int[] nums, int target) {
	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[mid] > nums[start]) { // the left segment is increasing
			// pay attention to equal 
			if(nums[start] <= target && target <= nums[mid]) //the [start, mid] is increasing
				end = mid;
			else
				start = mid;
		} 
		else { 
			if(nums[mid] <= target && target <= nums[end]) // the [mid, end] is increasing
				start = mid;
			else
				end = mid;
		}
	}
	
	if(nums[start] == target)
		return start;
	if(nums[end] == target)
		return end;
	
	return -1;
}

算法分析：

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

Free mock interview