刷题记录帖子

1148. Article Views I

1. SELECT
   
2.     DISTINCT author_id AS id
   
3. FROM
   
4.     Views
   
5. WHERE
   
6.     author_id = viewer_id
   
7. ORDER BY
   
8.     id
   

复制代码

1581. Customer Who Visited but Did Not Make Any Transactions

1. import pandas as pd
   
2. 
   
3. def find_customers(visits: pd.DataFrame, transactions: pd.DataFrame) -> pd.DataFrame:
   
4.     vistit_no_transactions = visits[~visits.visit_id.isin(transactions.visit_id)]
   
5.     df = vistit_no_transactions.groupby('customer_id', as_index=False)['visit_id'].count()
   
6.     return df.rename(columns={'visit_id': 'count_no_trans'})

复制代码

1152. Analyze User Website Visit Pattern

You are given two string arrays username and website and an integer array timestamp. All the given arrays are of the same length and the tuple [username[i], website[i], timestamp[i]] indicates that the user username[i] visited the website website[i] at time timestamp[i].

A pattern is a list of three websites (not necessarily distinct).

For example, ["home", "away", "love"], ["leetcode", "love", "leetcode"], and ["luffy", "luffy", "luffy"] are all patterns.
The score of a pattern is the number of users that visited all the websites in the pattern in the same order they appeared in the pattern.

For example, if the pattern is ["home", "away", "love"], the score is the number of users x such that x visited "home" then visited "away" and visited "love" after that.
Similarly, if the pattern is ["leetcode", "love", "leetcode"], the score is the number of users x such that x visited "leetcode" then visited "love" and visited "leetcode" one more time after that.
Also, if the pattern is ["luffy", "luffy", "luffy"], the score is the number of users x such that x visited "luffy" three different times at different timestamps.
Return the pattern with the largest score. If there is more than one pattern with the same largest score, return the lexicographically smallest such pattern.

Note that the websites in a pattern do not need to be visited contiguously, they only need to be visited in the order they appeared in the pattern.



Example 1:

Input: username = ["joe","joe","joe","james","james","james","james","mary","mary","mary"], timestamp = [1,2,3,4,5,6,7,8,9,10], website = ["home","about","career","home","cart","maps","home","home","about","career"]
Output: ["home","about","career"]
Explanation: The tuples in this example are:
["joe","home",1],["joe","about",2],["joe","career",3],["james","home",4],["james","cart",5],["james","maps",6],["james","home",7],["mary","home",8],["mary","about",9], and ["mary","career",10].
The pattern ("home", "about", "career") has score 2 (joe and mary).
The pattern ("home", "cart", "maps") has score 1 (james).
The pattern ("home", "cart", "home") has score 1 (james).
The pattern ("home", "maps", "home") has score 1 (james).
The pattern ("cart", "maps", "home") has score 1 (james).
The pattern ("home", "home", "home") has score 0 (no user visited home 3 times).
Example 2:

Input: username = ["ua","ua","ua","ub","ub","ub"], timestamp = [1,2,3,4,5,6], website = ["a","b","a","a","b","c"]
Output: ["a","b","a"]


Constraints:

3 <= username.length <= 50
1 <= username[i].length <= 10
timestamp.length == username.length
1 <= timestamp[i] <= 109
website.length == username.length
1 <= website[i].length <= 10
username[i] and website[i] consist of lowercase English letters.
It is guaranteed that there is at least one user who visited at least three websites.
All the tuples [username[i], timestamp[i], website[i]] are unique.

1. class Solution:
   
2.     def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
   
3.         data = [(user, ts, site) for user, ts, site in zip(username, timestamp, website)]
   
4.         data = sorted(data, key = lambda x: x[1])
   
5. 
   
6.         user_path = collections.defaultdict(list)
   
7.         for d in data:
   
8.             user_path[d[0]].append(d[2])
   
9. 
   
10.         freq_count = collections.defaultdict(int)
    
