Day 19

884 unusual words in two sentences

A sentence is a string of words separated by spaces. Each word consists of only lowercase letters.

If a word happens to appear once in one sentence but does not appear in the other sentence, the word is not common.

Give you two sentences s1 and s2 and return a list of all the infrequently used words. The words in the returned list can be organized in any order.

Method hash table

First connect the two sentences, then divide them with spaces, and establish a map to save the number of occurrences of each word. If the number of occurrences of a word is once, it indicates that it is an uncommon word.

class Solution {
    public String[] uncommonFromSentences(String s1, String s2) {
        String s = s1 + " " + s2;
        String[] strings = s.split(" ");
        ArrayList<String> resArray = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for (String str : strings) {
            if (map.containsKey(str))
                map.put(str, map.get(str) + 1);
            else map.put(str, 1);
        }

        for (String key : map.keySet()) {
            if (map.get(key) == 1) resArray.add(key);
        }
        String[] res = new String[resArray.size()];
        int index = 0;
        for (String i : resArray) res[index++] = i;
        return res;
    }
}

438 find all the letter ectopic words in the string

Given two strings S and p, find the substrings of all ectopic words of p in s, and return the starting indexes of these substrings. The order in which answers are output is not considered.

Ectopic words refer to strings (including the same string) formed by the rearrangement of the same letters.

method

A differ ent variable is used to record the number of unqualified characters in two strings, and a count array is used to record the number of occurrences of each character. During initialization, for the first string, let it increase the number of corresponding characters, and for the second string, let it reduce the number of corresponding strings. Then, two pointers start and end are used to mark the interval whose length is the length of the second string. Start represents the next position to move out and end represents the next position to move in. There are several situations:

• If the count value of the character at the end position is 0 before it is moved in, after it is moved in, the count value will be added with 1 for the move in operation. Therefore, after the character is moved in, the count value will not be 0. At this time, the difference should be added with 1, indicating that the difference becomes larger.
• If the count value is 0 after the end position is moved in, it indicates that the difference becomes smaller, and the difference should be reduced by 1.
• The logic is the same for the characters moved out at the start position.

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int length1 = s.length();
        int length2 = p.length();
        if (length2 > length1) return res;
        int[] count = new int[26];
        for (int i = 0; i < length2; ++i){
            ++count[s.charAt(i) - 'a'];
            --count[p.charAt(i) - 'a'];
        }
        int differ = 0;
        for (int i : count) if (i != 0) ++differ;
        if (differ == 0) res.add(0);
        for (int end = length2; end < length1; ++end){//end is the position to be moved into
            int start = end - length2;//Position to be removed

            if (count[s.charAt(end) - 'a'] == 0) ++differ;//First case
            count[s.charAt(end) - 'a']++;
            if (count[s.charAt(end) - 'a'] == 0) --differ;//The second case

            if (count[s.charAt(start) - 'a'] == 0) ++differ;//Similarly
            count[s.charAt(start) - 'a']--;
            if (count[s.charAt(start) - 'a'] == 0) --differ;

            if (differ == 0) res.add(start + 1);
        }
        return res;
    }
}

713 subarray with product less than K

Given a positive integer array nums and integer k.

Please find out the number of consecutive subarrays in the array whose product is less than k.

Method 1 violent operation

Traverse the length of the interval, and then move the whole interval continuously. If the conditions are met, the answer will be increased by 1. Considering that the multiplication may overflow, the intermediate results are saved with long variables.

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int res = 0;
        long mulResRegister = 1;//Register intermediate results to avoid repeated calculation
        boolean flag = false;
        int judge = 1;
        //Special judgment: if the multiplication of all elements does not exceed the target value, the answer can be returned directly
        for (int i : nums) {
            judge *= i;
            if (judge >= k){
                flag = true;
                break;
            }
        }
        if (!flag) return nums.length * (nums.length + 1) / 2;
        for (int subLen = 1; subLen <= nums.length; ++subLen){
            flag = false;
            int start = 0, end = start + subLen;
            long multiple = mulResRegister * nums[end - 1];
            if (multiple < k) {res++;flag = true;}
            mulResRegister = multiple;
            while (end < nums.length){
                start = end - subLen;
                multiple = multiple / nums[start] * nums[end];
                if (multiple < k) {
                    res++;
                    flag = true;
                }
                end++;
            }
            if (!flag) return res;//If the pruning does not satisfy all the intervals of the current length, it indicates that the interval with larger length is not satisfied, and the result is returned directly
        }
        return res;
    }
}

Method 2: double pointer

Define the following two pointers L and R. the R pointer starts from the beginning and traverses all the way back. Use a multiple to save the cumulative multiplication result. When the R pointer moves to the right, let the L pointer move to the first position where the total multiple result is less than k. because l is the smallest L, in this interval from L to R, all continuous sub intervals meet the requirements, with a total of r-l sub intervals, Keep r to the right until the end of the whole array, and accumulate the answers that meet the requirements at the same time.

tips: as for L, the rationality of not moving right from 0 every time is that because r moves all the way to the right, the product of [0,r] interval will be larger and larger. At this time, a left pointer l should be introduced. When the [0,r] interval has exceeded the target value, let the left pointer l narrow the search range of the interval. If l is on the left of L obtained by the above method, the interval product at this time must exceed k, so that the answer does not meet the requirements.

Time complexity: the l pointer can move to the end of the array at most, and the complexity is O(n+n)=O(n)

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int res = 0;
        int l = 0, r = 0;
        int multiple = 1;
        while (r < nums.length){
            multiple = multiple * nums[r++];
            while (l < r && multiple >= k) multiple /= nums[l++];
            if (multiple < k) res += r - l;
        }
        return res;
    }
}

209 minimum length subarray

Given an array containing n positive integers and a positive integer target.

Find out the continuous sub array [numsl, numsl + 1,..., numsr-1, numsr] with the smallest length satisfying its sum ≥ target in the array, and return its length. If there is no eligible subarray, 0 is returned.

Method double pointer

Analogy to the previous question, use two pointers L and r. The R pointer traverses backward all the time. Each time it moves, sum is added with num [R]. The L pointer is used to record the maximum left interval pointer that meets the conditions. Each time l moves, sum is subtracted from num [l]. The R pointer moves continuously to the right, and the answer is updated once every cycle to judge whether the conditions are met, and then record the minimum value of r-l.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int res = Integer.MAX_VALUE;
        int l = 0, r = 0, sum = 0;
        while (r < nums.length){
            sum += nums[r++];
            while (l < r){
                if (sum - nums[l] < target) break;
                else sum -= nums[l++];
            }
            if (sum >= target) res = Math.min(res, r - l);
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}