算法打卡第二天

5.爬楼梯(动态规划)

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

• 1 <= n <= 45

class Solution {
public:int climbStairs(int n) {// 动态规划 递归if(n <= 1)// 因为下面直接对dp[2]操作了，防止空指针return n;// 从0开始的vector <int> dp(n + 1);// 0舍弃dp [1] = 1;dp [2] = 2;// 从第三个楼梯处理for(int i = 3; i <= n ; ++i){dp[i] = dp[i - 1] + dp [i - 2];}return dp[n];}};

6.打家劫舍(动态规划)

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

/*
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。*/
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:// 递归int rob(vector<int> &nums){// 特殊情况// 没有房间 结束if (nums.size() == 0)return 0;// 只有一个房间 偷第一个房间if (nums.size() == 1)return nums[0];// 定义一个容器 动态数组vector<int> dp(nums.size());// 初始化第一个第二个元素 dp[0] = nums[0];//只有下标0房间只能偷dp[1] = max(nums[0], nums[1]);//有0有1选择大的偷// 从第三个元素遍历for(int i = 2; i < nums.size(); ++i){// 两种情况 第一中情况有i 第二种没有idp[i] = max(dp[i - 2] + nums[i], dp[i - 1] ) ;}// 返回最大值return dp[nums.size() - 1];}
};
int main()
{vector<int> arr1 = {1,2,3,1};vector<int> arr2= {2,7,9,3,1};Solution s ;cout << s.rob(arr1) << endl;cout << s.rob(arr2) << endl;return 0;
}

7.移除元素（数组 双指针）

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,,]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,,,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

• 思路就是两个指针，数组快指针的值付给慢指针，同时移动，当遇到目标值快指针继续移动，但是不把值给满指针，然后返回数组慢指针的值，就是新数组

// 双指针法（快慢指针法// 思路就是两个指针，数组快指针的值付给慢指针，同时移动，当遇到目标值快指针继续移动，但是不把值给满指针，然后返回数组慢指针的值，就是新数组
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:int removeElement(vector<int> &nums, int val){// 慢指针int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) // fastIndex是快指针{// 当快指针指向的值不等于目标值if (val != nums[fastIndex]){// 把快指针的值付给慢指针nums[slowIndex++] = nums[fastIndex];}// 当快指针指向的值等于目标值就不把快指针的值付给慢指针}// 返回慢指针 它是新数组中不等于 val 的元素的数量return slowIndex;}
};
int main()
{vector<int> arr1 = {3, 2, 2, 3};vector<int> arr2 = {0, 1, 2, 2, 3, 0, 4, 2};Solution s;int k1 = s.removeElement(arr1, 3);cout << s.removeElement(arr1, 3) << endl;for (int i = 0; i < k1; i++){cout << arr1[i] << " ";}cout << endl;cout << "=============" << endl;int k2 = s.removeElement(arr2, 2);cout << k2 << endl;for (int i = 0; i < k2; i++){cout << arr2[i] << " ";}return 0;
}

8.二分查找（数组）

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

使用左闭右闭即**[left, right]**

• while (left <= right) 要使用 <= ，因为left == right是有意义的(都是闭的)，所以使用 <=
• if (nums[middle] > target) right 要赋值为 middle - 1，因为已经判断力这个nums[middle]一定不是target，而且是[left, right]，是包含right 的，那么接下来要查找的左区间结束下标位置就是 middle - 1

/*
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。*/
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:int search(vector<int> &nums, int target)// 二分查找{// 左右下标int left = 0;                // 第一个int right = nums.size() - 1; // 最后一个  定义target在左闭右开的区间里，即：[left, right)while (left <= right)        // 当left==right，区间[left, right]依然有效，所以用 <={int middle = left +((right - left) / 2) ; // 避免越界if (nums[middle] > target)                // 在左边{right = middle - 1;}else if (nums[middle] < target) // 在右边{left = middle + 1;}else // 找到了目标值 返回{return middle;}}// 循环完了没有找到return -1;}
};
int main()
{Solution s;vector<int> arr1 = {-1, 0, 3, 5, 9, 12};vector<int> arr2 = {-1, 0, 3, 5, 9, 12};cout << s.search(arr1, 9) << endl;cout << s.search(arr2, 2) << endl;return 0;
}

9.有序数组的平方 （数组 双指针）

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

思路：

• 双指针法
  • 定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置
  • 思路就是两个指针，头指针指向0，尾指针指向最后一个元素，比较
  • 头尾就移动头指针向中间移动,反之就是尾指针向中间移动,

/*
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。*/// 双指针法
// 定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置
// 思路就是两个指针，头指针指向0，尾指针指向最后一个元素，比较
// 头》尾就移动头指针向中间移动,反之就是尾指针向中间移动,#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:vector<int> sortedSquares(vector<int> &nums){// 新数组 存储平方数组vector<int> result(nums.size(), 0);int k = nums.size() - 1; // 元素末尾// 定义两个指针循环int i = 0; int j = nums.size() - 1;while(i <= j) // i <= j，因为最后要处理两个元素{// 头平方大于尾平方if (nums[i] * nums[i] > nums[j] * nums[j]){result[k--] = nums[i] * nums[i];i++;}// 头平方小于尾平方else{result[k--] = nums[j] * nums[ j];j--;}}return result;}
};
int main()
{vector<int> arr1 = {-4, -1, 0, 3, 10};vector<int> arr2 = {-7, -3, 2, 3, 11};Solution s;vector<int> arr3 = s.sortedSquares(arr1);for (int i = 0; i < arr3.size(); i++){cout << arr3[i] << " ";}cout << endl;vector<int> arr4 = s.sortedSquares(arr2);for (int i = 0; i < arr4.size(); i++){cout << arr4[i] << " ";}return 0;
}