Programming Skills

Intersection of Two Linked Lists

[Problem]
https://leetcode.com/problems/intersection-of-two-linked-lists/

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

[Solution]

2 pointer traverse 2 list wisely,
then they will travel the same distance, and meet at the same point.

Use pointer p1=headA, p2=headB to traverse the list step by step simutaniously.
While(p1!=NULL && p2!=NULL)
If p1==p2,
return p1 (you got the intersection point).
else
p1 & p2 moving forward
if (both of them reach the NULL)
return NULL (no intersection)
if(p1 reach NULL)
move p1 to headB.
if(p2 reach NULL)
move p2 to headA.

The reason we design RED part is :
ListA is composed by 'unique part'(with len A) + 'intersection part'(with len I).
ListB is composed by 'unique part'(with len B) + 'intersection part'(with len I).

The distance p1 walk through is A+I+B.

The distance p2 walk through is B+I+A.

Now you can see that p1 and p2 will walk through the same distance,

and meet at the head of intersection part.


class Solution {
public:
    
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p1=headA, *p2=headB;
        while(p1 && p2){
            if(p1==p2) return p1;
            p1=p1->next;
            p2=p2->next;
            if(p1==p2) return p1;
            if(!p1) p1=headB;
            if(!p2) p2=headA;
        }
        return NULL;
    }
};

Middle of the Linked List

[Problem]
https://leetcode.com/problems/middle-of-the-linked-list/description/

Given a non-empty, singly linked list with head node 'head', return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

中文翻譯:
給你一個link-list, 回傳位於中間位置的那個node

[Solution]

Using 2 pointers strategy to increase performance.

We use 2 pointers to traverse this link list simultaneously.
Pointer1: 1 step forward at a time.
Pointer2: 2 steps forward at a time.
Pointer2's speed is 2 times faster than pointer1.
After k times, p2 will move 2k steps, and p1 will move k steps.
When p2 reach the end point of the list, p1 will reach the middle point (of the list).


class Solution {
public:
    ListNode* middleNode(ListNode* head) {

        ListNode *p1=head,*p2=head;
        
        while(p2 && p2->next){
            p2=p2->next->next;
            p1=p1->next;
        }
        
        return p1;
    }
};

Rotate List

[Problem]

https://leetcode.com/problems/rotate-list/description/

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

中文翻譯:
給你一個link list，請你向右選轉k次

然後回傳最後的list head

注意:k可能大於list長度

[Solution]

Find the k-th node from the right(tail) of the list, it is the new head.

Using 2 pointer strategy to increase the performance.

For example:

1->2->3->4->5->NULL, k = 2

The new head is '4', which is the 2-th node from the right of the list.

After you find it, you just need to :

1.connect 5 and 1 (connect old tail to old head)

2.break 3 and 4 (make 3 as new tail, make 4 as new head)

The fast way to find k-th node from right, is using "2 pointers strategy".

First, point p1 and p2 to head node.

Then:

1.p1 move k steps

2.p2 and p1 move forward 1 step at a time, untill p1->next==null.

p1 will be the old tail.

p2 will be (k+1)-th from the left(tail), which is the new tail.

p2->next will be k-th from the left, which is the new head.

Since you have the old head & tail, new head & tail, it's easy to build the rotated list.


class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        //using "2 pointers strategy" to find the "new head node"
        
        if(!head) return NULL;
        
        ListNode* p1=head;
        int len=1;
        while(k && p1->next){//1.p1 go k step
            k--;
            p1=p1->next;
            len++;
        }

        if(k>0){//help to skip redundant iterations
            k=(k-1)%len;
            p1=head;
            while(k && p1->next){
                k--;
                p1=p1->next;
            }
        }
        
        ListNode* p2=head;
        //2.p2 and p1 go untill p1->next==null
        while(p1->next){
            p1=p1->next;
            p2=p2->next;
        }

        //3.connect tail & head (p1->next=head)
        //3.p2->next is the new head(head = p2->next)
        //4.p2 is the new tail(p2->next=null)
        p1->next=head;
        ListNode* newhead=p2->next;
        p2->next=NULL;
        
        return newhead;      

    }
};

Best Time to Buy and Sell Stock

[Problem]
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

中文翻譯:
給你每一天的股價。問你如果最多只能買賣一次
在所有可能性中，最大的獲利數字是多少?

