LC Two Pointers

[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 ""

56. Merge Intervals

reference:
https://blog.csdn.net/tinkle181129/article/details/79990668