Daily question brushing record (11)

The first question is : The finger of the sword Offer II 005. Maximum product of word length

LeetCode: The finger of the sword Offer II 005. Maximum product of word length
describe :
Given an array of strings words, Please calculate when two strings words[i] and words[j] Does not contain the same characters , The maximum of the product of their lengths . Suppose that the string contains only English lowercase letters . If there is no pair of strings that do not contain the same characters , return 0.

Their thinking :

1. The length used here is words.length Array of ret To record every word String to binary format .
   for example : ac ===> 101 ; ad ===> 1001 ; bd ===> 1010
2. The method of converting string to binary , Is to traverse every character , Give Way ret[i] |= (1<<words[i].charAt(j)) , It means : The current character appears , Then record its corresponding bit in binary form , Because the characters are a~z 26 individual , From right to left , As long as there is 1, It means that the current element appears .
3. Traverse , in pairs And operation , As long as the result is equal to 0 , It means that the two do not contain the same elements . here , Record the length product of the largest two strings that do not contain the same element .

Code implementation :

class Solution {
    
    public int maxProduct(String[] words) {
    
        int[] ret = new int[words.length];
        for(int i = 0; i < words.length; i++) {
    
            for(int j = 0; j < words[i].length(); j++) {
    
            	//  As long as this character appears ,  Just turn this position into 1
                ret[i] = ret[i] | (1 << (words[i].charAt(j) - 'a'));
            }
        }
        int ans = 0;
        for(int i = 0; i < words.length-1; i++) {
    
            for(int j = i + 1; j < words.length; j++) {
    
            	//  Pairwise and operation 
                if((ret[i] & ret[j]) == 0) {
    
                	//  Record the maximum product 
                    ans = Math.max(ans, words[i].length() * words[j].length());
                }
            }
        }
        return ans;
    }
}

The second question is : The finger of the sword Offer II 007. Array and 0 Three numbers of

LeetCode: The finger of the sword Offer II 007. Array and 0 Three numbers of

describe :
Given an inclusion n Array of integers nums, Judge nums Are there three elements in a ,b ,c , bring a + b + c = 0 ？ Please find all and for 0 And No repetition Triple of .

Their thinking :

1. So let's sort it first ,
2. First of all, get number i individual Elements , Give Way left = i+1, right = len - 1;
3. From the remaining elements , Fetch , as long as nums[left] + nums[right] == target Just put this 3 Put elements into the result set , Note here , After joining , To the current left The value of the subscript and right The value of the subscript is de duplicated , In order to avoid adding
4. Pay attention every time you take elements , When i > 0 When . Be careful to take the same elements repeatedly . nums[i] = nums[i-1]

Code implementation :

class Solution {
    
    public List<List<Integer>> threeSum(int[] nums) {
    
    	//  Sort 
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length - 2;i++) {
    
            //  Here, it is forbidden to take the same elements repeatedly 
            if(i != 0 && nums[i] == nums[i-1]) continue;
            //  Because I got it nums[i]  To add up to 0,  You need to find and be  -nums[i] Of 
            int target = -nums[i];
            int left = i + 1;
            int right = nums.length-1;
            while (left < right) {
    
                if (nums[left] + nums[right] == target) {
    
                    //  The number of two subscripts here can meet the requirements ,  Just add these three elements into the set 
                    List<Integer> ret = new ArrayList<>();
                    ret.add(nums[i]);
                    ret.add(nums[left]);
                    ret.add(nums[right]);
                    ans.add(ret);
                    //  It's here to prevent left and right Repeat the subscript to get the same value ,  Deduplication 
                    int tmp = nums[left];
                    while (left < right && nums[left] == tmp){
    
                        left++;
                    }
                    tmp = nums[right];
                    while (left < right && nums[right] == tmp) {
    
                        right--;
                    }
                }else if (nums[left] + nums[right] < target) {
    
                    left++;
                }else {
    
                    right--;
                }
            }
        }
        return ans;
    }
}

Third question : The finger of the sword Offer II 008. And greater than or equal to target The shortest subarray of

LeetCode: The finger of the sword Offer II 008. And greater than or equal to target The shortest subarray of

describe :
Given a containing n An array of positive integers and a positive integer target .

