[LeetCode] 66. Plus One

• Problem: use vector to express digits, plus one to calculate result
• Concept: 算是簡單考 carry 的概念, mod 等基本運算
• Implementation:

• class Solution {
  public:
      vector plusOne(vector& digits) {
          vector result(digits);
          if (digits.size() == 0) return result;
  
          int carry = 1;  // init as plus one
          for (vector::iterator iter = digits.end() - 1; iter >= digits.begin(); iter--)        
          {
              int prevCarry = carry;
              carry = (*iter + carry) / 10; 
              *iter = (*iter + prevCarry) % 10; 
              if (0 == carry)
                  break;
          }   
          if (1 == carry) digits.insert(digits.begin(), 1); 
          return digits;
      }
  };
  

[C++] STL 中 list, vector 的差異

• C++ library 中, 著名的幾個 container 包含了 list, vector, map, set (hash map/set supported in C++11 or C++03/TR1)
• vector 是連續空間, 可以用 [] 作為 index來存取, 隨機存取速度快, 但插入 head 的速度慢, 若有 insert element 到 head, 且要求 complexity 要 O(1) 的話, 不能使用 vector
• list 非連續, 即 linked list 的封裝, 對於隨機存取速度慢, 但插入動作相當快速
• Ref: c++ list, vector, map, set 区别与用法比较