模拟题
class Solution {
public:
int findNthDigit(int n) {
long long k=1,c=9,s=1;//k是第几位，c是k位数有几个，s是k位数的起点
while(n>k*c){
n-=k*c;
k++,c*=10,s*=10;
}
s+=(n+k-1)/k-1;//看是k位数里面的第几个数
n=n%k?n%k:k;//看是那个k位数的第几位
return to_string(s)[n-1]-'0';
}
};
floyd
class Solution {
public:
vector<double> calcEquation(vector<vector<string>>& e, vector<double>& v, vector<vector<string>>& q) {
unordered_set<string> vers;
unordered_map<string,unordered_map<string,double>> d;
for(auto i=0;i<e.size();i++){
auto a=e[i][0],b=e[i][1];
auto c=v[i];
d[a][b]=c,d[b][a]=1/c;
vers.insert(a),vers.insert(b);
}
for(auto& k:vers)
for(auto& i:vers)
for(auto& j:vers){
if(d[i][k]&&d[j][k]){
d[i][j]=d[i][k]*d[k][j];
}
}
vector<double> res;
for(auto& c:q){
auto a=c[0],b=c[1];
if(d[a][b]) res.push_back(d[a][b]);
else res.push_back(-1);
}
return res;
}
};
水
class Solution {
public:
unordered_map<int,vector<int>> hash;
Solution(vector<int>& nums) {
for(auto i=0;i<nums.size();i++){
hash[nums[i]].push_back(i);//拉链法
}
}
int pick(int target) {
return hash[target][rand()%hash[target].size()];
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* int param_1 = obj->pick(target);
*/
水
class Solution {
public:
map<long long,int> dp;//防止遍历重复的
int integerReplacement(int n) {
return f(n);
}
long long f(long long n){
if(dp[n]) return dp[n];
if(n==1) return 0;
if(n%2==0) return dp[n]=f(n/2)+1;
return dp[n]=min(f(n+1),f(n-1))+1;
}
};
水，sb题
class Solution {
public:
int maxRotateFunction(vector<int>& nums) {
typedef long long LL;
LL sum=0,cur=0;
for(auto c:nums) sum+=c;//每一行减上一行都得这个和减去一个数
int n=nums.size();
for(int i=0;i<nums.size();i++) cur+=i*nums[i];//第一行是结果的基础
LL res=cur;
for(int i=n-1;i>=0;i--){
cur+=sum-(LL)n*nums[i];
res=max(res,cur);
}
return res;
}
};
双指针
class Solution {
public:
int K;
unordered_map<char,int> cnt;
void add(char c,int& x,int& y){
if(!cnt[c]) x++;
cnt[c]++;
if(cnt[c]==K) y++;
}
void del(char c,int& x,int& y){
if(cnt[c]==K) y--;
cnt[c]--;
if(!cnt[c]) x--;
}
int longestSubstring(string s, int _K) {
K=_K;
int res=0;
for(int k=1;k<=26;k++){//有几个不同的字母
cnt.clear();
for(int i=0,j=0,x=0,y=0;i<s.size();i++){
//i是右，j是左。x是i和j间不同字母的个数，y是满足条件的字母个数。
add(s[i],x,y);
while(x>k) del(s[j++],x,y);
if(x==y) res=max(res,i-j+1);//都满足条件啊
}
}
return res;
}
};
dfs
class Solution {
public:
string decodeString(string s) {
int u=0;
return dfs(s,u);
}
string dfs(string s,int& u){
string res;
while(u<s.size()&&s[u]!=']'){
if(s[u]>='a'&&s[u]<='z'||s[u]>='A'&&s[u]<='Z') res+=s[u++];
else if(s[u]>='0'&&s[u]<='9'){
int k=u;
while(s[k]>='0'&&s[k]<='9') k++;
auto x=stoi(s.substr(u,k-u));
u=k+1;//左括号
auto y=dfs(s,u);
u++;//右括号
while(x--) res+=y;
}
}
return res;
}
};
模拟
class Solution {
public:
int get(int x,int y){
return x>>y&1;
}
bool validUtf8(vector<int>& data) {
for(int i=0;i<data.size();i++){
if(!get(data[i],7)) continue;
int k=0;
while(k<=4&&get(data[i],7-k)) k++;
//第一字节看看开头有几个1
if(k>4||k==1) return false;
for(int j=0;j<k-1;j++){
int t=i+j+1;
if(t>=data.size()) return false;
if(!(get(data[t],7)&&!get(data[t],6))) return false;
//该字符后面的字节
}
i+=k-1;//跳到下一个字符
}
return true;
}
};
水题
class Solution {
public:
bool isSubsequence(string s, string t) {
int k=0;
for(auto c:t){
if(k<s.size()&&c==s[k])
k++;
}
return k==s.size();
}
};
模拟题白给
class Solution {
public:
int lastRemaining(int n) {
if(n==1) return 1;
return 2*(n/2+1-lastRemaining(n/2));
}
};