Summary Codes :-)


  • 0
    T

    • Subsets vs Subsets II
    • Search in Rotated Sorted Array vs Search in Rotated Sorted Array II

    Subsets

        iterative
        public List<List<Integer>> subsets(int[] nums) {
            
            ArrayList<List<Integer>> ans = new ArrayList<>();
            if(nums.length == 0) return ans;
            
            ans.add(new ArrayList<>());
            
            for(int num: nums){
                int size = ans.size();
                for(int i = 0; i < size; i ++){
                    List<Integer> tmp = new ArrayList<>(ans.get(i));
                    tmp.add(num);
                    ans.add(tmp);
                }
            }
            
            return ans;
        }
    
        recursive
        public List<List<Integer>> subsets(int[] nums) {
            
            ArrayList<List<Integer>> ans = new ArrayList<>();
            if(nums.length == 0) return ans;
            
            List<Integer> sub = new ArrayList<>();
            dfs(nums, 0, sub, ans);
            return ans;
        }
        
        public void dfs(int[] nums, int start, List<Integer> sub, ArrayList<List<Integer>> ans) {
            
            if(start > nums.length)
                return;
            
            ans.add(new ArrayList<>(sub));
            
            for(int i = start; i < nums.length; i ++){
                sub.add(nums[i]);
                dfs(nums, i + 1, sub, ans);
                sub.remove(sub.size() - 1);
            }
        }
    
        bit manipulation
        public List<List<Integer>> subsets(int[] nums) {
            
            ArrayList<List<Integer>> ans = new ArrayList<>();
            if(nums.length == 0) return ans;
            
            int n = 1 << nums.length;
            for(int i = 0; i < n; i ++){
                ans.add(getSub(nums, i));
            }
            return ans;
        }
        
        public List<Integer> getSub(int[] nums, int k) {
            
            List<Integer> subs = new ArrayList<>();
            
            int index = 0;
            for(int i = k; i > 0; i = i>>1){
                
                if((i & 1) == 1)
                    subs.add(nums[index]);
                index++;
            }
            return subs;
        }
    

    Subsets II(contain duplicates)

       iterative
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            
            ArrayList<List<Integer>> ans = new ArrayList<>();
            Arrays.sort(nums);
            
            int size = 0;
            ans.add(new ArrayList<>());
            for(int i = 0; i < nums.length; i ++){
                int start = i > 0 && nums[i-1] == nums[i]? size :  0;
                
                size = ans.size();
                for(int j = start; j < size; j ++){
                    List<Integer> tmp = new ArrayList<>(ans.get(j));
                    tmp.add(nums[i]);
                    ans.add(tmp);
                }
            }
            
            return ans;
        }
    
        recursive
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            
            ArrayList<List<Integer>> ans = new ArrayList<>();
            List<Integer> sub = new ArrayList<>();
            
            Arrays.sort(nums);
            dfs(nums, 0, sub, ans);
            return ans;
        }
        
        public void dfs(int[] nums, int start, List<Integer> sub, ArrayList<List<Integer>> ans){
            
            ans.add(new ArrayList<>(sub));
            
            for(int i = start; i < nums.length; i ++){
                
                if(i > start && nums[i] == nums[i-1]) continue;
                sub.add(nums[i]);
                dfs(nums, i + 1, sub, ans);
                sub.remove(sub.size() - 1);
            }
        }
    

    Search in Rotated Sorted Array

        public int search(int[] nums, int target) {
            
            if(nums.length == 0) return -1;
            
            int left = 0;
            int right= nums.length - 1;
            
            while(left <= right){
                
                int mid = (left + right) / 2;
                if(nums[mid] == target)    
                    return mid;
                    
                if(nums[mid] >= nums[left]){
                    if(nums[left] <= target && target < nums[mid])
                        right = mid - 1;
                    else
                        left = mid + 1;
                }
                else{
                    if(nums[mid] < target && target <= nums[right])
                        left = mid + 1;
                    else
                        right= mid - 1;
                }
            }
            
            return -1;
        }
    

    Search in Rotated Sorted Array II (allow dup)

        public boolean search(int[] nums, int target) {
           
            if(nums.length == 0) return false;
    
            int left = 0;
            int right= nums.length - 1;
            
            while(left <= right){
                
                int mid = (left + right) / 2;
                if(nums[mid] == target)    
                    return true;
                    
                if(nums[mid] > nums[left]){
                    if(nums[left] <= target && target < nums[mid])
                        right = mid - 1;
                    else
                        left = mid + 1;
                }
                else if (nums[mid] < nums[left]){
                    if(nums[mid] < target && target <= nums[right])
                        left = mid + 1;
                    else
                        right= mid - 1;
                }
                else
                    left++;
            }
           
           return false;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.