网站单页设计,装潢设计培训班学费多少钱,北京seo网站推广,长春市招标建设信息网001.找单独的数
难度#xff1a;易
问题描述
在一个班级中#xff0c;每位同学都拿到了一张卡片#xff0c;上面有一个整数。有趣的是#xff0c;除了一个数字之外#xff0c;所有的数字都恰好出现了两次。现在需要你帮助班长小C快速找到那个拿了独特数字卡片的同学手上…
001.找单独的数
难度易
问题描述
在一个班级中每位同学都拿到了一张卡片上面有一个整数。有趣的是除了一个数字之外所有的数字都恰好出现了两次。现在需要你帮助班长小C快速找到那个拿了独特数字卡片的同学手上的数字是什么。
要求
设计一个算法使其时间复杂度为 O(n)其中 n 是班级的人数。尽量减少额外空间的使用以体现你的算法优化能力。 测试样例
样例1 输入cards [1, 1, 2, 2, 3, 3, 4, 5, 5] 输出4 解释拿到数字 4 的同学是唯一一个没有配对的。 样例2 输入cards [0, 1, 0, 1, 2] 输出2 解释数字 2 只出现一次是独特的卡片。 样例3 输入cards [7, 3, 3, 7, 10] 输出10 解释10 是班级中唯一一个不重复的数字卡片。 约束条件
1 ≤ cards.length ≤ 10010 ≤ cards[i] ≤ 1000班级人数为奇数除了一个数字卡片只出现一次外其余每个数字卡片都恰好出现两次
思路提示
要解决这个问题我们可以利用异或XOR运算的特性。异或运算有以下几个关键性质
相同数字异或结果为0a ^ a 0任何数字与0异或结果为该数字本身a ^ 0 a异或运算满足交换律和结合律a ^ b ^ a (a ^ a) ^ b 0 ^ b b
基于这些性质我们可以设计一个算法来找到那个唯一的独特数字
解题思路
初始化一个变量 unique_number 为0。遍历数组中的每一个数字将 unique_number 与当前数字进行异或运算。最终unique_number 将只包含那个独特的数字因为所有成对的数字都会通过异或运算相互抵消。
算法步骤
初始化 unique_number 0。遍历数组 cards 中的每一个数字 card 更新 unique_number 为 unique_number ^ card。 返回 unique_number。
时间复杂度
**O(n)**我们只需要遍历数组一次。
空间复杂度
**O(1)**我们只使用了常数级别的额外空间。
通过这种方式我们可以在不使用额外空间的情况下以线性时间复杂度找到那个独特的数字。 MarsCode AI答案
Python:
def solution(cards):# 初始化结果变量为0result 0# 遍历数组中的每一个元素for card in cards:# 将结果与当前元素进行异或运算result ^ card# 返回最终结果return resultif __name__ __main__:# 添加你的测试用例print(solution([1, 1, 2, 2, 3, 3, 4, 5, 5]) 4)print(solution([0, 1, 0, 1, 2]) 2)
Go:
package mainimport fmtfunc solution(cards []int) int {result : 0for _, card : range cards {result ^ card}return result
}func main() {fmt.Println(solution([]int{1, 1, 2, 2, 3, 3, 4, 5, 5}) 4)fmt.Println(solution([]int{0, 1, 0, 1, 2}) 2)fmt.Println(solution([]int{7, 3, 3, 7, 10}) 10)
}
Rust:
fn solution(cards: Veci32) - i32 {// 使用异或运算来找到唯一的数字let mut unique_number 0;for card in cards {unique_number ^ card;}unique_number
}fn main() {// 添加你的测试用例println!({}, solution(vec![1, 1, 2, 2, 3, 3, 4, 5, 5]) 4);println!({}, solution(vec![0, 1, 0, 1, 2]) 2);println!({}, solution(vec![7, 3, 3, 7, 10]) 10);
} 002.徒步旅行中的补给问题
难度中
问题描述
小R正在计划一次从地点A到地点B的徒步旅行总路程需要 N 天。为了在旅途中保持充足的能量小R每天必须消耗1份食物。幸运的是小R在路途中每天都会经过一个补给站可以先购买完食物后再消耗今天的1份食物。然而每个补给站的食物每份的价格可能不同并且小R在购买完食物后最多只能同时携带 K 份食物。
现在小R希望在保证每天食物消耗的前提下以最小的花费完成这次徒步旅行。你能帮助小R计算出最低的花费是多少吗
**输入 **
n 总路程需要的天数k 小R最多能同时携带食物的份数data[i] 第i天补给站每份食物的价格
**输出 **
返回完成这次徒步旅行的最小花费
**约束条件 **
1 n,k 10001 data[i] 10000 测试样例
样例1 输入n 5 ,k 2 ,data [1, 2, 3, 3, 2] 输出9 样例2 输入n 6 ,k 3 ,data [4, 1, 5, 2, 1, 3] 输出9 样例3 输入n 4 ,k 1 ,data [3, 2, 4, 1] 输出10 问题理解
小R每天需要消耗1份食物并且每天经过一个补给站可以购买食物。小R最多能携带 K 份食物。我们需要找到一种策略使得小R在旅途中花费最少。
数据结构选择
我们可以使用一个数组来存储每天的食物价格并且使用一个变量来记录当前携带的食物数量。
算法步骤 初始化 设置一个变量 current_food 表示当前携带的食物数量初始为0。设置一个变量 total_cost 表示总花费初始为0。 遍历每一天 如果当前携带的食物数量 current_food 大于0则消耗1份食物。如果当前携带的食物数量 current_food 为0则需要购买食物。在购买食物时需要考虑当前补给站的价格和未来几天的价格以决定购买多少份食物。 购买策略 在购买食物时应该尽量购买未来几天价格较低的食物以减少总花费。可以使用一个滑动窗口来找到未来几天内的最低价格并决定购买的数量。
思路说明
题目要求在给定的天数 N 和最大携带食物量 K 的限制下计算出完成徒步旅行所需的最小花费。每天经过的补给站食物价格不同且每天必须消耗1份食物。我们可以通过维护一个单调递增的双端队列来记录当前窗口内的最小价格从而在每次购买食物时选择最便宜的选项。通过滑动窗口的方式逐步计算出每天的最小花费最终得到总的最小花费。
解题过程
初始化创建一个双端队列 mins 用于存储当前窗口内的最小价格及其对应的天数。初始化结果 result 为0。遍历每一天 维护单调队列在每次遍历中首先检查队列 mins 的末尾元素如果其价格大于当前天的价格则将其弹出直到队列为空或队列末尾元素的价格小于等于当前天的价格。然后将当前天的价格和天数加入队列。滑动窗口检查队列 mins 的头部元素如果其对应的天数已经不在当前窗口内即 mins[0][0] j - k则将其弹出。计算花费将当前窗口内的最小价格即队列头部元素的价格累加到 result 中。 返回结果遍历结束后result 即为完成徒步旅行的最小花费。
复杂度分析
时间复杂度O(N)其中 N 是天数。我们只需要遍历每一天并且在每次遍历中队列的插入和删除操作都是 O(1) 的时间复杂度。空间复杂度O(K)其中 K 是最大携带食物量。我们使用了一个双端队列来存储当前窗口内的最小价格其最大长度为 K。
知识点扩展
双端队列deque双端队列是一种允许在两端进行插入和删除操作的队列。在本题中我们使用双端队列来维护当前窗口内的最小价格通过在队列两端进行操作可以高效地维护单调性。单调队列单调队列是一种特殊的队列其内部元素保持单调递增或单调递减的顺序。在本题中我们使用单调递增队列来记录当前窗口内的最小价格从而在每次购买食物时选择最便宜的选项。滑动窗口滑动窗口是一种常见的算法技巧用于在数组或列表中维护一个固定大小的窗口并对其进行操作。在本题中我们通过滑动窗口的方式逐步计算出每天的最小花费。 MarsCode AI答案
Python:
from collections import dequedef solution(n: int, k: int, data: list) - int:assert n len(data)assert k nmins deque()result 0for j in range(n):while len(mins) 0 and mins[-1][1] data[j]:mins.pop()mins.append([j, data[j]])while mins[0][0] j - k:mins.popleft()result mins[0][1]return resultif __name__ __main__:print(solution(n 5 ,k 2 ,data [1, 2, 3, 3, 2]) 9)print(solution(n 6 ,k 3 ,data [4, 1, 5, 2, 1, 3]) 9)print(solution(n 4 ,k 1 ,data [3, 2, 4, 1]) 10)Go:
package mainimport (fmtmath
)func solution(n int, k int, data []int) int {// 初始化dp数组dp[i]表示在第i天结束时的最小花费dp : make([]int, n1)for i : 1; i n; i {dp[i] math.MaxInt32 // 初始化为一个很大的值}dp[0] 0 // 第0天不需要花费// 填充dp数组for i : 1; i n; i {for j : i - 1; j max(0, i-k); j-- {// 计算在第j天购买食物然后走到第i天的总花费cost : dp[j] data[i-1] * (i - j)if cost dp[i] {dp[i] cost}}}return dp[n]
}func max(a, b int) int {if a b {return a}return b
}func main() {fmt.Println(solution(5, 2, []int{1, 2, 3, 3, 2}) 9)fmt.Println(solution(6, 3, []int{4, 1, 5, 2, 1, 3}) 9)fmt.Println(solution(4, 1, []int{3, 2, 4, 1}) 10)
}
Rust:
use std::collections::VecDeque;fn solution(n: usize, k: usize, data: Vecusize) - usize {assert_eq!(n, data.len());assert!(k n);let mut mins: VecDeque(usize, usize) VecDeque::new();let mut result 0;for j in 0..n {while let Some((_, price)) mins.back() {if price data[j] {mins.pop_back();} else {break;}}mins.push_back((j, data[j]));while let Some((index, _)) mins.front() {if index j.saturating_sub(k) {mins.pop_front();} else {break;}}result mins.front().unwrap().1;}result
}fn main() {println!({}, solution(5, 2, vec![1, 2, 3, 3, 2]) 9);println!({}, solution(6, 3, vec![4, 1, 5, 2, 1, 3]) 9);println!({}, solution(4, 1, vec![3, 2, 4, 1]) 10);
}
代码解释
VecDeque: Rust中的VecDeque类似于Python中的deque支持高效的头部和尾部操作。assert_eq! 和 assert!: Rust中的断言函数用于确保输入的合法性。while let: Rust中的模式匹配语法用于简化循环条件。saturating_sub: Rust中的饱和减法防止下溢。 来源https://www.marscode.cn/practice
