KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not one, return 0 instead.

Example 1:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.


Example 2:

Input: nums = [-2,-1,2,1], k = 1
Output: 2
Explanation: The subarray [-1, 2] sums to 1 and is the longest.


Constraints:

`1 <= nums.length <= 2 105*-104 <= nums[i] <= 104*-109 <= k <= 109`

题目大意：

最长子数组和等于k，求长度

解题思路：

一开始以为类似于LeetCode 209 Minimum Size Subarray Sum用同向双指针。但这题不是连续，因为此题含负数，不会连续大于等于target。考虑用presum的two sum法。

解题步骤：

N/A

注意事项：

  1. 加入presum[0] = 0，因为这样才可以得到以首元素开始的子数组和
  2. 若presum已经在hashmap中了，不要加入，因为要保证最长数组，如 [-1, 1], target = 0, index可以为0, 2
  3. max_len答案只要初始化为0，不用最小值，因为最大长度必为非负

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
# presum[i] - presum[j] = k
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
	max_len, presum = 0, 0 # not float('-inf')
	sum_to_idx = collections.defaultdict(int)
	sum_to_idx[0] = 0
	for i in range(len(nums)):
		presum += nums[i]
		if presum - k in sum_to_idx:
			max_len = max(max_len, i - sum_to_idx[presum - k] + 1)
		if presum not in sum_to_idx: # remember
			sum_to_idx[presum] = i + 1
	return max_len

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Example 1:



Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]


Example 2:



Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]


Constraints:

n ==number of nodes in the linked list 0 <= n <= 10<sup>4</sup>
* -10<sup>6</sup> <= Node.val <= 10<sup>6</sup>

题目大意：

重排LL， 先偶位再奇位

解题思路：

N/A

解题步骤：

N/A

注意事项：

  1. LL四点注意事项： 删除节点.next = None
  2. 空输入特别处理

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def oddEvenList(self, head: ListNode) -> ListNode:
	if not head: # remember
		return None
	odd_head = ListNode(0)
	it, it_odd = head, odd_head
	while it.next:
		it_odd.next = it.next
		it.next = it.next.next
		if it.next:
			it = it.next
		it_odd = it_odd.next
		it_odd.next = None # remember
	it.next = odd_head.next
	return head

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Assume the following rules are for the tic-tac-toe game on an n x n board between two players:

1. A move is guaranteed to be valid and is placed on an empty block.
2. Once a winning condition is reached, no more moves are allowed.
3. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Implement the TicTacToe class:

TicTacToe(int n) Initializes the object the size of the board n. int move(int row, int col, int player) Indicates that the player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move.

Example 1:

Input
[“TicTacToe”, “move”, “move”, “move”, “move”, “move”, “move”, “move”]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Output
[null, 0, 0, 0, 0, 0, 0, 1]

Explanation
TicTacToe ticTacToe = new TicTacToe(3);
Assume that player 1 is “X” and player 2 is “O” in the board.
ticTacToe.move(0, 0, 1); // return 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

ticTacToe.move(0, 2, 2); // return 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

ticTacToe.move(2, 2, 1); // return 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

ticTacToe.move(1, 1, 2); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

ticTacToe.move(2, 0, 1); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

ticTacToe.move(1, 0, 2); // return 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

ticTacToe.move(2, 1, 1); // return 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|


Constraints:

2 <= n <= 100 player is 1 or 2.
0 <= row, col < n (row, col) are unique for each different call to move.
At most n<sup>2</sup> calls will be made to move.

*Follow-up: Could you do better than O(n<sup>2</sup>) per move() operation?

题目大意：

设计井字过三关

解题思路：

游戏题。最重要是是数据结构，类似于LeetCode 051 N-Queens和LeetCode 037 Sudoku Solver用matrix记录每行，每列，对角线和反对角线的和。这样验证时候只需要O(1).

解题步骤：

N/A

