

0201-0210

201. Bitwise AND of Numbers Range $\star\star$

class Solution {
 public:
  int rangeBitwiseAnd(int m, int n) {
    return m < n ? rangeBitwiseAnd(m >> 1, n >> 1) << 1 : m;
  }
};

202. Happy Number $\star$

class Solution {
 public:
  bool isHappy(int n) {
    int slow = helper(n);
    int fast = helper(helper(n));

    while (slow != fast) {
      slow = helper(slow);
      fast = helper(helper(fast));
    }

    if (slow == 1) return true;
    return false;
  }

 private:
  int helper(int n) {
    int sum = 0;

    while (n) {
      sum += pow(n % 10, 2);
      n /= 10;
    }

    return sum;
  }
};

203. Remove Linked List Elements $\star$

class Solution {
 public:
  ListNode* removeElements(ListNode* head, int val) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* curr = &dummy;

    while (curr) {
      ListNode* next = curr->next;
      while (next && next->val == val) next = next->next;
      curr->next = next;
      curr = next;
    }

    return dummy.next;
  }
};

204. Count Primes $\star$

class Solution {
 public:
  int countPrimes(int n) {
    if (n <= 2) return 0;

    vector<bool> prime(n, true);
    prime[0] = false;
    prime[1] = false;

    for (int i = 0; i < sqrt(n); ++i)
      if (prime[i])
        for (int j = i * 2; j < n; j += i) prime[j] = false;

    return count(prime.begin(), prime.end(), true);
  }
};

205. Isomorphic Strings $\star$

class Solution {
 public:
  bool isIsomorphic(string s, string t) {
    unordered_map<char, int> map_s;
    unordered_map<char, int> map_t;

    for (int i = 0; i < s.length(); ++i) {
      if (map_s[s[i]] != map_t[t[i]]) return false;
      map_s[s[i]] = i + 1;
      map_t[t[i]] = i + 1;
    }

    return true;
  }
};

206. Reverse Linked List $\star$

class Solution {
 public:
  ListNode* reverseList(ListNode* head) {
    ListNode* prev = NULL;
    ListNode* curr = head;

    while (curr) {
      auto next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
    }

    return prev;
  }
};

207. Course Schedule $\star\star$

class Solution {
 public:
  bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses);
    vector<int> visited(numCourses, 0);

    for (vector<int>& prerequisite : prerequisites)
      graph[prerequisite[1]].push_back(prerequisite[0]);

    for (int i = 0; i < numCourses; ++i)
      if (dfs(graph, visited, i)) return false;

    return true;
  }

 private:
  bool dfs(vector<vector<int>>& graph, vector<int>& visited, int curr) {
    if (visited[curr] == 1) return true;
    if (visited[curr] == 2) return false;

    visited[curr] = 1;

    for (int neighbor : graph[curr])
      if (dfs(graph, visited, neighbor)) return true;

    visited[curr] = 2;

    return false;
  }
};

208. Implement Trie (Prefix Tree) $\star\star$

class Trie {
 public:
  void insert(string word) {
    TrieNode* node = &root;
    for (char c : word) {
      TrieNode*& next = node->children[c - 'a'];
      if (!next) next = new TrieNode;
      node = next;
    }
    node->isWord = true;
  }

  bool search(string word) {
    TrieNode* node = find(word);
    return node && node->isWord;
  }

  bool startsWith(string prefix) { return find(prefix); }

 private:
  struct TrieNode {
    TrieNode() : children(26), isWord(false) {}
    ~TrieNode() {
      for (TrieNode* child : children) delete child;
    }

    vector<TrieNode*> children;
    bool isWord;
  };

  TrieNode root;

  TrieNode* find(string& prefix) {
    TrieNode* node = &root;
    for (char c : prefix) {
      TrieNode*& next = node->children[c - 'a'];
      if (!next) return nullptr;
      node = next;
    }
    return node;
  }
};

209. Minimum Size Subarray Sum $\star\star$

class Solution {
 public:
  int minSubArrayLen(int s, vector<int>& nums) {
    int ans = INT_MAX;
    int sum = 0;

    for (int i = 0, j = 0; i < nums.size(); ++i) {
      sum += nums[i];
      while (sum >= s) {
        ans = min(ans, i - j + 1);
        sum -= nums[j++];
      }
    }

    return ans != INT_MAX ? ans : 0;
  }
};

210. Course Schedule II $\star\star$

class Solution {
 public:
  vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    vector<int> ans;
    vector<vector<int>> graph(numCourses);
    vector<int> visited(numCourses, 0);

    for (vector<int>& prerequisite : prerequisites)
      graph[prerequisite[0]].push_back(prerequisite[1]);

    for (int i = 0; i < numCourses; ++i)
      if (dfs(graph, visited, i, ans)) return {};

    return ans;
  }

 private:
  bool dfs(vector<vector<int>>& graph, vector<int>& visited, int curr,
           vector<int>& ans) {
    if (visited[curr] == 1) return true;
    if (visited[curr] == 2) return false;

    visited[curr] = 1;

    for (int neighbor : graph[curr])
      if (dfs(graph, visited, neighbor, ans)) return true;

    visited[curr] = 2;
    ans.push_back(curr);

    return false;
  }
};