Ens

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); } }

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. 1 2 3 4 5 6 7 8 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 unsorted array of integers, find the length of longest continuous increasing subsequence (subarray). 1 2 3 4 5 6 Example 1: Input: [1,3,5,4,7] Output: 3 Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4. 1 2 3 4 5 Example 2: Input: [2,2,2,2,2] Output: 1 Explanation: The longest continuous increasing subsequence is [2], its length is 1. Note: Length of the array will not exceed 10,000. ...

Given a binary array, find the maximum number of consecutive 1s in this array. Example 1: 1 2 3 4 Input: [1,1,0,1,1,1] Output: 3 Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3. Note: The input array will only contain 0 and 1. The length of input array is a positive integer and will not exceed 10,000 Solution: ...