Yuan
0%

Posted on 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function insert(A: number[][], T: number[]): number[][] {
    let i=0
    // currrent ends before T start
    let res=[]
    while(i<A.length && A[i][1]<T[0]){
        res.push(A[i])
        i+=1
    }
    let u=[T[0],T[1]]
    // handle overlap part
    while(i<A.length && A[i][0]<=T[1]){
        u[0]=Math.min(u[0],A[i][0])
        u[1]=Math.max(u[1],A[i][1])
        i+=1
    }
    res.push(u)
    // handle the rest
    while(i<A.length){
        res.push(A[i])
        i+=1
    }
    return res
};

Posted on 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var removeDuplicates = function(nums) {
    let k=0,counter=1
    for(let i=0;i<nums.length;i++){
        if(i==0){
            nums[k]=nums[i]
            k++
            continue
        }
        if(nums[i]==nums[i-1]){
            counter++
        }else{
            counter=1
        }
        //only keep those counter less than 2
        if(counter<=2){
            nums[k]=nums[i]
            k++
        }

    }
    return k
};

Posted on

https://leetcode.com/problems/interleaving-string/?envType=study-plan-v2&envId=top-interview-150

Solution1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        @cache
        def f(i,j,k):
            if i<len(s1) and j<len(s2):
                if s1[i]==s3[k] and s2[j]==s3[k]:
                    return f(i+1,j,k+1) or f(i,j+1,k+1)
                if s1[i]==s3[k]:
                    return f(i+1,j,k+1)
                if s2[j]==s3[k]:
                    return f(i,j+1,k+1)
            if i<len(s1):
                return s1[i]==s3[k] and f(i+1,j,k+1)
            if j<len(s2):
                return s2[j]==s3[k] and f(i,j+1,k+1)
            return True
        if len(s1)+len(s2)!=len(s3):
            return False
        return f(0,0,0)

Solution2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False

        dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
        dp[0][0] = True
        for i in range(len(s1)+1):
            for j in range(len(s2)+1):
                if i>=1:
                    dp[i][j]|=dp[i-1][j] and s1[i-1]==s3[i+j-1]
                if j>=1:
                    dp[i][j]|=dp[i][j-1] and s2[j-1]==s3[i+j-1]
        return dp[len(s1)][len(s2)]

Posted on

https://leetcode.com/problems/minimum-path-sum/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minPathSum(self, G: List[List[int]]) -> int:
        Z=[[0]*len(G[0]) for _ in range(len(G))]
        for i in range(len(G)):
            for j in range(len(G[0])):
                if i==0 and j==0:
                    Z[i][j]=G[i][j]
                elif i==0:
                    Z[i][j]=Z[i][j-1]+G[i][j]
                elif j==0:
                    Z[i][j]=Z[i-1][j]+G[i][j]
                else:
                    Z[i][j]=min(Z[i-1][j],Z[i][j-1])+G[i][j]
        return Z[-1][-1]

Posted on

https://leetcode.com/problems/unique-paths/description/

Solution1: top down dp

1
2
3
4
5
6
7
class Solution:
    @cache
    def uniquePaths(self, m: int, n: int) -> int:
        if m==1 or n==1:
            return 1
        elif m>1 and n>1:
            return self.uniquePaths(m-1,n)+self.uniquePaths(m,n-1)

Solution2: bottom up dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        """
        assume we have solved P(i-1,j) and P(i,j-1)
        then P(i,j)=P(i-1,j)+P(i,j-1)
        """
        P=[[0]*n for _ in range(m)]
        for i in range(n):
            P[0][i]=1
        for j in range(m):
            P[j][0]=1
        for i in range(1,m):
            for j in range(1,n):
                P[i][j]=P[i-1][j]+P[i][j-1]
        return P[m-1][n-1]

Posted on

https://leetcode.com/problems/jump-game-ii/

We always make our furthest step and when i is bigger than far, we need to make one more step.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def jump(self, A: List[int]) -> int:
        if not A:
            return 0
        if A:
            Z=0
            end=0
            far=0
            for i in range(len(A)-1):
                far=max(far,i+A[i])
                if i==end:
                    Z+=1
                    end=far
            return Z

