刷题记录帖子

LC 293. Flip Game
Solved
Easy
Topics
conpanies icon
Companies
You are playing a Flip Game with your friend.

You are given a string currentState that contains only '+' and '-'. You and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move, and therefore the other person will be the winner.

Return all possible states of the string currentState after one valid move. You may return the answer in any order. If there is no valid move, return an empty list [].



Example 1:

Input: currentState = "++++"
Output: ["--++","+--+","++--"]
Example 2:

Input: currentState = "+"
Output: []


Constraints:

1 <= currentState.length <= 500
currentState[i] is either '+' or '-'.

1. class Solution:
   
2.     def generatePossibleNextMoves(self, currentState: str) -> List[str]:
   
3.         ind = 0
   
4.         n = len(currentState)
   
5.         ans = []
   
6. 
   
7.         while ind < n:
   
8. 
   
9.             if ind + 1 < n and currentState[ind] == '+' and currentState[ind+1] == '+':
   
10.                 if ind + 2 < n:
    
11.                     ans.append(currentState[:ind] + '--' + currentState[ind+2:])
    
12.                 else:
    
13.                     ans.append(currentState[:ind] + '--')
    
14. 
    
15. 
    
16.             ind += 1
    
17.         
    
18.         return ans
    
19. 
    
20.         

复制代码

想复杂了， Python 如果 在 Python 中，切片 s[n:] 如果 n 等于或超过字符串长度，会直接返回一个空字符串 ""，而不会报错。所以这里的   if ind + 2 < n:  是不需要的。

本质，这是一个固定长度为 2 的滑动窗口。

1. class Solution:
   
2.     def generatePossibleNextMoves(self, currentState: str) -> List[str]:
   
3.         res = []
   
4.         # 遍历到 n-1 即可，因为我们要检查 i 和 i+1
   
5.         for i in range(len(currentState) - 1):
   
6.             # 找到连续的 "++"
   
7.             if currentState[i] == '+' and currentState[i+1] == '+':
   
8.                 # 利用切片拼接：前段 + "--" + 后段
   
9.                 # currentState[i+2:] 即使越界也会返回 ""，非常安全
   
10.                 res.append(currentState[:i] + "--" + currentState[i+2:])
    
11.         
    
12.         return res

复制代码

157. Read N Characters Given Read4
Solved
Easy
Topics
conpanies icon
Companies
Given a file and assume that you can only read the file using a given method read4, implement a method to read n characters.

Method read4:

The API read4 reads four consecutive characters from file, then writes those characters into the buffer array buf4.

The return value is the number of actual characters read.

Note that read4() has its own file pointer, much like FILE *fp in C.

Definition of read4:

    Parameter:  char[] buf4
    Returns:    int

buf4[] is a destination, not a source. The results from read4 will be copied to buf4[].
Below is a high-level example of how read4 works:


File file("abcde"); // File is "abcde", initially file pointer (fp) points to 'a'
char[] buf4 = new char[4]; // Create buffer with enough space to store characters
read4(buf4); // read4 returns 4. Now buf4 = "abcd", fp points to 'e'
read4(buf4); // read4 returns 1. Now buf4 = "e", fp points to end of file
read4(buf4); // read4 returns 0. Now buf4 = "", fp points to end of file


Method read:

By using the read4 method, implement the method read that reads n characters from file and store it in the buffer array buf. Consider that you cannot manipulate file directly.

The return value is the number of actual characters read.

Definition of read:

    Parameters:        char[] buf, int n
    Returns:        int

buf[] is a destination, not a source. You will need to write the results to buf[].
Note:

Consider that you cannot manipulate the file directly. The file is only accessible for read4 but not for read.
The read function will only be called once for each test case.
You may assume the destination buffer array, buf, is guaranteed to have enough space for storing n characters.


Example 1:

