T1 5993. Multiply the found value by 2 

Give you an integer array nums, and give you an integer original, which is the first number to search in nums.

Next, you need to follow the following steps:

If the original is found in nums, multiply the original by 2 to get a new original (that is, make original = 2 * original).
Otherwise, stop the process.
As long as the new original can be found in the array, continue the process for the new original.
Returns the final value of original.

Tips:

• 1 <= nums.length <= 1000
• 1 <= nums[i], original <= 1000

Problem solving idea: we can use HashSet to store the numbers in the array, and then use the contents method of HashSet to judge each time. If it exists, the original will multiply by 2 to continue to judge. If it does not exist, it will directly return to the original.

The code and submission results are as follows:

class Solution {
    public int findFinalValue(int[] nums, int original) {
        HashSet<Integer> set = new HashSet();
        for(int i = 0 ; i < nums.length ; i++){
            set.add(nums[i]);
        }
        while(set.contains(original)){
            original *= 2;
        }
        return original;
    }
}

 

T2 5981. All subscripts with the highest score in the group 

Give you a binary array nums with subscript starting from 0, and the array length is n. Nums can be split into two arrays (possibly empty) by subscript i (0 < = I < = n): numleft and numright.

Numleft contains all elements from subscript 0 to i - 1 in nums (including 0 and i - 1), while numright contains all elements from subscript i to n - 1 in nums (including I and n - 1).
If i == 0, numleft is empty and numright will contain all elements in nums.
If i == n, numleft will contain all elements in nums, and numright is empty.
The grouping score of subscript i is the sum of the number of 0 in numleft and the number of 1 in numright.

Returns all different subscripts with the highest score in the group. You can return answers in any order.

 

 

Tips:

• n == nums.length
• 1 <= n <= 105
• Num [i] is 0 or 1

Problem solving idea: sliding window idea

We can use an index pointer to distinguish the left and right arrays by the position it refers to. When index is equal to 0, the left array is empty. We only need to count the number of elements with the value of 1 in the right array. Then write it down as count.

Create a HashMap < integer, list < integer > >, with key as count and value as array index.

The index pointer moves to the right. If num [index-1] = = 0, it means that the left array has one more 0 and the right array has one less 0 (but the right array will not change due to the lack of one 0). Count + +. If num [index-1] = = 1, it means that the left array has one more 1 (one more left array will not change), and the right array has one less 1 and count --.

In the process of traversal, update the key and value of HashMap.

The code and submission results are as follows:

class Solution {
    public static List<Integer> maxScoreIndices(int[] nums) {
        HashMap<Integer, List<Integer>> res = new HashMap<>();
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == 1){
                count++;
            }
        }
        ArrayList<Integer> list = new ArrayList<>();
        list.add(0);
        res.put(count,list);
        int max = count;
        for(int i = 1 ; i <= nums.length ;i++){
            if(nums[i-1] == 0){
                count++;
            }else{
                count--;
            }
            List<Integer> temp = res.getOrDefault(count, new ArrayList<Integer>());
            temp.add(i);
            res.put(count,temp);

            if(count > max){
                max = count;
            }
        }
        return res.get(max);
    }
}

T3 5994. Find the substring of the given hash value 

Given the integers p ， and m, the hash value of a string ， s ， with a length of k ， and a subscript starting from 0 ， is calculated according to the following function:

hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m.
Where) val(s[i]) represents the subscript of) s[i] in the alphabet, from) val('a') = 1 to) val('z') = 26.

Give you a string ， s ， and integers ， power, modulo, k ， and ， hashValue. Please return the first substring (sub, power, modulo) = = hashValue in s  with the length of k .

The test data guarantees that there must be at least one such substring.

A substring is defined as a sequence of consecutive non empty characters in a string.

 

Tips:

• 1 <= k <= s.length <= 2 * 104
• 1 <= power, modulo <= 109
• 0 <= hashValue < modulo
• s # contains only lowercase English letters.
• The test data ensures that there must be substrings that {meet the conditions.

Solution idea: we can save the k-power of p first to solve the problem of large power. Then slide the window to solve it.

The code and submission results are as follows:

class Solution {
    public static String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        long[] powNum = new long[k];
        power = power % modulo;
        for(int i = 0 ; i < k ; i++){
            if(i==0){
                powNum[i] = 1;
            }else{
                powNum[i] = (powNum[i-1] * power) % modulo;
            }
        }
        for(int l = 0 ; l + k <= s.length(); l++){
            int r = l + k ;
            String sub = s.substring(l,r);
            if(hash(sub,power,modulo,powNum) == hashValue){
                return sub;
            }
        }
        return "";
    }
    private static long hash(String s, int p, int m ,long[] powNum){
        long count = 0;
        for(int i = 0 ; i < s.length() ; i++){
            count += (s.charAt(i)-'a'+1)*powNum[i] % m;
            count %= m;
        }
        return  count % m;
    }
}

T4 didn't write it out

Conclusion: the difficulty is really OK.