LeetCode

The Problem You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint stopping you from robbing each of them is that adjacent houses have security systems connected, and they will automatically contact the police if two adjacent houses are broken into on the same night. Given an integer array nums representing the amount of money in each house, return the maximum amount of money you can rob tonight without alerting the police. ...

The problem You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Examples Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step Constraints 1 <= n <= 45 Brute Force Solution func climbStairs(_ n: Int) -> Int { func dfs(_ i: Int) -> Int { if i >= n { return i == n ? 1 : 0 } return dfs(i + 1) + dfs(i + 2) } return dfs(0) } Explanation Let’s visualize and look at the first example Input: n = 2, You can see that we can take two single steps or we can take one double step at once and find out that we have two different ways to solve this problem. ...

The Problem There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you. You are given a list of strings words from the alien language’s dictionary. It is claimed that the strings in words are sorted lexicographically by the rules of this new language. A string a is lexicographically smaller than a string b if, in the first position where a and b differ, string a has a letter that appears earlier in the alien language than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the shorter string is the lexicographically smaller one. ...

The Problem You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph. Return the number of connected components in the graph. Examples Input: n = 5, edges = [[0,1],[1,2],[3,4]] Output: 2 Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]] Output: 1 Constraints 1 <= n <= 2000 1 <= edges.length <= 5000 edges[i].length == 2 0 <= ai, bi < n ai != bi There are no repeated edges. Depth-First Search Solution func countComponents(_ n: Int, _ edges: [[Int]]) -> Int { var adj: [Int: [Int]] = [:] for i in 0 ..< n { adj[i] = [] } var visit = Array(repeating: false, count: n) for value in edges { let u = value[0] let v = value[1] adj[u]!.append(v) adj[v]!.append(u) } func dfs(_ node: Int) { for nei in adj[node]! { if !visit[nei] { visit[nei] = true dfs(nei) } } } var res = 0 for node in 0 ..< n { if !visit[node] { visit[node] = true dfs(node) res += 1 } } return res } Explanation From the description, we learn that we need to find the number of connected components in a graph. Let’s clarify what a connected component means: ...

The problem You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph. Return true if the edges of the given graph make up a valid tree, and false otherwise. Examples Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true ...