

0021-0030

21. Merge Two Sorted Lists $\star$

class Solution {
 public:
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1 || !l2) return l1 ? l1 : l2;

    if (l1->val > l2->val) swap(l1, l2);
    l1->next = mergeTwoLists(l1->next, l2);

    return l1;
  }
};

22. Generate Parentheses $\star\star$

class Solution {
 public:
  vector<string> generateParenthesis(int n) {
    vector<string> ans;

    helper("", n, n, ans);

    return ans;
  }

 private:
  void helper(string str, int l, int r, vector<string>& ans) {
    if (l == 0 && r == 0) ans.push_back(str);
    if (l > 0) helper(str + '(', l - 1, r, ans);
    if (l < r) helper(str + ')', l, r - 1, ans);
  }
};

23. Merge k Sorted Lists $\star\star\star$

class Solution {
 public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode dummy(0);
    ListNode* curr = &dummy;
    priority_queue<ListNode*, vector<ListNode*>, compareListNode> pq;

    for (auto list : lists)
      if (list) pq.push(list);

    while (!pq.empty()) {
      curr->next = pq.top();
      pq.pop();
      curr = curr->next;
      if (curr->next) pq.push(curr->next);
    }

    return dummy.next;
  }

 private:
  struct compareListNode {
    bool operator()(const ListNode* l1, const ListNode* l2) {
      return l1->val > l2->val;
    }
  };
};

24. Swap Nodes in Pairs $\star\star$

class Solution {
 public:
  ListNode* swapPairs(ListNode* head) {
    if (!head || !head->next) return head;

    ListNode dummy(0);
    dummy.next = head;
    int length = 0;
    for (auto curr = head; curr; curr = curr->next) ++length;

    auto prev = &dummy;
    auto curr = head;

    for (int i = 0; i < length / 2; ++i) {
      auto next = curr->next;
      curr->next = next->next;
      next->next = prev->next;
      prev->next = next;
      prev = curr;
      curr = curr->next;
    }

    return dummy.next;
  }
};

25. Reverse Nodes in k-Group $\star\star\star$

class Solution {
 public:
  ListNode* reverseKGroup(ListNode* head, int k) {
    if (!head || k == 1) return head;

    ListNode dummy(0);
    dummy.next = head;
    int length = 0;
    for (auto curr = head; curr; curr = curr->next) ++length;

    auto prev = &dummy;
    auto curr = head;

    for (int i = 0; i < length / k; ++i) {
      for (int j = 0; j < k - 1; ++j) {
        auto next = curr->next;
        curr->next = next->next;
        next->next = prev->next;
        prev->next = next;
      }
      prev = curr;
      curr = curr->next;
    }

    return dummy.next;
  }
};

26. Remove Duplicates from Sorted Array $\star$

class Solution {
 public:
  int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;

    int j = 0;
    for (int i = 1; i < nums.size(); ++i)
      if (nums[i] != nums[j]) nums[++j] = nums[i];

    return j + 1;
  }
};

27. Remove Element $\star$

class Solution {
 public:
  int removeElement(vector<int>& nums, int val) {
    int i = 0;
    for (int num : nums)
      if (num != val) nums[i++] = num;

    return i;
  }
};

28. Implement strStr() $\star$

class Solution {
 public:
  int strStr(string haystack, string needle) {
    const int m = haystack.length();
    const int n = needle.length();

    for (int i = 0; i < m - n + 1; i++)
      if (haystack.substr(i, n) == needle) return i;

    return -1;
  }
};

29. Divide Two Integers $\star\star$

class Solution {
 public:
  int divide(int dividend, int divisor) {
    if (dividend == INT_MIN && divisor == -1) return INT_MAX;

    long ans = 0;
    long dvd = labs(dividend);
    long dvs = labs(divisor);
    int sign = dividend > 0 ^ divisor > 0 ? -1 : 1;

    while (dvd >= dvs) {
      long m = 1;
      long temp = dvs;
      while (temp << 1 <= dvd) {
        m <<= 1;
        temp <<= 1;
      }
      dvd -= temp;
      ans += m;
    }

    return sign * ans;
  }
};

30. Substring with Concatenation of All Words $\star\star\star$

class Solution {
 public:
  vector<int> findSubstring(string s, vector<string>& words) {
    if (s.empty() || words.empty()) return {};

    const int m = s.length();
    const int n = words[0].length();

    vector<int> ans;

    unordered_map<string, int> map;
    for (string& word : words) ++map[word];

    for (int i = 0; i < n; ++i) {
      int index = i;
      int count = 0;
      unordered_map<string, int> tempMap;
      for (int j = i; j <= m - n; j += n) {
        string str = s.substr(j, n);
        if (map.count(str)) {
          ++tempMap[str];
          ++count;
          while (tempMap[str] > map[str]) {
            --tempMap[s.substr(index, n)];
            --count;
            index += n;
          }
          if (count == words.size()) {
            ans.push_back(index);
            --tempMap[s.substr(index, n)];
            --count;
            index += n;
          }
        } else {
          tempMap.clear();
          count = 0;
          index = j + n;
        }
      }
    }

    return ans;
  }
};