Posts

Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (S i , S j ) of elements in this subset satisfies: S i % S j = 0 or S j % S i = 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]   class Solution {     public List<Integer> largestDivisibleSubset(int[] nums) {     List<Integer> result = new ArrayList<Integer>();     if(nums==null||nums.length==0)         return result;       Arrays.sort(nums);       int[] arr = new int[nums.length];     int[] index = new int[nums.length];     Arrays.fill(arr, 1);     Arrays.fill(index, -1);       int max=0;     int maxIndex=-1;   ...

Insert Delete GetRandom O(1)

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(); ...

Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place   so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note:  You are not suppose to use the library's sort function for this problem. Example: Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2]   class Solution {    public void sortColors(int[] nums) {         int low = 0;         int mid = 0;         int high = nums.length - 1;         int temp = 0;         while (mid <= high) {             switch (nums[mid]) {                 ca...

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Example 1: Input: [1,3,5,6], 5 Output: 2 Example 2: Input: [1,3,5,6], 2 Output: 1 Example 3: Input: [1,3,5,6], 7 Output: 4 Example 4: Input: [1,3,5,6], 0 Output: 0   class Solution {     public int searchInsert(int[] nums, int target) {                 int i = 0, length = nums.length;                 for(i=0;i<length;i++){             if(nums[i] >= target){                 return i;             }   ...

Is Subsequence?

Given a string s and a string t , check if s is subsequence of t . A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not). Follow up: If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code? Example 1: Input: s = "abc", t = "ahbgdc" Output: true Example 2: Input: s = "axc", t = "ahbgdc" Output: false Constraints: 0 <= s.length <= 100 0 <= t.length <= 10^4 Both strings consists only of lowercase characters.   class Solution {     public boolean isSubsequence(String s, String t) {               if(s.length()==0)    ...

Power of Two

Given an integer, write a function to determine if it is a power of two. Example 1: Input: 1 Output: true Explanation: 2 0  = 1 Example 2: Input: 16 Output: true Explanation: 2 4  = 16 Example 3: Input: 218 Output: false METHOD 1:   class Solution { public boolean isPowerOfTwo(int n) {     if(n<=0)         return false;       while(n>2){         int t = n>>1;         int c = t<<1;           if(n-c != 0)             return false;           n = n>>1;     }       return true; } } Try it on Leetcode If a number is power of 2, it's binary form should be 10...0. So if we right shift a bit of the number and th...