注意事项：

  1. 对角线和反对角线只有一条，所以要先判断move的这个点是否在对角线上。
  2. 由于用-1来代表某一个player，所以判断和时候，用abs

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

    def __init__(self, n: int):
        self.board_len = n
        self.row = [0] * n
        self.col = [0] * n
        self.diag = 0
        self.anti_diag = 0

    def move(self, row: int, col: int, player: int) -> int:
        if player == 2:
            player = -1
        self.row[row] += player
        self.col[col] += player
        if row == col: # remember
            self.diag += player
        if row == self.board_len - 1 - col:
            self.anti_diag += player
        does_win = abs(self.row[row]) == self.board_len or abs(self.col[col]) == self.board_len or \
                abs(self.diag) == self.board_len or abs(self.anti_diag) == self.board_len # remember abs
        if does_win:
            if player == -1:
                return 2
            else:
                return player
        return 0

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given a 2D matrix matrix, handle multiple queries of the following type:

Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class: NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Example 1:



Input
[“NumMatrix”, “sumRegion”, “sumRegion”, “sumRegion”]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
Output
[null, 8, 11, 12]

Explanation
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)


Constraints: m == matrix.length
n == matrix[i].length 1 <= m, n <= 200
-10<sup>5</sup> <= matrix[i][j] <= 10<sup>5</sup> 0 <= row1 <= row2 < m
0 <= col1 <= col2 < n At most 10<sup>4</sup> calls will be made to sumRegion.

题目大意：

求子矩阵和

解题思路：

计算presum公式:

1
dp[i][j] = matrix[i-1][j-1] + dp[i-1][j] + dp[i][j] - dp[i-1][j-1]

计算子矩阵公式：

1
res = presum[x][y] - left - top + diag

解题步骤：

N/A

注意事项：

  1. dp有左上边界，计算子矩阵注意dp和输入差1

Python代码：

1
2
3
4
5
6
7
8
9
10
class NumMatrix(TestCases):

    def __init__(self, matrix: List[List[int]]):
        self.dp = [[0 for _ in range(len(matrix[0]) + 1)] for _ in range(len(matrix) + 1)]
        for i in range(1, len(self.dp)):
            for j in range(1, len(self.dp[0])):
                self.dp[i][j] = matrix[i - 1][j - 1] + self.dp[i - 1][j] + self.dp[i][j - 1] - self.dp[i - 1][j - 1]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.dp[row2 + 1][col2 + 1] - self.dp[row2 + 1][col1] - self.dp[row1][col2 + 1] + self.dp[row1][col1]

算法分析：

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

Posted on Edited on Disqus:

LeetCode



You are given an m x n grid rooms initialized with these three possible values.

-1 A wall or an obstacle. 0 A gate.
INF Infinity means an empty room. We use the value 2<sup>31</sup> - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Example 1:



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


Example 2:

Input: rooms = [[-1]]
Output: [[-1]]


Constraints: m == rooms.length
n == rooms[i].length 1 <= m, n <= 250
* rooms[i][j] is -1, 0, or 2<sup>31</sup> - 1.

题目大意：

求所有房间到门的最短距离

解题思路：

属于多始点BFS类型

解题步骤：

N/A

注意事项：

  1. 门的距离不更新，所以出列后要判断该点是否为门，不是用距离来判断

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
OFFSET = [(-1, 0), (1, 0), (0, 1), (0, -1)]
class Solution(TestCases):

    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        gates = []
        for i in range(len(rooms)):
            for j in range(len(rooms[0])):
                if rooms[i][j] == 0:
                    gates.append((i, j, 0))
        queue = collections.deque(gates)
        visited = set(gates)
        while queue:
            x, y, distance = queue.popleft()
            if rooms[x][y] != 0: # not distance != 0
                rooms[x][y] = distance
            for _dx, _dy in OFFSET:
                _x, _y = x + _dx, y + _dy
                if _x < 0 or _x >= len(rooms) or _y < 0 or _y >= len(rooms[0]) or \
                        rooms[_x][_y] == -1 or (_x, _y) in visited:
                    continue
                queue.append((_x, _y, distance + 1))
                visited.add((_x, _y))

算法分析：

时间复杂度为O(nm)，空间复杂度O(mn)

Free mock interview