Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root). For example: Given binary tree [3,9,20,null,null,15,7], 1 2 3 4 5 3 / \ 9 20 / \ 15 7 return its bottom-up level order traversal as: ...
You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins. Given n, find the total number of full staircase rows that can be formed. n is a non-negative integer and fits within the range of a 32-bit signed integer. Example 1: 1 2 3 4 5 6 n = 5 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ Because the 3rd row is incomplete, we return 2. ...
In a given grid, each cell can have one of three values: the value 0 representing an empty cell; the value 1 representing a fresh orange; the value 2 representing a rotten orange. Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead. ...
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n. 1 2 3 4 5 Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. 1 2 3 4 5 Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9. Solution 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int numSquares(int n) { int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i < dp.length; i++) { dp[i] = Integer.MAX_VALUE; for (int j = 1; j * j <= i; j++) { dp[i] = Math.min(dp[i], dp[i - j * j] + 1); } } return dp[n]; } } Solution 2021-11-30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int numSquares(int n) { int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; int max_square_index = (int) Math.sqrt(n) + 1; int[] squares = new int[max_square_index]; for (int i = 1; i < squares.length; i++) { squares[i] = i * i; } for (int i = 1; i < dp.length; i++) { for (int j = max_square_index - 1; j > 0; j--) { if (i - squares[j] >= 0) { int at = i - squares[j]; dp[i] = Math.min(dp[i], dp[at] + 1); } } } return dp[n]; } }
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0. If there are multiple solutions, return any subset is fine. Example 1: Input: [1,2,3] Output: [1,2] (of course, [1,3] will also be ok) Example 2: Input: [1,2,4,8] Output: [1,2,4,8] Solution: 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 class Solution { public List<Integer> largestDivisibleSubset(int[] nums) { int n = nums.length ; if (n== 0) { return Collections.emptyList(); } Arrays.sort(nums); int[] dp = new int[n]; dp[0] = 1; int ans = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[i] % nums[j] == 0) { dp[i] = Math.max(dp[i], dp[j] + 1); ans = Math.max(ans, dp[i]); } } } int prev = -1; List<Integer> result = new ArrayList<>(); for (int i = n - 1; i >= 0; i--) { if (dp[i] == ans && (prev == -1 || prev % nums[i] == 0)) { prev = nums[i]; ans--; result.add(nums[i]); } } Collections.sort(result); return result; } }
Given an unsorted array of integers, find the length of longest increasing subsequence. 1 2 3 4 5 Example: Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. Note: There may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O(n2) complexity. Follow up: Could you improve it to O(n log n) time complexity? ...
There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w. Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1. Example 1: 1 2 3 4 5 6 Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1 Output: 200 Explanation: The graph looks like this: ...
Cell compete: Eight houses, represented as a cells, are arranged as a straight line. Each days every cells competes with adjacent cells. An integer value 1 represents an active cell and a value of 0 represent an inactive cell. if the neigbour on both the sides of the cell are both active or inactive, the cell become inactive in the next day, otherwise the become active. The two cells on each or have a single adjacent cell, so asume that the onoccupied space in the opposite side is an inactive cell. even after updating the cell state, consider its previus state when updating the state of ohters cells. The state information of the cells should be updated simultaneosly. ...
Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL. For example, 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Given the tree: 4 / \ 2 7 / \ 1 3 And the value to search: 2 You should return this subtree: 2 / \ 1 3 In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL. ...
You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: 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 Recursive Solution: 1 2 3 4 5 6 7 8 9 10 class Solution { public int climbStairs(int n) { return climbStairs(0, n); } int climbStairs(int i, int n) { if (i > n) return 0; if (i == n) return 1; return climbStairs(i + 1, n) + climbStairs(i + 2, n); } } Recursive Solution with Memo 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int climbStairs(int n) { int[] memo = new int[n + 1]; return climbStairs(0, n, memo); } int climbStairs(int i, int n, int[] memo) { if (i > n) return 0; if (i == n) return 1; if (memo[i] > 0) { return memo[i]; } return memo[i] = climbStairs(i + 1, n, memo) + climbStairs(i + 2, n, memo); } }