BQ

Coding（37）
System Design（0）
Algorithm（0）
Ood（0） 高频题（0）

Coding（37）
System Design（0）
Algorithm（0）
Ood（0） 高频题（0）
1.LeetCode 767
2.LeetCode 28
3.LeetCode 20
4.LeetCode 123
5.Longest subarray
6.Even or odd
7.并查集问题
8.Max num of chocolate
9.Num of digits
10.Rotate matrix
11.背包问题变种
12.LeetCode 974
13.LeetCode 978
14.LeetCode 910
15.LeetCode 974
16.LeetCode 862
17.LeetCode 89
18.LeetCode 386
19.LeetCode 974
20.Leetcode 910
21.Leetcode 974
22.Leetcode 23
23.Leetcode 300
24.Leetcode713
25.leetcode910
26.LeetCode 974
27.LeetCode 415
28.LeetCode 2389
29.LeetCode 862
30.LeetCode 714
31.visiting cities
32.LeetCode 53
33.LeetCode 1222
34.LeetCode 198
35.LeetCode 20
36.LeetCode 51
37.LeetCode 79
1. LeetCode 767
Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

Example 1:

```Input: s = "aab"
Output: "aba"
```
Example 2:

```Input: s = "aaab"
Output: ""
```

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.
2. LeetCode 28
Implement strStr().

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

Example 1:

```Input: haystack = "hello", needle = "ll"
Output: 2
```
Example 2:

```Input: haystack = "aaaaa", needle = "bba"
Output: -1
```

Constraints:

• 1 <= haystack.length, needle.length <= 104
• haystack and needle consist of only lowercase English characters.
3. LeetCode 20
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example 1:

```Input: s = "()"
Output: true
```
Example 2:

```Input: s = "()[]{}"
Output: true
```
Example 3:

```Input: s = "(]"
Output: false
```

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.
4. LeetCode 123
You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

```Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.```
Example 2:

```Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later,
as you are engaging multiple transactions at the same time. You must sell before buying again.
```
Example 3:

```Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
```

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 105
5. Longest subarray

6. Even or odd

ODD.string中的每一个字母会对应到ASCI的原码：a-->97,b-->98，然后利用原码进行计算计算的规则是value=s[O]^k*s^k*...s[s.length()-1]^k.最终的sum=value+value...+ value[s.size()-1]-->check是EVEN还是ODD
7. 并查集问题

friend，把对应student1 和student2所在的group联合起来，如果是total，求两个student分别所在group size之和。要注意的是如果两个人在同一个group，只能算一次。
8. Max num of chocolate
calculate max num of chocolates (N jars of different nums of chocos, must not pick any adjacentjars)
9. Num of digits
find num of integers <= X whose digits adds up to Y
10. Rotate matrix
rotate N * M matrix by 90 degrees right
11. 背包问题变种
| 你要经过几个城市然后每个城市之间有两条路一个红的一个蓝的.每条路在每两个城市之间的weight不同，即两个一样长的数组，每次从red切换到blue会增加额外的weight,从blue切换到red则无消耗，然后让你沿着数组从头走到尾并且使weight和最小
eg：
red =[1,2，7，4，3]
blue =［1,0,3，5，1]
bluecost = 2
你从red开始，index=1时，blue<red你可能想切换到blue，但是你之前在red， red->blue,要加上bluecost=2.
12. LeetCode 974
Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

Example 1:

```Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], , [5, 0], [5, 0, -2, -3], , [0, -2, -3], [-2, -3]
```
Example 2:

```Input: nums = , k = 9
Output: 0
```

Constraints:

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• 2 <= k <= 104
13. LeetCode 978
Given an integer array arr, return the length of a maximum size turbulent subarray of arr.

A subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

More formally, a subarray [arr[i], arr[i + 1], ..., arr[j]] of arr is said to be turbulent if and only if:

• For i <= k < j:
• arr[k] > arr[k + 1] when k is odd, and
• arr[k] < arr[k + 1] when k is even.
• Or, for i <= k < j:
• arr[k] > arr[k + 1] when k is even, and
• arr[k] < arr[k + 1] when k is odd.

Example 1:

```Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr > arr < arr > arr < arr
```
Example 2:

```Input: arr = [4,8,12,16]
Output: 2
```
Example 3:

```Input: arr = 
Output: 1
```

Constraints:

• 1 <= arr.length <= 4 * 104
• 0 <= arr[i] <= 109
14. LeetCode 910
You are given an integer array nums and an integer k.

For each index i where 0 <= i < nums.length, change nums[i] to be either nums[i] + k or nums[i] - k.