Input: file = "abc", n = 4
Output: 3
Explanation: After calling your read method, buf should contain "abc". We read a total of 3 characters from the file, so return 3.
Note that "abc" is the file's content, not buf. buf is the destination buffer that you will have to write the results to.
Example 2:

Input: file = "abcde", n = 5
Output: 5
Explanation: After calling your read method, buf should contain "abcde". We read a total of 5 characters from the file, so return 5.
Example 3:

Input: file = "abcdABCD1234", n = 12
Output: 12
Explanation: After calling your read method, buf should contain "abcdABCD1234". We read a total of 12 characters from the file, so return 12.


Constraints:

1 <= file.length <= 500
file consist of English letters and digits.
1 <= n <= 1000

1. """
   
2. The read4 API is already defined for you.
   
3. 
   
4.     @param buf4, a list of characters
   
5.     [url=home.php?mod=space&uid=160137]@return[/url] an integer
   
6.     def read4(buf4):
   
7. 
   
8. # Below is an example of how the read4 API can be called.
   
9. file = File("abcdefghijk") # File is "abcdefghijk", initially file pointer (fp) points to 'a'
   
10. buf4 = [' '] * 4 # Create buffer with enough space to store characters
    
11. read4(buf4) # read4 returns 4. Now buf = ['a','b','c','d'], fp points to 'e'
    
12. read4(buf4) # read4 returns 4. Now buf = ['e','f','g','h'], fp points to 'i'
    
13. read4(buf4) # read4 returns 3. Now buf = ['i','j','k',...], fp points to end of file
    
14. """
    
15. 
    
16. class Solution:
    
17.     def read(self, buf, n):
    
18.         """
    
19.         :type buf: Destination buffer (List[str])
    
20.         :type n: Number of characters to read (int)
    
21.         :rtype: The number of actual characters read (int)
    
22.         """
    
23.         
    
24.         # 已读入到 buf 的字符总数
    
25.         copied_chars = 0
    
26.         # 临时缓冲区，用于存放 read4 读取的 4 个字符
    
27.         buf4 = [''] * 4
    
28.         
    
29.         while copied_chars < n:
    
30.             # 1. 从文件读取数据到临时缓冲区
    
31.             count = read4(buf4)
    
32.             
    
33.             # 如果没读到数据，说明文件已经结束
    
34.             if count == 0:
    
35.                 break
    
36.             
    
37.             # 2. 计算本次实际需要拷贝多少个字符
    
38.             # 剩余需要读取的字符数为 n - copied_chars
    
39.             # 我们只能从 count 和 剩余需求量 之间取最小值
    
40.             remaining_needed = n - copied_chars
    
41.             curr_copy_count = min(count, remaining_needed)
    
42.             
    
43.             # 3. 将数据从临时缓冲区 buf4 拷贝到目标缓冲区 buf
    
44.             for i in range(curr_copy_count):
    
45.                 buf[copied_chars] = buf4[i]
    
46.                 copied_chars += 1
    
47.             
    
48.             # 如果本次 read4 读到的字符少于 4 个，说明已经读到文件末尾了
    
49.             if count < 4:
    
50.                 break
    
51.         
    
52.         return copied_chars

复制代码

LC 2075. Decode the Slanted Ciphertext

1. class Solution:
   
2.     def decodeCiphertext(self, encodedText: str, rows: int) -> str:
   
3.         if not encodedText or rows == 0:
   
4.             return ""
   
5.         
   
6.         n = len(encodedText)
   