11.         for u, u_path in user_path.items():
    
12.             distinct_path = set()
    
13.             for i in range(len(u_path)):
    
14.                 for j in range(i+1, len(u_path)):
    
15.                     for k in range(j+1, len(u_path)):
    
16.                         distinct_path.add((u_path[i], u_path[j], u_path[k]))
    
17.             for k in distinct_path:
    
18.                 freq_count[k] += 1
    
19. 
    
20.         maxCount = -1
    
21.         res  = ()
    
22.         for k, v in freq_count.items():
    
23.             if v > maxCount or (v == maxCount and k < res):
    
24.                 maxCount = v
    
25.                 res = k
    
26.         
    
27.         return list(res)
    
28. 
    
29.    
    
30. 
    
31. 
    
32.         

复制代码

1. class Node:
   
2.     def __init__(self, name, timestamp, website):
   
3.         self.name = name
   
4.         self.timestamp = timestamp
   
5.         self.website = website
   
6. 
   
7. 
   
8. class Solution:
   
9.     def mostVisitedPattern(
   
10.         self, username: List[str], timestamp: List[int], website: List[str]
    
11.     ) -> List[str]:
    
12.         nodes = [
    
13.             Node(name, ts, site)
    
14.             for name, ts, site in zip(username, timestamp, website)
    
15.         ]
    
16.         nodes.sort(key=lambda x: x.timestamp)
    
17.         user_visits = defaultdict(list)
    
18.         for node in nodes:
    
19.             user_visits[node.name].append(node)
    
20. 
    
21.         route = defaultdict(int)
    
22.         for visits in user_visits.values():
    
23.             tmp = set()
    
24.             for i, j, k in combinations(range(len(visits)), 3):
    
25.                 path = (visits[i].website, visits[j].website, visits[k].website)
    
26.                 tmp.add(path)
    
27.             for path in tmp:
    
28.                 route[path] += 1
    
29. 
    
30.         max_count = -1
    
31.         result = ()
    
32.         for path, count in route.items():
    
33.             if count > max_count or (count == max_count and path < result):
    
34.                 max_count = count
    
35.                 result = path
    
36.         return list(result)

复制代码

1603. Design Parking System

1. class ParkingSystem:
   
2. 
   
3.     def __init__(self, big: int, medium: int, small: int):
   
4.         self.spaces = [big, medium, small]
   
5.         self.status = [0, 0, 0]
   
6.         
   
7. 
   
8.     def addCar(self, carType: int) -> bool:
   
9.         if self.status[carType-1] + 1 > self.spaces[carType-1]: return False
   
10.         else:
    
11.             self.status[carType-1] += 1
    
12.             return True
    
13. 
    
14. 
    
15. # Your ParkingSystem object will be instantiated and called as such:
    
16. # obj = ParkingSystem(big, medium, small)
    
17. # param_1 = obj.addCar(carType)

复制代码

1661. Average Time of Process per Machine

用负数来使得 start time 可以自动剪掉。

1. def get_average_time(activity: pd.DataFrame) -> pd.DataFrame:
   
2. 
   
3.     activity['timestamp'] = activity.apply(lambda x: x.timestamp * -1 if x.activity_type == 'start' else x.timestamp, axis=1)
   
4. 
   
5.     sum_machine_process = activity.groupby(['machine_id', 'process_id'], as_index=False)['timestamp'].sum()
   
6. 
   
7.     mean_machine = sum_machine_process.groupby(['machine_id'], as_index=False)['timestamp'].mean().round(3).rename(columns = {'timestamp': 'processing_time'})
   
8.    
   
9.     return mean_machine

复制代码

1757. Recyclable and Low Fat Products

1. import pandas as pd
   
2. 
   
3. def find_products(products: pd.DataFrame) -> pd.DataFrame:
   
4.     df = products[(products['low_fats'] == 'Y') & (products['recyclable'] == 'Y')]
   
5.     df = df[['product_id']]
   
