题目分析 题目给出了我们一个数字字符串，和一个数字k 题目说我们可以从字符串中去掉k位数字，返回最小数字字符串的方案 方法一：单调栈 实现思路 我们需要维护一个单调栈，将数字字符串每一个元素进行入栈处理（在这里我们用列表表示单调栈） 当取到的数字字符大于栈顶的时候，我们让数字正常入栈 当取到的数字字符小于栈顶的时候，我们就将栈顶元素出栈，并且一直比较新的栈顶元素，直到栈顶元素与取得元素相等或更小为止 出栈则说明我们去掉这个数字字符，相应k的值就需要自减 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param num st...

题目分析 题目给出了我们一个列表 我们要返回一个列表，其中列表的每一项代表列表该数字左边的所有数字和右边的所有数字的乘积（不含本身），不使用除法操作 方法一：维护两个乘积列表 实现思路 我们通过一次遍历，维护一个left和一个right列表 对于每一个i位置的数字，left[i]表示数字nums[i]左边所有的数字之积，right[i]表示数字nums[i]右边所有的数字之积。 在计算返回数组时，根据位置将left[i]和right[i]乘在一起即可 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums in...

题目分析 题目给出了我们一个只包含0，1，2三种数字的列表 题目要求我们将所有的0重新安排到列表左边，1在中间，2在右边，请返回重新组织后的列表 方法一：排序 实现思路 调用sort()函数对列表直接排序可以得到最终结果 （在快速通过竞赛或者机试的时候可以用，但是并不是题目考察内容） # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param colors int整型一维数组 # @return int整型一维数组 # class Solution: def sortColor(self , colors: ...

题目分析 题目给出了我们一条链表得头结点指针，和一个整数值k 题目要求我们根据给出得整数值k，开始将链表最后一个节点添加到头节点之前，重复此过程k次，返回当前的链表头节点 方法一：快慢指针 实现思路 我们先用一个指针将链表长度计算出来 然后将给定的k对链表长度取余，减少时间代价 先让快指针从头节点开始向前迭代k步 再让慢指针从起点出发，和快指针同时向后迭代 到快指针迭代到链表尾，慢指针停留的位置即新的链表末尾节点，慢指针下一个节点即新链表的首节点，最终返回新链表头即可 # class ListNode: # def __init__(self, x): # ...

题目分析 题目给出我们一个数组，表示每天的温度值 题目要求我们返回一个数组，每个元素表示，对于该天的温度，再经过几天温度比该天温度高，将这个天数的差值作为该元素放到返回数组中。如果不存在更高的温度了，则用0填充 方法一：暴力遍历 实现思路 我们外层循环遍历每一天 内层循环遍历该天之后的所有天数 判断该天之后是否有更高的温度出现，如果有，则添加下标差j-i到我们的res数组中，如果没有则添加0到res数组中 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 每日温度 # @param dailyTemperatures int...

