There are 8 prison cells in a row, and each cell is either occupied or vacant. Each day, whether the cell is occupied or vacant changes according to the following rules: If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied. Otherwise, it becomes vacant. (Note that because the prison is a row, the first and the last cells in the row can’t have two adjacent neighbors.) ...
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], 3 / \ 9 20 / \ 15 7 return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ] Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { Map<Integer, List<Integer>> map = new TreeMap<>((a,b) -> { return b - a; }); dfs(root, 0, map); System.out.println(map); List<List<Integer>> result = new ArrayList<>(); for (List<Integer> levelNodes: map.values()) { result.add(levelNodes); } return result; } void dfs(TreeNode node, int level, Map<Integer, List<Integer>> map) { if (node == null) { return; } dfs(node.left, level + 1, map); addLevelNode(map, node.val, level); dfs(node.right, level + 1, map); } void addLevelNode(Map<Integer, List<Integer>> map, int val, int level) { List<Integer> levelList = map.getOrDefault(level, new ArrayList<>()); levelList.add(val); map.put(level, levelList); } }
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: 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. Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9. Solution 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 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: 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. 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? Recursive O(2^n) Solution: class Solution { public int lengthOfLIS(int[] nums) { return lengthOfLIS(nums, Integer.MIN_VALUE, 0); } int lengthOfLIS(int[] nums, int prev, int currpos) { if (currpos == nums.length) { return 0; } int taken = 0; if (nums[currpos] > prev) { taken = 1 + lengthOfLIS(nums, nums[currpos], currpos + 1); } int nottaken = lengthOfLIS(nums, prev, currpos + 1); return Math.max(nottaken, taken); } } Recursive O(n*n) Solution with Memoization: class Solution { public int lengthOfLIS(int[] nums) { int[][] memo = new int[nums.length + 1][nums.length]; for (int[] l: memo) { Arrays.fill(l, -1); } return lengthOfLIS(nums, -1, 0, memo); } int lengthOfLIS(int[] nums, int prevpos, int currpos, int[][] memo) { if (currpos == nums.length) { return 0; } if (memo[prevpos + 1][currpos] >= 0) { return memo[prevpos + 1][currpos]; } int taken = 0; if (prevpos < 0 || nums[currpos] > nums[prevpos]) { taken = 1 + lengthOfLIS(nums, currpos, currpos + 1, memo); } int nottaken = lengthOfLIS(nums, prevpos, currpos + 1, memo); memo[prevpos + 1][currpos] = Math.max(nottaken, taken); return memo[prevpos + 1][currpos]; } } Solution: ...
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: 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, 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. ...