------------恢复内容开始------------ 第一题
简单的二分查找
代码语言：javascript复制class Solution {
public:
int findFinalValue(vector<int>& nums, int original) {
sort(nums.begin(), nums.end());
while(find(original, nums) != nums.size())
{
original *= 2;
}
return original;
}
int find(int x, vector<int>& nums)
{
int l = 0;
int r = nums.size()-1;
while(l<=r)
{
int mid = (l r)/2;
if(nums[mid]<x)
{
l = mid 1;
}
else if(nums[mid]>x)
{
r = mid-1;
}
else
{
return mid;
}
}
return nums.size();
}
};第二题
前缀和
代码语言：javascript复制class Solution {
public:
int sum0[100005];
int sum1[100005];
int n;
vector<int> maxScoreIndices(vector<int>& nums) {
n = nums.size();
if(nums[0]==0)
{
sum0[0]=1;
}
else
{
sum1[0]=1;
}
for(int i=1;i<n;i )
{
if(nums[i]==0)
{
sum0[i]=sum0[i-1] 1;
sum1[i]=sum1[i-1];
}
else
{
sum1[i]=sum1[i-1] 1;
sum0[i]=sum0[i-1];
}
}
int ans = max(sum1[n-1], sum0[n-1]);
for(int i=1;i<n;i )
{
ans = max(ans, sum0[i-1] sum1[n-1]-sum1[i-1]);
}
vector<int> res;
if(sum1[n-1]==ans)
{
res.push_back(0);
}
if(sum0[n-1]==ans)
{
res.push_back(n);
}
for(int i=1;i<n;i )
{
if(ans==sum0[i-1] sum1[n-1]-sum1[i-1])
{
res.push_back(i);
}
}
return res;
}
};第三题 O(n)的计算hash值。利用取模运算法则，从后往前先计算k个字符的hash 值， 然后开始向左移动，每次移动都要先减去右边最后一个值，然后再乘以P，最后加上左边的
代码语言：javascript复制class Solution {
public:
long long int num[20005];
long long int num2[20005];
int n;
string subStrHash(string s, int power, int modulo, int k, int hashValue) {
n = s.length();
for(int i=0;i<n;i )
{
num[i]=(s[i]-'a' 1);
}
long long int ans=0;
string res;
num2[0]=1;
for(int i=1;i<k;i )
{
num2[i] = ((power % modulo) * (num2[i-1] %modulo)) %modulo;
}
for(int i=n-1;i>= n-k;i--)
{
res = s[i];
ans = (num[i] * num2[k i - n])%modulo;
ans %= modulo;
}
int pos;
if(ans == hashValue)
{
pos = n-k;
}
for(int i=n-k-1;i>=0;i--)
{
//ans = abs(ans - ((num[i k] * num2[k-1])%modulo));
ans -= (num[i k] * num2[k-1])%modulo;
ans = 2*modulo;
ans %= modulo;
ans *= (power % modulo);
ans %= modulo;
ans = num[i];
ans %= modulo;
if(ans == hashValue)
{
pos = i;
continue;
}
}
res="";
for(int i=pos;i<pos k;i )
{
res =s[i];
}
return res;
}
};第四题
并查集，然后加上位运算异或，直接把两个word做异或运算，会超时。用二叉树来做异或就可以了
代码语言：javascript复制class Solution {
public:
int num[20005];
int f[20005];
map<int, int> m;
struct Node
{
Node* left;
Node* right;
int number;
int tag;
Node(int number)
{
this->left = NULL;
this->right = NULL;
this->number = number;
}
};
vector<int> groupStrings(vector<string>& words) {
for (int i = 0; i < words.size(); i )
{
int x = 0;
for (int j = 0; j < words[i].length(); j )
{
x |= 1 << (words[i][j] - 'a');
}
num[i] = x;
f[i] = i;
}
Node* root = new Node(0);
root->number ;
fun(root, num[0], 1, 0);
for (int i = 1; i < words.size(); i )
{
fun2(root, num[i], 1, 0, 0, i);
root->number ;
fun(root, num[i], 1, i);
}
int ans = 0;
int res = 0;
for (int i = 0; i < words.size(); i )
{
int fx = find(i);
if (m[fx] == 0)
{
ans ;
}
m[fx] ;
res = max(res, m[fx]);
}
vector<int> result;
result.push_back(ans);
result.push_back(res);
return result;
}
void fun(Node* root, int x, int pos, int tag)
{
if (pos == 27)
{
root->tag = tag;
return;
}
int y = x & 1;
if (y == 1)
{
if (root->left == NULL)
{
root->left = new Node(0);
}
root->left->number ;
fun(root->left, x >> 1, pos 1, tag);
}
else
{
if (root->right == NULL)
{
root->right = new Node(0);
}
root->right->number ;
fun(root->right, x >> 1, pos 1, tag);
}
}
void fun2(Node* root, int x, int pos, int diff1, int diff2, int tag)
{
if (diff1 >= 2 || diff2 >= 2)
{
return;
}
if (pos == 27)
{
int fa = find(root->tag);
int fb = find(tag);
f[fb] = fa;
return;
}
int y = x & 1;
if (y == 1)
{
if (root->left != NULL)
{
fun2(root->left, x >> 1, pos 1, diff1, diff2, tag);
}
if (root->right != NULL)
{
fun2(root->right, x >> 1, pos 1, diff1 1, diff2, tag);
}
}
else
{
if (root->left != NULL)
{
fun2(root->left, x >> 1, pos 1, diff1, diff2 1, tag);
}
if (root->right != NULL)
{
fun2(root->right, x >> 1, pos 1, diff1, diff2, tag);
}
}
}
int find(int x)
{
if (f[x] != x)
f[x] = find(f[x]);
return f[x];
}
};
