请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。 维护一个单调栈，单调递减的栈。太难解释过程了，动画教程：动画演示 单调栈 739.每日温度 class Solution { public: vector<int> dailyTemperatures(vector<int&...

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。 输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]输出：16解释：它的周长是上面图片中的 16 个黄色的边 思路：看下黄色边的特点，遇到边界+1，遇到水+1. class Solution { public: int islandP...

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。 输入：grid = [ ["1", "1", "1", "1", "0"], ["1", "1", "0", "1", "0"], ["1...

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 输入：height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]输出：6解释：上面是由数组[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 方法1： 维护单调递减栈，存放的是索引。 大于栈顶时开始计算雨水。栈顶能盛的雨水：先出栈存为a(min(右边大于它的height[i], 左边大于它的height[temp.top()]) - 它的高度height[a] ...

题目描述 给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。 示例:输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 好像应该用贪心算法比较好，所以暂且放置，学到了回到改。 思路：用动态规划做的，dp[i]保存跳到i需要的最小的步数往前看，j从i-1开始往前遍历，比较满足跳跃的第j步里哪个最小，就+1。 class ...

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。 示例 1：输入：nums = [2,3,1,1,4]输出：true解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。 思路：只求结果，考虑动态规划。dp[i]表示第i步是否可抵达 dp[i]=dp[j]&&(nums[j]>=i-j)第i步可以抵达的条件： 在之前的第j步可以抵达=dp[j]为true 第j步可以达到第i步，(nums[j]>=i-j)，第j步可迈...

题目描述 给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。回文串不一定是字典当中的单词。 示例1：输入："tactcoa"输出：true（排列有"tacocat"、"atcocta"，等等） 注意看题，这个是可以重新排列的所以需要满足字符串里的字符个数都是偶数 或者 有一个是奇数所以判断所有字符出现的次数，奇数次<=1是可以构成回文排列 哈希表计数 class Solution { public: bool canPermutePal...

题目描述 定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示： int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。输入两个整数，分别表示二位数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证...

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode...

题目描述 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 思路：count指针是不变量，其之前的元素一定是非目标元素for循环遍历，不等于val时继续往后移，等于val时，后count指针位置的值进行交换，然后count++，继续遍历 这样，非val值都会被交换到count之前，输出count表示个数 class Solution { public: int removeEl...

题目描述 有一只兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子，假如兔子都不死，问每个月的兔子总数为多少？本题有多组数据。 动态规划每个月的兔子数量为dp[i]dp[i]=dp[i-1]+dp[i-2] 其中i>=3兔子=上个月的+新出生由于第三个月才能开始生育，新出生的兔子取决于两个月前兔子的数量 #include<iostream> #include<vector> using namespace std; int main(){ int month; while(cin>>month){ ...

题目描述 将两个整型数组按照升序合并，并且过滤掉重复数组元素。输出时相邻两数之间没有空格。请注意本题有多组样例。 感觉解法比较多 STL直接用set自动排序+去重map自动排序，输出firstvector的sort排序，然后unique+erase去重，或者双指针自己写个去重 #include<iostream> #include<set> using namespace std; int main(){ int num1,num2; int temp; while(cin>>num1){ set<int&g...

题目描述 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 输入：[7, 1, 5, 3, 6, 4]输出：5 虽然并没有用动态规划用dp[i]表示第i天卖出时能拿到最多的钱，此时肯定是当天的股票价格减去之前的股票价格的最小值时挣得最多所以用min变量保存到第i天时股票的最小值用dp[i] = prices[i] - min因为要求最大值，...

题目描述 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 动态规划思路：易错点：注意第一行和第一列的值！！！第一列：dp[i][0] = dp[i - 1][0] + grid[i][0];第一行：dp[0][j] = dp[0][j - 1] + grid[0][j];其他：dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]; class Solution { public: int minPathSum(vector<vector<int...