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

C/C++ - Vector (STL) 用法與心得完全攻略

From：
http://mropengate.blogspot.jp/2015/07/cc-vector-stl.html
僅作個人學習之用

Vector是C++中一個非常好用的「容器」，是加強版的陣列，對自己的一些基本資訊提供成員函式來直接存取。

記得小時候考程式檢定的時候，初學vector，考試時就用vector開心解完閃人，而隔壁桌的還在用C慢慢刻，才初次見識到這個東西的強大，基本上寫c++很建議使用vector取代低階的array 和pointer，比較易維護，容易除錯 : )

一、Vector 簡介

Vector是C++標準程式庫中的一個類，可視為會自動擴展容量的陣列，是C++標準程式庫中的眾多容器（container）之一，以循序(Sequential)的方式維護變數集合，使用前預先#include "vector" 即可。

vector的特色

• 支援隨機存取
• 集合尾端增刪元素很快 : O(1)
• 集合中間增刪元素比較費時 : O(n)
• 以模板(泛型)方式實現，可以儲存任意類型的變數，包括使用者自定義的資料型態。
• 有一些容器提供 stable iterator 保證，很不幸的 vector 不保證。因此存在一些可能造成vector iterator 失效的操作。

二、成員函式概觀

vector 類別是以容器模式為基準設計的，也就是說，基本上它有 begin(), end(), size(), max_size(), empty(), swap()  這幾個方法。

存取元素的用法

• vec[i] - 存取索引值為 i 的元素參照。
• vec.at(i) - 存取索引值為 i 的元素的參照，
• vec.front() - 回傳 vector 第一個元素的參照。
• vec.back() - 回傳 vector 最尾元素的參照。

[用心去感覺] 少用 operator[]
少用 operator[]，因為可能會 Segmentation Fault。以 at() 存取會做陣列邊界檢查，如果存取越界將會拋出一個例外，這是與operator[]的唯一差異。

新增或移除元素的用法

• vec.push_back() - 新增元素至 vector 的尾端，必要時會進行記憶體配置。
• vec.pop_back() - 刪除 vector 最尾端的元素。
• vec.insert() - 插入一個或多個元素至 vector 內的任意位置。
• vec.erase() - 刪除 vector 中一個或多個元素。
• vec.clear() - 清空所有元素。

[用心去感覺]  push_back()的效率問題
少依賴 push_back() 的自動記憶體配置，不是不要用push_back，是不要讓push_back自己判定記憶體需求，能自己要記憶體的就自己要，善用 reserve()、resize() 或 constructor 引數。

取得長度/容量的用法

• vec.size() - 取得 vector 目前持有的元素個數。
• vec.empty() - 如果 vector 內部為空，則傳回 true 值。
• vec.capacity() - 取得 vector 目前可容納的最大元素個數。這個方法與記憶體的配置有關，它通常只會增加，不會因為元素被刪減而隨之減少。
• 重新配置／重設長度
• vec.reserve() - 如有必要，可改變 vector 的容量大小（配置更多的記憶體）。在眾多的 STL 實做，容量只能增加，不可以減少。
• vec.resize() - 改變 vector 目前持有的元素個數。
• 疊代 (Iterator)
• vec.begin() - 回傳一個Iterator，它指向 vector 第一個元素。
• vec.end() - 回傳一個Iterator，它指向 vector 最尾端元素的下一個位置（請注意：它不是最末元素）。
• vec.rbegin() - 回傳一個反向Iterator，它指向 vector 最尾端元素的。
• vec.rend() - 回傳一個Iterator，它指向 vector 的第一個元素。

[用心去感覺] 容量 (capacity) 和長度 (size)
每個 vector 都有兩個重要的數字：容量 (capacity) 和長度 (size) 。

• 容量 (capacity) : 是這個 vector  擁有的空間。
• 長度 (size) : 是實際儲存了元素的空間大小。capacity 不小於 size 是個不變條件。

reserve() 的目的是擴大容量。做完時，vector 的長度不變，capacity 只會長大不會縮小，資料所在位置可能會移動(因為會重配空間)。因為 vector 一開始是空的，立刻預留顯然比填了資料後才預留省了拷資料的時間。
* 重配空間 : 配置新空間、拷資料、歸還舊空間、更新陣列位置。

resize() 的目的是改變 vector 的長度。做完時，vector 的長度會改變為指定的大小，capacity 則視需要調整，確保不小於 size，資料所在位置可能會移動。如果變小就擦掉尾巴的資料，如果變大就補零。補零如果會超過容量，會做重配空間的動作。

三、常用的vector程式寫法

1. 尋訪

//1. 使用足標運算子 function member - at
for(int i=0; i<v.size(); i++) cout << v[i] << " ";
for(int i=0; i<v.size(); i++) cout << v.at(i) << " ";

//2. 使用 iterator
vector<int>::iterator it_i;
for(it_i=ff.begin(); it_i!=ff.end(); ++it_i) cout << *it_i << " "; 

2. Construction and Assignment

