⭐ New pit in winter vacation -- daily question notes of code Fox
5993. Multiply the value found by 2-week question 1
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**
The final return value of original.
class Solution {
public int findFinalValue(int[] nums, int original) {
Arrays.sort(nums);
for(int i:nums){
if(original==i){
original*=2;
}
}
return original;
}
}
5981. All subscripts with the highest score in the group - weekly question 2
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 * * (including * * 0 and i - 1) from subscript 0 to i - 1 in nums, while numright contains all elements * * (including * * I and n - 1) from subscript i to n - 1 in nums.
- 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.
class Solution {
public List<Integer> maxScoreIndices(int[] nums) {
List<Integer> list=new ArrayList<>();
for(int i=1;i<nums.length;i++){
nums[i]+=nums[i-1];
}
int max=0;
for(int i=0;i<=nums.length;i++){
int mid=(i>0?(i-nums[i-1]+nums[nums.length-1]-nums[i-1]):nums[nums.length-1]);
if(max<mid){
list=new ArrayList<>();
list.add(i);
max=mid;
}
else if(max==mid){
list.add(i);
}
}
return list;
}
}
5994. Find the substring of the given hash value - Mid - weekly question 3
Title Description:
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.
Problem solving ideas:
The correct solution to this problem is to use the sliding window to find the increase and decrease law of hash value of each sliding window, slide from back to front, delete the added value of the last letter each time, uniformly multiply the remaining value by power (equivalent to the added value of the position, and then move one bit), and then add a new value
Code implementation:
//This problem is not implemented by myself. Only part of the code is added for understanding
//brute force
class Solution {
public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
long[] pows = new long[k];
pows[0] = 1;
for (int i = 1; i < k; i++) {
pows[i] = pows[i - 1] * power % modulo;
}
for (int i = 0; i <= s.length() - k; i++) {
String subStr = s.substring(i, i + k);
if (val(subStr, pows, modulo) == hashValue) {
return subStr;
}
}
return "";
}
private int val(String subStr, long[] pows, int modulo) {
long res = 0;
for (int i = 0; i < subStr.length(); i++) {
res += (subStr.charAt(i) - 'a' + 1) * pows[i];
res %= modulo;
}
return (int) (res % modulo);
}
}
//Slide the window from back to front, using mathematical laws
class Solution {
public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
char[] str = s.toCharArray();
int n = str.length;
long x = 0, b = 1;
String ans = null;
//The hash value of the last k-long substring is calculated from the back to the front
for (int i = 0; i < k; i++) {
char ch = str[n - 1 - i];
x = (x * power + ch - 'a' + 1) % modulo;
}
if (x == hashValue)
ans = s.substring(n - k);
//Calculate pow(power,k-1)%modulo to be used
for (int i = 0; i < k - 1; i++)
b = b * power % modulo;
//Back one at a time, subtract the value of the last letter (b * (STR [i + k] - [a '+ 1), multiply the remaining value by power, and add the value of one letter entered forward
for (int i = n - k - 1; i >= 0; i--) {
x = (x + modulo - (b * (str[i + k] - 'a' + 1) % modulo)) % modulo;
char ch = str[i];
x = (x * power + ch - 'a' + 1) % modulo;
if (x == hashValue)
ans = s.substring(i, i + k);
}
return ans;
}
}
5995. String grouping - Hard - weekly question 4
Title Description:
Give you a string array words with subscript starting from 0. Each string contains only lowercase English letters. In any substring of words, each letter appears at most once.
If we can get the letter set of s2 from the letter set of s1 through one of the following operations, we call the two strings associative:
- Add a letter to the letter set of s1.
- Delete a letter from the letter set of s1.
- Replace one letter in s1 with any other letter (or replace it with the letter itself).
The array words can be divided into one or more groups without intersection. A string and a group belong to this group if any of the following conditions are met:
- It is associated with at least one other string within the group.
- It is the only string in this group.
Note that you need to ensure that after grouping, any string in one group is not associated with the strings of other groups. It can be proved that the grouping scheme is unique under this condition.
Please return an array ans with a length of 2:
- ans[0] is the total number of words groups.
- ans[1] is the number of strings contained in the group with the largest number of strings.
Problem solving ideas:
Preprocessing: according to the requirements of the topic, 26 bits can be used to save the string status, and Map can be used to save the string status and number
Use depth first, extract one group at a time - specific method
- Get a string from the Map, store it in the List, remove the string from the Map, the number of groups + 1, and the initial number of the group is the number of strings
- As long as the List is not empty, remove the header for use every time, and find all the strings in the Map that can be obtained by the deformation of the header
- Each time a string is found, it is removed from the Map, added to the List, and the counter in the group increases the number of strings
See the following for specific methods:
Code implementation:
class Solution {
public int[] groupStrings(String[] words) {
//Bit operation pre stored array
int[] j=new int[27];
for(int i=0;i<=26;i++){
j[i]=1<<i;
}
//oMap saves the initial string array information
Map<Integer,Integer> oMap=new HashMap<>();
for(String i:words){
//Use StoInt to represent a String with non repeated lowercase letters as an int type of the letter with a 1 on the bit
int mid=StoInt(i);
oMap.put(mid,oMap.getOrDefault(mid,0)+1);
}
//count is the number of groups, and max is the current maximum number of groups
int count=0;
int max=0;
while(!oMap.isEmpty()){
int midc=0;
List<Integer> list=new ArrayList<>();
//Get an element from the Map, remove it, and initialize the quantity in the group
for(Map.Entry<Integer,Integer> e:oMap.entrySet()){
list.add(e.getKey());
midc+=e.getValue();
break;
}
oMap.remove(list.get(0));
//Loop until all members of the group in the oMap are found
while(!list.isEmpty()){
int mid=list.get(0);
list.remove(0);
//Increase or decrease deformation, and reverse 1 bit each time
for(int i:j){
int mid_i=mid^i;
if(oMap.get(mid_i)!=null){
midc+=oMap.get(mid_i);
list.add(mid_i);
oMap.remove(mid_i);
}
}
//Character conversion deformation, inverting 1 each time, and then inverting a 0
for(int i:j){
if((mid&i)>0){
for(int k:j){
if((mid&k)==0){
int mid_i=mid^i^k;
if(oMap.get(mid_i)!=null){
midc+=oMap.get(mid_i);
list.add(mid_i);
oMap.remove(mid_i);
}
}
}
}
}
}
//If the element in the group is greater than the current max
if(midc>max){
max=midc;
}
//Grouping + 1
count++;
}
return new int[]{count,max};
}
int StoInt(String s){
int res=0;
for(int i=0;i<s.length();i++){
res|=(1<<(int)(s.charAt(i)-'a'+1));
}
return res;
}
}
ending
Title Source: LeetCode link: https://leetcode-cn.com/problems
⭐ Pay attention to the author, take you to brush the questions, and learn the most commonly used algorithm skills from simple algorithm questions (one question per day in winter vacation)
⭐ Pay attention to the author's problem brushing - simple to advanced, which makes you unknowingly become a ruthless problem brushing machine. Please send a private letter if you have any questions