Posted on

https://leetcode.com/problems/palindrome-partitioning/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def partition(self, A: str) -> List[List[str]]:
        def g(l,r):
            while l<=r:
                if A[l]!=A[r]:
                    return False
                elif A[l]==A[r]:
                    l+=1
                    r-=1
            return True

        def f(start,C):
            if start>=len(A):
                Z.append(C[:])
                return
            if start<len(A):
                for end in range(start,len(A)):
                    if g(start,end):
                        C.append(A[start:end+1])
                        f(end+1,C)
                        C.pop()
        if not A:
            return []
        Z=[]
        f(0,[])
        return Z

Posted on

https://leetcode.com/problems/word-search/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def exist(self, A: List[List[str]], W: str) -> bool:
        def f(x,y,idx):
            nonlocal Z
            if idx>=len(W):
                Z=True 
            elif idx<len(W) and 0<=x<len(A) and 0<=y<len(A[0]) and A[x][y]==W[idx] and (x,y) not in S:
                S.add((x,y))
                for a,b in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
                    if not Z:
                        f(a,b,idx+1)
                S.discard((x,y))
        Z=False
        for i in range(len(A)):
            for j in range(len(A[0])):
                S=set()
                f(i,j,0)
        return Z

We can set A[x][y] as # to mark it as visited to prevent the same cell from being visited more than one time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def exist(self, A: List[List[str]], W: str) -> bool:
        def f(x,y,idx):
            nonlocal Z
            if idx>=len(W):
                Z=True 
            elif idx<len(W) and 0<=x<len(A) and 0<=y<len(A[0]) and A[x][y]==W[idx]:
                A[x][y]='#'
                for a,b in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
                    if not Z:
                        f(a,b,idx+1)
                A[x][y]=W[idx]
        Z=False
        for i in range(len(A)):
            for j in range(len(A[0])):
                f(i,j,0)
        return Z

Posted on Edited on

https://leetcode.com/problems/sort-list/

Solution1: hash table

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p=head
        A=[]
        if not head:
            return None
        while p:
            A.append(p)
            p=p.next
        A.sort(key=lambda x:x.val)
        for i in range(len(A)-1):
            A[i].next=A[i+1]
        A[-1].next=None
        return A[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var sortList = function(head) {
    if(!head){
        return head
    }
    let A=[]
    let p=head
    while(p){
        A.push(p)
        p=p.next
    }
    A.sort((a,b)=>{
        return a.val-b.val
    })
    for(let i=0;i<A.length-1;i++){
        A[i].next=A[i+1]
    }
    A[A.length-1].next=null
    return A[0]
};

TopDown merge sort

Divide:

The original list is divided into two halves. And we repeat the process until the base case is reached, which is a sublist of 0 or 1 element.

Conquer:

The list that has 0 or 1 element is originally sorted.

Combine:

We merge two sorted sublist into a single sorted list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var sortList = function(head) {
    if(!head || !head.next) {
        return head
    }
    let mid=getMidAndSplit(head)
    let left=sortList(head)
    let right=sortList(mid)
    return merge(left,right)

    function getMidAndSplit(head){
        let slow=head
        let fast=head
        let slowPrev=head
        while(fast && fast.next){
            [slow,slowPrev]=[slow.next,slow]
            fast=fast.next.next
        }
        slowPrev.next=null
        return slow
    }
    function merge(l,r){
        let dummy=new ListNode()
        let p=dummy
        while(l&&r){
            if(l.val<r.val){
                p.next=l
                l=l.next
            }else{
                p.next=r
                r=r.next
            }
            p=p.next
        }
        p.next=l?l:r
        return dummy.next
    }
};

Posted on Edited on

Solution1: hash table

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
        D={}
        p=head
        k=0
        while p:
            D[p]=k
            p=p.next
            k+=1
        p=head
        A=[]
        while p:
            A.append(ListNode(p.val))
            p=p.next
        
        p=head
        for i in range(len(A)):
            if i<len(A)-1:
                A[i].next=A[i+1]
            if p.random is None:
                A[i].random=None
            elif p.random:
                A[i].random=A[D[p.random]]
            p=p.next
        return A[0]