Leetcode- coin change

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:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:

coins = [2], amount = 3

return -1.

Refer to : Coin change algorithm

Let's try to understand this algorithm using an example. If we are make change of 50 using infinite number of coins of denominations {20,10,5,1} then 

total number of ways to make change of 50 using denominations {20,10,5,1} = total number of ways to make change of 50 using 0 coins of 20 + total number of ways to make change of 50 using 1 coin of 20 + total number of ways to make change of 50 using 2 coins of 20

Now first term on the right hand side of above equation that is - total number of ways to make change of 50 using 0 coins of 20 can be restated as total number of ways to make change of 50 using denominations {10,5,1}

And second term that is total number of ways to make change of 50 using 1 coin of 20 = total number of ways to make change of 30 using denominations {10,5,1}
Similarly, total number of ways to make change of 50 using 2 coins of 20 = total number of ways to make change of 10 using denominations {10,5,1}.As you can see, this algorithm is recursive in nature and the recursion tree for the above example looks like following. Only one complete path is shown in recursion tree due to space constraint.

The base case for this algorithm would be when the denomination set has only coins of 1 in it. In that case total number of ways to make change would be 1. Also when amount to make change of is 0, total number of ways to make change would be 1(0 coins of all denominations).

The formal steps of this algorithm are - 
1. If the current denomination is 1 then return 1. This is the base case.

2. If current denomination is 20, set next denomination as 10; if current denomination is 10, set next denomination as 5 and if current denomination is 5, set next denomination as 1.
3. Now implement the recurrence relation: numberOfWays(amount, denom) =  numberOfWays(amount - 0*denom, nextDenom) + numberOfWays(amount - 1*denom, nextDenom) + ... + numberOfWays(0, nextDenom) using a while loop.

The time complexity of this algorithm is exponential as can be easily observed from recursion tree.

Dynamic Programming - Memoization approach: For the same example, if we look at the recursion tree shown below which highlights the re-computations for the sub-problems of n = 30 and  denominations = {5,1}, n = 20 and  denominations = {5,1} and so on.

To avoid these re-computations, we could store the results when computed and re-use them if required again. This reduces the time complexity of this algorithm to O(nm) where n is total amount to make change for and m is total number of denominations. For the example shown in the recursion tree n would be 50 and m would be 4. This approach takes extra space of O(nm).

Let dp[v] to be the minimum number of coins required to get the amount v. 
dp[i+a_coin] = min(dp[i+a_coin], dp[i]+1) if dp[i] is reachable. 
dp[i+a_coin] = dp[i+a_coin] is dp[i] is not reachable.  

We initially set dp[i] to be MAX_VALUE.  !!

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount < 0) return -1;
        if (amount == 0) return 0;
        // The combinations of each coin can't be larger than amount.
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;

        //minimun amount of coin to reach 0 value
        for (int i = 1; i < amount + 1; ++i)
            for (int j = 0; j < coins.size(); ++j)
                if (coins[j] <= i)
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);

        return dp[amount] > amount ? -1 : dp[amount];
      // amount+1 means the dp value was unchanged meaning that 
     //it can't be further combined by other coins

    }
};

Read More

Leetcode - Combination / Combination sum 1/2/3

1. Combination

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

In this kind problem, we will need to go through from 1 to n in increasing order.

We need to apply the Backtracking method here to solve this problem. Backtraking

And the Depth First Search style algorithm can be applied to the scenario give all the possible

solutions to the problem.

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int>> ret;
        if(n <= 0) //corner case invalid check
            return ret;

        vector<int> curr;
        DFS(ret,curr, n, k, 1); //we pass ret as reference at here
        return ret;
    }

    void DFS(vector<vector<int>>& ret, vector<int> curr, int n, int k, int level)
    {
        if(curr.size() == k)
        {
            ret.push_back(curr);
            return;
        }
        if(curr.size() > k)  // consider this check to save run time
            return;

        for(int i = level; i <= n; ++i)
        {
            curr.push_back(i);
            DFS(ret,curr,n,k,i+1);
            curr.pop_back();
        }
    }

};

