最大数

问题描述

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:
输入: [10,2]
输出: 210

示例 2:
输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-number

思路

将int数组转化为字符串，将字符串按从大到小的顺序排序，这里需要注意的是手写cmp比较字符串的大小时，用return str1+str2>str2+str1;将排序好的string类型的数组拼接成一个字符串。最后必须要进行除0操作。如"00"->"0","0123"->"123"

题解

class Solution {
public:
    static  bool cmp(string str1,string str2){
        return str1+str2>str2+str1;
    }
    string largestNumber(vector<int>& nums) {
        vector<string> tmp;
        for(int i=0;i<nums.size();i++){
            tmp.push_back(to_string(nums[i]));
        }
        string ret="";
        int n=tmp.size();
        sort(tmp.begin(),tmp.end(),cmp);
        for(int i=0;i<n;i++){
            ret+=tmp[i];
        }
        int flag=0;
        int location=0;
        for(int i=0;i<ret.size();i++){
            if(ret[i]!='0'){
                flag=1;
                location=i;
                break;
            }
        }
        if(flag==0) ret="0";
        else{
            string ret1="";
            for(int i=location;i<ret.size();i++){
                ret1+=ret[i];
            }
            ret=ret1;
        }
        return ret;
    }
};

长度最小的子数组

问题描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

示例: 
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum

思路

求出数组nums元素的总和，如果sum<s;那么直接返回0；
让i从0开始遍历，作为满足条件的连续子数组开始的位置，j从i开始遍历，当nums[j]的和大于s的时候，判断j-i+1是否小于min，更新min。最后返回min即可。

题解

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        for(int i=0;i<n;i++){
            sum=sum+nums[i];
        }
        if(sum<s){
            return 0;
        }
        int min=INT_MAX;
        for(int i=0;i<n;i++){
            int tmp=0;
            int flag=0;
            int j;
            for(j=i;j<n;j++){
                tmp+=nums[j];
                if(tmp>=s){
                    flag=1;
                    break;
                }
            }
            if(flag==1){
                if(j-i+1<min){
                    min=j-i+1;
                }
            }
        }
        return min;
    }
};

组合总和 III

问题描述

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。 

示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-iii

思路

这个题比较简单，用到的是回溯算法。
要解决的问题是在1~9之间选择k个数字，使得他们的和为n。每次选择的数字是1~9，因为不能重复，所以每次递归从上一次的位置加1开始，将每次递归的结果存到一个tmp数组里面，当tmp的size到k时，判断他们的和是否为n，如果为n，将tmp插入到ret，不管sum是否等于n，都要返回到上一层。返回到上一层后，千万别忘记，将sum减i，并且在tmp中弹出i；

题解

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ret;
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k,n,0,1);
        return ret;
    }
    void dfs(int k,int n,int sum,int location){
        if(tmp.size()==k){
            if(sum==n){
                ret.push_back(tmp);
            }
            return;
        }
        for(int i=location;i<=9;i++){
            tmp.push_back(i);
            sum=sum+i;
            dfs(k,n,sum,i+1);
            sum=sum-i;
            tmp.pop_back();
        }

    }
};

组合总和

问题描述

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。

说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
 
示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum

思路

本题用回溯算法，思路比较简单。
要解决的问题是，从组合中选取几个数，使得和为target。思路和以前的题没啥太大的区别，这里就不多做赘述了。
需要注意的两点是，1、没有个数的限制，只需要保证sum==target。所以，当深度达到sum>=target时，返回到上一层。这里同样需要注意，返回到上一层后将tmp.pop_back();将sum-=candidates[i];

题解

class Solution {
public:
    vector<int> tmp;
    vector<vector<int> > ret;
    int n;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        n=candidates.size();
        dfs(candidates,target,0,0);
        return ret;
    }
    void dfs(vector<int> &candidates,int target,int sum,int location){
       if(sum>target){
           return;
       } else if(sum==target){
           ret.push_back(tmp);
           return;
       }
       for(int i=location;i<n;i++){
           tmp.push_back(candidates[i]);
           sum+=candidates[i];
           dfs(candidates,target,sum,i);
           tmp.pop_back();
           sum=sum-candidates[i];
       }
    }
};

数组中的第K个最大元素

问题描述

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array

思路

用了排序，从大到小进行了排序
注意：在类中的函数要加static才能在生成对象前在类中调用

题解

class Solution {
public:
    static bool cmp(int left, int right) {
        return left > right;
    }

    int findKthLargest(vector<int> &nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end(), cmp);
        
        return nums[k - 1];

    }
};