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. ...
A string s of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts. Example 1: Input: s = "ababcbacadefegdehijhklij" Output: [9,7,8] Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts. Note: ...
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police. ...
Given an array A of 0s and 1s, we may change up to K values from 0 to 1. Return the length of the longest (contiguous) subarray that contains only 1s. Example 1: Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2 Output: 6 Explanation: [1,1,1,0,0,1,1,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined. Example 2: Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 Output: 10 Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined. Note: ...
Design a data structure that supports all following operations in average O(1) time. insert(val): Inserts an item val to the set if not already present. remove(val): Removes an item val from the set if present. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned. Example: // Init an empty set. RandomizedSet randomSet = new RandomizedSet(); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomSet.insert(1); // Returns false as 2 does not exist in the set. randomSet.remove(2); // Inserts 2 to the set, returns true. Set now contains [1,2]. randomSet.insert(2); // getRandom should return either 1 or 2 randomly. randomSet.getRandom(); // Removes 1 from the set, returns true. Set now contains [2]. randomSet.remove(1); // 2 was already in the set, so return false. randomSet.insert(2); // Since 2 is the only number in the set, getRandom always return 2. randomSet.getRandom(); Solution: ...