KK's blog

LeetCode 346 Moving Average from Data Stream

Posted on 2022-01-24 Disqus:

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Implement the MovingAverage class:

MovingAverage(int size) Initializes the object with the size of the window size. double next(int val) Returns the moving average of the last size values of the stream.

Example 1:

Input
[“MovingAverage”, “next”, “next”, “next”, “next”]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

Constraints:

1 <= size <= 1000 -105 <= val <= 105
* At most 104 calls will be made to next.

题目大意：

求data stream特定窗口的平均数

解题思路：

结构上跟LRU cache类似

解题步骤：

N/A

注意事项：

用queue

Python代码：

def __init__(self, size: int):
	self.queue = collections.deque()
	self.size = size
	self.sum = 0

def next(self, val: int) -> float:
	if len(self.queue) < self.size:
		self.queue.append(val)
		self.sum += val
	else:
		n = self.queue.popleft()
		self.sum -= n
		self.queue.append(val)
		self.sum += val
	return self.sum / len(self.queue)

算法分析：

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

LeetCode 328 Odd Even Linked List

Posted on 2022-01-23 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 <= 104
* -106 <= Node.val <= 106

题目大意：

重排LL，先偶位再奇位

解题思路：

N/A

解题步骤：

N/A

注意事项：

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

Python代码：

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)

LeetCode 325 Maximum Size Subarray Sum Equals k

Posted on 2022-01-23 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 10⁵*-10⁴ <= nums[i] <= 10⁴*-10⁹ <= k <= 10⁹`

题目大意：

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

解题思路：

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

解题步骤：

N/A

注意事项：

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

Python代码：

# 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)

LeetCode 315 Count of Smaller Numbers After Self

Posted on 2022-01-23 Edited on 2022-02-02 Disqus:

LeetCode

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example 1:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Example 2:

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

Example 3:

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

Constraints:

1 <= nums.length <= 105 -104 <= nums[i] <= 104

题目大意：

数组中，统计每一位比自己小的数。

解题思路：

一开始考虑用递减栈。但不可行, 因为这是统计题，而不是求比自己大的一个数LeetCode 503 Next Greater Element II。类似于merge sort，考虑统计逆序数

解题步骤：

N/A

注意事项：

由于mergesort会改变数组顺序，所以统计数组count也要对应的数也会变，所以将原数组变成(数值, 下标)对，count就可以统计原数组
计算逆序对时候，放在nums[i][0] <= nums[j][0]中，核心在count[nums[i][1]] += j - mid - 1

Python代码：

def countSmaller(self, nums: List[int]) -> List[int]:
	count = [0] * len(nums)
	num_with_idx = [(n, i) for i, n in enumerate(nums)]
	self.merge_sort(num_with_idx, 0, len(nums) - 1, count)
	return count

def merge_sort(self, nums, start, end, count):
	if start >= end:
		return
	mid = start + (end - start) // 2
	self.merge_sort(nums, start, mid, count)
	self.merge_sort(nums, mid + 1, end, count)
	self.merge(nums, start, mid, end, count)

def merge(self, nums, start, mid, end, count):
	i, j = start, mid + 1
	res = []
	while i <= mid and j <= end:
		if nums[i][0] <= nums[j][0]:
			res.append(nums[i])
			count[nums[i][1]] += j - mid - 1
			i += 1
		else:
			res.append(nums[j])
			j += 1
	while i <= mid:
		res.append(nums[i])
		count[nums[i][1]] += j - mid - 1
		i += 1
	while j <= end:
		res.append(nums[j])
		j += 1
	nums[start:end + 1] = res

算法分析：

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

LeetCode 348 Design Tic-Tac-Toe

Posted on 2022-01-23 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 n2 calls will be made to move.

*Follow-up: Could you do better than O(n2) per move() operation?

题目大意：

设计井字过三关

解题思路：

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

解题步骤：

N/A

注意事项：

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

Python代码：

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)