KK's blog

LeetCode 1706 Where Will the Ball Fall

Posted on 2022-11-06 Disqus:

You have a 2-D grid of size m x n representing a box, and you have n balls. The box is open on the top and bottom sides.

Each cell in the box has a diagonal board spanning two corners of the cell that can redirect a ball to the right or to the left.

A board that redirects the ball to the right spans the top-left corner to the bottom-right corner and is represented in the grid as 1. A board that redirects the ball to the left spans the top-right corner to the bottom-left corner and is represented in the grid as -1.

We drop one ball at the top of each column of the box. Each ball can get stuck in the box or fall out of the bottom. A ball gets stuck if it hits a “V” shaped pattern between two boards or if a board redirects the ball into either wall of the box.

Return an array answer of size n where answer[i] is the column that the ball falls out of at the bottom after dropping the ball from the i<sup>th</sup> _column at the top, or -1 if the ball gets stuck in the box._

Example 1:

Input: grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
Output: [1,-1,-1,-1,-1]
Explanation: This example is shown in the photo.
Ball b0 is dropped at column 0 and falls out of the box at column 1.
Ball b1 is dropped at column 1 and will get stuck in the box between column 2 and 3 and row 1.
Ball b2 is dropped at column 2 and will get stuck on the box between column 2 and 3 and row 0.
Ball b3 is dropped at column 3 and will get stuck on the box between column 2 and 3 and row 0.
Ball b4 is dropped at column 4 and will get stuck on the box between column 2 and 3 and row 1.

Example 2:

Input: grid = [[-1]]
Output: [-1]
Explanation: The ball gets stuck against the left wall.

Example 3:

Input: grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]
Output: [0,1,2,3,4,-1]

Constraints:

m == grid.length n == grid[i].length
1 <= m, n <= 100 grid[i][j] is 1 or -1.

题目大意：

二维数组每一个cell都是1或者-1，分别表示一个玻璃板的放置方向，正对角线或者反对角线。球从每一个列投下，根据玻璃板的设置，若成功从底部滑出，输入列号，否则输入-1. 求这个结果数组。

解题思路：

这是Q&A题目。游戏模拟题大多用DFS，因为就是选择一条路径走到底。

解题步骤：

N/A

注意事项：

任何情况都是row + 1，而不是-1
题目要求若成功，输出球跌出的列号，而不是boolean = 1

Python代码：

def findBall(self, grid: List[List[int]]) -> List[int]:
	return [self.dfs(grid, 0, j) for j in range(len(grid[0]))]

def dfs(self, grid, row, col):
	if row == len(grid):
		return col
	if grid[row][col] == 1:
		if col + 1 == len(grid[0]) or grid[row][col + 1] == -1:
			return -1
		else:
			return self.dfs(grid, row + 1, col + 1)
	else:
		if col - 1 < 0 or grid[row][col - 1] == 1:
			return -1
		else:
			return self.dfs(grid, row + 1, col - 1)

算法分析：

时间复杂度为O(nm)，空间复杂度O(1), n, m分别为行数和列数。

LeetCode 1337 The K Weakest Rows in a Matrix

Posted on 2022-11-06 Disqus:

LeetCode

You are given an m x n binary matrix mat of 1‘s (representing soldiers) and 0‘s (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1‘s will appear to the left of all the 0‘s in each row.

A row i is weaker than a row j if one of the following is true:

The number of soldiers in row i is less than the number of soldiers in row j. Both rows have the same number of soldiers and i < j.

Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.

Example 1:

Input: mat =
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]],
k = 3
Output: [2,0,3]
Explanation:
The number of soldiers in each row is:
- Row 0: 2
- Row 1: 4
- Row 2: 1
- Row 3: 2
- Row 4: 5
The rows ordered from weakest to strongest are [2,0,3,1,4].

Example 2:

Input: mat =
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]],
k = 2
Output: [0,2]
Explanation:
The number of soldiers in each row is:
- Row 0: 1
- Row 1: 4
- Row 2: 1
- Row 3: 1
The rows ordered from weakest to strongest are [0,2,3,1].

Constraints:

m == mat.length n == mat[i].length
2 <= n, m <= 100 1 <= k <= m
* matrix[i][j] is either 0 or 1.

题目大意：

二维数组含0和1，1表示士兵，0表示平民。每一行定义弱度，若士兵个数少且行号靠前，较弱。求前k个较弱的行号。

解题思路：

Easy题。Q&A的题目，关于前k个最值，第一时间想到用heap。求最小值，所以用最大堆

解题步骤：

N/A

注意事项：

求最大堆，引入负值。此题属于二维堆，第二个维度跟第一个维度一样，从小到大，所以也采用负号。

Python代码：

def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
	nums_soldiers = [(sum(mat[i]), i) for i in range(len(mat))]
	res = []
	for i in range(len(nums_soldiers)):
		if i < k:
			heappush(res, (-nums_soldiers[i][0], -nums_soldiers[i][1]))
		# put into the heap if weaker
		elif -nums_soldiers[i][0] > res[0][0] or \
				(nums_soldiers[i][0] == res[0][0] and -nums_soldiers[i][1] > res[0][1]):
			heapreplace(res, (-nums_soldiers[i][0], -nums_soldiers[i][1]))
	res.sort(key=lambda x: (-x[0], -x[1]))
	return [-res[i][1] for i in range(len(res))]

算法分析：

时间复杂度为O(nlogk)，空间复杂度O(n), n为行数

LeetCode 2089 Find Target Indices After Sorting Array

Posted on 2022-10-02 Disqus:

LeetCode

You are given a 0-indexed integer array nums and a target element target.

