双序列双指针 Two Sequences Two Pointers¶
Table of Contents¶
- 2109. Adding Spaces to a String (Medium)
- 2540. Minimum Common Value (Easy)
- 88. Merge Sorted Array (Easy)
- 2570. Merge Two 2D Arrays by Summing Values (Easy)
- 350. Intersection of Two Arrays II (Easy)
- 1855. Maximum Distance Between a Pair of Values (Medium)
- 1385. Find the Distance Value Between Two Arrays (Easy)
- 925. Long Pressed Name (Easy)
- 809. Expressive Words (Medium)
- 2337. Move Pieces to Obtain a String (Medium)
- 777. Swap Adjacent in LR String (Medium)
- 844. Backspace String Compare (Easy)
- 986. Interval List Intersections (Medium)
- 1537. Get the Maximum Score (Hard)
- 244. Shortest Word Distance II (Medium) 👑
- 2838. Maximum Coins Heroes Can Collect (Medium) 👑
- 1229. Meeting Scheduler (Medium) 👑
- 1570. Dot Product of Two Sparse Vectors (Medium) 👑
- 1868. Product of Two Run-Length Encoded Arrays (Medium) 👑
2109. Adding Spaces to a String¶
from typing import List
def addSpaces(s: str, spaces: List[int]) -> str:
res = []
spaces.sort()
n = len(spaces)
j = 0
for i, ch in enumerate(s):
if j < n and i == spaces[j]:
res.append(" ")
j += 1
res.append(ch)
return "".join(res)
if __name__ == "__main__":
s = "LeetcodeHelpsMeLearn"
spaces = [8, 13, 15]
print(addSpaces(s, spaces)) # Leetcode Helps Me Learn
2540. Minimum Common Value¶
88. Merge Sorted Array¶
from typing import List
class merge:
@staticmethod
def lr(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
p1, p2, t = m - 1, n - 1, m + n - 1
while p1 >= 0 or p2 >= 0:
if p1 == -1:
nums1[t] = nums2[p2]
p2 -= 1
elif p2 == -1:
nums1[t] = nums1[p1]
p1 -= 1
elif nums1[p1] > nums2[p2]:
nums1[t] = nums1[p1]
p1 -= 1
else:
nums1[t] = nums2[p2]
p2 -= 1
t -= 1
if __name__ == "__main__":
nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3
merge.lr(nums1, m, nums2, n)
assert nums1 == [1, 2, 2, 3, 5, 6]
#include <cassert>
#include <vector>
using namespace std;
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1, p2 = n - 1, t = m + n - 1;
while (p1 >= 0 || p2 >= 0) {
if (p1 == -1) {
nums1[t] = nums2[p2];
p2--;
} else if (p2 == -1) {
nums1[t] = nums1[p1];
p1--;
} else if (nums1[p1] > nums2[p2]) {
nums1[t] = nums1[p1];
p1--;
} else {
nums1[t] = nums2[p2];
p2--;
}
t--;
}
}
};
int main() {
Solution solution;
vector<int> nums1 = {1, 3, 6, 0, 0, 0};
vector<int> nums2 = {2, 5, 6};
vector<int> output = {1, 2, 3, 5, 6, 6};
solution.merge(nums1, 3, nums2, 3);
assert(nums1 == output);
return 0;
}
2570. Merge Two 2D Arrays by Summing Values¶
350. Intersection of Two Arrays II¶
"""
- Return the intersection of two arrays.
"""
from collections import defaultdict
from typing import List
# Hashmap
def intersect(nums1: List[int], nums2: List[int]) -> List[int]:
hashmap = defaultdict(int) # {num: count}
result = []
for i in nums1:
hashmap[i] += 1
for i in nums2:
if hashmap[i] > 0:
result.append(i)
hashmap[i] -= 1
return result
# |-------------|-------------|--------------|
# | Approach | Time | Space |
# |-------------|-------------|--------------|
# | Hashmap | O(n + m) | O(min(n, m)) |
# |-------------|-------------|--------------|
nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(intersect(nums1, nums2)) # [2, 2]
1855. Maximum Distance Between a Pair of Values¶
1385. Find the Distance Value Between Two Arrays¶
from bisect import bisect_left
from typing import List
# Binary Search
def findTheDistanceValue(arr1: List[int], arr2: List[int], d: int) -> int:
arr2.sort()
res = 0
for x in arr1:
i = bisect_left(arr2, x - d)
if i == len(arr2) or arr2[i] > x + d:
res += 1
return res
arr1 = [4, 5, 8]
arr2 = [10, 9, 1, 8]
d = 2
print(findTheDistanceValue(arr1, arr2, d)) # 2