2. Combination sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is: 

[
  [7],
  [2, 2, 3]
]

In this case, we apply DFS and backtracking to solve this problem. Noted that we will sort the

candidates first and during the loop we will skip to the last element of same values.

class Solution { public: vector<vector<int> > combinationSum(vector<int> &candidates, int target) { vector<vector<int> > allSol; vector<int> sol; if(candidates.empty()) return allSol; sort(candidates.begin(),candidates.end()); findCombSum(candidates, 0, target, sol, allSol); return allSol; } void findCombSum(vector<int> &candidates, int start, int target, vector<int> &sol, vector<vector<int>> &allSol) { if(target==0) { allSol.push_back(sol); return; } for(int i=start; i<candidates.size(); i++) { if(i>start && candidates[i]==candidates[i-1]) continue; if(candidates[i]<=target) { sol.push_back(candidates[i]); findCombSum(candidates, i, target-candidates[i], sol, allSol); sol.pop_back(); } if(candidates[i]>target) return; //This can save the runtime } } };

3. Combination sum 2

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, 
A solution set is: 

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Comparing to combination sum 1, the answer can't contain duplicate numbers.

All we need to do is increment the the i- value to accomplish this part.

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<vector<int> > allSol;
        if(num.empty()) return allSol;
        sort(num.begin(),num.end());
        vector<int> sol;
        findCombSum2(num, 0, target, sol, allSol);
        return allSol;
    }
    
    void findCombSum2(vector<int> &num, int start, int target, vector<int> &sol, vector<vector<int> > &allSol) {
        if(target==0) {
            allSol.push_back(sol);
            return;
        }
        
        for(int i=start; i<num.size(); i++) {
            if(i>start && num[i]==num[i-1]) continue;
            if(num[i]<=target) {
                sol.push_back(num[i]);
                findCombSum2(num, i+1, target-num[i], sol, allSol);
                sol.pop_back();
            }
        }
    }
};

4. Combination sum 3

.Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

class Solution {
public:
    vector<vector<int> > combinationSum3(int k, int n) {
        vector<vector<int> > res;
        vector<int> out;
        combinationSum3DFS(k, n, 1, out, res);
        return res;
    }
    void combinationSum3DFS(int k, int n, int level, vector<int> &out, vector<vector<int> > &res) {
        if (n < 0) return;
        if (n == 0 && out.size() == k) res.push_back(out);
        for (int i = level; i <= 9; ++i) {
            out.push_back(i);
            combinationSum3DFS(k, n - i, i + 1, out, res);
            out.pop_back();
        }
    }
};

Read More

Iterative DFS and Recursive DFS

Iterative DFS

DFS(source):
  s <- new stack
  visited <- {} // empty set
  s.push(source)
  while (s is not empty):
    current <- s.pop()
    if (current is in visited):
        continue
    visited.add(current)
    // do something with current
    for each node v such that (current,v) is an edge:
        s.push(v)

Recursive DFS

1  procedure DFS(G,v):
2      label v as discovered
3      for all edges from v to w in G.adjacentEdges(v) do
4          if vertex w is not labeled as discovered then
5              recursively call DFS(G,w)

A DFS does not specify which node you see first. 
It is not important because the order between edges is not defined 

Read More

Leecode-Minimum Path Sum in Java

題目

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

----

It's a traditional Dynamic programming problem.

All we have to do is to choose the small sum in each time then record all the entries.

So, we may have a TWO-DIMENSION ARRAY to store the value 

and the answer will be at entry[m-1][n-1] .

However, it's a waste of the memory since we don't need to save all the values in the array.

So, we can use the REFACTOR-ARRAY to reuse the value and record every row.

The answer will be the last element in the last row computation.

public class Solution {


