LeetCode
1518.换水问题
题目
超市正在促销，你可以用 numExchange 个空水瓶从超市兑换一瓶水。最开始，你一共购入了 numBottles 瓶水。
如果喝掉了水瓶中的水，那么水瓶就会变成空的。
给你两个整数 numBottles 和 numExchange ，返回你 最多 可以喝到多少瓶水。
解析
其实这个问题有点像游戏抽奖 我花x块钱抽奖 每抽y块钱返还我z块钱 我一共能抽多少次
我们可以注意到 你能换的空瓶的数量是可计算的
每喝m瓶水,获得m个瓶子,可兑换m / numExchange个水,然后剩下m / numExchange + m % numExhange瓶水,直到剩下的瓶子<numExchange时不能兑换.
所以我们发现这是个递归问题 当然也一个循环解决
我们发现兑换后的空瓶子 = 空瓶子 / numExchange + 空瓶子 % numExchange
然后再用兑换后的空瓶子去重复这个过程
于是我们得到
/// 计算可以兑换的水的数量
fn calculate_empty(exchange: usize,empty: usize) -> usize {
if empty < exchange {return 0;} // 当空瓶子 < 交换数量时 返回0
let water = empty / exchange; // 此轮兑换的水数量
let empty = water + empty % exchange; // 这一轮剩下的空瓶子
return water + caculate_empty(exchange,empty); // 这一轮换的水 + 下一轮换的水
}
我们其实也可以通过外部变量把递归改成循环
fn exchange_water(exchange: usize,waters: usize) -> usize{
let mut waters: usize = waters.clone(); // 目前换的水的数量
let mut empty: usize = waters.clone(); // 目前空瓶子数量
while empty >= exchange { // 当空瓶子还能换时继续换
let new = empty / exchange; // 这一轮能换的水数量
waters += new; // 累加上去
empty = new + empty % exchange; // 空瓶子数量更新
}
return waters;
}
2221.数组的三角和
题目
给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是 0 到 9 之间（两者都包含）的一个数字。
nums 的 三角和 是执行以下操作以后最后剩下元素的值：
nums 初始包含 n 个元素。如果 n == 1 ，终止 操作。否则，创建 一个新的下标从 0 开始的长度为 n - 1 的整数数组 newNums 。
对于满足 0 <= i < n - 1 的下标 i ，newNums[i] 赋值 为 (nums[i] + nums[i+1]) % 10 ，% 表示取余运算。
将 newNums 替换 数组 nums 。
从步骤 1 开始 重复 整个过程。
请你返回 nums 的三角和。
解析
事实上 这其实就是差分 然后差分到n-1阶而已. 我们可以根据n阶差分的公式直接得到结果.
但是我们仍旧从朴素的方法开始
我们可以用队列来解决这个问题: 1,2,3,4,5
先加入1 然后加入2, 相加后弹出1, 然后入队3. 然后一直到5,5后面没有元素入队便结束
我们可确定两点 1. 只用处理n-1次差分 2. 一次差分需处理 len -1 次
于是我们得到了双端队列解法
fn sanjiaohe(array: Vec<i32>) -> i32 {
let mut deque = VecDeque::from(array);
let len = deque.len();
for i in 0..len-1 { // 要处理n-1层
let deque_len = len - i; // 这一层的元素长度
for j in 0..deque_len-1 { // 这一层的元素要处理的次数len -1
let a = deque.pop_front().unwrap(); // 先把头弹出
deque.push_back((a + deque[0]) % 10); // 把加好后的入队到队尾
}
deque.pop_front(); // 每层处理后队头会多出一个元素 弹出它
}
deque[0]
}
但是我们会发现这个解法用了额外的空间 事实上,我们可以使用原址处理
fn sanjiaohe(mut array: Vec<i32>) -> i32 {
let len = array.len();
for i in 0..len-1 { // 要处理n-1层
for j in 0..len-1-i { // 这一层的元素要处理的次数len -1
array[j] = (array[j] + array[j+1]) % 10;
}
array.pop(); // 队尾会多出元素 弹出即可
}
array[0]
}
3100.换水问题II
题目
给你两个整数 numBottles 和 numExchange 。
numBottles 代表你最初拥有的满水瓶数量。在一次操作中，你可以执行以下操作之一：
喝掉任意数量的满水瓶，使它们变成空水瓶。
用 numExchange 个空水瓶交换一个满水瓶。然后，将 numExchange 的值增加 1 。
注意，你不能使用相同的 numExchange 值交换多批空水瓶。例如，如果 numBottles == 3 并且 numExchange == 1 ，则不能用 3 个空水瓶交换成 3 个满水瓶。
返回你 最多 可以喝到多少瓶水。
解析
其实这就是相当于1518变成了每次只兑换一瓶然后下次兑换一瓶时要多加个空瓶子
fn exchange_water(exchange: usize,waters: usize) -> usize{
let mut exchange = exchange;
let mut waters: usize = waters.clone(); // 目前换的水的数量
let mut empty: usize = waters.clone(); // 目前空瓶子数量
while empty >= exchange { // 当空瓶子还能换时继续换
waters += 1; // 累加一个
empty = empty -exchange + 1; // 空瓶子
exchange += 1; // 要换的数量+1
}
return waters;
}
但事实上 其实有个数学规律在里面
令空瓶换水次数为t 交换的总空瓶为empty瓶 产生的总空瓶为total 则有 \(empty \leq total\)
由于每次换水所需的空瓶数都+1 则
则
而 $\( total = bottles + t \)$
则 $\( t \cdot exchange + t(t-1) /2 - bottles + t \leq 0 \)$
42.接雨水
题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
解析
实际上我们可发现 每个index的雨水量和左右两边最高的柱子有关系
而我们可以通过两个数组分别存储从左开始的最高柱子高度 和 从右开始的最高柱子高度
比如对于 [0,1,0,2,1,0,1,3,2,1,2,1]
它的left_max数组为 [0,1,1,2,2,2,2,3,3,3,3,3]
right_max为 [3,3,3,3,3,3,3,3,2,2,2,1]
那么
rain[0] = min(left_max[0],right_max[0]) - height[0];
rain[1] = min(left_max[1],right_max[1]) - heigt[1];
fn trap_rain_water(height_map: Vec<i32>) -> i32 {
let len = height_map.len(); // 高度表长度
let mut left_max = vec!(0;len); // 初始化从左开始最大值表
let mut right_max = vec!(0;len);
let mut max_index = 0;
for i in 0..len { // 遍历并得到从左开始最大值表
if height_map[i] > height_map[max_index] {
max_index = i;
}
left_max[i] = height_map[max_index];
}
max_index = len -1;
for j in (0..len).rev() {
if height_map[j] > height_map[max_index] {
max_index = j;
}
right_max[j] = height_map[max_index];
}
let mut rain =0; // rain的总量
for i in 0..len {
let cur_rain = min(left_max[i],right_max[i]) - height_map[i]; // 套公式
rain += cur_rain;
}
rain
}
然而我们可以不用构建这两个最大值数组 而使用双指针来解决
我们维护一个左指针和右指针 分别指向左边和右边遍历的最大值的位置
若左边小于右边的最大值时 最大接水量由左边决定
fn trap(height: Vec<i32>) -> i32 {
if height.len() <= 2 {
return 0;
}
let mut left = 0;
let mut right = height.len() - 1;
let mut left_max = left;
let mut right_max = right;
let mut total_water = 0;
while left < right {
if height[left_max] <= height[right_max] { // 左最大 <= 右
left += 1; // 左右移
if height[left_max] < height[left] { // 左最大值更新
left_max = left;
}
total_water += height[left_max] - height[left]; // 套公式
} else {
right -= 1;
if height[right_max] < height[right] {
right_max = right;
}
total_water += height[right_max] - height[right];
}
}
total_water
}
407.接雨水II
题目
给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。