题目分析 题目给出了我们一棵二叉树，其根节点作为输入 题目要求我们返回该二叉树中最大的宽度，即返回二叉树某一层中，从最左边的节点到最右边的节点最远的距离（包括它们之间的空节点也要计入距离） 方法一：DFS深度优先遍历 实现思路 我们将根节点root编号(pos)记为1，因此在该树中，对于任何一个节点node，我们将其和子节点的编号设置为 pos(node.left)=pos(node)×2pos(node.right)=pos(node)×2+1pos(node.left) = pos(node) × 2\\ pos(node.right) = pos(node)×2+1pos(...

题目分析 题目给出了一个target目标钱数，和一个nums数组，其中元素代表是硬币的币值 题目说不同硬币的币值可以无限次挑选 题目要求返回凑出target目标数的硬币挑选方案的数量 方法一：动态规划 实现思路 我们规定dp[i][j]表示在前i种硬币中挑选，凑出j的方案数，最终返回结果是dp[len(nums)][target] 因此对于每一个dp[i][j]我们知道 第i个硬币选择0个，有dp[i][j] = dp[i-1][j] 第i个硬币选择1个，有dp[i][j] = dp[i-1][j-nums[i-1]] 第i个硬币选择k个，有dp[i][j] = dp[i-1][...

题目分析 题目给出我们一个大小为n*m的二维数组矩阵 题目要求我们按照对角线的访问顺序访问二维数组，并且返回访问顺序的列表 方法一：分类讨论 实现思路 由于对角线访问的时候存在两个方向，因此我们记录一个方向转换的标记，通过奇偶来确定当前应该遍历的方向，偶数代表从左下遍历到右上的方向，奇数代表从右上遍历到左下的方向 由于不知道n和m的大小，我们可以将一个矩阵分为四部分进行讨论 访问左上三角形区域，即当前访问的任何元素mat[i][j]，都有i<=n, j<=m，此时可以确定的是每次新的方向开始的时候，奇数起点行值为0，偶数起点的列值为0 当矩阵m>n时，列比行长...

题目分析 题目给出一课树的根节点作为输入 题目要求我们判断该树是否为完全二叉树 方法一：层序遍历 实现思路 对于完全二叉树，我们关心该树每一层从左到右是否是完全连续的 因此层序遍历可以按照层的规则进行遍历 在某一层的遍历过程中，如果我们遇到了一个空指针位置，则继续遍历有两种情况 如果继续遍历，后面的节点全都是空指针节点，则说明该树是完全二叉树 如果继续遍历，后面的节点重新出现了非空节点，则说明该树非完全二叉树 # class TreeNode: # def __init__(self, x): # self.val = x # ...

题目分析 题目给出我们一个数组，数组中每个数字表示当前位置能够向数组末尾前进的步数 题目要求我们判断给定数组下，是否能从数组开始位置到达末尾位置，返回判断的结果 方法一：动态规划（超时） 实现思路 我们用一个一维的dp数组，dp[i]=1表示当前位置i可以到达 我们遍历nums数组，针对位置i的数字 如果此时dp[i]=0则说明前面的移动过程未能到达当前位置，则返回False 如果此时dp[i]=1，则根据nums[i]的大小，向后更新nums[i]个可到达位置，将dp数组中对应位置标记为1 最后判断dp[n-1]是否为1即可 需要额外注意下一些边界条件的设置，比...

题目分析 题目给出我们一棵树的根节点 题目要求我们返回这棵树的最大的直径，其中直径定义为，树上任意两个叶子节点路径长度的最大值 方法一：（双重递归）递归确定深度+递归确定直径 实现思路 我们用两个递归函数来得到最终的最长直径结果 递归函数一depth 目标：获取当前节点的深度 返回条件：当前节点为空None时返回深度为0 递归主体：递归左子树获取其深度l，递归右子树获取其高度r，因此当前节点的深度为max(l,r)+1 递归函数二diameterOfBinaryTree 目标：获得当前节点为根的树中最大直径 返回条件：当前节点为空None时返回树中最大直径为0 递...

题目分析 题目给出了我们两个递增数组 题目要求我们返回两个数组中所有数字的中位数 方法一：双指针归并 实现思路 由于我们知道两个数组是升序的，我们用双指针的方式对两个表进行遍历 比较两个指针所指数字的大小选择是否要移动指针，进行不断迭代 直到两个指针所指数字某一个指针率先达到了中位数目标位置，则返回最终的数字 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param arr1 int整型一维数组 # @param arr2 int整型一维数组 # @return int整型 # class Solution:...

题目分析 题目给出我们两个升序数组，并给出一个target值 题目要求我们考虑两个升序数组，两者第target个小的数字。 方法一：合并后排序 实现思路 首先将两个列表数字全部合并起来 然后对整个合并后的列表进行排序 最后直接随机访问下标为target-1的目标数字即可 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param arr1 int整型一维数组 # @param arr2 int整型一维数组 # @param target int整型 # @return int整型 # class Soluti...

题目分析 题目给出了我们一个二维数组，其中标为1的位置含义为出发点，标为2的位置的含义为终点，标记为-1的位置含义为不可达点，其他位置数字为0，表示可以经过的点 从出发点到终点，一定有最短的路径长度，题目要求我们返回最短的路径长度的路径方案数。 方法一：DFS深度优先遍历 实现思路 我们需要维护一个命名为mp的map结构，表示（当前达到商家的路径长度，该长度对应方案数量）的映射集合，由于map的有序性，最终返回的结果为mp.begin()->second 我们可以用深度优先搜索的思路，从经理所在的位置出发向四个方向进行深度搜索 dfs递归函数表示的含义为： 在Ci...