[Solution]

Dynamic programming.
Answer of K is based on answer of K-1, and prices[K] - min prices of(0~K-1).

1.The relation between original problem and sub-problem.
At the end of K-th day(last day), there are only 2 mutually exclusive cases to get the profit.
Case 1: I sold the stock at K-th day.
You want to sell stock at K-th day, you must buy stock on i-th, which i<k.
You want to maximize the profit, so price[i] must be the minimum of prices[0]~prices[K-1].

Case 2: I did not sell the stock at K-th day.
Since you did not sell the stock on K-th day and it is the last day,
you must buy and sell the stock before K-th day.
And this is a sub-problem of original problem.

The max profit is max of case1 and case2.

2.The base case
When K=1, there is only one day and one price, your max profit can only be 0.
When K=2, you can buy on the first day and sell it on the second day.
But if you can't get profit from that, you should not buy/sell at all.
So the profit is max(prices[1]-prices[0], 0).

Let's write code~


class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() <= 1) return 0;
        
        vector<int> t(prices.size(),0);
        t[0]=0;
        t[1]=max(0,prices[1]-prices[0]);
        int mini = min(prices[0],prices[1]);
        
        for(int i=2;i<prices.size();i++){
            t[i] = max(t[i-1], prices[i]-mini);
            mini = min(prices[i],mini);
        }
        return t[prices.size()-1];
    }
};

N-Queens

[Problem]
https://leetcode.com/problems/n-queens/description/

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

[Solution]

Recursively decide the Queen's position under previous condition.

Main operation of recursive function:
Each recursive call represents a row.
1.Put the queen on a position(column) of current row.
2.Check if this queen's position conflict with previous queen's position
If not conflict, start next row.
If conflict, skip this position.
3.repeat 1&2 until every position has been tried.

Recursive function terminates when :
When the n-th queen's legal position is decided, you get a legal solution.
There is no more queen's position needed to be decided.

Let's write code:


class Solution {
public:

    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ret;
        vector<string> ans;
        vector<int> pos(n,0);
        putqueen(n,0,pos,ans,ret);
        return ret;
    }
    
    void putqueen(int n, int row, 
                  vector<int>& pos, 
                  vector<string>& ans,
                  vector<vector<string>>& ret){
        //terminate condition
        if(row >= n){
            ret.push_back(ans);
            return;
        }
        
        //n possible position
        for(int p=0;p<n;p++){
            int i=row-1;
            for(;i>=0;i--){ //check if p is a legal position 
                if(pos[i]==p || pos[i]-p == row-i || p-pos[i] == row-i )
                    break;
            }
            if(i<0){//if p is legal, start next row
                pos[row]=p;
                string str(n,'.');
                str[p]='Q';
                ans.push_back(str);
                putqueen(n, row+1, pos, ans, ret);
                ans.pop_back();
            }    
        }
    }
};

Coin Change 2

[Problem]
https://leetcode.com/problems/coin-change-2/description/

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Note: You can assume that

0 <= amount <= 5000
1 <= coin <= 5000
the number of coins is less than 500
the answer is guaranteed to fit into signed 32-bit integer

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10] 
Output: 1

中文翻譯:

給你'coins'陣列，代表你有哪些種類的coin可以使用。

然後給你'amount'，代表一個金額。

問你如果要用coins來組成amount，有多少種方式 ?

[Solution]

Dynamic Programming.
The number of ways to make up the amount with coins[1]~coin[n] is equal to
the number of ways to make up the amount without coin[n]
+
the number of ways to make up the amount with at least one coin[n]

1.The relation between original problem and sub-problem.
Let's say we have coin [1,2,5] and amount=12.
The number of ways to make up 12 by [1,2,5] can be separate into 2 mutually exclusive cases :
Case 1.Not allow to use coin '5'
This mean you can only use [1,2] to make up 12.
It becomes a smaller sub-problem "the number of ways to make up the 12 by [1,2]"
Case 2.Must use at least one coin '5'
We must use at least one '5' , the so remaining amount is 12-5=7.
It becomes a smaller sub-problem "the number of ways to make up the 7 by [1,2,5]"

Finally, the answer of original problem will be the sum of case1 and case2.

2.The base case

When the amount = 0, there is only 1 way.

So we can build up a 2D reference table, from smallest sub-problem "make up 0 by [1]" to "make up 12 by [1,2,5]".