6.     return df
   
7.    

复制代码

3314. Construct the Minimum Bitwise Array I
3315. Construct the Minimum Bitwise Array II

1. class Solution:
   
2.     def minBitwiseArray(self, nums: List[int]) -> List[int]:
   
3.         ans = []
   
4.         for i in range(len(nums)):
   
5.             res = -1
   
6.             d = 1 # mask
   
7.             while (nums[i] & d) != 0:
   
8.                 res = nums[i] - d
   
9.                 d <<= 1
   
10.             ans.append(res)
    
11.         return ans
    
12.         

复制代码

Only data length are different, so brute force works for I but not for II.

But the following log operations works

这段代码其实是一个经典 bit trick 的反向构造。我按「在干什么 → 为什么这样做 → 举例」来解释。

一、这段代码在干什么（整体）

对 nums 里的每个数 x：

找到一个 最小的 y，使得
y | (y + 1) == x
如果找不到，就返回 -1

最终返回的是一个数组，每个元素是对应的 y。

二、逐行解释
for i in range(len(nums)):


遍历数组里的每个数。

res = -1


默认结果是 -1，表示不存在合法解。

d = 1


d 是一个 bit mask，从最低位开始（1, 2, 4, 8, ...）。

while (nums[i] & d) != 0:


意思是：
👉 只要 nums[i] 在第 d 这一位上是 1，就继续

也就是说：

从最低位开始

一直扫 连续的 trailing 1s

res = nums[i] - d


关键行 🔑

如果 nums[i] 在 d 位是 1：

尝试把这一位 清零

得到候选值 y = nums[i] - d

d <<= 1


检查下一位（左移一位）。

nums[i] = res


循环结束后，把找到的 最后一个合法 y 写回数组。

三、为什么这能反推出 y | (y+1) = x？

回忆我们之前说的结论：

y | (y+1)
会把 y 的 trailing 1s 以及它左边的第一个 0 全变成 1

那么反过来想：

如果 x = y | (y+1)，那 x 必须：

最低位开始是连续的 1

一旦遇到 0，就结束（不能再往上）

所以：

能构造 y 的前提：
x 至少有一个 trailing 1

四、代码的核心逻辑（精华）

while (nums[i] & d) != 0
👉 扫描 x 的 trailing 1s

每遇到一个 1：

y = x - d


相当于：

把某一位从 1 变成 0

低位保持为 1

最后一次成功的 y：

对应的是：
👉 把 最左边的 trailing 1 变成 0

这是 最小的 y

五、举例说明
例 1：x = 7 (111)
d = 1 → 111 & 001 = 1 → res = 6 (110)
d = 2 → 111 & 010 = 2 → res = 5 (101)
d = 4 → 111 & 100 = 4 → res = 3 (011)
d = 8 → 111 & 1000 = 0 → stop


结果：

y = 3
3 | 4 = 7 ✅

例 2：x = 8 (1000)
8 & 1 = 0 → while 不进
res = -1


因为没有 trailing 1：

不存在 y 使得 y | (y+1) = 8

六、一句话总结（面试版）

这段代码对每个 x，从最低位开始扫描 trailing 1s，
尝试逐步清掉某一位 1，
找到最小的 y，使得 y | (y+1) == x，
若 x 没有 trailing 1，则返回 -1。

1. class Solution:
   
2.     def minBitwiseArray(self, nums: List[int]) -> List[int]:
   
3.         for i in range(len(nums)):
   
4.             res = -1
   
5.             d = 1
   
6.             while (nums[i] & d) != 0:
   
7.                 res = nums[i] - d
   
8.                 d <<= 1
   
9.             nums[i] = res
   
10.         return nums

复制代码

5. Longest Palindromic Substring

Brute Force, O(N^3)

1. class Solution:
   
2.     def longestPalindrome(self, s: str) -> str:
   
3.         def check(i, j):
   
4.             left = i      # start
   
5.             right = j - 1 # start + curr_substring_length
   
