刷题记录帖子

1. class Solution:
   
2.     def countValidSelections(self, nums: List[int]) -> int:
   
3.         res = 0
   
4.         l, r = 0, sum(nums)
   
5.         for i in range(len(nums)):
   
6.             if nums[i] == 0:
   
7.                 if l == r : res += 2
   
8.                 if l - 1 == r or l == r-1: res += 1
   
9.             else:
   
10.                 l += nums[i]
    
11.                 r -= nums[i]
    
12.         return res

复制代码

LC 3354

sum_left --> sum of all elements in left to nums[i]
sum_right --> sum of all elements in right to nums[i]
when nums[i] ==0 and sum_right == sum_left : count+=2
when nums[i] ==0 and sum_right-1==sum_left : count +=1
when nums[i] == 0 and sum_right == sum_left-1 : count +=1

Math LC

1. class Solution:
   
2.     def totalMoney(self, n: int) -> int:
   
3.         n_week = n // 7
   
4.         if n_week > 0:
   
5.             res = (6 * n_week + (n_week + 1) * n_week) * 7 // 2
   
6.             remaining_week_end = n_week + (n - 7 * n_week)
   
7.             remaining_week_start = n_week + 1
   
8.             res += ((remaining_week_start + remaining_week_end) * (n - 7 * n_week) // 2)
   
9.             return res
   
10.         else:
    
11.             # first week
    
12.             return ((1+n) * n)//2
    

复制代码

LC 1716

LC 28

Although I know it shall be using KMP this is the easiest one to implement. Or directly using Python functions

1. class Solution:
   
2.     def strStr(self, haystack: str, needle: str) -> int:
   
3.         if len(needle) > len(haystack): return -1
   
4.         else:
   
5.             return haystack.find(needle)
   
6.         

复制代码

1. class Solution:
   
2.     def strStr(self, haystack, needle):
   
3.         for i in range(len(haystack) - len(needle) + 1):
   
4.             if haystack[i:i+len(needle)] == needle:
   
5.                 return i
   
6.         return -1

复制代码

LC 108

Typical pre-order traversal to form BST from sorted array

1. # Definition for a binary tree node.
   
2. # class TreeNode:
   
3. #     def __init__(self, val=0, left=None, right=None):
   
4. #         self.val = val
   
5. #         self.left = left
   
6. #         self.right = right
   
7. class Solution:
   
8.     def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
   
9.         if not nums: return None
   
10.         mid = len(nums) // 2
    
11.         root = TreeNode(nums[mid])
    
12.         root.left = self.sortedArrayToBST(nums[0:mid])
    
13.         root.right = self.sortedArrayToBST(nums[mid+1:len(nums)])
    
14.         return root

复制代码

225. Implement Stack using Queues

关键点，两个 queue，在 pop 的时候，一个 pop 一个接受，实现了 pop O(n), push O(1)

1. class MyStack:
   
2. 
   
3.     def __init__(self):
   
4.         self.q1 = []
   
5.         self.q2 = []
   
6.         self.topval = None   
   
7. 
   
8.     def push(self, x: int) -> None:
   
9.         self.q1.append(x)
   
10.         self.topval = x
    
11. 
    
12.     def pop(self) -> int:
    
13.         curr = None
    
14.         while len(self.q1) > 1:
    
15.             curr = self.q1.pop(0)
    
16.             self.q2.append(curr)
    
17.         self.topval = curr
    
18.         curr = self.q1.pop(0)
    
19.         self.q1, self.q2 = self.q2, self.q1
    
20.         return curr
    
21. 
    
22.     def top(self) -> int:
    
23.         return self.topval
    
24. 
    
25.     def empty(self) -> bool:
    
26.         return not (self.q1 or self.q2)
    
27. 
    
28. 
    
29. # Your MyStack object will be instantiated and called as such:
    
30. # obj = MyStack()
    
31. # obj.push(x)
    
32. # param_2 = obj.pop()
    
33. # param_3 = obj.top()
    
34. # param_4 = obj.empty()

复制代码

LC489

You are controlling a robot that is located somewhere in a room. The room is modeled as an m x n binary grid where 0 represents a wall and 1 represents an empty slot.

The robot starts at an unknown location in the room that is guaranteed to be empty, and you do not have access to the grid, but you can move the robot using the given API Robot.

You are tasked to use the robot to clean the entire room (i.e., clean every empty cell in the room). The robot with the four given APIs can move forward, turn left, or turn right. Each turn is 90 degrees.

When the robot tries to move into a wall cell, its bumper sensor detects the obstacle, and it stays on the current cell.

Design an algorithm to clean the entire room using the following APIs:

interface Robot {
  // returns true if next cell is open and robot moves into the cell.
  // returns false if next cell is obstacle and robot stays on the current cell.
  boolean move();

  // Robot will stay on the same cell after calling turnLeft/turnRight.
  // Each turn will be 90 degrees.
  void turnLeft();
  void turnRight();

  // Clean the current cell.
  void clean();
}
Note that the initial direction of the robot will be facing up. You can assume all four edges of the grid are all surrounded by a wall.



Custom testing:

The input is only given to initialize the room and the robot's position internally. You must solve this problem "blindfolded". In other words, you must control the robot using only the four mentioned APIs without knowing the room layout and the initial robot's position.



Example 1:


Input: room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], row = 1, col = 3
Output: Robot cleaned all rooms.
Explanation: All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.
Example 2:

