2023-02-16:两种颜色的球,蓝色和红色,都按1~n编号,共计2n个, 为方便放在一个数组中,红球编号取负,篮球不变,并打乱顺序, 要求同一种颜色的球按编
2023-03-07 09:41:25 时间
2023-02-16:两种颜色的球,蓝色和红色,都按1~n编号,共计2n个,
为方便放在一个数组中,红球编号取负,篮球不变,并打乱顺序,
要求同一种颜色的球按编号升序排列,可以进行如下操作:
交换相邻两个球,求最少操作次数。
3,-3,1,-4,2,-2,-1,4、
最终交换结果为:
1,2,3,-1,-2,-3,-4,4。
最少交换次数为10,
n <= 1000。
答案2023-02-16:
动态规划,IndexTree。
代码用rust编写。代码如下:
use std::collections::HashMap;
use std::iter::repeat;
fn main() {
let mut arr = vec![3, -3, 1, -4, 2, -2, -1, 4];
println!("{}", min_swaps(&mut arr));
}
// [3,-3,1,-4,2,-2,-1,4]
// -3 -4 -2 -1 -> -1 -2 -3 -4
// 3 1 2 4 -> 1 2 3 4
// 这个题写对数器太麻烦了
// 所以这就是正式解
fn min_swaps(arr: &mut Vec<i32>) -> i32 {
let n = arr.len() as i32;
let mut map: HashMap<i32, i32> = HashMap::new();
let mut top_a = 0;
let mut top_b = 0;
for i in 0..n {
if arr[i as usize] > 0 {
top_a = get_max(top_a, arr[i as usize]);
} else {
top_b = get_max(top_b, abs(arr[i as usize]));
}
map.insert(arr[i as usize], i);
}
let mut it = IndexTree::new(n);
for i in 0..n {
it.add(i, 1);
}
return f(top_a, top_b, &mut it, n - 1, &mut map);
}
// 可以改二维动态规划!
// 因为it的状态,只由topA和topB决定
// 所以it的状态不用作为可变参数!
fn f(top_a: i32, top_b: i32, it: &mut IndexTree, end: i32, map: &mut HashMap<i32, i32>) -> i32 {
if top_a == 0 && top_b == 0 {
return 0;
}
let mut p1 = i32::MAX;
let mut p2 = i32::MAX;
let mut index: i32;
let mut cost: i32;
let mut next: i32;
if top_a != 0 {
index = *map.get(&top_a).unwrap();
cost = it.sum(index, end) - 1;
it.add(index, -1);
next = f(top_a - 1, top_b, it, end, map);
it.add(index, 1);
p1 = cost + next;
}
if top_b != 0 {
index = *map.get(&(-top_b)).unwrap();
cost = it.sum(index, end) - 1;
it.add(index, -1);
next = f(top_a, top_b - 1, it, end, map);
it.add(index, 1);
p2 = cost + next;
}
return get_min(p1, p2);
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}
fn abs(a: i32) -> i32 {
if a < 0 {
-a
} else {
a
}
}
struct IndexTree {
tree: Vec<i32>,
nn: i32,
}
impl IndexTree {
pub fn new(size: i32) -> Self {
Self {
tree: repeat(0).take((size + 1) as usize).collect(),
nn: size,
}
}
pub fn add(&mut self, mut i: i32, v: i32) {
i += 1;
while i <= self.nn {
self.tree[i as usize] += v;
i += i & -i;
}
}
pub fn sum(&mut self, l: i32, r: i32) -> i32 {
return if l == 0 {
self.sum0(r + 1)
} else {
self.sum0(r + 1) - self.sum0(l)
};
}
fn sum0(&mut self, mut index: i32) -> i32 {
let mut ans = 0;
while index > 0 {
ans += self.tree[index as usize];
index -= index & -index;
}
return ans;
}
}
相关文章
- 基于 Amazon Lambda 的无服务器视频转码方案
- Karpenter : 新一代 Kubernetes auto scaling 工具
- 使用Kubeadm在亚马逊云科技国内区域自建Kubernetes集群 (一) 自建Kubernetes集群和挂载持久化存储
- 通过 Amazon CloudFront 实时日志快速构建自定义的 CDN 监控
- 在多账户场景下将 Amazon WAF 安全自动化解决方案与 Amazon Firewall Manager 结合使用
- 静态属性 java_java静态属性初始化注意
- 使用 Amazon WAF 进行 Captcha人机验证
- 扩展 Amazon SageMaker PyTorch 容器
- 全面的技能培养加快云成果的实现
- Amazon EKS 版本管理策略与升级流程
- 基于 Amazon SageMaker 利用 MONAI 处理医疗影像数据最佳实践
- java treeset_java基础教程案例:[8]Treeset
- 基于Alphafold2一键构建云上高可用蛋白质结构预测平台
- 亚马逊云科技 X-Ray 请求追踪与故障排查实践
- Gamelift 敏捷开发与实时日志监控解决方案
- 构建 ElastiCache for Redis Cluster 代理服务集群(下篇)
- 构建 ElastiCache for Redis Cluster 代理服务集群(上篇)
- 利用 Amazon HPC 加速药物研发分子对接任务
- EKS 使用Spot 实例最佳实践
- 使用Amazon Glue构建无服务器流式ETL作业