我的LeetCode题解
74.搜索二维矩阵（矩阵）(medium)
给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 1：
1输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 32输出：true
示例 2：
xxxxxxxxxx21输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 132输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
解答
x181class Solution {2public:3 bool searchMatrix(vector<vector<int>>& matrix, int target) {4 int m = matrix.size(), n = matrix[0].size();5 int i = 0, j = n - 1;6 while (i < m && j >= 0) { // 还有剩余元素7 if (matrix[i][j] == target) {8 return true; // 找到 target9 }10 if (matrix[i][j] < target) {11 i++; // 这一行剩余元素全部小于 target，排除12 } else {13 j--; // 这一列剩余元素全部大于 target，排除14 }15 }16 return false;17 }18};
20.有效的括号（栈）(easy)
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([])"
输出：true
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
解答
xxxxxxxxxx1311bool isValid(char * s){2 int length = strlen(s); //求出字符串s的长度3 4 char Stack[length]; //定义一个顺序栈5 int top = -1; //初始化栈6
7 //从左往右扫描字符串s8 for(int i = 0; i < length; i++){ 9 if(s[i] == '(' || s[i] == '[' || s[i] == '{'){ //扫描到“左括号”10 Stack[++top] = s[i]; //将“左括号”入栈11 }else{ 12 if(top == -1)13 return false; //扫描到“右括号”且栈为空，则括号匹配失败（“右括号”为单身）14
15 char topElem; 16 topElem = Stack[top--]; //出栈一个元素并赋值给topElem17
18 if(s[i] == ')' && topElem != '(')19 return false; //左右括号不匹配20 if(s[i] == ']' && topElem != '[')21 return false; //左右括号不匹配22 if(s[i] == '}' && topElem != '{')23 return false; //左右括号不匹配24 }25 }26
27 if(top != -1)28 return false; //扫描到完字符串s后栈不空，则括号匹配失败（“左括号”为单身）29 return true;30 31}
121.买卖股票的最佳时机（贪心算法）(easy)
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
xxxxxxxxxx41输入：[7,1,5,3,6,4]2输出：53解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。4注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
xxxxxxxxxx31输入：prices = [7,6,4,3,1]2输出：03解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 1050 <= prices[i] <= 104
解答
xxxxxxxxxx1171int maxProfit(int* prices, int pricesSize){2 if(pricesSize==0) return 0;3 int result=0,max=prices[0],min=prices[0];4 for(int i=1;i<pricesSize;i++)5 {6 if(prices[i]>max) //股票价格上升了7 {8 max=prices[i];9 result=fmax(max-min,result);10 }11 else if(prices[i]<min) //最低价格下降了12 {13 min=max=prices[i];14 }15 }16 return result;17}
70.爬楼梯（动态规划）(easy)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
xxxxxxxxxx51输入：n = 22输出：23解释：有两种方法可以爬到楼顶。41. 1 阶 + 1 阶52. 2 阶
示例 2：
xxxxxxxxxx61输入：n = 32输出：33解释：有三种方法可以爬到楼顶。41. 1 阶 + 1 阶 + 1 阶52. 1 阶 + 2 阶63. 2 阶 + 1 阶
提示：
1 <= n <= 45
解答
xxxxxxxxxx1231int climbStairs(int n)2{3 int sum0=1,sum1=2;4 int temp;5 int answer=0;6 int i,j;7 if(n==1)8 {9 return 1;10 }11 if(n==2)12 {13 return 2;14 }15 for(i=3;i<=n;i++)16 {17 temp=sum0+sum1;18 sum0=sum1;19 sum1=temp;20 }21 answer=temp;22 return answer;23}
136.只出现一次的数字（技巧）(easy)
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
输入：nums = [2,2,1]
输出：1
示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：
输入：nums = [1]
输出：1
提示：
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104除了某个元素只出现一次以外，其余每个元素均出现两次。
解答
xxxxxxxxxx1131int singleNumber(int* nums, int numsSize){2int i,j;3int result;4for(i=0;i<numsSize;i++)5 for(j=0;j<numsSize;j++)6 {7 if((nums[i]==nums[j])&&(i!=j))8 break;9 if(j==numsSize-1)10 result=nums[i];11 }12return result;13}
98.验证二叉搜索树（二叉树）(medium)
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
xxxxxxxxxx21输入：root = [2,1,3]2输出：true
示例 2：
xxxxxxxxxx31输入：root = [5,1,4,null,null,3,6]2输出：false3解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
树中节点数目范围在
[1, 104]内-231 <= Node.val <= 231 - 1
解答
xxxxxxxxxx1211class Solution {2public:3 bool isValidBST(TreeNode* root) {4 bool flag = true;5 long long pre = LONG_MIN;6 auto inOrder = [&](this auto&& inOrder, TreeNode* root) -> void {7 if (root == nullptr) {8 return;9 }10 inOrder(root->left);11 if(root->val <= pre) {12 flag = false;13 return;14 }15 pre = root->val;16 inOrder(root->right);17 };18 inOrder(root);19 return flag;20 }21};
94.二叉树的中序遍历（二叉树）(easy)
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
xxxxxxxxxx21输入：root = [1,null,2,3]2输出：[1,3,2]
示例 2：
xxxxxxxxxx21输入：root = []2输出：[]
示例 3：
xxxxxxxxxx21输入：root = [1]2输出：[1]
提示：
树中节点数目在范围
[0, 100]内-100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
解答
xxxxxxxxxx1171class Solution 2{3 public:4 vector<int> inorderTraversal(TreeNode* root) 5 {6 vector<int> result;7 inorderhelp(root,result);8 return result;9 };10 void inorderhelp(TreeNode* node,vector<int>& value)11 {12 if(node==nullptr)13 { return ;}14 inorderhelp(node->left,value);15 value.push_back(node->val);16 inorderhelp(node->right,value); 17 }18};
104.二叉树的最大深度（二叉树）(easy)
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
xxxxxxxxxx21输入：root = [3,9,20,null,null,15,7]2输出：3
示例 2：
xxxxxxxxxx21输入：root = [1,null,2]2输出：2
提示：
树中节点的数量在
[0, 104]区间内。-100 <= Node.val <= 100
解答
xxxxxxxxxx1111class Solution 2{3 public:4 int maxDepth(TreeNode* root) {5 if (root == nullptr) {6 return 0;7 }8 int l_depth = maxDepth(root->left);9 int r_depth = maxDepth(root->right);10 return max(l_depth, r_depth) + 1;11 }12};
102.二叉树的层序遍历（二叉树）(medium)
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
xxxxxxxxxx21输入：root = [3,9,20,null,null,15,7]2输出：[[3],[9,20],[15,7]]
示例 2：
xxxxxxxxxx21输入：root = [1]2输出：[[1]]
示例 3：
xxxxxxxxxx21输入：root = []2输出：[]
提示：
树中节点数目在范围
[0, 2000]内-1000 <= Node.val <= 1000
解答
x
1class Solution {2public:3 vector<vector<int>> levelOrder(TreeNode *root) {4 if (root == nullptr) return {};5 vector<vector<int>> ans;6 queue<TreeNode *> q;7 q.push(root);8 while (!q.empty()) {9 vector<int> vals;10 for (int n = q.size(); n--;) {11 auto node = q.front();12 q.pop();13 vals.push_back(node->val);14 if (node->left) q.push(node->left);15 if (node->right) q.push(node->right);16 }17 ans.emplace_back(vals);18 }19 return ans;20 }21};
1.两数之和（哈希）(easy)
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
xxxxxxxxxx31输入：nums = [2,7,11,15], target = 92输出：[0,1]3解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
xxxxxxxxxx21输入：nums = [3,2,4], target = 62输出：[1,2]
示例 3：
xxxxxxxxxx21输入：nums = [3,3], target = 62输出：[0,1]
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
解答
xxxxxxxxxx1171class Solution {2public:3 vector<int> twoSum(vector<int>& nums, int target) {4 int i,j;5 for(i=0;i<nums.size()-1;i++)6 {7 for(j=i+1;j<nums.size();j++)8 {9 if(nums[i]+nums[j]==target)10 {11 return {i,j};12 }13 }14 }15 return {i,j};16 };17};
128.最长连续序列（哈希）(medium)
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
xxxxxxxxxx31输入：nums = [100,4,200,1,3,2]2输出：43解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
xxxxxxxxxx21输入：nums = [0,3,7,2,5,8,4,6,0,1]2输出：9
示例 3：
xxxxxxxxxx21输入：nums = [1,0,1,2]2输出：3
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109
解答：
核心思路：对于nums中的元素x，以x为起点，不断查找下一个数x+1,x+2,⋯是否在nums中，并统计序列的长度。
为了做到O(n)的时间复杂度，需要两个关键优化：
把nums中的数都放入一个哈希集合中，这样可以O(1)判断数字是否在nums中。如果x−1在哈希集合中，则不以x为起点。为什么呢？因为以x−1为起点计算出的序列长度，一定比以x为起点计算出的序列长度要长！这样可以避免大量重复计算。比如nums=[3,2,4,5]，从3开始，我们可以找到3,4,5这个连续序列；而从2开始，我们可以找到2,3,4,5这个连续序列，一定比从3开始的序列更长。 ⚠注意：遍历元素的时候，要遍历哈希集合，而不是nums！如果nums=[1,1,1,…,1,2,3,4,5,…]（前一半都是1），遍历nums的做法会导致每个1都跑一个O(n)的循环，总的循环次数是O(n^2)，会超时。
哈希做法：
x
1class Solution {2public:3 int longestConsecutive(vector<int>& nums) {4 int ans = 0;5 unordered_set<int> st(nums.begin(), nums.end()); // 把 nums 转成哈希集合6 for (int x : st) { // 遍历哈希集合7 if (st.contains(x - 1)) {8 continue;9 }10 // x 是序列的起点11 int y = x + 1;12 while (st.contains(y)) { // 不断查找下一个数是否在哈希集合中13 y++;14 }15 // 循环结束后，y-1 是最后一个在哈希集合中的数16 ans = max(ans, y - x); // 从 x 到 y-1 一共 y-x 个数17 }18 return ans;19 }20};非哈希做法：
x
1201class Solution {2public:3 int longestConsecutive(vector<int>& nums) {4 sort(nums.begin(),nums.end());5 int max = 0;6 int tep = 1;7 int size = nums.size();8 if(size == 0)return 0;9 for(int i = 0; i<size-1; i++){10 if(nums[i+1] == nums[i]+1)tep++;11 else if(nums[i+1] == nums[i]){12 }else{13 if(tep > max)max = tep;14 tep = 1;15 }16 }17 if(tep > max)max = tep;18 return max;19 }20};