Let's write the code :


class Solution {
public:
    int change(int amount, vector<int>& coins){
        vector<int> dpt(amount+1,0);
        dpt[0]=1;//base case
        for(auto c:coins){
            for(int a=c;a<=amount;a++){
                dpt[a]+=dpt[a-c];    
            }
        }
        return dpt[amount];
    }    
}

Coin Change

[Problem]
https://leetcode.com/problems/coin-change/description/

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins=[1,2,5], amount=11
Output: 3
Explanation: 11=5+5+1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Note:
You may assume that you have an infinite number of each kind of coin.

中文翻譯:

給你'coins'陣列，代表你有哪些種類的coin可以使用。

然後給你'amount'，代表一個金額。

問你如果要用coins來組成amount，最少可以用幾個coin來表示。

[Solution]

Dynamic Programming.
Solution(amount) is the min of
(solution(amount - coin[1])+1,
solution(amount - coin[2])+1,
,...,
solution(amount - coin[n])+1)

Let's say there are n kinds of coins(idx=1~n), then there are n ways to make up the amount of money.
1.choose a coin[1], and calculate the answer of coinChange(coins, amount-coin[1])
2.choose a coin[2], and calculate the answer of coinChange(coins, amount-coin[2])
3.choose a coin[3], and calculate the answer of coinChange(coins, amount-coin[3])
....
n.choose a coin[n], and calculate the answer of coinChange(coins, amount-coin[n])

In case i, we will get solution of "a coin[i] had been chosen" condition.
So the solution of coinChange(coins, amount) is the minimum of case1~n.

Since some of the answers will be used repeatedly during the procedure, so we should build a dynamic programming table, instead of using recursive function call.

Let's write code.


class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dpt(amount+1,-1);//dp table. dpt[i]=solution of amount=i, under 'coins'
        dpt[0]=0;//base case
        
        for(int a=1;a<=amount;a++){
            //if amount = a 
            //there are coins.size() ways to make up the amount
            // 1.pick coins[0], then calculate solution of amount=a-coins[0]
            // 2.pick coins[1], then calculate solution of amount=a-coins[1]
            // 3.pick coins[2], then calculate solution of amount=a-coins[2]
            // ...total coins.size() cases...
            //The min of case 1,2,3,.. will be the solution of amount=a 
            for(auto c:coins){
                if(a-c>=0 && dpt[a-c]!=-1)
                    dpt[a]=dpt[a]==-1 ? dpt[a-c]+1 : min(dpt[a-c]+1, dpt[a]);
            }
        }
        
        return dpt[amount];
    }
};

Generate Parentheses

[Problem]
https://leetcode.com/problems/generate-parentheses/description/

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

中文翻譯:
給你N個左括號，N個右括號，請你列出所有合理的組合(如上例)。

[Solution]

Recursively choosing parentheses under previous condition.

Main operation of recursive function:
There are 2N slots for you to put left or right parenthesis in.
In each round, you can choose either a left or a right parenthesis,
and leave the rest of the parentheses to the following recursive function call.

Recursive function terminates when :
1.No parenthesis left.
2.Number of left parentheses is more than number of right parentheses.

Let's write code~


class Solution {
public:
    
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        string ans;
        gen(n,n,ans,ret);
        return ret;
    }
    
    void gen(int l, int r, string& ans, vector<string>& ret){
        if(l>r) return;
        if(l==r && l==0){ 
            ret.push_back(ans);
            return;
        }
        if(l>0){
            ans.push_back('(');
            gen(l-1,r,ans,ret);
            ans.pop_back();
        }
        
        if(r>0){
            ans.push_back(')');
            gen(l,r-1,ans,ret);
            ans.pop_back();
        }
    }
    
};

Unique Paths 2 (with obstacles)

[Problem]
https://leetcode.com/problems/unique-paths-ii/description/

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

中文翻譯:
和之前的unique path題一樣，問你起點道終點有幾種方法。
不過這次的矩陣上有些格子不能走。

[solution]

Dynamic Programming.
The answer of (x,y) = answer of (x,y-1) + answer of (x-1,y).
But if (x,y) is an obstacle, answer of (x,y) = 0.

The solution is the same with previous problem.
But there are some obstacles on the grid.
So the answer of those obstacles are '0', which means no way to go to those obstacles.

