[Uber]Trapping rain water
[基本功]将arr左侧分为小于等于pv=arr[0]，右侧为大于pv！
arr = [5,7,4,2,9,8]
pv = arr[0]
i = j = len(arr)-1
#j to the end are greater than pv
while i>0:
if arr[i]>pv:
arr[i],arr[j] = arr[j],arr[i]
i -= 1
j -= 1
else:
i -= 1
arr[j],arr[0] = arr[0],arr[j]
print(arr) #[4, 2, 5, 7, 9, 8]
[蝈蝈电面]LC 31 Next Permutation
[1,3,2]-->[2,1,3]
[1,2,3] → [1,3,2]
[1,3,5,4,8,9]-->[1,3,5,4,9,8]
思路：从尾部扫，遇到第一个升序就发现了机会！比如[1,3]。但是以为是 lexicographically next greater permutation of numbers, 所以仅仅这两个swap还不够，比如[1,2,3,5,4,9,8]，我们在[4,9]发现了机会，但是答案是[1,2,3,5,8,4,9]，因此要做两个操作，第一，我们要找到之后大于4的最小的数来和swap，第二，4之后的数字需要reverse一下变成升序，因为现在它们是降序排列的。
No return, modify in place!
beat 100%
class Solution:
def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
# find the first asending piece from tail
pivot = -1
for i in range(len(nums) - 2, -1, -1):
if nums[i] < nums[i + 1]:
pivot = i
break
if pivot == -1:
nums.reverse()
return
# find the next larger number to replace pivot
for j in range(len(nums) - 1, -1, -1):
if nums[j] > nums[pivot]:
nums[pivot], nums[j] = nums[j], nums[pivot]
break
nums[pivot+1:] = nums[pivot+1:][::-1]
[Uber电面] LC 3 Longest Substring Without Repeating Characters
小改动，要求输出最长的substring，不是长度。最后问了一下复杂度。
Easy:
LC 344 Reverse String
定义头尾指针，调换对应的字符
class Solution(object):
def reverseString(self, s):
"""
:type s: str
:rtype: str
"""
s = list(s)
start = 0
end = len(s)-1
while(start<end):
s[start],s[end] = s[end],s[start]
start+=1
end-=1
return ''.join(s)
LC 345. Reverse Vowels of a String
逆转字符串中的元音字母
class Solution(object):
def reverseVowels(self,s):
dic=['a','o','e','i','u','A','O','E','I','U']
tmp=list(s)
start,end = 0,len(tmp)-1
while(start<end):
while(start<end and tmp[start] not in dic):
start+=1
while(end>start and tmp[end] not in dic):
end-=1
if start<end:
tmp[start],tmp[end] = tmp[end],tmp[start]
start+=1
end-=1
return ''.join(tmp)
LC 26. Remove Duplicates from Sorted Array
删除排序数组中的重复数字，返回剩余数组的长度.
Duplicates are guaranteed to be removed up to j-1. j is supposed to be filled with next new number.
Attention: it is sorted!
class Solution(object):
def removeDuplicates(self, nums):
if nums == []: return 0
j = 1
for i in range(1,len(nums)):
if nums[i]!=nums[i-1]:
nums[j] = nums[i]
j+=1
return j
LC 27 Remove Element
删除数组中指定的数字，返回剩余数组的长度, in place!
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
if nums == []: return 0
j = 0
for i in range(len(nums)):
if nums[i]!=val:
nums[j]=nums[i]
j+=1
return j
LC 283. Move Zeroes
将数组中的0移到最后. No zeros from 0 to j-1, so we will fill 0 from j onwards.
class Solution(object):
def moveZeroes(self, nums):
j=0
for i in range(len(nums)):
if nums[i]!=0:
nums[j]=nums[i]
j=j+1
for i in range(j,len(nums)):
nums[i]=0
Medium:
LC 763. Partition Labels (Two Pointers, Greedy)
Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
S will consist of lowercase letters ('a' to 'z') only.
LC 524. Longest Word in Dictionary through Deleting
给定string s和list d,判断s删去一部分字符是否可以组成d中的字符串，如果可以求长度最长且字典序最小的字符串。否则返回空串。If there are more than one possible results, return the longest word with the smallest lexicographical order.
Input: s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output: "apple"
Input: s = "abpcplea", d = ["a","b","c"]
Output: "a"
How to check if a needle (word) is a subsequence of a haystack (S)? This is a classic problem with the following solution: walk through haystack, keeping track of the position (i) of the needle. Whenever word[i] matches the current character in S, we only have to match word[i+1:], so we increment i. At the end of this process, i == len(word) if and only if we've matched every character in word to some character in S.
def findLongestWord(self, S, D):
D.sort(key = lambda x: (-len(x), x))
for word in D:
i = 0
for c in S:
if i < len(word) and word[i] == c:
i += 1
if i == len(word):
return word
return ""
- Merge Intervals
reference:
https://blog.csdn.net/tinkle181129/article/details/79990668
