题目描述 给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。 输入 : candies = [1, 1, 2, 2, 3, 3]输出 : 3解析 : 一共有三种种类的糖果，每一种都有两个。最优分配方案：妹妹获得[1, 2, 3], 弟弟也获得[1, 2, 3]。这样使妹妹获得糖果的种类数最多。 思路：弟弟妹妹所分得糖果的数量都是candyType.size()/2通过set去重得到糖果的种类数如果糖是各种各样的都有，种类数大于糖果数量的一半，那妹妹也只能拿到一半的糖果如果糖...

题目描述 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 输入：[1, 2, 3, 1]输出：4解释：偷窃 1 号房屋(金额 = 1) ，然后偷窃 3 号房屋(金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。 动态规划dp[i]表示最后一个偷i号房间时能拿到的最多金额 从0号房间开始dp[i]=max(dp[i-j]+nums[i]...

题目描述 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？ 动态规划 题目问总共有多少条不同的路径？所以dp[i][j]表示到达(i,j)点时的路径条数；dp[i][j]=dp[i-1][j]+dp[i][j-1] 所以到达该点的路径等于左边点的路径+上边点的路径和需要注意的是左边界和右边界，路径只有一条 class Solution { public: int uniquePaths(int m, int n)...

题目描述： 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。题目数据保证答案符合 32 位整数范围。 输入：nums = [1, 2, 3], target = 4输出：7解释：所有可能的组合为：(1, 1, 1, 1)(1, 1, 2)(1, 2, 1)(1, 3)(2, 1, 1)(2, 2)(3, 1)请注意，顺序不同的序列被视作不同的组合。 输出种类，不需要过程所以动态规划dp[i]表示总和为 i的元素组合的个数,dp[i]=sum(dp[i-j]) j是nums里的元素这里有...

题目描述 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 输入: 2输出 : 1解释 : 2 = 1 + 1, 1 × 1 = 1。 输入: 10输出 : 36解释 : 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 只问最大成绩，不问哪些数字，只求结果不要过程的用动态规划因为返回你可以获得的最大乘积，所以dp[i]表示拆分i后能获取的最大乘积 dp[i]=max( dp[j]*(i-j), j*(i-j)) 其中j属于[1,i) 后项是因为有的数字 拆分后最大乘积小于本身 比如dp[2]=1，那么会对...

题目描述 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。 题目问个数最少是多少个，这种只求结果不需要过程的就采用动态规划。dp[i]表示 和等于i时需要的最小的完全平方数的个数dp[i]=min(dp[i-j*j]+1) j属于(1,（根号n）)易错点是注意 当遇到平方数时，dp[i]=0，可以放在外面单独判断，或者等第二个for循环走到最后，j=sqrt(i)，为1 class Solution { public: int n...

题目描述 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：'A' -> 1'B' -> 2...'Z' -> 26要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"111" 可以将 "1" 中的每个 "1" 映射为 "A" ，从而得到 "AAA" ，或者可以将 "11" 和 "1"（分别为 "K" 和 "A" ）映射为 "KA&qu...

题目描述 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。 递归一种直接是数字判断，或者换成字符串判断易错点：还有一位时返回的是1，不是2，否则就重复了，如25 class Solution { public: int translateNum(int num) { return Count(to_string(num)); } int Count(string s) {...

题目描述 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6 动态规划dp[i]代表以元素nums[i]为结尾的连续子数组最大和只关注之前的最大解dp[i-1]和当前的数字nums[i] class Solution { public: int maxSubArray(vector<int>& nums) { vector<int> ...

题目描述 Redraiment是走梅花桩的高手。Redraiment可以选择任意一个起点，从前到后，但只能从低处往高处的桩子走。他希望走的步数最多，你能替Redraiment研究他最多走的步数吗？ 参考leetcode最长递增子序列动态规划：dp数组保存每部最优解 dp[i]=max(dp[i],dp[j]+1) 且j属于[0,i)class Solution { public: int lengthOfLIS(vector<int>& nums) { vector<int> dp(nums.size(),1); i...

序列I：15,123,456,786,453,46,7,5,3,665,453456,745,456,786,453,123（第一个15表明后续有15个整数）序列R：5,6,3,6,3,0（第一个5表明后续有5个整数）输出：30, 3,6,0,123,3,453,7,3,9,453456,13,453,14,123,6,7,1,456,2,786,4,46,8,665,9,453456,11,456,12,786说明：30----后续有30个整数3----从小到大排序，第一个R为0，但没有满足条件的I，不输出0，而下一个R是36--- 存在6个包含3的I0--- 123所在的原序号为0123-...

题目描述 功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）最后一个数后面也要有空格 从2开始，循环到根号x即可，余数为0时输出除数，因为有重复的所以要while循环知道除完结果为1为止另外还有一种情况就是本身就是质数的，只有1和它本身相乘可以，所以最后判断一下，如果不是除尽退出循环的的，输出本身 #include<iostream> #include<math.h> using namespace std; int main(){ long num; cin>>num;...

题目描述 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。 class Solution { public: string frequencySort(string s) { map<char,int> mymap; for(auto i:s) mymap[i]++; vector<pair<char,int>> mypair(mymap.begin(),mymap.end());//记住写法 sort(mypair.begin(),mypair.e...

题目描述 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 方法1： 用这道题默写了下三向切分的快排 class Solution { public: void quicksort(vector<int>& nums,int left,int right){ if(left>=right) return; srand(time(0)); int pivot = r...