Save all vowels to a set. Use two pointers to move from beginning and end. Keep moving the pointer until the pointer encounter a vowel character. Swap vowels.
def reverseVowels(self, s: str) -> str:
_set = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}
i = 0
j = len(s) - 1
strs = list(s)
while i < j :
while i < j and strs[i] not in _set :
i += 1
while i < j and strs[j] not in _set :
j -= 1
strs[i], strs[j] = strs[j], strs[i]
i += 1
j -= 1
return ''.join(strs)
Use two pointers to move from beginning and end. Keep moving the pointer until the pointer encounter an alphanumeric character. Check if both characters are the same.
def isPalindrome(self, s: str) -> bool:
i = 0
j = len(s) - 1
s = list(s)
while i < j:
while i < j and not s[i].isalnum():
i += 1
while i < j and not s[j].isalnum():
j -= 1
if s[i].lower() != s[j].lower():
return False
i += 1
j -= 1
return True
Use two pointers to start both at the beginning of array. i to count the numbers of non-zero elements, j to traverse to find none zero elements. When j detects a candidate, swap with i, i++.
def moveZeroes(self, nums: List[int]) -> None:
i = 0
for j in range(len(nums)):
if nums[j] != 0:
nums[i], nums[j] = nums[j], nums[i]
i += 1
Instead of swap, filling the rest of i with 0 also works. This is because i counts the number of non-zeros, the rest would be zeros.
def moveZeroes(self, nums: List[int]) -> None:
i = 0
for j in range(0, len(nums)):
if nums[j] != 0 :
nums[i] = nums[j]
i += 1
while i < len(nums):
nums[i] = 0
i += 1
def merge(self, nums1: List[int], m: int,
nums2: List[int], n: int) -> None:
i = m - 1
j = n - 1
k = m + n - 1
while i >= 0 and j >= 0:
if nums2[j] > nums1[i]:
nums1[k] = nums2[j]
j -= 1
else :
nums1[k] = nums1[i]
i -= 1
k -= 1
nums1[:j + 1] = nums2[:j + 1]
def removeElement(self, nums: List[int], val: int) -> int:
i = 0
for j in range(0, len(nums)):
if nums[j] != val:
nums[i] = nums[j]
i += 1
return i
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
for j in range(0, len(nums)) :
if nums[i] != nums[j]:
i += 1
nums[i] = nums[j]
return i + 1
One j pointer to loop over the array, the other pointer stores the right sequence of the result, which satisfy that 2 digits behind was smaller than number at j. If the numbers one those two pointers are the same, it means that there are 3 or more than 3 same numbers, thus move j only until you find the next larger element.
For example:
i j
[1,1,1,2,2,4,5,6,6,6]
This is a situation to replace the number at i with the number at j.
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
for j in range(0, len(nums)) :
if i < 2 or nums[i - 2] < nums[j]:
nums[i] = nums[j]
i += 1
return i
844. Backspace String Compare
Word Consisted by Another Word
Use set to store the shorter array and check on the array.
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
_set = set()
for n in nums1:
_set.add(n)
res = set()
for n in nums2:
if n in _set:
res.add(n)
return list(res)
Use HashMap on 350 to count each element. If sorted. Use two pointers start from beginning.
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
res = []
i = 0
j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] == nums2[j]:
res.append(nums1[i])
i += 1
j += 1
elif nums1[i] < nums2[j]:
i += 1
else:
j += 1
return res
Follow up:
What if nums1's size is small compared to nums2's size? Which algorithm is better? HashMap
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
Store the two strings in distributed system(whether self designed or not), then using MapReduce technique to solve the problem;
Processing the Strings by chunk, which fits the memory, then deal with each chunk of data at a time;
Processing the Strings by streaming, then check.
Flip 0 to n - k and flip n - k to n, then flip the entire array
def getHint(self, secret: str, guess: str) -> str:
bullset = set()
count = {}
bull = 0
for i in range(0, len(secret)):
if secret[i] == guess[i]:
bull += 1
bullset.add(i)
else :
if secret[i] in count:
count[secret[i]] += 1
else:
count[secret[i]] = 1
cow = 0
for i in range(0, len(guess)):
if i not in bullset:
if guess[i] in count and count[guess[i]] > 0:
cow += 1
count[guess[i]] -= 1
return str(bull) + "A" + str(cow) + "B"
def maxArea(self, height: List[int]) -> int:
i = 0
j = len(height) - 1
result = 0
while i < j:
result = max(result, min(height[i], height[j]) * (j - i))
if height[i] < height[j]:
i += 1
else:
j -= 1
return result
public int trap(int[] height) {
int LMax = 0, RMax = 0;
int L = 0, R = height.length - 1;
int res = 0;
while (L < R) {
if (height[L] < height[R]) {
if (height[L] > LMax) {
LMax = height[L];
} else {
res += LMax - height[L];
}
L++;
} else {
if (height[R] > RMax) {
RMax = height[R];
} else {
res += RMax - height[R];
}
R--;
}
}
return res;
}
217. Contains Duplicate
219. Contains Duplicate II
220. Contains Duplicate III
def findCelebrity(self, n: int) -> int:
cand = 0
for i in range(1, n):
if not knows(i, cand):
cand = i
for i in range(n):
if cand != i and (not knows(i, cand) or knows(cand, i)):
return -1
return cand
Use L and R on each k
public void sortColors(int[] nums) {
int L = 0, R = nums.length - 1, k = 0;
while (k <= R) {
if (nums[k] == 0) {
swap(nums, L++, k++);
} else if (nums[k] == 2) {
swap(nums, R--, k);
} else {
k++;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
Since the requirement states "can't use division", we can only generate the result by multiplication. It starts to build an array with all product of the elements before current. For example:
Array = [3,5,1,2], res start withs [1,1,1, 1], then res[i] = res[i - 1] * array[i - 1]
res = [1, 3, 15, 15]
Then multiply from the right, with a start variable as 1, keeps the variable as all the products along the way.
product = 1
res = [ 15 ] then product = 2 * 1 = 2
res = [ . 30,15 ] then product = 1 * 2
res = [ 6, 30,15 ] then product = 5 * 2 = 10
res = [10, 6, 30,15 ]
This method is due to multiply all elements before the current product from left, then multiply all products from the right. It skips the current element.
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, 1);
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] * nums[i - 1];
}
int product = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] = res[i] * product;
product *= nums[i];
}
return res;
}
334. Increasing Triplet Subsequence
This question can be solved by sort, which takes O(nlogn). A better way is to use a slow and fast pointer:
Start with index 0, find the point where two pointers meet. That indicates that there is a cycle in the array.
Move one pointer to the start point. Move both pointers forward in the same speed until they meet again.
Return the index, which is the entrance of the cycle
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast) break;
}
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
169. Majority Element
229. Majority Element II
Trapping Rain Water
41. First Missing Positive
public int shortestDistance(String[] words, String word1, String word2) {
int ind1 = -1;
int ind2 = -1;
int min = Integer.MAX_VALUE;
for (int i = 0 ; i < words.length; i++) {
if (words[i].equals(word1)) {
ind1 = i;
} else if (words[i].equals(word2)) {
ind2 = i;
}
if (ind1 != -1 && ind2 != -1) min = Math.min(min, Math.abs(ind1 - ind2));
}
return min;
}
Map<String, List<Integer>> map;
public WordDistance(String[] words) {
map = new HashMap<>();
for (int i = 0; i < words.length; i++) {
map.putIfAbsent(words[i], new ArrayList<>());
map.get(words[i]).add(i);
}
}
public int shortest(String word1, String word2) {
List<Integer> l1 = map.get(word1);
List<Integer> l2 = map.get(word2);
int i = 0, j = 0;
int min = Integer.MAX_VALUE;
while (i < l1.size() && j < l2.size()) {
int a = l1.get(i), b = l2.get(j);
min = Math.min(min, Math.abs(a - b));
if (a < b) {
i++;
} else {
j++;
}
}
return min;
}
