# 2154. 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.

Solution idea: use the hash table to record the elements in the array, and directly look up the specified finger in the hash table until the final value is found

public int findFinalValue(int[] nums, int original) { HashSet<Integer> map = new HashSet<>(); for (int num : nums) { map.add(num); } while(map.contains(original)){ original = original * 2; } return original; }

# 2155. 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.

Example: Input: nums = [0,0,1,0] Output:[2,4] Explanation: group by subscript - 0 : numsleft by [] . numsright by [0,0,1,0] . Score 0 + 1 = 1 . - 1 : numsleft by [0] . numsright by [0,1,0] . Score 1 + 1 = 2 . - 2 : numsleft by [0,0] . numsright by [1,0] . Score 2 + 1 = 3 . - 3 : numsleft by [0,0,1] . numsright by [0] . Score 2 + 0 = 2 . - 4 : numsleft by [0,0,1,0] . numsright by [] . The score is 3 + 0 = 3 . Subscripts 2 and 4 can get the highest grouping score 3. Attention, the answer [4,2] It is also regarded as the correct answer.

Solution idea: first find the score when i is 0, and then traverse all positions in turn on this basis.

public List<Integer> maxScoreIndices(int[] nums) { List<Integer> ans = new ArrayList<>(); int maxScore; // Find the fraction when i is 0 int leftScore = 0,rightScore = 0; for (int num : nums) { rightScore += num; } maxScore = rightScore; ans.add(0); // Find out other positions in turn for(int i = 1;i <= nums.length; i++){ if(nums[i-1] == 0){ leftScore++; }else{ rightScore--; } // Find the maximum score and its corresponding subscript position if(maxScore < leftScore + rightScore){ ans.clear(); ans.add(i); maxScore = leftScore + rightScore; }else if(maxScore == leftScore + rightScore){ ans.add(i); } } return ans; }

# 2156. Find the substring of the given hash value

Given the integers p and m, the hash value of a string s with length k and 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 with length k in s, which satisfies hash (sub, power, module) = = hashValue.

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.

Example:

Input: s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32 Output:"fbx" Explanation:"fbx" The hash value of is hash("fbx", 31, 100) = (6 * 1 + 2 * 31 + 24 * 312) mod 100 = 23132 mod 100 = 32 . "bxz" The hash value of is hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 312) mod 100 = 25732 mod 100 = 32 . "fbx" Is the first substring of length 3 with a hash value of 32, so we return "fbx" . be careful,"bxz" The hash value of is also 32, but it is smaller in the string "fbx" Later.

Method 1: violent solution, sliding window.

public String subStrHash(String s, int power, int modulo, int k, int hashValue) { long[] poweri = new long[k]; // Calculate the power from 0 power to k-1 power and store it poweri[0] = 1; for(int i = 1;i < k;i++){ poweri[i] = poweri[i-1]*power; poweri[i] %= modulo; } int left = 0; int right = k; // Slide the window forward while(right <= s.length()){ long val = 0; int pi = 0; for(int i = left;i < right;i++){ val += (s.charAt(i)-'a' + 1) * poweri[pi++]; val %= modulo; } // Find the corresponding string and jump out of the loop if(val == hashValue){ break; } left++; right++; } // Returns the string found return s.substring(left,right); }