Given two vectors of integers v1 and v2, implement an iterator to return their elements alternately.
Implement the ZigzagIterator class:
ZigzagIterator(List<int> v1, List<int> v2) initializes the object with the two vectors v1 and v2.
boolean hasNext() returns true if the iterator still has elements, and false otherwise.
int next() returns the current element of the iterator and moves the iterator to the next element.
Example 1:
<pre>Input: v1 = [1,2], v2 = [3,4,5,6]
Output: [1,3,2,4,5,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].
</pre>
Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?
</div>
题目大意：
求所有可能组合的和等于target。元素可以复用且顺序在组合中可以任意。
LeetCode 377 Combination Sum IV 题目基本一样，唯一区别是结果元素有序，属于排列
LeetCode 518 Coin Change 2 题目基本一样，唯一区别是结果元素无序，属于组合
Given a string s and an integer k, return the length of the longest substring ofssuch that the frequency of each character in this substring is greater than or equal tok.
Example 1:
<pre>Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.
</pre>
Example 2:
<pre>Input: s = "ababbc", k = 2
Output: 5
Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
</pre>
deflongestSubstring(self, s: str, k: int) -> int: res = 0 for i inrange(1, 27): res = max(res, self.longest_substring(s, k, i)) return res
deflongest_substring(self, s, k, n) -> int: left, char_to_count = 0, collections.defaultdict(int) res = 0 for i inrange(len(s)): char_to_count[ord(s[i]) - ord('a')] += 1 whilelen(char_to_count) == n + 1: char_to_count[ord(s[left]) - ord('a')] -= 1# use left not i if char_to_count[ord(s[left]) - ord('a')] == 0: char_to_count.pop(ord(s[left]) - ord('a')) left += 1 valid_count = len([_ for _ in char_to_count.values() if _ >= k]) iflen(char_to_count) == valid_count: res = max(res, i - left + 1) return res
Given a n * n matrix grid of 0's and 1's only. We want to represent the grid with a Quad-Tree.
Return the root of the Quad-Tree representing the grid.
Notice that you can assign the value of a node to True or False when isLeaf is False, and both are accepted in the answer.
A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:
val: True if the node represents a grid of 1's or False if the node represents a grid of 0's.
isLeaf: True if the node is leaf node on the tree or False if the node has the four children.
<pre>class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}</pre>
We can construct a Quad-Tree from a two-dimensional area using the following steps:
If the current grid has the same value (i.e all 1's or all 0's) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
Recurse for each of the children with the proper sub-grid.
If you want to know more about the Quad-Tree, you can refer to the wiki.
Quad-Tree format:
The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.
It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val].
If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0.
Example 1:
<pre>Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The explanation of this example is shown below:
Notice that 0 represnts False and 1 represents True in the photo representing the Quad-Tree.
</pre>
Example 2:
<pre>Input: grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:
</pre>
You are given an n x n integer matrix board where the cells are labeled from 1 to n<sup>2</sup> in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.
You start on square 1 of the board. In each move, starting from square curr, do the following:
Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n<sup>2</sup>)].
This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
The game ends when you reach the square n<sup>2</sup>.
A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n<sup>2</sup> do not have a snake or ladder.
Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.
For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.
Return the least number of moves required to reach the squaren<sup>2</sup>. If it is not possible to reach the square, return-1.
Example 1:
<pre>Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation:
In the beginning, you start at square 1 (at row 5, column 0).
You decide to move to square 2 and must take the ladder to square 15.
You then decide to move to square 17 and must take the snake to square 13.
You then decide to move to square 14 and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
This is the lowest possible number of moves to reach the last square, so return 4.
</pre>
if next_step in visited: # remember to put it after dest_label continue if dest_label != -1: queue.append(next_step) visited.add(next_step) distance[next_step] = distance[node] + 1 else: max_non_jump = next_step if max_non_jump in visited: # remember to put it after dest_label continue queue.append(max_non_jump) visited.add(max_non_jump) distance[max_non_jump] = distance[node] + 1 return -1# remember
defget_board_cell(self, n, label): # 6, 6 label -= 1# rememeber row_id = label // n # 0 col_id = label % n return n - 1 - row_id, n - 1 - col_id if row_id % 2 == 1else col_id
defsnakesAndLadders_dp(self, board: List[List[int]]) -> int: N = len(board) * len(board) + 1 dp = [float('inf') for _ inrange(N)] dp[1] = 0# remember # i is label id i = 1 # for i in range(2, N): while i < N: for k inrange(1, 7): if i + k < N: board_x, board_y = self.get_board_cell(len(board), i + k) dest_label = board[board_x][board_y] next_step = dest_label if dest_label != -1else i + k if dest_label != -1: if dest_label < i and dp[i] + 1 < dp[dest_label]: # remember dp[dest_label] = min(dp[dest_label], dp[i] + 1) i = dest_label - 1# remember to assign at the end break
dp[next_step] = min(dp[next_step], dp[i] + 1) # remember + 1 inside min i += 1 return dp[-1] if dp[-1] != float('inf') else -1# remember
</pre>
</pre>
