题意整理 n个加油站排成一圈，每一个站点有对应的油，存储在gas数组，从一个站点走到下一个站点需要若干油量，存储在cost数组。 问能否绕环路行驶一周，如果可以则返回出发的加油站编号，如果不能，则返回-1。 方法一（枚举起始站点） 1.解题思路 首先枚举所有可能的起始加油站。如果剩余油量大于等于0，则进入内层循环，确定当前起始站点是否合法。 每次检查当前剩余油量rest。如果小于0，则不合法，终止循环。如果每次都大于等于0，则当前起始站点合法，返回对应加油站。 2.代码实现 import java.util.*; public class Solution { /** ...

题意整理 给定一个地图CityMap及它的行长度n和列长度m，其中1代表经理位置，2代表商家位置，-1代表不能经过的地区，0代表可以经过的地区。 求从经理位置出发到达商家位置的所有最短路径有多少种。 方法一（广度优先搜索） 1.解题思路 首先定义一个队列，用于广度优先搜索。定义一个标记数组，用于标记该位置是否访问过。定义一个距离数组dist，用于记录起点到当前位置的最短距离。定义一个dp数组，用于记录起点到当前位置最短距离的方案数。 然后将起点坐标放入队列，并初始化方案数和标记，进行搜索。 搜索的过程中，需要往上下左右四个方向进行搜索。如果没有越界，并且不在障碍区，分两种情况进行讨论。一...

题意整理 给定两个升序的数组arr1和arr2。 求这两个数组合并后的下中位数。 方法一（归并） 1.解题思路 本题需要求两个有序数组合并后的下中位数，假设合并后数组的长度为m+nm+nm+n，则下中位数刚好是新数组中第(m+n)/2(m+n)/2(m+n)/2小的数，令K等于(m+n)/2(m+n)/2(m+n)/2，则可以将问题转化为求新数组中恰好第K小的数。 执行K次循环，每次将较小的值赋值给res。 新建两个变量id1、id2，id1是arr1数组游标，id2是arr2数组游标。如果id1和id2都没有到末尾，将两者指向的值中较小的赋值给res，并后移游标。 如果id1到达末尾，...

题意整理 给定两个升序的数列arr1、arr2，和一个整数target。 找出两个数列中第K小的值，其中K等于target。 方法一（归并） 1.解题思路 执行K次循环，每次将较小的值赋值给res。 新建两个变量id1、id2，id1是arr1数组游标，id2是arr2数组游标。如果id1和id2都没有到末尾，将两者指向的值中较小的赋值给res，并后移游标。 如果id1到达末尾，则继续将arr2数组的值赋值给res。否则，将arr1数组的值赋值给res。 有一种简单的做法是直接将两个数组的值存储到一个新数组中，然后对新数组进行排序，索引为K-1的值即是第K小的数。但是如果两个数组的长度...

题意整理 给定一个数组nums和一个目标值target。 从nums中选出三个数，使它们的和尽量接近目标数，即三数之和与目标数的差的绝对值尽可能小。 方法一（暴力循环） 1.解题思路 直接三层循环，遍历所有可能的第1个数、第2个数、第3个数，每次选择绝对值尽可能小的，并更新对应的三数之和。 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型一维数组 ...

题意整理 给定一个非负索引值num，返回杨辉三角中从上到下第num层。索引值从0开始。 杨辉三角中，每个数是左上方和右上方的数之和。 方法一（数组模拟） 1.解题思路 首先新建一个二维数组，用于存储所有数字。遍历每一层，确定每一层子数组，根据每个数等于左上方和右上方的数之和，确定每一层子数组的每一个值。最后返回第num层的子数组即可。 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @pa...

题意整理 给定一个字符串s，字符串s只包含三种字符: '('，'*'，')'。 判断s是不是一个合法的括号字符串。 合法的条件是：每一个左括号必须有一个右括号与之匹配，每一个右括号必须有一个左括号与之匹配。匹配的左括号必须在右括号前面。'*'号可以视为左括号、可以视为右括号、也可以视为空字符。空字符视为合法的括号字符串。 方法一（栈） 1.解题思路 新建两个栈left、star，分别记录未匹配的左括号和'*'号对应下标 遍历整个字符串，如果是左括号，则将下标入left栈。如果是'*'号，则将下标入star栈。如果是右括号，先拿left栈里元素抵消，再拿star栈的元素抵消，都没有，则返回...

题意整理 给定一个整数数组nums和一个整数target。 返回该数组能构成多少种不同的表达式等于target。 方法一（动态规划） 1.解题思路 本题可以转化为一个0-1背包问题。 我们将前面添加号的分为一组，记其累加和为a，将前面添减号的分为一组，记其累加和为b。如果能构成一个表达式，使得结果为target，则有a+b=sum,a−b=targeta+b=sum,a-b=targeta+b=sum,a−b=target，其中sum为数组中所有数字的累加和。继续化简一下，可以得到：a=(sum+target)/2a=(sum+target)/2a=(sum+target)/2。如果数组中...

题意整理 给定一个整数数组，数组中有一个数出现了一次，其他数出现了两次。 找到只出现一次的数。 方法一（哈希表） 1.解题思路 新建一个哈希表，然后遍历nums数组。如果出现过num，则从map中移除，如果没出现，则放入map中。最后留在map的一定是只出现一次的数字。 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @retur...

题意整理 A和B玩一个游戏。 桌子上有n个石头，A、B轮流从桌子上取石头，每一回合可以取1-3个，谁最先取完石头则获胜，否则另一方获胜。 给定石头数n，判断最终谁会获得胜利。 方法一（动态规划） 1.解题思路 状态定义：dp[i]dp[i]dp[i]表示i个石头时是否能获胜。 状态初始化：i为1、2、3时，先手必定获胜，赋值为true。 状态转移：只要检查i-1、i-2、i-3个石头时是否能赢，即可判断当前i个石头是否能赢。即dp[i]=!dp[i−1]∣∣!dp[i−2]∣∣!dp[i−3]dp[i] =!dp[i-1]||!dp[i-2]||!dp[i-3]dp[i]=!dp[i−1...

题意整理 给定一个逆波兰表达式，表达式中仅包含加减乘除和数字。 求表达式的值。 方法一（栈） 1.解题思路 逆波兰表达式求值的过程总是先列出运算符前面两个数字，然后将这两个数字进行相应运算，得到一个新的数字，这个数又与后面的数进行相应运算，直到结束。 所以，可以先新建一个栈，当遇到数字时，直接压入栈中，遇到运算符时，先取出栈顶的两个数字，进行相应运算，再压回栈中。最后栈中剩下的那个元素即是表达式的值。 图解展示： 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿...

题意整理 给定一个二叉搜索树，树上的节点各不相同。 现在要将其修改为累加树，使每个节点的值变成原树中更大节点之和。 方法一（递归） 1.解题思路 由于二叉搜索树的左子树节点值总是小于当前节点，右子树节点值总是大于当前节点。所以按右、根、左顺序遍历时，树中的节点值一定是从大到小变化的，只要在遍历的过程中记录当前累加和，即可得到当前节点即将被替换的值。 图解展示： 2.代码实现 import java.util.*; /** * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNo...

题意整理 给定一个只包含正整数的数组nums。 问是否能从这个数组取出若干个数使得取出的数之和和剩下的数之和相同。 方法一（动态规划） 1.解题思路 可以转化为0-1背包问题。只要从数组中找出若干个数，使得这些数的和等于所有数之和的一半即可。假设数组所有数的累加和为sum，则背包的容量为sum/2。在转换之前，可以提前过滤掉一些不合法的情况。当sum为奇数时，显然不能分成相等的两半，直接返回false，当数组最大值大于sum/2时，显然也不能分成相等的两半，直接返回false。 状态定义：dp[i][j]dp[i][j]dp[i][j]表示i个元素内，是否能凑成目标和为j。 状态初始化：...

题意整理 给定一个整数数组，找出一个连续子数组，将这个子数组升序排列后整个数组都变为升序数组。 求满足条件的最短的连续子数组的长度。 方法一（排序） 1.解题思路 首先定义一个新数组arr，将原数组的值复制到新数组。 对原数组nums进行排序。 从前往后，找到第一个不相等的元素位置，记为子数组的起点。从后往前，找到第一个不相等的元素位置，记为子数组的终点。计算起点、终点距离，即可知道对应子数组的长度。 图解展示： 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，...