回溯

lc

lc2121

hash抽象分组后前缀和

注意 这个地方的下标个数统计要-1...

(ll)b[i] * (m - i-1);

class Solution {

typedef long long ll;

public:

vector<long long> getDistances(vector<int>& arr)

{

int n=arr.size();

vector<ll> ret(n);

unordered_map<int,vector<int>> hash;

for(int i=0;i<n;i++)

{

hash[arr[i]].push_back(i);

}

for(auto& [a,b]:hash)

{

int m=b.size();

vector<ll> p(m+1);

for(int i=1;i<=m;i++)

p[i]=p[i-1]+b[i-1];

for(int i=0;i<m;i++)

{

ll f = (ll)b[i] * i - p[i];

ll e = (p[m] - p[i+1]) -(ll)b[i] * (m - i-1);

ret[b[i]] = f + e;

}

}

return ret;

}

};

lc320

优雅的回溯

//缩写

dfs(p + 1, cnt + 1);

//结算 +cnt +p后

dfs(p + 1, 0); // p+1、重置cnt为0

数字串回溯tricks:

if (cnt > 0)

path.erase(path.end() - to_string(cnt).size(), path.end());

class Solution {
public:
vector<string> generateAbbreviations(string word)
{
int n = word.size();
string path;
vector<string> ret;
auto dfs = [&](this auto&& dfs,int p, int cnt)
{
if (p == n) {
if (cnt > 0)
path += to_string(cnt);

ret.push_back(path);

if (cnt > 0) path.erase(path.end() - to_string(cnt).size(), path.end());//回溯
return;
}
//缩写
dfs(p + 1, cnt + 1);

// 结算+保留
if (cnt > 0)
path += to_string(cnt);
path += word[p];

dfs(p + 1, 0); // p+1、重置cnt为0
// 回溯
path.pop_back();
if (cnt > 0) {
path.erase(path.end() - to_string(cnt).size(), path.end());
}
};
dfs(0, 0);
return ret;
}
};