6.             while left < right:
   
7.                 if s[left] != s[right]: return False
   
8.                 left += 1
   
9.                 right -= 1
   
10.             return True
    
11. 
    
12.         for length in range(len(s), 0, -1):
    
13.             for start in range(len(s) - length + 1):
    
14.                 if check(start, start+length):
    
15.                     return s[start : start+length]

复制代码

DP solution

1. class Solution:
   
2.     def longestPalindrome(self, s: str) -> str:
   
3.         # dp
   
4.         # dp[i][j] = dp[i+1][j-1] AND (s[i] == s[j])
   
5. 
   
6.         n = len(s)
   
7.         dp = [[False] * n for _ in range(n)]
   
8.         ans = (0, 0)
   
9. 
   
10.         # fill digonal line
    
11.         for i in range(n):
    
12.             dp[i][i] = True
    
13.             ans = (i, i)
    
14.         
    
15.         # fill i, i+1 line
    
16.         for i in range(n-1):
    
17.             j = i + 1
    
18.             if s[i] == s[j]:
    
19.                 dp[i][j] = True
    
20.                 ans = (i, j)
    
21.         # fill for length >= 3 substrings
    
22.         for length in range(2, n, 1):
    
23.             for i in range(n - length):
    
24.                 j = i + length
    
25.                 if s[i] == s[j] and dp[i+1][j-1]:
    
26.                     dp[i][j] = True
    
27.                     ans = (i, j)
    
28.         return s[ans[0]:ans[1]+1] #+1 was due to String Slice

复制代码

128. Longest Consecutive Sequence


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        freq = set(nums)

        maxLen = 0

        for num in freq:
            # ensures we only start counting from the beginning of a sequence.
            if num - 1 in freq: continue
            currLen = 1
            while num+1 in freq:
                num = num+1
                currLen += 1
            maxLen = max(currLen, maxLen)

        return maxLen

3752. Lexicographically Smallest Negated Permutation that Sums to Target

注意不要在遍历 list 的时候删除元素，可以直接原地改变。

1. class Solution:
   
2.     def lexSmallestNegatedPerm(self, n: int, target: int) -> List[int]:
   
3.         """
   
4.         once n set, the numbers will be used is fix, shall be abs(x), x from 1,2,3...n, either postive or negative
   
5. 
   
6.         so the maxSum will be (n+1) * n /2
   
7.         minSum = -1 * maxSum
   
8. 
   
9.         target must [minSum, maxSum]
   
10. 
    
11.         if target = maxSum or target = minSum, return all postive or all neagtive
    
12.         else:
    
13.             we start from all postive values and the flip the largest possible values to reach lexicographically smallest array
    
14.             you shall put larger values to negative ones to make it lexicographically smallest
    
15. 
    
16.             diff = maxSum - target
    
17.         
    
18.         k from n to 1,
    
19.             if 2*k > diff, continue
    
20.             if 2*k == diff
    
21.                 ans = [1,2.... - k,....n]
    
22.             else:
    
23.                 diff = diff - 2k
    
24.                 ans = [1,2.... - k,....n]
    
25.         """
    
26.         maxSum = n * (n+1) / 2
    
27.         if target > maxSum or target < -1 * maxSum: return []
    
28.         if target == maxSum: return [i for i in range(1, n+1)]
    
29.         if target == -1 * maxSum: return sorted([-1*i for i in range(1, n+1)])
    
30. 
    
31.         diff = maxSum -  target
    
32.         ans = []
    
33. 
    
34.         for k in range(n, 0, -1):
    
35.             if 2*k <= diff:
    
36.                 diff -= 2*k
    
37.                 ans.append(-1* k)
    
38.             else:
    
39.                 ans.append(k)
    
40. 
    
41.         if diff != 0: return []
    
42.         return sorted(ans)

复制代码

