刷题打卡，第十三天
题目一、面试题 17.19. 消失的两个数字
题目二、70.爬楼梯
题目三、746. 使用最小花费爬楼梯
题目一、面试题 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; } } retur n 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; } }
提交结果：
⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞，收藏以及关注是对作者最大的鼓励喔 ~~
贵在坚持：
