KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<div>

Design an iterator that supports the peek operation on an existing iterator in addition to the hasNext and the next operations.

Implement the PeekingIterator class:

  • PeekingIterator(Iterator<int> nums) Initializes the object with the given integer iterator iterator.
  • int next() Returns the next element in the array and moves the pointer to the next element.
  • boolean hasNext() Returns true if there are still elements in the array.
  • int peek() Returns the next element in the array without moving the pointer.

Note: Each language may have a different implementation of the constructor and Iterator, but they all support the int next() and boolean hasNext() functions.

Example 1:

<pre>Input ["PeekingIterator", "next", "peek", "next", "next", "hasNext"] [[[1, 2, 3]], [], [], [], [], []] Output [null, 1, 2, 2, 3, false]

Explanation PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [<u>1</u>,2,3] peekingIterator.next(); // return 1, the pointer moves to the next element [1,<u>2</u>,3]. peekingIterator.peek(); // return 2, the pointer does not move [1,<u>2</u>,3]. peekingIterator.next(); // return 2, the pointer moves to the next element [1,2,<u>3</u>] peekingIterator.next(); // return 3, the pointer moves to the next element [1,2,3] peekingIterator.hasNext(); // return False </pre>

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • All the calls to next and peek are valid.
  • At most 1000 calls will be made to next, hasNext, and peek.

Follow up: How would you extend your design to be generic and work with all types, not just integer?</div>

题目大意：

实现数组的peeking Iterator。数组的Iterator是给定的。

解题思路：

预读一个数

解题步骤：

N/A

注意事项：

  1. 预读一个next数

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
class PeekingIterator(TestCases):

    def __init__(self, iterator):
        """
        Initialize your data structure here.
        :type iterator: Iterator
        """
        self.iterator = iterator
        if self.iterator.hasNext():
            self.num = self.iterator.next()
        else:
            self.num = None

    def peek(self):
        """
        Returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """
        return self.num

    def next(self):
        """
        :rtype: int
        """
        tmp = self.num
        if self.iterator.hasNext():
            self.num = self.iterator.next()
        else:
            self.num = None
        return tmp

    def hasNext(self):
        """
        :rtype: bool
        """
        return self.num is not None

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

<pre>Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] </pre>

Example 2:

<pre>Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]] </pre>

Constraints:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

</div>

题目大意：

顺时针循环矩阵90度

解题思路：

先上下对称，再沿正对角线(左上到右下)对称。正对角线实现比较容易

解题步骤：

N/A

注意事项：

  1. 先上下对称，再沿正对角线(左上到右下)对称。正对角线实现比较容易

Python代码：

1
2
3
4
5
6
7
8
def rotate(self, matrix: List[List[int]]) -> None:
	for i in range(len(matrix) // 2):
		for j in range(len(matrix[0])):
			matrix[i][j], matrix[len(matrix) - 1 - i][j] = matrix[len(matrix) - 1 - i][j], matrix[i][j]

	for i in range(len(matrix)):
		for j in range(i, len(matrix[0])):
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

算法分析：

时间复杂度为<code>O(n<sup>2</sup>)</code>，空间复杂度O(1)

Posted on Edited on Disqus:

LeetCode

<div>

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:

<pre>Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2] </pre>

Example 2:

<pre>Input: nums = [2,0,1] Output: [0,1,2] </pre>

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?

</div>

题目大意：

排序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

<div>

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:

<pre>Input: root = [2,1,3] Output: true </pre>

Example 2:

<pre>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. </pre>

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

</div>

题目大意：

验证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

<div>

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:

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

Example 2:

<pre>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. </pre>

Example 3:

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

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.

</div>

算法思路：

二分法

注意事项：

  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)

Free mock interview