Given a non-empty array of digits representing a non-negative integer, increment one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself. Example 1: Input: [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123. Example 2: ...
Given a list of lists of integers, nums, return all elements of nums in diagonal order as shown in the below images. Example 1: Input: nums = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,4,2,7,5,3,8,6,9] Example 2: Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]] Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16] Example 3: Input: nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]] Output: [1,4,2,5,3,8,6,9,7,10,11] Example 4: Input: nums = [[1,2,3,4,5,6]] Output: [1,2,3,4,5,6] Constraints: 1 <= nums.length <= 10^5 1 <= nums[i].length <= 10^5 1 <= nums[i][j] <= 10^9 There at most 10^5 elements in nums. Solution: ...
The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. Note: 0 ≤ x, y < 231. Example: Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ The above arrows point to positions where the corresponding bits are different. Solution: ...
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: ...