# 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) {
}
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;
// 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();
maxScore = leftScore + rightScore;
}else if(maxScore == leftScore + rightScore){
}
}
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);
}
```

Keywords: leetcode

Added by Cep on Sat, 05 Feb 2022 10:24:25 +0200