17.06
二出现的次数-数位dp
把数字转成字符串，用记忆化搜索逐位枚举可能的数字，统计每一位选2时的累计次数，最后返回总次数
class Solution {
public:
int numberOf2sInRange(int n)
{
auto s = to_string(n);
int m = s.length(), dp[m][m];
memset(dp, -1, sizeof(dp));
function<int(int, int, bool)> f = [&](int i, int cnt2, bool is_limit) -> int
{
if (i == m) return cnt2;
if (!is_limit && dp[i][cnt2] >= 0) return dp[i][cnt2];
int res = 0;
for (int d = 0, up = is_limit ? s[i] - '0' : 9; d <= up; ++d) // 枚举要填入的数字 d
res += f(i + 1, cnt2 + (d == 2), is_limit && d == up);
if (!is_limit) dp[i][cnt2] = res;
return res;
};
return f(0, 0, true);
}
};
lcr97
dp[i][j]记s前j个字符凑t前i个字符的子序列数，空t对应1种
字符相等时累加前一匹配数，不等则继承左值，最终得总数量。
class Solution {
//dp:无后效性的记忆化
typedef unsigned long long ull;
public:
int numDistinct(string s, string t)
{
int m = t.size(), n = s.size();
vector<vector<ull>> dp(m + 1, vector<ull>(n + 1, 0));
//t s
// init：当 t 为空时，s 的任何位置都包含 1 个子序列（空序列）
for (int j = 0; j <= n; j++)
dp[0][j] = 1;
s = " " + s; // 调整下标从 1 开始
t = " " + t;
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
dp[i][j] = dp[i][j - 1]; // 默认继承左侧的值（不取 s[j]）
if (s[j] == t[i])
dp[i][j] += dp[i - 1][j - 1]; // 若字符相等，加上取 s[j] 的情况
}
}
return dp[m][n];
}
};
lc2731
碰撞后“交换方向”等价于“机器人穿过对方、身份互换”
机器人可视为无差别，只需计算所有两两对的距离
class Solution {
const int mod = 1e9 + 7;
typedef long long ll;
public:
int sumDistance(vector<int>& nums, string s, int d) {
int n = nums.size();
vector<ll> pos(n);
for (int i = 0; i < n; i++) {
pos[i] = nums[i] + (s[i] == 'R' ? (ll)d : -(ll)d);
}
sort(pos.begin(), pos.end());
ll ret = 0;
ll pre_sum = pos[0] % mod;
for (int i = 1; i < n; i++) {
ll current = ( (ll)i * (pos[i] % mod) ) % mod;
ret = (ret + current - pre_sum+ mod) % mod; // +mod避免负数
pre_sum = (pre_sum + pos[i] % mod) % mod;
}
return ret;
}
};
wa 注意是所有bot dist
class Solution {
const int mod=1e9+7;
public:
int sumDistance(vector<int>& nums, string s, int d)
{
int n=nums.size();
for(int i=0;i<n;i++)
{
int t=d;
if(s[i]=='L') t=-t;
nums[i]+=t;
}
sort(nums.begin(),nums.end());
int ret=0;
for(int i=1;i<n;i++)
{
ret+=abs(nums[i]-nums[i-1]);
}
return ret;
}
};
