题目的主要信息： 这是一个经典的博弈。 你和你的朋友，两个人玩一个游戏。 桌子上有 n 个石头 你和你的朋友轮流取石头，你先手。 每一回合可以取 1~3 个石头。 轮到你的朋友时桌上没有石头则你获胜，否则你的朋友获胜。 你和你的朋友都尽力让自己获胜，如果你有方法必胜，则返回 true ，如果你的朋友有方法必胜，则返回 false 方法一： 采用递归（超时）。遍历三种情况，即取1个、取2个、取3个，然后再递归计算朋友的情况f(n−1)、f(n−2)、f(n−3)f(n-1)、f(n-2)、f(n-3)f(n−1)、f(n−2)、f(n−3)，如果朋友失败，则我们获胜。如果无论我们取多少个，朋...

题目的主要信息： 在一条环路上有 n 个加油站，其中第 i 个加油站有 gas[i] 升油，假设汽车油箱容量无限，从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。 请问能否绕环路行驶一周，如果可以则返回出发的加油站编号，如果不能，则返回 -1。 题目数据可以保证最多有一个答案。 方法一： 暴力法。遍历所有可能的起点，判断以i为起点是否能够行驶一周，判断的方法是，每到一个加油站就计算当前油箱的剩余量，如果油箱剩余量已经小于零，则表示以i为起点无法绕行一周。如果在行驶过程中没有出现油量小于零的情况，表示成功绕行一周。 具体做法： class Solution { ...

题目的主要信息： 现在有一个城市销售经理，需要从公司出发，去拜访市内的某位商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，他每次移动只能在左右中选择一个方向 或 在上下中选择一个方向，现在问他有多少种最短方案到达商家地址。 给定一个地图 CityMap 及它的 行长度 n 和 列长度 m ，其中1代表经理位置， 2 代表商家位置， -1 代表不能经过的地区， 0 代表可以经过的地区，请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于 10。 注意：需保证所有方案的距离都是最短的方案 方法一： 层次遍历。把路径看成一颗树，用层次遍历的方法保证路径都是最短。从起始位置出发，...

题目的主要信息： 给定两个升序的数组 arr1 和 arr2 ，求两个数组合并后的下中位数 注意：下中位数指在两个数组的数个数在偶数时取更小的 方法一： 先合并两个数组，然后再对合并后的数组排序，计算中位数的位置，最后直接返回中位数。 具体做法： class Solution { public: int getUpMedian(vector<int>& arr1, vector<int>& arr2) { for(int i=0;i<arr2.size();i++){//合并 arr1.push_ba...

题目的主要信息： 给定两个升序的数列 arr1 和 arr2 ，和一个整数 target ，请你找出两个数列中第 K 小的值。 方法一： 同时遍历两个数组，由于两个数组已经是升序排序的，所以每次我们两数相比取更小的，直到取到第k个数就结束循环。需要注意的是，如果在遍历过程中，有数组提前结束遍历，则在另一个数组中继续。 具体做法： class Solution { public: int findKthNum(vector<int>& arr1, vector<int>& arr2, int target) { int i = 0...

题目的主要信息： 给定一个数组 nums 和一个目标值 target ，请问从 nums 中选出三个数，使其之和尽量接近目标数，即三数之和与目标数只差绝对值尽可能小。 返回满足题面要求的三数之和。 方法一： 暴力法。用min保存已知最小的差绝对值，枚举所有可能的三个数组合，计算当前三数之和与目标数之间的差的绝对值，然后和min比较，在min中记录较小的值，同时sum记录已知最接近的三数之和，枚举结束后，返回sum。 具体做法： class Solution { public: int ClosestSum(vector<int>& nums, int target)...

题目的主要信息： 给定一个非负索引值 num ，请返回杨辉三角中从上到下第 num 层。索引值从 0 开始。 杨辉三角中，每个数是左上方和右上方的数之和。 方法一： 模拟杨辉三角。用二维数组res模拟杨辉三角。用一个for循环计算第i层的数字，因为杨辉三角中每个数等于左上方和右上方的数之和，所以从res 中取出第i-1层的所有数字，遍历计算第i层的数字。最后返回第num层的数字。 具体做法： class Solution { public: vector<int> getRow(int num){ vector<vector<int>&gt...

题目的主要信息： 给定一个整数数组nums和一个整数target，请你返回该数组能构成多少种不同的表达式等于target。 规则如下： 将数组里每个整数前面可以添加"+"或者"-"符号，组成一个表达式，例如[1,2]，可以变成”+1+2","+1-2","-1+2","-1-2"，这四种 只能添加"+"与"-"符号，不能添加其他的符号 如果构不成等于target的表达式，请返回0 保证返回的结果个数在整数范围内 方法一： 暴力递归。用count记录所有目标和表达式的个数，用dfs进行递归遍历所有可能的表达式。dfs的结束条件是遍历到了数组的末尾且表达式之和为target，否则分两种情况继续...

题目的主要信息： 给定一个字符串s，字符串s只包含以下三种字符: (，*，)，请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则: 左括号'('必须有对应的右括号')' 右括号')'必须有对应的左括号'(' 左括号必须在对应的右括号前面 *可以视为单个左括号，也可以视为单个右括号，或者视为一个空字符 空字符串也视为合法的括号字符串 方法一： 正序和倒序遍历两遍，分别把星号当做左括号和右括号。 从左往右遍历，把星号视为左括号，在遍历的过程中如果出现左括号数量比右括号少，表示该字符串不合法，返回false； 从右往左遍历，把星号视为右括号，在遍历的过程中如果出现右括号数量比左括...

题目的主要信息： 给定一个整数数组，数组中有一个数出现了一次，其他数出现了两次，请找出只出现了一次的数。 方法一： 暴力法。用哈希表统计数组中数字的出现次数。首先遍历一遍数组，统计每个数字nums[i]出现的次数，如果在哈希表中已有nums[i]，则将其删除；如果哈希表中没有nums[i]，则在哈希表中设置该数字的次数为1。统计完一轮次数后，哈希表中只有只出现一次的数字，再遍历一遍哈希表，即可找到只出现一次的数字。 具体做法： class Solution { public: int singleNumber(vector<int>& nums) { ...

题目的主要信息： 给定一个只包含正整数的数组 nums ，请问能否把这个数组取出若干个数使得取出的数之和和剩下的数之和相同。 方法一：递归（超时） 首先计算数组nums的元素之和sum，如果找得到等和子集，等和子集的和为sum/2，所以如果sum为奇数，则不可能找到等和子集。当sum为偶数时，用dfs函数进行递归处理，每次都对当前元素进行选或不选操作，直到找到和为sum/2的子集。 具体做法： class Solution { public: bool dfs(vector<int>& nums, int iter, int sum){ if(su...

题目的主要信息： 给定一个整数数组，找出一个最短的连续子数组，将这个子数组升序排列后整个数组都将是升序数组。 方法一：暴力法 遍历一遍所有子数组，用len保存符合题意的最短子数组长度。首先对子数组进行排序，然后判断该子数组排序后，整个数组否变为升序数组，如果子数组升序排列后整个数组都将是升序数组，和len中的子数组长度进行对比，保存较小的那个。 具体做法： class Solution { public: int findUnsortedSubarray(vector<int>& nums) { int len = nums.size(); ...

题目的主要信息： 给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度，如果可以跳到数组最后一个位置，请你求出跳跃路径中所能获得的最多的积分。 方法一： 暴力计算。dp数组为得分数组，dp[i]表示第i个位置最大得分。遍历一遍原始数组nums用来更新dp数组，遍历更新从i位置开始所有可以跳到的位置j的最大得分，dp[j] = max(dp[j],dp[i] + nums[j])。这样遍历一遍后dp[n-1]即为跳到最后一位可以得到的最大得分。 具体做法： class Solution { public: int maxJumpGra...

题目的主要信息： 给一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数，n > 1 并且 m > 1，m <= n ），每段绳子的长度记为 k[1],...,k[m]k[1],...,k[m]k[1],...,k[m] 。请问k[1]∗k[2]∗...∗k[m]k[1]*k[2]*...*k[m]k[1]∗k[2]∗...∗k[m]可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。 方法一： 暴力法。根据均值不等式： 当a1=a2=...=ana_1=a_2=...=a_na...