Find the sum of the array ≥ target The smallest length of Continuous subarray [numsl, numsl+1, ..., numsr-1, numsr] , And return its length . If there is no sub array that meets the conditions , return 0 .

Their thinking :

1. Here we use the sliding window
2. Give Way left = 0, right =0, The initial window size is 0
3. use total Record nums[right] Value . Judge the present total and target value
   • If at present total >= target , Record the current Subscript distance ( Finally, only the smallest ) , At this time let total -= nums[left] , left++,
4. Loop each time right++
5. Sliding window size is always maintained [left,right]
6. Returns the minimum subscript distance
   

Code implementation :

class Solution {
    
    public int minSubArrayLen(int target, int[] nums) {
    
        int start = 0;
        int end = 0;
        int ans = Integer.MAX_VALUE;
        int total = 0;
        //  The size is  [start,end]  Sliding window of 
        while (end < nums.length) {
    
            total += nums[end];
            while (total >= target) {
    
                ans = Math.min(ans, end-start+1);
                total -= nums[start];
                start++;
            }
            end++;
        }
        return ans==Integer.MAX_VALUE?0:ans;
    }
}

Fourth question : The finger of the sword Offer II 009. The product is less than K Subarray

LeetCode: The finger of the sword Offer II 009. The product is less than K Subarray

describe :
Given an array of positive integers nums And integer k , Please find out that the product in the array is less than k The number of successive subarrays of .

Their thinking :

1. Use the sliding window to solve problems
2. Record the current product each time ret *= nums[j], Judge whether it is greater than k
   • If this is greater than k, Let the left edge of the window move (i++), Record the current subscript
3. Return all possible times

Code implementation :

class Solution {
    
    public int numSubarrayProductLessThanK(int[] nums, int k) {
    
        int i = 0;
        int ret = 1;
        int ans = 0;
        //  The sliding window  [i,j]
        for (int j = 0; j < nums.length; j++) {
    
            ret *= nums[j];
            while(i <= j && ret >= k) {
    
                ret /= nums[i];
                i++;
            }
            //  This method is used here to calculate and prevent double counting 
            ans += j - i + 1;
        }
        return ans;
    }
}

Fifth question : The finger of the sword Offer II 010. And for k Subarray

LeetCode: The finger of the sword Offer II 010. And for k Subarray

describe :
Given an array of integers and an integer k , Please find the array with k The number of consecutive subarrays of .

Their thinking :

1. Here we use hash table , Record the value of the current sum ret.
2. Judge Is there an element ret-k, This adds up to k, Record the current value value
3. Note here k = nums[i] The situation of , You need to add in advance 0 The situation of .

Code implementation :

class Solution {
    
    public int subarraySum(int[] nums, int k) {
    
        Map<Integer,Integer> map = new HashMap<>();
        int ans = 0; 
        map.put(0,1);
        int ret = 0;
        for(int i = 0; i < nums.length; i++) {
    
            ret += nums[i];
            if (map.containsKey(ret - k)) {
    
                ans += map.get(ret - k);
            }
            map.put(ret,map.getOrDefault(ret,0)+1);
        }
        return ans;
    }
}

Sixth question : The finger of the sword Offer II 011. 0 and 1 The same number of subarrays

LeetCode: The finger of the sword Offer II 011. 0 and 1 The same number of subarrays

describe :
Given a binary array nums , Find the same number of 0 and 1 The longest continuous subarray of , And returns the length of the subarray .

Their thinking :

1. First, let all in the array be 0 The element becomes -1, In this way, we only need to judge whether the sum is 0, We can know 0 and 1 Whether the number of is the same .
2. If the current element does not exist in the hash table , Is added to the hash table ,value The value is the current subscript
3. If the current element exists in the hash table , Record the current maximum subscript difference

Code implementation :

class Solution {
    
    public int findMaxLength(int[] nums) {
    
        for(int i = 0; i < nums.length; i++) {
    
            if(nums[i] == 0) nums[i] = -1;
        }
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        int ans = 0;
        int target = 0;
        for(int i = 0; i < nums.length; i++) {
    
            target += nums[i];
            if (map.containsKey(target)) {
    
                ans = Math.max(ans,i-map.get(target));
            }else {
    
                map.put(target,i);
            }
        }
        return ans;
    }
}