Input: room = [[1]], row = 0, col = 0
Output: Robot cleaned all rooms.


Constraints:

m == room.length
n == room[i].length
1 <= m <= 100
1 <= n <= 200
room[i][j] is either 0 or 1.
0 <= row < m
0 <= col < n
room[row][col] == 1
All the empty cells can be visited from the starting position.

1. # """
   
2. # This is the robot's control interface.
   
3. # You should not implement it, or speculate about its implementation
   
4. # """
   
5. #class Robot:
   
6. #    def move(self):
   
7. #        """
   
8. #        Returns true if the cell in front is open and robot moves into the cell.
   
9. #        Returns false if the cell in front is blocked and robot stays in the current cell.
   
10. #        :rtype bool
    
11. #        """
    
12. #
    
13. #    def turnLeft(self):
    
14. #        """
    
15. #        Robot will stay in the same cell after calling turnLeft/turnRight.
    
16. #        Each turn will be 90 degrees.
    
17. #        :rtype void
    
18. #        """
    
19. #
    
20. #    def turnRight(self):
    
21. #        """
    
22. #        Robot will stay in the same cell after calling turnLeft/turnRight.
    
23. #        Each turn will be 90 degrees.
    
24. #        :rtype void
    
25. #        """
    
26. #
    
27. #    def clean(self):
    
28. #        """
    
29. #        Clean the current cell.
    
30. #        :rtype void
    
31. #        """
    
32. 
    
33. class Solution:
    
34.     def cleanRoom(self, robot):
    
35.         """
    
36.         :type robot: Robot
    
37.         :rtype: None
    
38.         """
    
39.         directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    
40.         visited = set()
    
41. 
    
42.         def DFS(x, y, d):
    
43.             robot.clean()
    
44.             visited.add((x, y))
    
45.             for i in range(4):
    
46.                 new_d = (d+i) % 4
    
47.                 new_x, new_y = x + directions[new_d][0], y + directions[new_d][1]
    
48.                 if (new_x, new_y) not in visited and robot.move():
    
49.                     DFS(new_x, new_y, new_d)
    
50.                     # need to restore robote since it moved in if condition
    
51.                     # this is to ensure backtrack to the old position to check next direction
    
52.                     robot.turnRight()
    
53.                     robot.turnRight()
    
54.                     robot.move()
    
55.                     robot.turnRight()
    
56.                     robot.turnRight()
    
57.                 # explore new direction
    
58.                 robot.turnRight()
    
59.         
    
60.         DFS(0, 0, 0)

复制代码

LC 36

More short solution

1. class Solution:
   
2.     def isValidSudoku(self, board: List[List[str]]) -> bool:
   
3.         N = 9
   
4. 
   
5.         # Use hash set to record the status
   
6.         rows = [set() for _ in range(N)]
   
7.         cols = [set() for _ in range(N)]
   