int array[] = {0,1,2,3,4};
vector v(10,0); // {0,0,0,0,0,0,0,0,0,0}
vector v1;
vector v3(v.begin(), v.end())
v1.assign(10, 0); // v1 設 10 個 0
v1.assign(v.begin(), v.end()); // v1 複制 v
v1.assign(v.begin(), v.begin()+5); // 複製 v 前5個元素到 v1
v1.assign(array, array+5); // 複製 array 前5個元素到 v1

3. 用C++的Vector產生動態二維陣列

vector<int> row;
row.assign(n,0);//配置一個row的大小
vector< vector<int> > array_2D;
array_2D.assign(n,row);//配置2維

4. 使用者自定義的資料型態

class NODE
{
    public:
        char symbol;
        int  count;  
};

int main() 
{   
 NODE temp;
 vector<NODE> gem_list;
 
 temp.symbol = 'a';
 temp.count = 0;
 gem_list.push_back(temp);
 
 // .. 經過幾次push_back
 
 for(int i=0; i<gem_list.size(); i++)
 cout<<gem_list[i].symbol<<" "<<gem_list[i].count<<endl;
 
    return 0;
}

[用心去感覺] 優先使用vectors 和iterators 取代低階的array 和pointer
Pointers 和Arrays 對於某些低階任務可能有存在的必要，但我們應該盡量避免使用它們，因為他們容易出錯又很難除錯。一般而言應該優先使用程式庫提供的抽象事物而非語言內建的arrays 和pointers，這一忠告在「多用strings，少用C-Style 字串（亦即以null結尾之字元array）」這件事上尤其合適。

現代化C++程式不該再使用C-Style字串，C++程式應該總是優先使用vectors 和iterators 取代低階的array 和pointer。

References

Ping不見路 - STL vector 效率小記
http://pingyeh.blogspot.tw/2011/09/stl-vector.html#efficiency

Wiki - Vector (STL)

https://zh.wikipedia.org/wiki/Vector_(STL)

PTT C_and_CPP - [問題] array, pointer V.S. vector, Iterator

https://www.ptt.cc/bbs/C_and_CPP/M.1360250822.A.995.html

Edison.X. Blog - vector 心得整理
http://edisonx.pixnet.net/blog/post/34345257-vector-%E5%BF%83%E5%BE%97%E6%95%B4%E7%90%86

Edison.X. Blog - [STL Note] vector 注意事項 & FAQ
http://edisonx.pixnet.net/blog/post/93629406-%5Bstl-note%5D-vector-%E6%B3%A8%E6%84%8F%E4%BA%8B%E9%A0%85-%26-faq

[C/C++] 用C++的Vector產生動態二維陣列
http://falldog7.blogspot.tw/2007/09/cc-cvector.html

C++ 動態配置記憶體心得（下）
http://blog.ericsk.org/archives/412

Read More

Leetcode-Convert Sorted Array to Binary Tree

題目

Given an array where elements are sorted in ascending order,

convert it to a height balanced BST.

因為已經是排序過的，所以就很簡單了

Binary Search Tree的特性就是左小右大

所以這一題就把在中間位置的值，拿來當Root然後左右跑遞迴

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

Leetcode-Unique Binary Search Trees in Java

問題

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,

Given n = 3, there are a total of 5 unique BST's.


這題跟一個離散數學的觀念有關

就是Catalan Number

是一個很神奇的數字

它的表示可以是如此



任何能夠表達成上列這樣形式的問題都可以套入Catalan 公式求解

有五六十個例子，所以才說他很神奇

例如：

1.是一個有n個X和n個Y組成的字串，且所有的前綴字串皆滿足X的個數大於等於Y的個數

2.n組括號的合法運算式

3.在方陣從(0,0)走到(n,n)的方法數 


有興趣請參照以下部落格

https://johnmayhk.wordpress.com/2014/02/03/cn/

然後就是本題的 n 個node的話，有幾種異構二元樹

想看看n個點要不都是左，要不就是右

左邊1個點，右邊就是n-1(這個1)-1個點去排樹

左邊兩個點，右邊就是n-1-2個點去排樹

所以就跟上面那個Catalan的式子符合

C0的話就是 沒有點，那就是空樹，答案是1

C1就是只有一個點，那也是1，只有一種樹


所以這樣就可已寫了

下面有兩種方法來寫


1.Recursive

遞迴來寫很簡單

public class Solution {
    public int unqbntree(int n) {
        
        if(n==0||n==1)
           return 1;
        
        int sum=0;
  
        for(int i=1;i<=n;i++)
         sum+=unqbntree(n-i)*unqbntree(i-1);
      
        return sum;
    }

不過妳可以發現，重複做到了很多次，浪費了時間


2. DP

public class Solution {
    public int unqbntree(int n) {
        
        int []G=new int[n+1];
        
        G[0]=G[1]=1;
        
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++)
               G[i]+=G[j-1]*G[i-j];
        }
    
        
        return G[n];
    }

其實就拿空間換時間而已 想最快的話就套公式 不過面試官看了應該會吐血就是了。

Read More