A target index is an index i such that nums[i] == target.

Return a list of the target indices of nums after sorting nums in non-decreasing order. If there are no target indices, return an empty list. The returned list must be sorted in increasing order.

Example 1:

Input: nums = [1,2,5,2,3], target = 2
Output: [1,2]
Explanation: After sorting, nums is [1,2,2,3,5].
The indices where nums[i] == 2 are 1 and 2.

Example 2:

Input: nums = [1,2,5,2,3], target = 3
Output: [3]
Explanation: After sorting, nums is [1,2,2,3,5].
The index where nums[i] == 3 is 3.

Example 3:

Input: nums = [1,2,5,2,3], target = 5
Output: [4]
Explanation: After sorting, nums is [1,2,2,3,5].
The index where nums[i] == 5 is 4.

Constraints:

1 <= nums.length <= 100 1 <= nums[i], target <= 100

题目大意：

如果数组已排序，求target对应的所有下标。

解题思路：

这道题是Easy题，也是Q&A中被问到的，Binary Search不是最优解，但是可以用它作为解法研究。

解题步骤：

标准binary search

注意事项：

N/A

Python代码：

def targetIndices(self, nums: List[int], target: int) -> List[int]:
	sorted_nums = sorted(nums)
	target_index = self.binary_search(sorted_nums, target)
	res = []
	print(target_index)

	for i in range(target_index - 1, -1, -1):
		if sorted_nums[i] == target:
			res.append(i)
	res = res[::-1]
	for i in range(target_index, len(sorted_nums)):
		if sorted_nums[i] == target:
			res.append(i)
	return res

def binary_search(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]:
			end = mid
		else:
			start = mid

	if nums[end] == target:
		return end
	elif nums[start] == target:
		return start
	else:
		return -1

算法II解题思路：

first_postition & last position

Python代码：

def targetIndices(self, nums: List[int], target: int) -> List[int]:
	sorted_nums = sorted(nums)
	target_upper_index = self.last_position(sorted_nums, target)
	target_lower_index = self.first_position(sorted_nums, target)
	res = [i for i in range(target_lower_index, target_upper_index + 1)]
	return [] if target_upper_index == -1 else res

def first_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]:
			end = mid
		elif target > nums[mid]:
			start = mid
		else:
			end = mid

	if nums[start] == target:
		return start
	elif nums[end] == target:
		return end
	else:
		return -1

def last_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]:
			end = mid
		elif target > nums[mid]:
			start = mid
		else:  # Depends on the target on the right side or left side. For fist pos, use end = mid
			start = mid

	if nums[end] == target:
		return end
	elif nums[start] == target:
		return start
	else:
		return -1

算法分析：

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

LeetCode 791 Custom Sort String

Posted on 2022-03-19 Disqus:

LeetCode

You are given two strings order and s. All the words of order are unique and were sorted in some custom order previously.

Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.

Return any permutation of s that satisfies this property.

Example 1:

Input: order = “cba”, s = “abcd”
Output: “cbad”
Explanation:
“a”, “b”, “c” appear in order, so the order of “a”, “b”, “c” should be “c”, “b”, and “a”.
Since “d” does not appear in order, it can be at any position in the returned string. “dcba”, “cdba”, “cbda” are also valid outputs.

Example 2:

Input: order = “cbafg”, s = “abcd”
Output: “cbad”

Constraints:

1 <= order.length <= 26 1 <= s.length <= 200
order and s consist of lowercase English letters. All the characters of order are unique.

题目大意：

给一个字符串，求这个字符串的一个排列，使得字母顺序按照另一个给定字符串order的顺序。

解题思路：

由限制条件知道，order字母是唯一的，order字母可以重复。所以只要统计s频率，然后按照字母顺序开始重写

解题步骤：

N/A

注意事项：

Python代码：

def customSortString(self, order: str, s: str) -> str:
	char_to_count = collections.Counter(s)
	res = ''
	for c in order:
		if c in char_to_count:
			res += c * char_to_count[c]
			char_to_count.pop(c)
	for c, count in char_to_count.items():
		res += c * count
	return res

算法分析：

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

LeetCode 426 Convert Binary Search Tree to Sorted Doubly Linked List

Posted on 2022-03-19 Disqus:

LeetCode

Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.

Example 1:

Input: root = [4,2,5,1,3]


Output: [1,2,3,4,5]

Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

Example 2:

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

Constraints:

The number of nodes in the tree is in the range [0, 2000]. -1000 <= Node.val <= 1000
All the values of the tree are *unique.

题目大意：

将二叉树变成双向链表，left为父节点，right为儿子节点

解题思路：

类似于LeetCode 114 Flatten Binary Tree to Linked List，先假设左右儿子，已经是双向LL，下面就是将root这个节点插入到两个LL之间其将它们首尾相连

解题步骤：

N/A

注意事项：

要将左右儿子节点的LL，首尾相连。首尾节点获得要在if语句前，因为右儿子的left会连到root，就找不到它的尾部。首尾相连要发生在最后。

Python代码：

def treeToDoublyList(self, root: 'Node') -> 'Node':
	if not root:
		return None
	if not root.left and not root.right:
		root.left, root.right = root, root
		return root
	left_head = self.treeToDoublyList(root.left)
	right_head = self.treeToDoublyList(root.right)
	# remember this part and order, can't be placed after ifs
	new_head = left_head if left_head else root
	new_tail = right_head.left if right_head else root
	if left_head:
		left_head.left.right, root.left = root, left_head.left
	if right_head:
		root.right, right_head.left = right_head, root
	new_head.left, new_tail.right = new_tail, new_head
	return new_head

算法分析：

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