kkbtrainingI

爬楼梯 原题链接：https://leetcode.cn/problems/climbing-stairs/ 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 1.递推与递归==思路==：简单的递推问题（斐波那契数列） 到达第一阶梯的方法数为1 到达第二阶梯的方法数为1 到达第三阶梯的方法数为 第一阶梯的方法数 + 第二阶梯的方法数 …… 到达第n阶梯的方法数为 第 n - 1 阶梯的方法数 + 第 n - 2 阶梯的方法数 ans[i] = ans[i - 1] + ans[i - 2]; 1234567891011121314class Solution {public: int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; int ans[2] = {1, 2}; int a = 0, b = 1; for (int i = 3; i <= n; ++i) { ans[a] += ans[b]; swap(a, b); } return ans[b]; }};

第一个错误的版本 原题链接：https://leetcode.cn/problems/first-bad-version/ 你是产品经理，目前正在带领一个团队开发新的产品。 不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。 实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。 1.二分答案01123456789101112131415class Solution {public: int firstBadVersion(int n) { long long l = 1, r = n; while (l != r) { long long mid = (l + r) /2; if (isBadVersion(mid)) { r = mid; } else { l = mid + 1; } } return l; }};

x的平方根 原题链接：https://leetcode.cn/problems/sqrtx/ 给你一个非负整数 x ，计算并返回 x 的 算术平方根。 由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。 注：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。 1.二分答案10123456789101112131415class Solution {public: int mySqrt(int x) { long long l = 0, r = x; while (l != r) { long long mid = (r + l + 1) / 2; if (mid * mid <= x) { l = mid; } else { r = mid - 1; } } return r; }};

加一 原题链接：https://leetcode.cn/problems/plus-one/ 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数0之外，这个整数不会以零开头。 1.参考解答==思路==：大整数加法 将最后一位加1 如果最后一位在加法操作后等于10，则需要进行进位 如果在下标为0的数字位等于10，则需要将数字的整体位数加1 1

最大子数组和 原题链接：https://leetcode.cn/problems/maximum-subarray/ 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组是数组中的一个连续部分。 12345678class Solution {public: int maxSubArray(vector<int>& nums) { int final = nums[0], ans = nums[0]; ans = max(nums[i], ans + nums[i]); fin = max(fin, ans); }}; 这是一道典型的使用「动态规划」解决的问题，需要我们掌握动态规划问题设计状态的技巧（无后效性）， 并且需要知道如何推导状态转移方程，最后再去优化空间。 1.动态规划step1问题理解「力扣」第 53 题（最大子序和）是「力扣」第 124 题（二叉树的最大路径和）的线性版本，它们的状态设计思想和状态转移是类似的，希望大家能够通过本题题解进一步体会状态是如何想到的（即子问题的定义需要从哪些方面考虑）。 本题接的重点在「关键 1：理解题意」和「关键 2：如何定义子问题（如何定义状态）」和「最后再谈谈「无后效性」。 关键 1：理解题意 题目要我们找出和最大的连续子数组的值是多少，「连续」是关键字，连续很重要，不是子序列。 题目只要求返回结果，不要求得到最大的连续子数组是哪一个。这样的问题通常可以使用「动态规划」解决。 关键 2：如何定义子问题（如何定义状态） 设计状态思路：把不确定的因素确定下来，进而把子问题定义清楚，把子问题定义得简单。动态规划的思想通过解决了一个一个简单的问题，进而把简单的问题的解组成了复杂的问题的解。 友情提示：上面这句话大家姑且这么一看，脑子里有个印象，没有那么绝对。可能不同的人看会有不同的理解。如果我以后讲解的动态规划的设计思想与这里讲解的「设计状态思路」不一样的，我会再和大家说明。如果讲解有误导的地方，还请大家指出。 我们 不知道和最大的连续子数组一定会选哪一个数，那么我们可以求出 所有 经过输入数组的某一个数的连续子数组的最大和。 例如，示例 1 输 ...

有效的括号 原题链接：https://leetcode.cn/problems/valid-parentheses/ 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 1.化简思维可以将问题先简化为1种括号的匹配问题（判断左括号、右括号的数量是否相等），再扩展括号匹配的种类： +1可以等价为进入，-1可以等价为出去 一对()可以等价为一个完整的事件 (())可以看做事件与事件之间的完全包含关系 1种括号匹配123456789101112131415//写法1bool isValid(char *s) { int lum = 0, rnum = 0; int len = strlen(s); for (int i = 0; i < len; ++i) { switch (s[i]) { case '(' : ++lnum; break; case ')' : ++rnum; break; default : return flase; } if (lnum >= rnum) continue; return false; } return lnum = rnum;} 123456789101112131415//写法2bool isValid(char *s) { int lum = 0; int len = strlen(s); for (int i = 0; i < len; ++i) { switch (s[i]) { case '(' : ++lnum; break; ...

外观数列 原题链接：https://leetcode.cn/problems/count-and-say/ 给定一个正整数 n，输出外观数列的第 n 项。 外观数列是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。你可以将其视作是由递归公式定义的数字字符串序列： countAndSay(1) = "1" countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。 前五项如下： 123456789101. 12. 113. 214. 12115. 111221第一项是数字 1 描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221" 要描述一个数字字符串，首先要将字符串分割为最小数量的组，每个组都由连续的最多相同字符组成。 对于每个组，先描述字符的数量然后描述字符，形成一个描述组。 要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。 例如，数字字符串 "3322251" 的描述如下图： 1.遍历上个字符串得到下个遍历前一个字符串 得到后一个字符串 1234567891011121314151617181920212223242526class Solution {public: void work(string &str, int cnt, char c) { str += (char)(cnt + '0');//数字数量 str += c;//数字字符 } void func(string &str1, string &str2) { int cnt = 0; for ( ...

搜索插入位置 原题链接：https://leetcode.cn/problems/search-insert-position/ 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 1.暴力法123456789class Solution {public: int searchInsert(vector<int>& nums, int target) { for (int i = 0; i < nums.size(); ++i) { if (nums[i] >= target) return i; } return nums.size(); }}; 2.二分查找12345678910111213141516class Solution {public: int searchInsert(vector<int>& nums, int target) { if (nums[nums.size() - 1] < target) return nums.size(); int l = 0, r = nums.size() - 1; while (l != r) { int mid = (l + r) / 2; if (nums[mid] >= target) { r = mid; } else { l = mid + 1; } } return l; }};

移除指定元素 原题链接：https://leetcode.cn/problems/remove-element/ 1.巧妙的移动元素1234567891011121314class Solution {public: int removeElement(vector<int>& nums, int val) { int count = 0; for (int i = 0; i < nums.size(); ++i) { if (nums[i] == val) { count++; } else { nums[i - count] = nums[i]; } } return nums.size() - count; }}; 2.重复项删除类似12345678910111213class Solution {public: int removeElement(vector<int>& nums, int val) { int black = 0; for (int red = 0; red < nums.size(); ++red) { if (nums[red] != val) { nums[black] = nums[red]; black++; } } return black; }};

删除有序数组中的重复项 原题链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/ 不要使用额外的空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。 1.双指针1234567891011121314class Solution {public: int removeDuplicates(vector<int>& nums) { if (nums.size() == 0) return 0; int black = 0; for (int red = 1; red < nums.size(); ++red) { if (nums[red] != nums[black]) { black++; nums[black] = nums[red]; } } return black + 1; }};