   public int minPathSum(int[][] grid) {
     
     if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;

          int[] temp = new int[grid[0].length]; // Refactor array
        
          for (int i = 0; i < grid.length; i++)
            for (int j = 0; j < grid[0].length; j++) {
                if (j > 0)
      
                  if (i > 0)
                    temp[j] = Math.min(temp[j], temp[j - 1]);  
     // temp[j] represents a[i-1][j] , temp[j-1] represents a[i][j-1] 
                  else
                    temp[j] = temp[j - 1];
                
                temp[j] += grid[i][j];
            }
        
     //The computation of first row and the first column are simple
    //Java initiate all the elements to zero 
    // so we just need to add to get the correct value.
        
            
        
          return temp[temp.length - 1];   //answer's here
    }


}

Read More

Difference and uses of onCreate(), onCreateView() and onActivityCreated()

onCreate():

The onCreate() method in a Fragment is called after the Activity's onAttachFragment() but before that Fragment's onCreateView().
In this method, you can assign variables, get Intent extras, and anything else that doesn't involve the View hierarchy (i.e. non-graphical initialisations). This is because this method can be called when the Activity's onCreate() is not finished, and so trying to access the View hierarchy here may result in a crash.

onCreateView():

After the onCreate() is called (in the Fragment), the Fragment's onCreateView() is called. You can assign your View variables and do any graphical initialisations. You are expected to return a View to this method, and this is the main UI view, but if your Fragment does not use any layouts or graphics, you can return null.

onActivityCreated():

As the name states, this is called after the Activity's onCreate() has completed. It is called after onCreateView(), and is mainly used for final initialisations (for example, modifying UI elements).

---

To sum up...
They are all called in the Fragment but are called at different times.
The onCreate() is called first, for doing any non-graphical initialisations. Next, you can assign and declare any View variables you want to use in onCreateView(). Afterwards, use onActivityCreated() to do any final initialisations you want to do once everything has completed.

轉載自此StackOverFlow

Read More

struct 與 Class 的差別在哪裡？

有兩種情況下的區別

(1)C的struct與C++的class的區別

(2)C++中的struct和class的區別

第一種情況下面很簡單

C是一種Procedural Programming的語言

在C裡面，Struct只是來作為一種複雜數據的集合定義

只能定義成員變數，不能定義成員函數

但是在C++裡面，struct就可以定義成員函數

至於第二種的情況則是

雖然在C++中的struct可以定義成員函數，也可以做繼承

但是struct的繼承預設為public，而class中的繼承是private

class可以被使用於Template當中但struct不行

在c++中的stuct就只是為了使C++能夠兼容C而已

Read More

Leecode Generate Parentheses in Java

題目：

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

這個題目如果是問個數的話，那就是Catalan Number的一種了

不過這一題沒那麼簡單，是要你把所有的Pattern都生出來

簡單的畫一下Recursion tree就大概知道了

左括號的數目一定要 >=右括號的數目

重點應該是在於，我怎麼要讓程式自動在一個左括號之後

能夠自動去選擇我下一個要是左括，或者是右括號

這樣才能生成所有想要的結果。


所以在這裡會有分歧點

需要一個if來判斷現在是左括號還有quota可以用

另一個if來判斷現在是不是還有右括號，而且右括號數目比左括號多

這兩種狀況就能涵蓋所有的結果

public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        
    if(nums==null)
        return null;
        
    if(nums.length==1)
        return new TreeNode(nums[0]);
    
    TreeNode node = BuildTree(0,nums.length-1,nums);
    return node;

    }
    
    TreeNode BuildTree(int start,int end, int[]nums){
        
        if(start>end)
            return null;
        
        int mid=(start+end)/2;
        TreeNode node=new TreeNode(nums[mid]);
        
        node.left=BuildTree(start,mid-1,nums);
        node.right=BuildTree(mid+1,end,nums);
        
        return node;
     }
    
    
}

Read More