[Uber]Trapping rain water
[基本功]將arr左側(cè)分為小于等于pv=arr[0]勾栗，右側(cè)為大于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]
思路：從尾部掃内列，遇到第一個(gè)升序就發(fā)現(xiàn)了機(jī)會！比如[1,3]。但是以為是 lexicographically next greater permutation of numbers, 所以僅僅這兩個(gè)swap還不夠，比如[1,2,3,5,4,9,8]馋评，我們在[4,9]發(fā)現(xiàn)了機(jī)會，但是答案是[1,2,3,5,8,4,9]刺啦，因此要做兩個(gè)操作留特，第一，我們要找到之后大于4的最小的數(shù)來和swap洪燥，第二磕秤，4之后的數(shù)字需要reverse一下變成升序，因?yàn)楝F(xiàn)在它們是降序排列的捧韵。
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
小改動(dòng)市咆，要求輸出最長的substring，不是長度再来。最后問了一下復(fù)雜度蒙兰。
Easy:
LC 344 Reverse String
定義頭尾指針，調(diào)換對應(yīng)的字符
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
逆轉(zhuǎn)字符串中的元音字母
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
刪除排序數(shù)組中的重復(fù)數(shù)字芒篷，返回剩余數(shù)組的長度.
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
刪除數(shù)組中指定的數(shù)字搜变，返回剩余數(shù)組的長度, 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
將數(shù)組中的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
