//31. 下一个排列
function nextPermutation(nums: number[]): void {
    /**
     * 从后开始找出第一个降序的数，
     * 再从后开始找到第一个比他大的数，交换
     * 她后面的数全是从后开始升序的，直接reverse就变成降序就是最小的
     */
    if(nums.length<=1) return
    const len = nums.length
    let start = 0
    for(let i=len-2;i>=0;i--){
        //找到第一个降序的位置
       if(nums[i]<nums[i+1]){
            for(let j=len-1;j>i;j--) {
                if(nums[j]>nums[i]){
                    [nums[i],nums[j]] = [nums[j],nums[i]]
                    break
                }
            }
            start = i+1
            break
       }
    }

    reverse(start)

    function reverse(start:number){
        let i = start
        let j = len
        while(i<j){
            [nums[i],nums[j-1]] = [nums[j-1],nums[i]]
            i++
            j--
        }
    }
};

// 621. 任务调度器
function leastInterval(tasks: string[], n: number): number {
    let count:number[] = new Array(26)
    count.fill(0)
    const A = 'A'.charCodeAt(0)
    tasks.forEach(v=>{
        count[v.charCodeAt(0)-A]++
    })
    count.sort((a,b)=>b-a)
    let res = 0
    while(count[0]!=0){
        for(let i=0;i<n+1;i++){
            if(count[0]==0)break
            if(i<26&&count[i]!=0)count[i]--
            res++
        }
        count.sort((a,b)=>b-a)
    }
    return res
};
// 406. 根据身高重建队列
function reconstructQueue(people: number[][]): number[][] {
    //排序 再插入
   people.sort((a,b)=>{
       return a[0]==b[0]?a[1]-b[1]:b[0]-a[0]
   })
   let ans = new Array(people.length)
   people.forEach(v=>{
       for(let i= people.length-1;i>v[1];i--){
           ans[i] = ans[i-1]
       }
       ans[v[1]] = v
   })
   return ans
};

// 399. 除法求值 
function calcEquation(equations: string[][], values: number[], queries: string[][]): number[] {
    // dfs做法，题解还有并查集做法
    let map:Map<string,Map<string,number>> = new Map()

    function find(from:string,to:string,vis:Set<string>):number{
        if(!map.has(from)) return Number.MIN_VALUE
        let tmp = map.get(from)!
        if(tmp.has(to)) return tmp.get(to)!
        for(let it of tmp){
            if(!vis.has(it[0])){
                vis.add(it[0])
                let res = find(it[0],to,vis)
                if(res!=Number.MIN_VALUE) return it[1]*res 
            }
        }
        return Number.MIN_VALUE
    }

    for(let i=0;i<equations.length;i++){
        let from = equations[i][0]
        let to = equations[i][1]
        let v = values[i]
        if(!map.has(from)){
            map.set(from,new Map())
        }
        if(!map.has(to)){
            map.set(to,new Map())
        }
        map.set(from,map.get(from)!.set(to,v))
        map.set(to,map.get(to)!.set(from,1/v))
    }
    let ans:number[] = []
    for(let i=0;i<queries.length;i++){
        let vis:Set<string> = new Set()
        let res = find(queries[i][0],queries[i][1],vis)
        ans.push(res==Number.MIN_VALUE?-1.0:res)
    }
    return ans
};

// 剑指 Offer 26. 树的子结构
function isSubStructure(A: TreeNode | null, B: TreeNode | null): boolean {
    //判断是否可以以当前节点为起点，B是A的子结构
    function isS(A:TreeNode|null,B:TreeNode|null):boolean{
        if(B==null) return true
        if(A==null) return false
        if(A.val!=B.val) return false
        return isS(A.left,B.left)&&isS(A.right,B.right)
    }
    if(B==null||A==null) return false
    return isS(A,B)||isSubStructure(A!.left,B)||isSubStructure(A!.right,B)
};