#LeetCode:3. Longest Substring Without Repeating Characters

用 Sliding Window 的方式,用前後兩個 index 去紀錄目前所找到的子字串。

每次往後延伸 Window 時,先檢查前面是否有重複出現過該字母,若有就把頭移到重複出現的該字母前一次出現的 index 的後面一位,如果前一次的 index 已經不在所夾住的子字串中則忽略。接著再將目前往後延伸到的字母所在 index 給記錄下來,以利之後的查找。這樣在每次延伸出來的子字串中找出最長的長度即是答案。

C++(46ms)

/*******************************************************/
/* LeetCode 3. Longest Substring Without Repeating     */
/*             Characters                              */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/23                                 */
/*******************************************************/
class Solution {
public:
  int lengthOfLongestSubstring(string s) {
    map<char, int> currentIndexMap;

    int sLength = s.length();
    int maxSubstringLength = 0;
    int head = 0;
    for(int i = 0 ; i < sLength ; ++i){
      if(currentIndexMap.find(s[i]) != currentIndexMap.end()){
        head = max(currentIndexMap[s[i]] + 1, head);
      }

      currentIndexMap[s[i]] = i;
      maxSubstringLength = max(maxSubstringLength, i - head + 1);
    }

    return maxSubstringLength;      
  }
};

#LeetCode:2. Add Two Numbers

將兩個 Linked List 中的數值做相加,並將進位加給下一個 Node 即可。要多加小心指標的操作。

C++(64ms)

/*******************************************************/
/* LeetCode 2. Add Two Numbers                         */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/23                                 */
/*******************************************************/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    int carry = 0;
    ListNode *head = NULL;
    ListNode *p1 = l1, *p2 = l2, *current = NULL;
    while(p1 != NULL || p2 != NULL){
      int sum = _iterateCurrent(&p1) + _iterateCurrent(&p2) + carry;
      int value = sum % 10;
      carry = sum / 10;

      if(head == NULL){
        head = new ListNode(value);
        current = head;
      }
      else{
        current->next = new ListNode(value);
        current = current->next;
      }
    }

    if(carry > 0) current->next = new ListNode(carry);

    return head;
  }

private:
  int _iterateCurrent(ListNode** p){
    if(*p != NULL){
      int value = (*p)->val;
      *p = (*p)->next;  
      return value;
    }

    return 0;
  }
};

#LeetCode:1. Two Sum

建 Hash 表將所選到之數字 a 所不足的那格 target - a 把自己的 index (i) 紀錄下來,這樣等到該不足之數 target - a 出現的時候可以直接查到與第 i 格湊起來即是答案。

C++(10ms)

/*******************************************************/
/* LeetCode 1. Two Sum                                 */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/23                                 */
/*******************************************************/
class Solution {
public:
  vector<int> twoSum(vector<int>& nums, int target) {
    map<int, int> complementMap;
    for(int i = 0 ; i < nums.size() ; ++i){
      auto complement = complementMap.find(nums[i]);
      if(complement != complementMap.end()){
        int result[] = {complement->second, i};
        return vector<int>(result, result + 2);
      }
      complementMap[target - nums[i]] = i;
    }
  }
};