// 36. 有效的数独
function isValidSudoku(board: string[][]): boolean {

    function isNum(n:string):boolean{
       return n!='.'
    }

    function getSquare(i:number,j:number):number{
        const row = Math.floor(i/3)
        const col = Math.floor(j/3)
        return row*3+col
    }

    const row:Array<Set<number>> = new Array(9).fill(null).map(v=>new Set())
    const col:Array<Set<number>> = new Array(9).fill(null).map(v=>new Set())
    const square:Array<Set<number>> = new Array(9).fill(null).map(v=>new Set())

    for(let i=0;i<9;i++){
        for(let j=0;j<9;j++){
            if(isNum(board[i][j])){
                const n = board[i][j].charCodeAt(0) - '0'.charCodeAt(0)
                // console.log(n)
                const squareIndex = getSquare(i,j)
                if(row[i].has(n)||col[j].has(n)||square[getSquare(i,j)].has(n))
                 return false
                row[i].add(n)
                col[j].add(n)
                square[squareIndex].add(n)
            }
        }
    }
    return true
};

// 34. 在排序数组中查找元素的第一个和最后一个位置
function searchRange(nums: number[], target: number): number[] {
    //!不优雅
    let low = 0
    let high = nums.length-1
    let ans = [-1,-1]
    while(low<=high){
        let mid = Math.floor((low+high)/2)
        if(nums[mid]<target){
            low = mid + 1
        }else if(nums[mid]>target){
            high = mid - 1
        }else{
            let ll = low
            let hl = mid
            let lr = mid
            let hr = high
            let left = mid
            let right = mid
            //搜索左边开始的位置
            while(ll<=hl){
                let l_mid = Math.floor((ll+hl)/2)
                if(nums[l_mid]>target){
                    hl = l_mid-1
                }else if(nums[l_mid]<target){
                    ll = l_mid+1
                }else{
                    left = l_mid
                    hl = l_mid-1
                }
            }
            //搜索右边结束的位置
            while(lr<=hr){
                let r_mid = Math.floor((lr+hr)/2)
                if(nums[r_mid]>target){
                    hr = r_mid-1
                }else if(nums[r_mid]<target){
                    lr = r_mid+1
                }else{
                    right = r_mid
                    lr = r_mid+1
                }
            }

            ans[0] = left
            ans[1] = right
            break
        }
    }
    ans.indexOf
    return ans
};

// 530. 二叉搜索树的最小绝对差

class TreeNode {
      val: number
      left: TreeNode | null
      right: TreeNode | null
      constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
          this.val = (val===undefined ? 0 : val)
          this.left = (left===undefined ? null : left)
          this.right = (right===undefined ? null : right)
      }
}

function getMinimumDifference(root: TreeNode): number {
    let ans = Number.MAX_VALUE
    let preValue = root?.val
    function mid(root:TreeNode|null){
        if(root==null)return
        mid(root.left)
        // ans = Math.min(Math.abs(preValue-root.val))
        // preValue = root.val
        console.log(root.val)
        mid(root.right)
    }

    mid(root)
    return ans
};

// 91. 解码方法
function numDecodings(s: string): number {

    function isValid(str:string):boolean{
        return (str.length==1&&str.charAt(0)!='0')||
        (str.length==2&&
            (str.charAt(0)=='1'||(str.charAt(0)=='2'&&str.charCodeAt(1)>=48&&str.charCodeAt(1)<=54)))
    }

    const len = s.length

    
    const CacheStatus = -99
    let cache:Array<number> = new Array(len)
    cache.fill(CacheStatus)
    function search(start:number):number{
        if(cache[start]!=CacheStatus) return cache[start]

        let one = 0
        let two = 0
        if(start<len-1){
            one = isValid(s.substring(start,start+1)) ? search(start+1) : 0
        }else{
            one = isValid(s.charAt(start)) ? 1 : 0
        }

        if(start<len-2){
            two = isValid(s.substring(start,start+2)) ? search(start+2) : 0
        }else if(start == len -2){
            two = isValid(s.substring(start,start+2)) ? 1 : 0
        }

        cache[start] = one + two 
        return cache[start]
    }  

    function dp():number{
        const dp_table = new Array(len).fill(0)
        dp_table[0] = isValid(s.charAt(0))? 1 : 0
        dp_table[1] = isValid(s.substring(0,2))? 1: 0
        if(isValid(s.charAt(1))&&dp_table[0]==1) dp_table[1]++
        for(let i=2;i<len;i++){
            if(isValid(s.charAt(i))) dp_table[i] = dp_table[i-1]
            if(isValid(s.substring(i-1,i+1))) dp_table[i] += dp_table[i-2]
        }
        return dp_table[len-1]
    }

    return dp()
};

// LCP 12. 小张刷题计划
function minTime(time: number[], m: number): number {

    function check(t:number):boolean{
        let sum = 0
        let max = 0
        let hasUse = false
        let day = 0
        for(let i=0;i<time.length;i++){
            if(sum+time[i]<=t){
                sum+= time[i]
                max = Math.max(max,time[i])
            }else if(!hasUse){
                sum -= max
                sum += Math.min(max,time[i])
                hasUse = true
            }else{
                day++
                if(day==m) return false
                i--
                sum = 0
                max = 0
                hasUse = false
            }
        }
        return true
    }
    let low = 0
    let high = time.reduce((pre,cur)=>pre+cur,0)
    while(low<=high){
        let mid = Math.floor((low+high)/2)
        if(check(mid)){
            high = mid -1 
        }else{
            low = mid + 1
        }
    }
    return low
};


//24. 两两交换链表中的节点
function swapPairs(head: ListNode | null): ListNode | null {
    //!链表操作，先摘下来再重建链表
    // const hEvent = new ListNode(-1)
    // hEvent.next = null
    // const hOdd = new ListNode(-1)
    // hOdd.next = null
    // let event = true
    // let p = head
    // let pOdd:ListNode|null = hOdd
    // let pEvent:ListNode|null = hEvent
    // while(p!=null){
    //     if(event){
    //         pEvent.next = p
    //         pEvent = p
    //         p = p.next
    //         pEvent.next = null
    //     }else{
    //         pOdd.next = p
    //         pOdd = p
    //         p = p.next
    //         pOdd.next = null
    //     }
    //     event = !event
    // }
    // const newHead = new ListNode(-1)
    // newHead.next = null
    // p = newHead
    // event = false
    // pOdd = hOdd.next
    // pEvent = hEvent.next
    // while(pOdd!=null){
    //     if(event){
    //         p.next = pEvent!
    //         pEvent = pEvent!.next
    //         p= p.next
    //     }else{
    //         p.next = pOdd
    //         pOdd = pOdd!.next
    //         p = p.next
    //     }
    //     event = !event
    // }
    // if(pEvent!=null){
    //     p.next = pEvent
    // }
    // return newHead.next

    //!直接对链表操作
    const dummyHead = new ListNode(-1)
    dummyHead.next = head
    let temp = dummyHead
    while(temp.next!=null&&temp.next.next!=null){
        let n1 = temp.next
        let n2 = n1.next
        temp.next = n2
        n1.next = n2!.next
        n2!.next = n1
        temp = n1
    }
    return dummyHead.next
};