【Day13】LeetCode力扣刷题[面试题 17.19. 消失的两个数字][70.爬楼梯][746. 使用最小花费爬楼梯]
【Day13】LeetCode力扣刷题[面试题 17.19. 消失的两个数字][70.爬楼梯][746. 使用最小花费爬楼梯]
CSDN话题挑战赛第2期 参赛话题：学习笔记
刷题打卡，第十三天
题目一、面试题 17.19. 消失的两个数字
原题链接：面试题 17.19. 消失的两个数字
题目描述：
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？ 以任意顺序返回这两个数字均可。 / 示例 1: 输入: [1] 输出: [2,3] / 示例 2: 输入: [2,3] 输出: [1,4] / 提示：
- nums.length <= 30000
解题思路：
利用异或运算符解答：
0 ^ a = a;
当一个数重复异或会抵消：
a ^ b ^ a = b;
那么我们将1-N个数异或，再将nums[]中的数异或，就得到了消失的两个数的异或值。
之后将出现的数分为 二进制表示的第 1 位为 0 的数，和 二进制表示的第 1位为 1 的数。
将他们异或，消除重复，就分别得到了两个消失的数。
提交代码：
class Solution {
public int[] missingTwo(int[] nums) {
int n = nums.length+2; //nums[]长度+2才是1到N的个数
int diff = 0; //准备获取消失两个数的异或值
//先对1-N进行异或处理
for(int i = 1;i <= n; ++i) diff ^= i;
//再对消失了两个数的nums[]进行异或处理
//被异或过的数再次异或会抵消，即a^a^b = b
//还有0^a = a,所以diff初始值为0；
//这么一来，现在的diff相当于疑惑了两个消失的数:a^b
for(int num : nums) diff ^= num;
int lsb = (diff & -diff);//取出diff的二进制表示中最低位那个1
int T1 = 0,T2 = 0;
//利用lsb将1-N中出现的数分为两类，出现两次的一类，出现一次的（消失的数）一类
//再将它们全部异或起来，抵消出现两次的，剩下消失的两个数
for(int i = 1;i <= n;++i){
if((i & lsb) != 0){
T1 ^= i;
}else{
T2 ^= i;
}
}
for(int num : nums){
if((num & lsb) != 0){
T1 ^= num;
}else{
T2 ^= num;
}
}
return new int[]{T1,T2};
}
}提交结果：
题目二、70.爬楼梯
原题链接：70.爬楼梯
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 示例 1： 输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 ①1 阶 + 1 阶 ② 2 阶 / 示例 2： 输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 ①1 阶 + 1 阶 + 1 阶 ② 1 阶 + 2 阶 ③ 2 阶 + 1 阶 提示： 1 <= n <= 45
解题思路:
动态规划：
每多一阶台阶，上台阶的方法都是前两阶上台阶方法数量的和；
提交代码：
class Solution {
public int climbStairs(int n) {
int a = 0,b = 0,sum = 1;
for(int i = 0;i < n;++i){
a = b;
b = sum;
sum = a+b;
}
return sum;
}
}提交结果：
题目三、746. 使用最小花费爬楼梯
原题链接：746. 使用最小花费爬楼梯
题目描述：
给你一个整数数组
cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。 你可以选择从下标为0或下标为1的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。 / 示例 1： 输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。 / 示例 2： 输入：cost = [1,100,1,1,1,100,1,1,100,1] 输出：6 解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。 总花费为 6 。
解题思路：
与上一道爬楼梯的解题思路一致，只是不需要记录爬楼梯的方法，而是记录前两阶价格中，更优惠的方案
提交代码：
class Solution {
public int minCostClimbingStairs(int[] cost) {
int a = 0,b = 0,curr = 0;
//依旧是动态规划
//与爬楼梯问题几乎一样，只不过是方式换成了最低消费
for(int i = 2;i <= cost.length;++i){
//至于前两阶相关，选价格较低的方案
curr = Math.min(a+cost[i-2],b+cost[i-1]);
a = b;
b = curr;
}
return curr;
}
}提交结果：
腾讯云开发者
