Leetcode每日一题 —— 2615. 等值距离和
- 内容介绍
- 文章标签
- 相关推荐
2615. 等值距离和 - 力扣（LeetCode）
2615. 等值距离和 - 给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ，arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ，则令 arr[i] 等于 0 。 返回数组 arr 。 示例 1： 输入：nums = [1,3,1,1,2] 输出：[5,0,3,4,0] 解释： i = 0 ，nums[0] == nums[2]...
思路
也就是对于每个下标 i 对应的数字 nums[i]，要找到与其相等的所有其他数字 nums[j]，累加 abs(i-j)。
题目输入规模可能很大，时间复杂度要控制在 O(n\log n) 以下。
咱们在意的是某个数字 nums[i] 在数组内出现的所有下标，但如果直接按数字分组维护列表，扫描所耗费的时间从总体上看来是难以接受的。
既要涉及求和，而且还需要尽量是线性时间复杂度，能猜到可能能用到前缀和思想。
对于一个下标 i，我可以计算前缀中所有 i-j 之和，再计算其后缀中所有 j-i 之和，这个位置的前缀加后缀就是最终结果 arr[i] 了。
怎么生成这样的前缀和呢？从计算某个位置的前缀 prefix[i] 来思考：
比如
[1,3,1,1,1,2]这个数组，若要计算prefix[4]
- 首先
nums[4]=1，要从上一个前缀和处转移过来，我们可以用哈希表存上一个1出现的地方：3 prefix[4]可转移自prefix[3]，但是怎么从prefix[3]计算出prefix[4]？prefix[3]等于(3-0) + (3-2)。而prefix[4]则等于(4-0) + (4-2) + (4-3)，如果把prefix[3]的部分代入进去可以发现是prefix[3] + (4-3) + (4-3) + (4-3)，也就是在prefix[3]的基础上重复累加离上一个1出现的位置的距离多次。很显然这个次数就是1之前出现的次数。
因此在递推的时候可以用哈希表维护 nums[i] 上一次出现的下标以及 nums[i] 之前出现过的次数。递推得到前缀和和后缀和即可。
代码
写出来感觉还是挺直白的，应该还有很大可优化空间。
class Solution {
public:
vector<long long> distance(vector<int>& nums) {
int n=nums.size();
vector<long long> res(n,0);
// 也就是要找到所有相等元素的下标距离的和
// 输入规模比较大，可以分组做前缀和后缀和
vector<long long> prefix(n,0);
// 某个数字 -> (其最后一次出现的下标, 这个数字出现的次数)
unordered_map<int,pair<int,int>> iMap;
for(int i=0;i<n;i++){
int appearCnt=0;
if(iMap.count(nums[i])>0){
// 之前这个数字出现过
// 比如 1 ... 1 1
// 第三次出现的 1 的和前缀相当于 [前两个 1 的距离] + [第三次 1 和第二次 1 的距离] * [前面 1 出现的次数 = 2]
int prevIdx=iMap[nums[i]].first;
appearCnt=iMap[nums[i]].second;
prefix[i]=prefix[prevIdx]+(i-prevIdx)*appearCnt;
// cout<<"prefix["<<i<<"]="<<prefix[i]<<endl;
}
iMap[nums[i]]=make_pair(i,appearCnt+1);
}
// 接着边生成后缀边得到结果
vector<long long> postfix(n,0);
iMap.clear();
for(int i=n-1;i>=0;i--){
int appearCnt=0;
if(iMap.count(nums[i])>0){
int prevIdx=iMap[nums[i]].first;
appearCnt=iMap[nums[i]].second;
postfix[i]=postfix[prevIdx]+(prevIdx-i)*appearCnt;
}
res[i]=prefix[i]+postfix[i];
iMap[nums[i]]=make_pair(i,appearCnt+1);
}
return res;
}
};
继续复习一些题
139. 单词拆分 - 力扣（LeetCode）
- 注意内层递推的写法，不能在没有判断的情况下直接继承前一个状态，因为在枚举单词，后面的单词如果不匹配后缀，可能会覆盖掉可能的结果。
func wordBreak(s string, wordDict []string) bool {
// 一维动态规划题
// dp[i] 定义为 i 之前的 s[0...i-1] 子串是否能被 wordDict 拼出
// 这类动态规划题好像很适合让下标从 1 开始，把 0 位置作为哨兵，方便边界处理
n:=len(s)
dp:=make([]bool,n+1)
// 显然 dp[0]=true
dp[0]=true
for i:=1;i<=n;i++{
// 枚举每个单词的出现情况
for _,w:=range wordDict{
if i<len(w){
// 单词过长，跳过
continue;
}
// 否则看是否能当前单词拼接
// 👇 错误写法，前面单词能匹配后缀，但如果后面枚举的单词不匹配，会覆盖掉！
// if s[i-len(w):i]==w {
// dp[i]=dp[i-len(w)]
// }
if s[i-len(w):i]==w && dp[i-len(w)] {
dp[i]=true
}
}
}
return dp[n]
}
--【壹】--：
class Solution:
def distance(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [0] * n
dic = {}
for i, x in enumerate(nums):
if x not in dic:
dic[x] = []
dic[x].append(i)
for x in dic:
idx = dic[x]
m = len(idx)
tot = 0
for i in range(m):
tot += idx[i] - idx[0]
ans[idx[0]] = tot
for i in range(1, m):
tot += (2 * i - m) * (idx[i] - idx[i - 1])
ans[idx[i]] = tot
return ans
--【贰】--：
buildIM :: [Int] -> IM.IntMap ([Int], Int, Int)
buildIM =
let update !i (is, !s, !c) = let !s' = s + i; !c' = c + 1 in (i : is, s', c')
updateMap m (i, x) = IM.alter (Just . maybe (one i, i, 1) (update i)) x m
in foldl' updateMap mempty . zip [0 ..]
calcDist :: ([Int], Int, Int) -> [(Int, Int)]
calcDist ([], _, _) = []
calcDist (nums', s, n) =
let nums = reverse nums'
initVal = s - n * fromMaybe 0 (viaNonEmpty head nums)
diffs = zipWith (-) (fromMaybe [] (viaNonEmpty tail nums)) nums
multipliers = [i - n | i <- [2, 4 ..]]
in zip nums (scanl' (+) initVal (zipWith (*) multipliers diffs))
distances :: [Int] -> [Int]
distances nums =
let im = buildIM nums
n = length nums
distList = concatMap calcDist (IM.elems im)
arr = Arr.accumArray (const id) 0 (0, n - 1) distList
in Arr.elems arr
手动做了一下融合捏。
推的是 v_0 = S - na_0，且 v_k = v_{k-1} + (2k-n)(a_k-a_{k-1})，全用差分也可以推但是写起来太恶心了就算了吧
leftDistances :: [Int] -> [Int]
leftDistances = go 0 mempty
where
go _ _ [] = []
go i m (x : xs) =
let (c, s) = IM.findWithDefault (0, 0) x m
!c' = c + 1
!s' = s + i
!m' = IM.insert x (c', s') m
in (c * i - s) : go (i + 1) m' xs
distances' :: [Int] -> [Int]
distances' nums =
zipWith (+) (leftDistances nums) (reverse (leftDistances (reverse nums)))
如果把分组和计算过程手动融合就可以只算左边的距离（什么手写状态机？），再倒过来算一次右边的加上就行
--【叁】--：
简单排序后是个简单数学题，但是我数学不好心态浮躁，一个公式捣鼓了半天也没像到一个巧妙的表达。公式没有化简,意义应该挺直白的. 好在跑的挺快的.小坑在一开始想回避但也没回避到的:存在等值且最大时最后一次循环不更新答案,在最后塞一个不存在的最大值就行了.其他语言有空补.
class Solution {
public:
vector<long long> distance(vector<int>& nums) {
int n = nums.size();
std::vector<std::pair<int,int>> v(n,std::pair<int,int>());
std::vector<long long> res(n,0ll);
for(int i = 0; i < n; i++) {
v[i] = std::make_pair(nums[i],i);
}
std::sort(v.begin(),v.end(),[](const pair<int,int>& a, const pair<int,int>& b) -> bool {
if(a.first != b.first) {
return a.first < b.first;
}
return a.second < b.second;
});
v.push_back(std::make_pair(1e6,n + 1));
long long sum = v[0].second;
for(int i = 1,j = 0; i < n + 1; i++) {
if(v[i].first != v[i - 1].first) {
int l = j,r = i - 1;
long long presum = 0ll;
while(j < i) {
long long base = v[j].second;
res[v[j].second] = sum - base * (r - j + 1) + base * (j - l) - presum * 2;
presum += base;
j++;
}
sum = 0;
}
sum += v[i].second;
}
return res;
}
};
go 的类型很严格噢, 不统一就会错.
然后它的sort 参数好像是下标,不让动
type Num struct {
val int
id int
}
func distance(nums []int) []int64 {
n := len(nums)
res := make([]int64,n)
v := make([]Num,n)
for i := 0; i < n; i++ {
v[i].val = nums[i]
v[i].id = i
}
sort.Slice(v, func(i, j int) bool {
if v[i].val != v[j].val {
return v[i].val < v[j].val
}
return v[i].id < v[j].id
})
v = append(v,Num{1e6,n + 1})
var sum int64 = int64(v[0].id)
for i, j := 1, 0; i < n + 1; i++ {
if v[i].val != v[i - 1].val {
l, r := j, i - 1
var psum int64 = 0
for j < i {
var base int64 = int64(v[j].id)
res[v[j].id] = sum - base * int64(r - j + 1) + base * int64(j - l) - 2 * psum
psum += base
j++
}
sum = 0
}
sum += int64(v[i].id)
}
return res
}
python 用下数组得了.但是跑的挺慢的, 语法不熟.
class Solution:
def distance(self, nums: List[int]) -> List[int]:
n = len(nums)
v = [[0,0] for _ in range(n)]
res = [0 for _ in range(n)]
for i in range(n):
v[i][0],v[i][1] = nums[i],i
v.sort(key = lambda x: (x[0],x[1]))
v.append([1e6,n + 1])
sum = 0
j = 0
for i in range(n + 1):
if v[i][0] != v[i - 1][0]:
l, r = j, i - 1
psum = 0
while j < i:
base = v[j][1]
res[v[j][1]] = sum - base * (r - j + 1) + base * (j - l) - 2 * psum
j += 1
psum += base
sum = 0
sum += v[i][1]
return res
2615. 等值距离和 - 力扣（LeetCode）
2615. 等值距离和 - 给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ，arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ，则令 arr[i] 等于 0 。 返回数组 arr 。 示例 1： 输入：nums = [1,3,1,1,2] 输出：[5,0,3,4,0] 解释： i = 0 ，nums[0] == nums[2]...
思路
也就是对于每个下标 i 对应的数字 nums[i]，要找到与其相等的所有其他数字 nums[j]，累加 abs(i-j)。
题目输入规模可能很大，时间复杂度要控制在 O(n\log n) 以下。
咱们在意的是某个数字 nums[i] 在数组内出现的所有下标，但如果直接按数字分组维护列表，扫描所耗费的时间从总体上看来是难以接受的。
既要涉及求和，而且还需要尽量是线性时间复杂度，能猜到可能能用到前缀和思想。
对于一个下标 i，我可以计算前缀中所有 i-j 之和，再计算其后缀中所有 j-i 之和，这个位置的前缀加后缀就是最终结果 arr[i] 了。
怎么生成这样的前缀和呢？从计算某个位置的前缀 prefix[i] 来思考：
比如
[1,3,1,1,1,2]这个数组，若要计算prefix[4]
- 首先
nums[4]=1，要从上一个前缀和处转移过来，我们可以用哈希表存上一个1出现的地方：3 prefix[4]可转移自prefix[3]，但是怎么从prefix[3]计算出prefix[4]？prefix[3]等于(3-0) + (3-2)。而prefix[4]则等于(4-0) + (4-2) + (4-3)，如果把prefix[3]的部分代入进去可以发现是prefix[3] + (4-3) + (4-3) + (4-3)，也就是在prefix[3]的基础上重复累加离上一个1出现的位置的距离多次。很显然这个次数就是1之前出现的次数。
因此在递推的时候可以用哈希表维护 nums[i] 上一次出现的下标以及 nums[i] 之前出现过的次数。递推得到前缀和和后缀和即可。
代码
写出来感觉还是挺直白的，应该还有很大可优化空间。
class Solution {
public:
vector<long long> distance(vector<int>& nums) {
int n=nums.size();
vector<long long> res(n,0);
// 也就是要找到所有相等元素的下标距离的和
// 输入规模比较大，可以分组做前缀和后缀和
vector<long long> prefix(n,0);
// 某个数字 -> (其最后一次出现的下标, 这个数字出现的次数)
unordered_map<int,pair<int,int>> iMap;
for(int i=0;i<n;i++){
int appearCnt=0;
if(iMap.count(nums[i])>0){
// 之前这个数字出现过
// 比如 1 ... 1 1
// 第三次出现的 1 的和前缀相当于 [前两个 1 的距离] + [第三次 1 和第二次 1 的距离] * [前面 1 出现的次数 = 2]
int prevIdx=iMap[nums[i]].first;
appearCnt=iMap[nums[i]].second;
prefix[i]=prefix[prevIdx]+(i-prevIdx)*appearCnt;
// cout<<"prefix["<<i<<"]="<<prefix[i]<<endl;
}
iMap[nums[i]]=make_pair(i,appearCnt+1);
}
// 接着边生成后缀边得到结果
vector<long long> postfix(n,0);
iMap.clear();
for(int i=n-1;i>=0;i--){
int appearCnt=0;
if(iMap.count(nums[i])>0){
int prevIdx=iMap[nums[i]].first;
appearCnt=iMap[nums[i]].second;
postfix[i]=postfix[prevIdx]+(prevIdx-i)*appearCnt;
}
res[i]=prefix[i]+postfix[i];
iMap[nums[i]]=make_pair(i,appearCnt+1);
}
return res;
}
};
继续复习一些题
139. 单词拆分 - 力扣（LeetCode）
- 注意内层递推的写法，不能在没有判断的情况下直接继承前一个状态，因为在枚举单词，后面的单词如果不匹配后缀，可能会覆盖掉可能的结果。
func wordBreak(s string, wordDict []string) bool {
// 一维动态规划题
// dp[i] 定义为 i 之前的 s[0...i-1] 子串是否能被 wordDict 拼出
// 这类动态规划题好像很适合让下标从 1 开始，把 0 位置作为哨兵，方便边界处理
n:=len(s)
dp:=make([]bool,n+1)
// 显然 dp[0]=true
dp[0]=true
for i:=1;i<=n;i++{
// 枚举每个单词的出现情况
for _,w:=range wordDict{
if i<len(w){
// 单词过长，跳过
continue;
}
// 否则看是否能当前单词拼接
// 👇 错误写法，前面单词能匹配后缀，但如果后面枚举的单词不匹配，会覆盖掉！
// if s[i-len(w):i]==w {
// dp[i]=dp[i-len(w)]
// }
if s[i-len(w):i]==w && dp[i-len(w)] {
dp[i]=true
}
}
}
return dp[n]
}
--【壹】--：
class Solution:
def distance(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [0] * n
dic = {}
for i, x in enumerate(nums):
if x not in dic:
dic[x] = []
dic[x].append(i)
for x in dic:
idx = dic[x]
m = len(idx)
tot = 0
for i in range(m):
tot += idx[i] - idx[0]
ans[idx[0]] = tot
for i in range(1, m):
tot += (2 * i - m) * (idx[i] - idx[i - 1])
ans[idx[i]] = tot
return ans
--【贰】--：
buildIM :: [Int] -> IM.IntMap ([Int], Int, Int)
buildIM =
let update !i (is, !s, !c) = let !s' = s + i; !c' = c + 1 in (i : is, s', c')
updateMap m (i, x) = IM.alter (Just . maybe (one i, i, 1) (update i)) x m
in foldl' updateMap mempty . zip [0 ..]
calcDist :: ([Int], Int, Int) -> [(Int, Int)]
calcDist ([], _, _) = []
calcDist (nums', s, n) =
let nums = reverse nums'
initVal = s - n * fromMaybe 0 (viaNonEmpty head nums)
diffs = zipWith (-) (fromMaybe [] (viaNonEmpty tail nums)) nums
multipliers = [i - n | i <- [2, 4 ..]]
in zip nums (scanl' (+) initVal (zipWith (*) multipliers diffs))
distances :: [Int] -> [Int]
distances nums =
let im = buildIM nums
n = length nums
distList = concatMap calcDist (IM.elems im)
arr = Arr.accumArray (const id) 0 (0, n - 1) distList
in Arr.elems arr
手动做了一下融合捏。
推的是 v_0 = S - na_0，且 v_k = v_{k-1} + (2k-n)(a_k-a_{k-1})，全用差分也可以推但是写起来太恶心了就算了吧
leftDistances :: [Int] -> [Int]
leftDistances = go 0 mempty
where
go _ _ [] = []
go i m (x : xs) =
let (c, s) = IM.findWithDefault (0, 0) x m
!c' = c + 1
!s' = s + i
!m' = IM.insert x (c', s') m
in (c * i - s) : go (i + 1) m' xs
distances' :: [Int] -> [Int]
distances' nums =
zipWith (+) (leftDistances nums) (reverse (leftDistances (reverse nums)))
如果把分组和计算过程手动融合就可以只算左边的距离（什么手写状态机？），再倒过来算一次右边的加上就行
--【叁】--：
简单排序后是个简单数学题，但是我数学不好心态浮躁，一个公式捣鼓了半天也没像到一个巧妙的表达。公式没有化简,意义应该挺直白的. 好在跑的挺快的.小坑在一开始想回避但也没回避到的:存在等值且最大时最后一次循环不更新答案,在最后塞一个不存在的最大值就行了.其他语言有空补.
class Solution {
public:
vector<long long> distance(vector<int>& nums) {
int n = nums.size();
std::vector<std::pair<int,int>> v(n,std::pair<int,int>());
std::vector<long long> res(n,0ll);
for(int i = 0; i < n; i++) {
v[i] = std::make_pair(nums[i],i);
}
std::sort(v.begin(),v.end(),[](const pair<int,int>& a, const pair<int,int>& b) -> bool {
if(a.first != b.first) {
return a.first < b.first;
}
return a.second < b.second;
});
v.push_back(std::make_pair(1e6,n + 1));
long long sum = v[0].second;
for(int i = 1,j = 0; i < n + 1; i++) {
if(v[i].first != v[i - 1].first) {
int l = j,r = i - 1;
long long presum = 0ll;
while(j < i) {
long long base = v[j].second;
res[v[j].second] = sum - base * (r - j + 1) + base * (j - l) - presum * 2;
presum += base;
j++;
}
sum = 0;
}
sum += v[i].second;
}
return res;
}
};
go 的类型很严格噢, 不统一就会错.
然后它的sort 参数好像是下标,不让动
type Num struct {
val int
id int
}
func distance(nums []int) []int64 {
n := len(nums)
res := make([]int64,n)
v := make([]Num,n)
for i := 0; i < n; i++ {
v[i].val = nums[i]
v[i].id = i
}
sort.Slice(v, func(i, j int) bool {
if v[i].val != v[j].val {
return v[i].val < v[j].val
}
return v[i].id < v[j].id
})
v = append(v,Num{1e6,n + 1})
var sum int64 = int64(v[0].id)
for i, j := 1, 0; i < n + 1; i++ {
if v[i].val != v[i - 1].val {
l, r := j, i - 1
var psum int64 = 0
for j < i {
var base int64 = int64(v[j].id)
res[v[j].id] = sum - base * int64(r - j + 1) + base * int64(j - l) - 2 * psum
psum += base
j++
}
sum = 0
}
sum += int64(v[i].id)
}
return res
}
python 用下数组得了.但是跑的挺慢的, 语法不熟.
class Solution:
def distance(self, nums: List[int]) -> List[int]:
n = len(nums)
v = [[0,0] for _ in range(n)]
res = [0 for _ in range(n)]
for i in range(n):
v[i][0],v[i][1] = nums[i],i
v.sort(key = lambda x: (x[0],x[1]))
v.append([1e6,n + 1])
sum = 0
j = 0
for i in range(n + 1):
if v[i][0] != v[i - 1][0]:
l, r = j, i - 1
psum = 0
while j < i:
base = v[j][1]
res[v[j][1]] = sum - base * (r - j + 1) + base * (j - l) - 2 * psum
j += 1
psum += base
sum = 0
sum += v[i][1]
return res