最大数

问题描述

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

示例 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;
    }
};

先序遍历构造二叉树

问题描述

返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。
(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍历 node.right。）

示例：
输入：[8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]

提示：
1 <= preorder.length <= 100
先序 preorder 中的值是不同的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal

思路

题解

组合总和 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();
        }

    }
};

最大二叉树

问题描述

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。
Example 1:

输入: [3,2,1,6,0,5]
输入: 返回下面这棵树的根节点：

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
注意:
给定的数组的大小在 [1, 1000] 之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-binary-tree

思路

题解