2026/02/28

[LeetCode] 128 Longest Consecutive Sequence

 練習使用unordered set

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
  int longestConsecutive(vector<int>& Nums) {
    std::unordered_set<int> numSet;
    for (auto &num : Nums)
      numSet.insert(num);

    int ans = 0;
    for (auto &num : Nums) {
      int next = 1;
      while (numSet.count(num + next)) {
        numSet.erase(num + next);
        next++;
      }

      int prev = 1;
      while (numSet.count(num - prev)) {
        numSet.erase(num - prev);
        prev++;
      }

      ans = max(ans, next + prev - 1);
    }
    return ans;
  }
};
Labels:

2026/02/27

[LeetCode] 206. Reverse Linked List 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
  ListNode* reverseList(ListNode* head) {
    ListNode* prevNode = nullptr;
    ListNode* nextNode = nullptr;
    ListNode* curNode = head;
    while (curNode != nullptr) {
      nextNode = curNode->next;
      curNode->next = prevNode;
      prevNode = curNode;
      curNode = nextNode;
    }
    return prevNode;
  }
};
Labels:

2026/02/26

[LeetCode] 1 Two Sum 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
  map<int, int> idxMap;
  vector<int> twoSum(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); i++)
      idxMap[nums[i]] = i;
    
    for (int i = 0; i < nums.size(); i++) {
      int remain = target - nums[i];
      if (idxMap.find(remain) != idxMap.end() && 
          idxMap[remain] != i) {
        return {i, idxMap[remain]};
      }
    }
    
    return {};
  }
};
Labels:

2026/02/25

[Leetcode] 21 Merge Two Sorted Lists

 寫得好冗= ="

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr)
          return list2;
        if (list2 == nullptr)
          return list1;

        ListNode* curNode = nullptr;
        if (list1->val <= list2->val) {
          curNode = list1;
          list1 = list1->next;
        }
        else {
          curNode = list2;
          list2 = list2->next;
        }
        ListNode* startNode = curNode;

        while (list1 != nullptr && list2 != nullptr) {
          if (list1->val <= list2->val) {
            curNode->next = list1;
            curNode = list1;
            list1 = list1->next;
          }
          else {
            curNode->next = list2;
            curNode = list2;
            list2 = list2->next;
          }
        }

        if (list1 != nullptr && list2 == nullptr)
          curNode->next = list1;
        else if (list1 == nullptr && list2 != nullptr)
          curNode->next = list2;

        return startNode;
    }
};

改良 : 加個dummy

  
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
  ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* startNode = new ListNode(5566);
    ListNode* curNode = startNode;

    while (list1 != nullptr && list2 != nullptr) {
      if (list1->val <= list2->val) {
        curNode->next = list1;
        list1 = list1->next;
      }
      else {
        curNode->next = list2;
        list2 = list2->next;
      }
      curNode = curNode->next;
    }

    if (list1 != nullptr && list2 == nullptr)
      curNode->next = list1;
    else if (list1 == nullptr && list2 != nullptr)
      curNode->next = list2;

    return startNode->next;
  }
};
Labels:

2026/02/24

[LeetCode] 1721 Swapping Nodes in a Linked List

要自己做dummy

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
  ListNode* getBeginKthNode(ListNode* head, int k) {
    ListNode* node = head;
    for (int i = 0; i < k; i++)
      node = node->next;
    return node;
  }

  ListNode* getEndKthNode(ListNode* head, int k) {
    ListNode* fastNode = getBeginKthNode(head, k);
    ListNode* slowNode = head;

    while (fastNode != nullptr) {
      slowNode = slowNode->next;
      fastNode = fastNode->next;
    }

    return slowNode;
  }

  ListNode* swapNodes(ListNode* head, int k) {
    ListNode* DUMMY = new ListNode(5566, head);
    ListNode* beginKthNode = getBeginKthNode(DUMMY, k);
    ListNode* endKthNode = getEndKthNode(DUMMY, k);
    swap(beginKthNode->val, endKthNode->val);
    return head;
  }
};
Labels:

2026/02/23

[LeetCode] 133 Clone Graph 

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     vector<Node*> neighbors;
  7.     Node() {
  8.         val = 0;
  9.         neighbors = vector<Node*>();
  10.     }
  11.     Node(int _val) {
  12.         val = _val;
  13.         neighbors = vector<Node*>();
  14.     }
  15.     Node(int _val, vector<Node*> _neighbors) {
  16.         val = _val;
  17.         neighbors = _neighbors;
  18.     }
  19. };
  20. */
  22. class Solution {
  23. public:
  24.   std::map<int, Node*> cloneNodeMap;
  26.   Node* cloneGraph(Node* curNode) {
  27.     if (curNode == nullptr)
  28.       return nullptr;
  29.     auto cloneNode = new Node(curNode->val);
  30.     cloneNodeMap[curNode->val] = cloneNode;
  32.     for (Node* neighbor : curNode->neighbors) {
  33.       if (cloneNodeMap[neighbor->val] == nullptr) {
  34.         Node* cloneNeighbor = cloneGraph(neighbor);
  35.         cloneNode->neighbors.push_back(cloneNeighbor);
  36.       }
  37.       else
  38.         cloneNode->neighbors.push_back(cloneNodeMap[neighbor->val]);
  39.     }
  41.     return cloneNode;
  42.   }
  43. };