7.         ncols = int(n // rows)
   
8. 
   
9.         ans = []
   
10. 
    
11.         for i in range(ncols):
    
12.             # process each slanted cols
    
13.             r = 0
    
14.             c = i
    
15.             while r < rows and c < ncols:
    
16.                 ans.append(encodedText[ r * ncols + c])
    
17.                 r += 1
    
18.                 c += 1
    
19.         
    
20.         return "".join(ans).rstrip()
    
21. 
    
22.         
    
23.         

复制代码

这道题目的核心是找到数组 index 和 decodedText 的对应规律，

r x cols + c

这里需要记住，decoded text 是按照 行存储的。

所以对于 (r,c) 在矩阵中的位置，需要跳过前面行的所有 cols，来排列在 加密text 里面。

实在不行，其实面试的时候，直接上例子吧，推算几个答案。

LC. 3707. Equal Score Substrings

1. class Solution:
   
2.     def scoreBalance(self, s: str) -> bool:
   
3.         n = len(s)
   
4.         pre_sum = [0] * (n+1)
   
5. 
   
6.         for i in range(1, n+1):
   
7.             pre_sum[i] = pre_sum[i-1] + (ord(s[i-1]) - ord('a') + 1)
   
8.             
   
9.         if pre_sum[n] % 2 == 1: return False
   
10.         else:
    
11.             for i in range(1, n):
    
12.                 if pre_sum[i] == pre_sum[n] // 2:
    
13.                     return True
    
14.         
    
15.         return False
    
16.         

复制代码

LC. 3701. Compute Alternating Sum

1. class Solution:
   
2.     def alternatingSum(self, nums: List[int]) -> int:
   
3.         s = 0
   
4. 
   
5.         for i in range(len(nums)):
   
6.             if i % 2 == 1:
   
7.                 s -= nums[i]
   
8.             else:
   
9.                 s += nums[i]
   
10.         return s

复制代码

LC. 3697. Compute Decimal Representation

1. class Solution:
   
2.     def decimalRepresentation(self, n: int) -> List[int]:
   
3.         res = []
   
4.         d = 0
   
5. 
   
6.         while n:
   
7.             c = n % 10
   
8.             if c != 0: res.append(c * 10 ** d)
   
9.             d += 1
   
10.             n = n // 10
    
11. 
    
12.         
    
13. 
    
14.         return res[::-1]
    
15.         

复制代码

优化，用数字 p 来记录当前的位数，而不是用幂来记录。

不过也不是啥大优化。

1. class Solution:
   
2.     def decimalRepresentation(self, n: int) -> list[int]:
   
3.         res = []
   
4.         # 我们从低位向高位处理，但为了降序，我们可以先拿到所有结果再翻转
   
5.         # 或者直接计算当前 n 的最大量级。为了简洁，翻转你的思路是最稳的。
   
6.         p = 1
   
7.         while n > 0:
   
8.             digit = n % 10
   
9.             if digit != 0:
   
10.                 res.append(digit * p)
    
11.             n //= 10
    
12.             p *= 10
    
13.         
    
14.         return res[::-1] # 降序排列

复制代码

LC. 657. Robot Return to Origin

1. class Solution:
   
2.     def judgeCircle(self, moves: str) -> bool:
   
3.         directions = { 'R': (1, 0), 'L': (-1, 0), 'U': (0, 1), 'D': (0, -1)}
   
4.         x, y = 0, 0
   
5.         
   
6.         for move in moves:
   
7.             x += directions[move][0]
   
8.             y += directions[move][1]
   
9. 
   
10.         return x == 0 and y == 0
    
11.             
    
12.         

复制代码

LC 3692. Majority Frequency Characters

1. class Solution:
   
2.     def majorityFrequencyGroup(self, s: str) -> str:
   
3.         count = Counter(s)
   
4. 
   
5.         freq_group = defaultdict(list)
   
6. 
   
7.         for key, val in count.items():
   
8.             freq_group[val].append(key)
   
9. 
   
10.         freq_list = []
    
11. 
    
12.         for key, val in freq_group.items():
    
13.             freq_list.append((len(val), key))
    
14.         freq_list.sort(reverse = True)
    
15. 
    
16.         return "".join(freq_group[freq_list[0][1]])

复制代码

LC. 3696. Maximum Distance Between Unequal Words in Array I
Solved
Easy
Topics
Hint
You are given a string array words.

Find the maximum distance between two distinct indices i and j such that:

words[i] != words[j], and
the distance is defined as j - i + 1.
Return the maximum distance among all such pairs. If no valid pair exists, return 0.



Example 1:

Input: words = ["leetcode","leetcode","codeforces"]

Output: 3

Explanation:

In this example, words[0] and words[2] are not equal, and they have the maximum distance 2 - 0 + 1 = 3.

Example 2:

Input: words = ["a","b","c","a","a"]

Output: 4

Explanation:

In this example words[1] and words[4] have the largest distance of 4 - 1 + 1 = 4.

Example 3:

Input: words = ["z","z","z"]

Output: 0

Explanation:

In this example all the words are equal, thus the answer is 0.



Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.


我的解法，其实还是记录第一次出现的单词的位置，

1. class Solution:
   
2.     def maxDistance(self, words: List[str]) -> int:
   
3.         w_ind = dict()
   
4.         max_dist = float('-inf')
   
5. 
   
6.         for ind, w in enumerate(words):
   
7. 
   
8.             for w_pre in w_ind:
   
9.                 if w_pre != w:
   
10.                     max_dist = max(max_dist, ind - w_ind[w_pre]+1)
    
11.             
    
12.             if w not in w_ind:
    
13.                 w_ind[w] = ind
    
14.         if max_dist == float('-inf'):
    
15.             return 0
    
16.         else:
    
17.             return max_dist
    
18. 
    
19.         

复制代码

但是可以简化逻辑，

我们只需要锁定两个特殊的“最左侧”位置：

first_idx: 整个数组第一个词的下标（即 0）。

diff_idx: 整个数组中，第一个与第一个词不同的词的下标。

其实我们不需要遍历字典里的每一个单词。要让距离最大，只需要考虑两种情况：

当前词 words[j] 和全数组最左边的词 words[0] 比较（如果它们不等）。

如果 words[j] 恰好等于 words[0]，那它只能和全数组第一个与 words[0] 不相等的词比较。

1. class Solution:
   
2.     def maxDistance(self, words: List[str]) -> int:
   
3.         n = len(words)
   
4.         # 找到第一个和 words[0] 不一样的词的位置
   
5.         diff_idx = -1
   
6.         for i in range(1, n):
   
7.             if words[i] != words[0]:
   
8.                 diff_idx = i
   
9.                 break
   
10.         
    
11.         # 如果没找到，说明全数组都一样
    
12.         if diff_idx == -1:
    
13.             return 0
    
14.             
    
15.         max_dist = 0
    
16.         for j in range(n):
    
17.             # 情况 1：当前词不等于第一个词，跟第一个词比
    
18.             if words[j] != words[0]:
    
19.                 max_dist = max(max_dist, j - 0 + 1)
    
20.             # 情况 2：当前词等于第一个词，跟第一个不同的词（diff_idx）比
    
21.             else:
    
22.                 max_dist = max(max_dist, j - diff_idx + 1)
    
23.                
    
24.         return max_dist

复制代码

LC 874. Walking Robot Simulation

1. class Solution:
   
2.     def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
   
3.         direction = (0, 1)
   
4.         x = 0
   
5.         y = 0
   
6.         ans = -1
   
7. 
   
8.         obstacles = set((o[0], o[1]) for o in obstacles )
   
9. 
   
10.         for command in commands:
    
11.             if command == -2:
    
12.                 d1, d2 = direction
    
13.                 direction = (-1 * d2, d1)
    
14.             elif command == -1:
    
15.                 d1, d2 = direction
    
16.                 direction  = (d2 , -1 * d1)
    
17.             else:
    
18.                 for i in range(command):
    
19.                     tmp_x, tmp_y = x + direction[0], y + direction[1]
    
20.                     if (tmp_x, tmp_y) in obstacles:
    
21.                         break
    
22.                     else:
    
23.                         ans = max(ans, tmp_x **2 + tmp_y **2)
    
24.                         x, y = tmp_x, tmp_y
    
25.         
    
26.         return max(ans, 0)

复制代码