Leetcode227. 基本计算器 II
Leetcode227. 基本计算器 II
题目描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
示例 1：
12输入：s = "3+2*2"输出：7
示例 2：
12输入：s = " 3/2 "输出：1
示例 3：
12输入：s = " 3+5 / 2 "输出：5
提示：
1≤s.length≤3∗1051 \leq s.length \leq 3 * 10^51≤s.length≤3∗105
s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0,231−1][0, 2^{31} - 1][0,231−1] 内
题目数据保证答案是一个 32-bit 整数
解题思路
这道题可以运用栈来模拟运算。思路应该说没有什么难度，加减直接压入栈就好，乘除就得先和栈中的顶元素计算，然后压入栈中。最后，将栈中的元素顺序计算就好。关键的难度在于实现，要注意需要将字符串同步转化为整数。 ...
Leetcode 226. 翻转二叉树
Leetcode 226. 翻转二叉树
题目描述
翻转一棵二叉树。
示例：
12345678910111213141516输入： 4 / \ 2 7 / \ / \1 3 6 9输出： 4 / \ 7 2 / \ / \9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出>>翻转二叉树这道题，这太糟糕了。
这是永远的嘲讽啊！太狠了
解题思路
运用递归的思想，先将左子树和右子数递归翻转，然后将翻转后的左子树和右子树调换位置。递归出口就是根节点为空或者只有根节点的情况。
示例代码
12345678910TreeNode* invertTree(TreeNode* root) { if(root==nullptr) return nullptr; if(!root->left&&!root->right) return r ...
Leetcode225. 用队列实现栈
Leetcode225. 用队列实现栈
题目描述
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
12345678910111213输入：["MyStack", "push", "push", "top", "pop", "empty" ...
Leetcode221. 最大正方形
Leetcode221. 最大正方形
题目描述
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例 1：
12输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]输出：4
示例 2：
12输入：matrix = [["0","1"],["1","0"]]输出：1
示例 3：
12输入：matrix = [[&qu ...
Leetcode 215. 数组中的第K个最大元素
Leetcode 215. 数组中的第K个最大元素
题目描述
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例
示例 1:
12输入: [3,2,1,5,6,4] 和 k = 2输出: 5
示例 2:
12输入: [3,2,3,1,2,4,5,5,6] 和 k = 4输出: 4
说明
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度
解题思路
最自然的想法就是构造一个大根堆，然后删除 k-1 个堆顶元素然后就得到了第k大的元素，时间复杂度为 O(n log n) 。但是，今天我们使用快速排序的思想来解决第k大的问题。其目的在于熟悉对快速排序思想的掌握。
具体方法为：快速排序的每一次划分都会确定一个元素的位置，返回 index 。我们已知数组的长度 n ，因而可以确定这个元素是第几大的元素。然后就是快速排序的思想，以这个元素的位置为界，划分为左区和右区。如果正好就是找这个元素，直接返回；否则，运用这个元素的位置信息去判断在左区递归寻找还是右区递归寻找。时间复杂度也为 O(n log n) 。
这个 ...
Leetcode209. 长度最小的子数组
Leetcode209. 长度最小的子数组
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。
示例 1：
123输入：target = 7, nums = [2,3,1,2,4,3]输出：2解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
12输入：target = 4, nums = [1,4,4]输出：1
示例 3：
12输入：target = 11, nums = [1,1,1,1,1,1,1,1]输出：0
提示：
1≤target≤1091 \leq target \leq 10^91≤target≤109
1≤nums.length≤1051 \leq nums.length \leq 10^51≤nums.length≤105
1≤nums[i]≤1051 \leq nums[i] \leq 10^51≤nums[i]≤10 ...
Leetcode200. 岛屿数量图
Leetcode200. 岛屿数量图
题目描述
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
1234567输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"]]输出：1
示例 2：
1234567输入：grid = [ ["1",&qu ...
Leetcode 199：二叉树的右视图
Leetcode 199：二叉树的右视图
题目描述
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例
12345678910输入: [1,2,3,null,5,null,4]输出: [1, 3, 4]解释: 1 <--- / \2 3 <--- \ \ 5 4 <---
解题思路
这道题是二叉树的右视图，也就是输出每一层的最后一个结点的值。所以在层序遍历的基础上加以改动就ok。
示例代码
12345678910111213141516171819vector<int> rightSideView(TreeNode* root) { vector<int>res; if(root==nullptr) return {}; queue<TreeNode*>q; q.push(root); while(!q ...
Leetcode198. 打家劫舍
Leetcode198. 打家劫舍
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
1234输入：[1,2,3,1]输出：4解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
1234输入：[2,7,9,3,1]输出：12解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 400
解题思路
这道题可以考虑用动态规划去做。首先定义dp[i]表示从第一间房间到i号房间能偷到的最高金 ...
Leetcode179. 最大数
Leetcode179. 最大数
题目描述
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
**注意：**输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 1：
12输入：nums = [10,2]输出："210"
示例 2：
12输入：nums = [3,30,34,5,9]输出："9534330"
示例 3：
12输入：nums = [1]输出："1"
示例 4：
12输入：nums = [10]输出："10"
提示：
1≤nums.length≤1001 \leq nums.length \leq 1001≤nums.length≤100
0≤nums[i]≤1090 \leq nums[i] \leq 10^90≤nums[i]≤109
解题思路
这道题如果数组中的数没有相同数字开头，那么这道题非常好做。直接将整数类型的数组转换为字符串类型的数组，然后直接按字符串比较大小的方式将里面的字符串从大到小排序（比较过程是，首先比较输入数组的每个 ...