Hans.An Engineer in Taiwan.

Doing something you intrinsically are enthusiastic with.

2016年2月29日 星期一

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

上午11:14 Posted by Unknown No comments
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

Wiki - Vector (STL)

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

2016年2月27日 星期六

Leetcode-Convert Sorted Array to Binary Tree

清晨7:34 Posted by Unknown No comments

題目

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;
     }
    
    
}

2016年2月23日 星期二

Leetcode-Unique Binary Search Trees in Java

上午10:39 Posted by Unknown No comments


問題

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

是一個很神奇的數字

它的表示可以是如此

C_n=C_0C_{n-1}+C_1C_{n-2}+C_2C_{n-3}+\dots+C_{n-2}C_1+C_{n-1}C_0

任何能夠表達成上列這樣形式的問題都可以套入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];
    }
其實就拿空間換時間而已 想最快的話就套公式 不過面試官看了應該會吐血就是了。

2016年2月22日 星期一

Leetcode-LinkedList circle detection

凌晨3:24 Posted by Unknown No comments


問題：

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?



這題算是很常見的題目

我記得群暉也有考過

並不難


結構上會給你一個Linklist

直覺解法是可以在結構裡面加一個遞增變數

然後一層一層標記，最後只要遇到下一個標記比現在的短就算Circle

不過這裡沒辦法給你改結構，而且這樣就要額外空間

採用另一個簡單的方法


就是slow，一次走一步

另一個fast，一次走兩步

然後只要有Circle，Fast遲早會在某地和slow相會




public class Solution {
    public boolean hasCycle(ListNode head) {
        
        ListNode slow=head;
        ListNode fast=head;
        
        if(head==null)
            return false;
            
        while(fast.next!=null && fast.next.next!=null){
            
            fast=fast.next.next;
            slow=slow.next;
            
            if(slow==fast)
                return true;
        }
      
      
        return false;
      
        
    }

Leetcode- Missing Number in Java

凌晨3:14 Posted by Unknown No comments


題目：

Given an array containing n distinct numbers taken
 from 0, 1, 2, ..., n, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3] return 2.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

如果要跑Linear Runtime的話
很明顯就是不能夠先排序再去找了
排序最快平均也會到O(nlogn)
這種時候還是回來想想其他辦法

對於這種排除某個元素的問題
最好是可以想看看如何使用bit manipulation 來做

XOR這個東西很好用
可以遇到不同的東西就變１　
其實就是變相讓它融入你
如果那個東西剛好是你沒有的
那麼就會有種補缺漏的效果

根據ＸＯＲ的簡單用法
Ａ　ＸＯＲ　Ｂ＝Ｃ
Ｃ　ＸＯＲ　Ａ＝Ｂ
所以
問題測資　ＸＯＲ　ＭＩＳＳＩＮＧ　ＮＵＭ＝全部沒缺
全部沒缺　ＸＯＲ　闕漏部分＝ＭＩＳＳＩＮＧ　ＮＵＭＢＥＲ

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            res ^= (i + 1) ^ nums[i];
        }
        return res;
    }
};

2016年2月21日 星期日

Leetcode-Invert Binary Tree in Java

晚上11:37 Posted by Unknown No comments

問題：反轉二元樹


這題目就很簡單，沒什麼困難的

就是用一個遞迴從root一路做到最底部就是了

放在Easy剛好(會這麼說是有很多medium等級的題目還是很Easy)

Java

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        
        if(root!=null){
            swap(root);
        }
        
        return root;
        
    }
    
     public void swap(TreeNode node){
        
        TreeNode temp = node.right;
        node.right = node.left;
        node.left=temp;
        
        if(node.left!=null)
            swap(node.left);
        if(node.right!=null)
            swap(node.right);
    }
       
}



C++


    

  1. 
class Solution {
    

    2. 

  2. 
public:
    

    3. 

  3. 
    TreeNode* invertTree(TreeNode* root) {
    

    4. 

  4. 
       
    

    5. 

  5. 
       if(!root)
    

    6. 

  6. 
        return NULL;
    

    7. 

  7. 
       
    

    8. 

  8. 
       if(root!=NULL&&(root->left!=NULL||root->right!=NULL)){    
    

    9. 

  9. 
           TreeNode* temp;
    

    10. 

  10. 
           temp=root->left;
    

    11. 

  11. 
           root->left=root->right;
    

    12. 

  12. 
           root->right=temp;
    

    13. 

  13. 
           
    

    14. 

  14. 
           invertTree(root->left);
    

    15. 

  15. 
           invertTree(root->right);
    

    16. 

  16. 
       }
    

    17. 

  17. 
       
    

    18. 

  18. 
       return root;
    

    19. 

  19. 
       
    

    20. 

  20. 
    }
    

    21. 

  21. 
   
    

    22. 

  22. 
   
    

    23. 

  23. 
   
    

    24. 

  24. 
   
    

    25. 

  25. 
};
    

    26.
這種轉樹的題目很基本

 可以從這種題目慢慢體會遞迴的感覺

 在很多地方都會用到

2016年2月20日 星期六

LeetCode--Single Number II in Java

上午8:15 Posted by Unknown No comments



Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
這種題目大概第一想法會想用Hashmap
然後Linear Time去做應該是沒問題，不過很明顯不是最好的做法使用的Hashmap空間也會因為給的測資越來越長而變大所以這種題目大部分都會使用到 bitmask的方式來做

考慮全部用binary表示，
如果我們把 第 i個位置上所有數字的和對3取餘，
那麼只會有兩個結果 0 或 1 (因為3個0或3個1相加餘數都為0).
因此取餘數的結果就是那個  Single Number.

public int singleNumber(int[] nums) {
        
    int[] arr=new int[32]; //把每個數字的32位元都一一存下來
    int result = 0;  
    
    for (int i = 0; i < 32; i++) {
        for (int j = 0; j < nums.length; j++) {
            if (((nums[j] >> i) & 1)==1) { //把每位元加總起來
                arr[i]++;
            }
         } 
        result |= ((arr[i] % 3) << i);  
        //然後把結果%3之後把結果shift到result
    }
    
    
    return result;
這方法很簡單明瞭，跑起來也不差。

在O(n)之內 但還有不需要空間且更快一點的辦法

則是要用到bit manipulation mask的東西 (這一系列要快都必須這樣做)

在這裡使用三個常數來做

1.ones= 來表示第i-th的bit已經出現1次
2.twos=來表示第i-th的bit已經出現2次
3.threes=來表示第i-th的bit已經出現三次
當three出現的時候就去清除 ones跟 twos最後迴圈完的結果 ones就是本題要的答案 


public int singleNumber(int[] nums) {
        
int ones = 0, twos = 0, threes = 0; 

for (int i = 0; i < n; i++) { 

  twos |= ones & A[i]; //twos holds the number appear twice
  ones ^= A[i];  // appear once
  threes = ones & twos; // appear three times
  ones &= ~threes; 
  twos &= ~threes;  
  //這裡會把出現三次的部分 1轉成零　清除ones twos中的threes部分
  return ones;
}


有更厲害的人討論出General solution

推廣到K次以上