The score of nums is the difference between the maximum and minimum elements in nums.

Return the minimum score of nums after changing the values at each index.

Example 1:

```Input: nums = , k = 0
Output: 0
Explanation: The score is max(nums) - min(nums) = 1 - 1 = 0.
```
Example 2:

```Input: nums = [0,10], k = 2
Output: 6
Explanation: Change nums to be [2, 8]. The score is max(nums) - min(nums) = 8 - 2 = 6.
```
Example 3:

```Input: nums = [1,3,6], k = 3
Output: 3
Explanation: Change nums to be [4, 6, 3]. The score is max(nums) - min(nums) = 6 - 3 = 3.
```

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 104
• 0 <= k <= 104
15. LeetCode 974
Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

Example 1:

```Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], , [5, 0], [5, 0, -2, -3], , [0, -2, -3], [-2, -3]
```
Example 2:

```Input: nums = , k = 9
Output: 0
```

Constraints:

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• 2 <= k <= 104
16. LeetCode 862
Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

Example 1:

```Input: nums = , k = 1
Output: 1
```
Example 2:

```Input: nums = [1,2], k = 4
Output: -1
```
Example 3:

```Input: nums = [2,-1,2], k = 3
Output: 3
```

Constraints:

• 1 <= nums.length <= 105
• -105 <= nums[i] <= 105
• 1 <= k <= 109
17. LeetCode 89
An n-bit gray code sequence is a sequence of 2n integers where:

• Every integer is in the inclusive range [0, 2n - 1],
• The first integer is 0,
• An integer appears no more than once in the sequence,
• The binary representation of every pair of adjacent integers differs by exactly one bit, and
• The binary representation of the first and last integers differs by exactly one bit.
Given an integer n, return any valid n-bit gray code sequence.

Example 1:

```Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit
```
Example 2:

```Input: n = 1
Output: [0,1]
```

Constraints:

• 1 <= n <= 16
18. LeetCode 386
Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.

You must write an algorithm that runs in O(n) time and uses O(1) extra space.

Example 1:

```Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
```
Example 2:

```Input: n = 2
Output: [1,2]
```

Constraints:

• 1 <= n <= 5 * 104
19. LeetCode 974
Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

Example 1:

```Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], , [5, 0], [5, 0, -2, -3], , [0, -2, -3], [-2, -3]
```
Example 2:

```Input: nums = , k = 9
Output: 0
```

Constraints:

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• 2 <= k <= 104
20. Leetcode 910
You are given an integer array nums and an integer k.

For each index i where 0 <= i < nums.length, change nums[i] to be either nums[i] + k or nums[i] - k.

The score of nums is the difference between the maximum and minimum elements in nums.

Return the minimum score of nums after changing the values at each index.

Example 1:

```Input: nums = , k = 0
Output: 0
Explanation: The score is max(nums) - min(nums) = 1 - 1 = 0.
```
Example 2:

```Input: nums = [0,10], k = 2
Output: 6
Explanation: Change nums to be [2, 8]. The score is max(nums) - min(nums) = 8 - 2 = 6.
```
Example 3:

```Input: nums = [1,3,6], k = 3
Output: 3
Explanation: Change nums to be [4, 6, 3]. The score is max(nums) - min(nums) = 6 - 3 = 3.
```

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 104
• 0 <= k <= 104
21. Leetcode 974
Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

Example 1:

```Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], , [5, 0], [5, 0, -2, -3], , [0, -2, -3], [-2, -3]
```
Example 2:

```Input: nums = , k = 9
Output: 0
```

Constraints:

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• 2 <= k <= 104
22. Leetcode 23
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

```Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
```
Example 2:

```Input: lists = []
Output: []
```
Example 3:

```Input: lists = [[]]
Output: []
```

Constraints:

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.
23. Leetcode 300
Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

```Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
```
Example 2:

```Input: nums = [0,1,0,3,2,3]
Output: 4
```
Example 3:

```Input: nums = [7,7,7,7,7,7,7]
Output: 1
```

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

24. Leetcode713
Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

Example 1:

```Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
, , , , [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
```
Example 2:

```Input: nums = [1,2,3], k = 0
Output: 0
```

Constraints:

• 1 <= nums.length <= 3 * 104
• 1 <= nums[i] <= 1000
• 0 <= k <= 106
30. LeetCode 714
https://leetcode.com/problems/subarray-product-less-than-k/
31. visiting cities

red和blue为i-1城到城的距离，bluecost为红线转蓝线的距离，蓝转红无距离。