Labels:

[LeetCode] 19 Remove Nth Node From End of List

判斷被刪掉是否是head

稍微有點繞


  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.   const int MAGIC = 55668787;
  14.   ListNode* removeNthFromEnd(ListNode* head, int n) {
  15.     ListNode* slowNode = head;
  16.     ListNode* prevNode = new ListNode(MAGIC, slowNode);
  17.     ListNode* fastNode = head;
  18.     
  20.     // step 1 : find n-th node from the end
  21.     for (int i = 0; i < n; i++)
  22.       fastNode = fastNode->next;
  23.     
  24.     while (fastNode != nullptr) {
  25.       prevNode = slowNode;
  26.       slowNode = slowNode->next;
  27.       fastNode = fastNode->next;
  28.     }
  30.     // Step 2 : Remove slowNode  
  31.     //          In this moment, slowNode is the n-th node from the end
  32.     prevNode->next = slowNode->next;
  34.     if (slowNode == head) 
  35.       if (slowNode->next == nullptr)
  36.         return nullptr;
  37.       else
  38.         return prevNode->next;
  39.     else
  40.       return head;
  41.   }
  42. };
Labels:

2026/02/22

[LeetCode] 142 Linked List Cycle II

 延續LeetCode 141

先用快慢指針找到相遇點

再從head跟相遇點用一樣速度前進, 就會遇到cycle的進入點


  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode* takeOneStep(ListNode *node) {
  12.     if (node == nullptr)
  13.       return nullptr;
  14.     return node->next;
  15.   }
  17.   ListNode* takeTwoStep(ListNode *node) {
  18.     if (node == nullptr)
  19.       return nullptr;
  20.     ListNode* tmp = node->next;
  21.     if (tmp == nullptr)
  22.       return nullptr;
  23.     return tmp->next;
  24.   }
  26.   // LeetCode 141. Linked List Cycle
  27.   ListNode *foundMeetingPoint(ListNode *head) {
  28.     ListNode* stepOneNode = takeOneStep(head);
  29.     ListNode* stepTwoNode = takeTwoStep(head);
  30.     
  31.     while (stepOneNode != nullptr && stepTwoNode != nullptr) {
  32.       if (stepOneNode == stepTwoNode)
  33.         break;
  34.       stepOneNode = takeOneStep(stepOneNode);
  35.       stepTwoNode = takeTwoStep(stepTwoNode);
  36.     }
  38.     if (stepOneNode == nullptr || stepTwoNode == nullptr)
  39.       return nullptr;
  40.     return stepOneNode;
  41.   }
  43.   ListNode *detectCycle(ListNode *head) {
  44.     // Step 1 : find meeting point in cycle
  45.     ListNode *meet = foundMeetingPoint(head);
  46.     if (meet == nullptr)
  47.       return nullptr;
  49.     // Step 2 : the middle point of head and meeting point is entry point of cycle
  50.     ListNode *start = head;
  52.     while(meet != start) {
  53.       start = takeOneStep(start);
  54.       meet = takeOneStep(meet);
  55.     }
  57.     return start;
  58.   }
  59. };
Labels:

2026/02/20

[LeetCode] 141 : Linked List Cycle

Naive version
  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.   bool hasCycle(ListNode *head) {
  12.     std::map<ListNode*, bool> nodeMap;
  13.     ListNode* curNode = head;
  14.     nodeMap[curNode] = true;
  16.     while(curNode != nullptr) {
  17.       curNode = curNode->next;
  18.       if (nodeMap[curNode]) 
  19.         return true;
  20.       else
  21.         nodeMap[curNode] = true;
  22.     }
  24.     return false;
  25.   }
  26. };
Follow up : two pointer version for O(1) memory 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* takeOneStep(ListNode *node) {
    if (node == nullptr)
      return nullptr;
    return node->next;
  }

  ListNode* takeTwoStep(ListNode *node) {
    if (node == nullptr)
      return nullptr;
    ListNode* tmp = node->next;
    if (tmp == nullptr)
      return nullptr;
    return tmp->next;
  }

  bool hasCycle(ListNode *head) {
    ListNode* stepOneNode = takeOneStep(head);
    ListNode* stepTwoNode = takeTwoStep(head);
    
    while (stepOneNode != nullptr && stepTwoNode != nullptr) {
      if (stepOneNode == stepTwoNode)
        return true;
      stepOneNode = takeOneStep(stepOneNode);
      stepTwoNode = takeTwoStep(stepTwoNode);
    }

    return false;
  }
};
Labels:
訂閱： 文章 (Atom)