好，这题其实**想法很巧，但一旦抓住关键就很顺**。我按「**问题重述 → 关键观察 → 构造思路 → 为什么字典序最小 → 边界情况**」来讲。

---

## 一、题目在要求什么（换句话说）

你要构造一个长度为 `n` 的数组 `a`，满足：

1. **和等于 `target`**
2. **`|a[i]|` 恰好是 `{1,2,...,n}` 的一个排列**

   * 每个数 `1..n` 用一次
   * 但可以是正的，也可以是负的
3. 在所有合法解里，返回 **字典序最小** 的那个

如果做不到，返回 `[]`。

---

## 二、关键观察 1：总和能到的范围是有限的

如果所有数都取正：

```
maxSum = 1 + 2 + ... + n = n(n+1)/2
```

如果所有数都取负：

```
minSum = -maxSum
```

👉 **必要条件**：

```
-target ∈ [ -maxSum , maxSum ]
```

不在这个区间，**直接无解**。

> 这一步可以直接剪掉很多情况（Example 2）。

---

## 三、关键观察 2：从“全正”开始最容易控制

先假设数组是：

```
[1, 2, 3, ..., n]
```

此时：

```
sum = maxSum
```

如果 `sum == target`，直接返回。

否则我们需要 **降低总和**。

---

## 四、翻转一个数能改变多少和？

如果把 `k` 从 `+k` 变成 `-k`：

```
sum 减少 2k
```

👉 所以问题变成：

> 用若干个 `2k`，凑出
> `diff = maxSum - target`

---

## 五、关键观察 3：为什么要“优先翻转大的数”

我们要满足两个目标：

1. **和要对**
2. **字典序最小**

### 字典序最小 ≈ 前面的数尽量小

* 负数 < 正数
* 绝对值越大，负数越小（-n 最小）

👉 **想让字典序最小，就要让前面尽量出现大的负数**

所以策略是：

> **优先考虑把大的数变成负数**

---

## 六、核心贪心思路（非常重要）

令：

```
diff = maxSum - target
```

从 `k = n → 1`：

* 如果 `diff >= 2k`

  * 把 `k` 变成 `-k`
  * `diff -= 2k`
* 否则跳过

最后如果：

```
diff != 0
```

说明凑不出来 → 返回 `[]`

---

## 七、为什么这个贪心是对的？

### 1️⃣ 可行性

* `2, 4, 6, ..., 2n` 覆盖所有偶数
* `diff` 一定是偶数（`maxSum` 和 `target` 同奇偶）

👉 用 `2k` 是**完备的**

---

### 2️⃣ 字典序最小性（这是重点）

* 翻转大的数：

  * 会产生 **更小的负数**
  * 且这些负数在排序后会排在最前面
* 如果你先翻小的数：

  * 会让 `-1, -2` 提前
  * 但错过 `-n, -(n-1)` 这种更小的数

👉 **从大到小翻，字典序一定最小**

---

## 八、最后一步：排序！

注意：
我们构造的是一个集合，并不保证顺序。

但题目只关心 **数组本身的字典序**，
所以最后要：

```
排序数组（升序）
```

负的大数自然排最前面。

---

## 九、完整流程总结（面试版）

1. 计算 `maxSum = n(n+1)/2`
2. 如果 `target` 不在 `[-maxSum, maxSum]` → `[]`
3. `diff = maxSum - target`
4. 从 `k = n → 1`，如果 `diff >= 2k`，翻转 `k`
5. 如果 `diff != 0` → `[]`
6. 对结果排序，返回

---

## 十、Example 1 走一遍

```
n = 3
target = 0
maxSum = 6
diff = 6
```

从大到小：

* k = 3 → diff >= 6 → 翻 → diff = 0

结果集合：

```
[-3, 1, 2]
```

排序后：

```
[-3, 1, 2] ✅
```

---

## 十一、一句话记忆法

> 从 `[1..n]` 全正开始，
> 用“翻转大数”来抵消多余的和，
> 最后排序即可得到 **字典序最小解**。

---