Let's write code~
We only need to modify one line for checking if it's a obstacle.


class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int>> matrix(2, vector<int>(n+1,0));
        matrix[1][0]=1;
        for(int r=1;r<=m;r++){
            for(int c=1;c<=n;c++){
                matrix[r%2][c]=(obstacleGrid[r-1][c-1]==1) ?  0 : matrix[r%2][c-1] + matrix[(r-1)%2][c];
            }
            if(r==1) matrix[1][0]=0;
        }
        return matrix[m%2][n];     
    }
};

Subsets

[Problem]
https://leetcode.com/problems/subsets/description/

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

中文翻譯:
給你一個集合，集合內的數字都不相同
請回傳所有的子集合

[Solution]

Dynamic programming.
The answer of K numbers is based on answer of K-1 numbers.

Let's assume the input is [1,2], so the power set are:
[]
[1]
[2]
[1,2]

Now we extend the input by putting one more number into it [1,2,3].
For every existing subset, we can decide we want to add the new number '3' into it or not.
In the DON'T ADD case, all subsets are:
[]
[1]
[2]
[1,2]
In the ADD case, all subsets are:
[3]
[1,3]
[2,3]
[1,2,3]

The power set of [1,2,3], is the union of DON'T ADD case and ADD case.

So the conclusion is :
The power set of K numbers is the union of
DON'T ADD K to K-1's power set, and ADD K to K-1's power set.

Let's write code~


class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        ans.push_back(vector<int>(0)); //add base case
        for(int i=0;i<nums.size();i++){
            //add nums[i] into all previous sets
            int pre_set_num = ans.size();
            for(int s=0;s<pre_set_num;s++){
                vector<int> newset = ans[s];
                newset.push_back(nums[i]);
                ans.push_back(newset);
            }
        }
        return ans;
    }    
};

[Method 2]
And here is another recursive method which is easy to understand.
For each element in the input array, we can decide we wanna keep it or not.
By recursively doing this, we can find all combination.


class Solution {
public:

    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        vector<int> subset(0);
        DFS(nums, subset, ans, 0);
        return ans;
    }
    
    void DFS(vector<int>& nums, vector<int>& subset,vector<vector<int>>& ans, int target){
        if(target == nums.size()){
            ans.push_back(subset);
            return;
        }
    
        DFS(nums, subset, ans, target+1);
        subset.push_back(nums[target]);
        DFS(nums, subset, ans, target+1);
        subset.pop_back();
        return;        
    }
};

Unique Paths

[Problem]
https://leetcode.com/problems/unique-paths/description/

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

中文翻譯:
一個m x n的矩陣，左上角(0,0)有一個機器人，右下角(m,n)是終點。
機器人每次只能向右或向下走，請問走到終點有多少走法?

[Solution]

Dynamic Programming.
The answer of (x,y) = answer of (x,y-1) + answer of (x-1,y).

The robot can only move 1 step down or 1 step right.
So, if the robot is on position (x,y), the previous position must be (x,y-1) or (x-1,y).
So the number of ways to get to (x,y), is equal to
the number of ways to get to (x,y-1) + the number of ways to get to (x-1,y).

There are two ways of dynamic programming implementation :
1.Top down: recursive call from (x,y) --> (0,0)
2.Bottom up: build table from (0,0) --> (x,y)

We choose method 2 because the information will be used repeatedly.
The space complexity is O(m*n)
The time complexity is O(m*n)


class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> matrix(m+1, vector<int>(n+1,0));
        matrix[1][0]=1;
        for(int r=1;r<=m;r++){
            for(int c=1;c<=n;c++){
                matrix[r][c]=matrix[r][c-1] + matrix[r-1][c];
            }
        }
        return matrix[m][n];
    }
};

There is advance solution which saves more memory space.
During building table, we found that we only need the last row.
So we only to declare a table which size is 2 rows, one for current, one for previous.
The space complexity is O(n).


class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> matrix(2, vector<int>(n+1,0));
        matrix[1][0]=1;
        for(int r=1;r<=m;r++){
            for(int c=1;c<=n;c++){
                matrix[r%2][c]=matrix[r%2][c-1] + matrix[(r-1)%2][c];
            }
            if(r==1) matrix[1][0]=0;
        }
        return matrix[m%2][n];
    }    
};

訂閱：文章 (Atom)