8.         boxes = [set() for _ in range(N)]
   
9. 
   
10.         for r in range(N):
    
11.             for c in range(N):
    
12.                 val = board[r][c]
    
13.                 # Check if the position is filled with number
    
14.                 if val == ".":
    
15.                     continue
    
16. 
    
17.                 # Check the row
    
18.                 if val in rows[r]:
    
19.                     return False
    
20.                 rows[r].add(val)
    
21. 
    
22.                 # Check the column
    
23.                 if val in cols[c]:
    
24.                     return False
    
25.                 cols[c].add(val)
    
26. 
    
27.                 # Check the box
    
28.                 idx = (r // 3) * 3 + c // 3
    
29.                 if val in boxes[idx]:
    
30.                     return False
    
31.                 boxes[idx].add(val)
    
32. 
    
33.         return True

复制代码

1. class Solution:
   
2.     def isValidSudoku(self, board: List[List[str]]) -> bool:
   
3.         nrows, ncols = len(board), len(board[0])
   
4.         # no repetion in row
   
5.         for i in range(nrows):
   
6.             num_set = set()
   
7.             for ele in board[i]:
   
8.                 if ele.isnumeric():
   
9.                     if ele not in num_set: num_set.add(ele)
   
10.                     else: return False
    
11. 
    
12.         # no repetion in col
    
13.         for j in range(ncols):
    
14.             num_set_col = set()
    
15.             for i in range(nrows):
    
16.                 if board[i][j].isnumeric():
    
17.                     if board[i][j] not in num_set_col: num_set_col.add(board[i][j])
    
18.                     else: return False
    
19. 
    
20.         # sub-boxes not repetion
    
21.         pos = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1,-1), (1,1), (1,-1),(-1, 1)]
    
22.         # sudoku sub-boxes centers
    
23.         for i in range(1, 8, 3):
    
24.             for j in range(1, 8, 3):
    
25.                 num_set_sub_boxes = set()
    
26.                 if board[i][j].isnumeric(): num_set_sub_boxes.add(board[i][j])
    
27.                 for p in pos:
    
28.                     if board[i+p[0]][j+p[1]].isnumeric():
    
29.                         if board[i+p[0]][j+p[1]] not in num_set_sub_boxes:
    
30.                             num_set_sub_boxes.add(board[i+p[0]][j+p[1]])
    
31.                         else: return False
    
32.         return True
    
33. 
    
34. 
    
35.         

复制代码

LC 796
String operations

1. class Solution:
   
2.     def rotateString(self, s: str, goal: str) -> bool:
   
3.         if len(s) != len(goal):
   
4.             return False
   
5.         length = len(s)
   
6. 
   
7.         # Try all possible rotations of the string
   
8.         for _ in range(length):
   
9.             # Perform one rotation
   
10.             s = s[1:] + s[0]
    
11.             if s == goal:
    
12.                 return True
    
13.         return False

复制代码

拼接两个字符串 S 就是旋转 S。

A clever way to exploit this is by concatenating s with itself. Why? Because this effectively creates a string that contains all possible rotations of s within it. For example, if s = "abcde", then s + s = "abcdeabcde". Notice how every possible rotation of s appears somewhere in this concatenated string.

1. class Solution:
   
2.     def rotateString(self, s: str, goal: str) -> bool:
   
3.         # edge case
   
4.         if len(s) != len(goal): return False
   
5.         double_s = s + s
   
6.         return double_s.find(goal) != -1

复制代码

LC 896. Monotonic Array

1. class Solution:
   
2.     def isMonotonic(self, nums: List[int]) -> bool:
   
3.         increasing, decreasing = True, True
   
4. 
   
5.         for i in range(len(nums)-1):
   
6.             if nums[i] > nums[i+1]: increasing = False
   
7.             if nums[i] < nums[i+1]: decreasing = False
   
8. 
   
9.         return increasing or decreasing

复制代码

LC 961. N-Repeated Element in Size 2N Array

1. class Solution:
   
2.     def repeatedNTimes(self, nums: List[int]) -> int:
   
3.         freq = collections.Counter(nums)
   
4.         for n in freq.keys():
   
5.             if freq[n] > 1: return n

复制代码