// 59. 螺旋矩阵 II
function generateMatrix(n: number): number[][] {

    //返回下次应该加入的值
    function generate(startX:number,startNum:number,matrix:number[][],rows:number):number{
        //右上角的列，左下角的行
        const r = rows - 1 - startX
        //向右
        for(let i= startX;i<=r;i++) matrix[startX][i] = startNum++
        //向下
        for(let i= startX+1;i<=r;i++) matrix[i][r] = startNum++
        //向左
        for(let i= r-1;i>=startX;i--) matrix[r][i] = startNum++
        //向上
        for(let i= r-1;i>startX;i--) matrix[i][startX] = startNum++
        return startNum
    }

    const rows = n
    const res:number[][] = new Array(n).fill(0).map(()=> new Array(n))
    // const res:number[][] = [...new Array(n)].map(()=>new Array(n))
    // const res:number[][] = []
    // for(let i=0;i<n;i++){
    //     res.push(new Array(n))
    // }
    let start = 0
    let num = 1
    while(start*2<rows){
        num = generate(start++,num,res,rows)
    }
    return res
};

// 8. 字符串转换整数 (atoi)
function myAtoi(s: string): number {
    enum CharType{
        NUM,
        WHITE,
        SIGN,
        OTHER
    }

    function getCharType(s:string):CharType{
        if(s==' ') return CharType.WHITE
        else if(s=='+'||s=='-') return CharType.SIGN
        else if(s.charCodeAt(0)>='0'.charCodeAt(0)&&s.charCodeAt(0)<='9'.charCodeAt(0)) return CharType.NUM
        return CharType.OTHER
    }

    enum Status{
        S_START,
        S_WHITE,
        S_SIGN,
        S_NUM,
        S_END
    }

    function generateStatusInfo():Map<Status,Map<CharType,Status>>{
        let map:Map<Status,Map<CharType,Status>> = new Map()
        //Start
        let s_m:Map<CharType,Status> = new Map()
        s_m.set(CharType.WHITE,Status.S_WHITE)
        s_m.set(CharType.SIGN,Status.S_SIGN)
        s_m.set(CharType.NUM,Status.S_NUM)
        s_m.set(CharType.OTHER,Status.S_END)
        map.set(Status.S_START,s_m)
        //white
        let s_w:Map<CharType,Status> = new Map()
        s_w.set(CharType.WHITE,Status.S_WHITE)
        s_w.set(CharType.SIGN,Status.S_SIGN)
        s_w.set(CharType.NUM,Status.S_NUM)
        s_w.set(CharType.OTHER,Status.S_END)
        map.set(Status.S_WHITE,s_w)
        //sign
        let s_s:Map<CharType,Status> = new Map()
        s_s.set(CharType.NUM,Status.S_NUM)
        s_s.set(CharType.SIGN,Status.S_END)
        s_s.set(CharType.OTHER,Status.S_END)
        s_s.set(CharType.WHITE,Status.S_END)
        map.set(Status.S_SIGN,s_s)
        //num
        let s_n:Map<CharType,Status> = new Map()
        s_n.set(CharType.NUM,Status.S_NUM)
        s_n.set(CharType.SIGN,Status.S_END)
        s_n.set(CharType.WHITE,Status.S_END)
        s_n.set(CharType.OTHER,Status.S_END)
        map.set(Status.S_NUM,s_n)
        //end
        return map
    }

    const transfer = generateStatusInfo()
    let n = 0
    let sign = 1
    let cur = Status.S_START
    for(let i=0;i<s.length&&cur!=Status.S_END;i++){
        const c = s.charAt(i)
        const type = getCharType(c)
        const m = transfer.get(cur) as Map<CharType,Status>
        if(m.has(type)) cur = m.get(type) as Status
        if(cur==Status.S_NUM){
            n*=10
            n+=Number.parseInt(c)
        }else if(cur==Status.S_SIGN){
            sign = c=='-'?-1:1
        }
    }

    if(cur==Status.S_END||cur==Status.S_NUM){
        const ans = n*sign
        const MIN = -2147483648
        const MAX = 2147483647
        if(ans>MAX) return MAX
        else if(ans<MIN) return MIN
        return ans 
    }
    return 0
};

// 231. 2的幂
function isPowerOfTwo(n: number): boolean {
    //!去掉最右边的1
    // return n>0&&(n&(n-1))==0 
    //！提取最右边的0
    return n>0&&(n&(-n))==n
};

//73. 矩阵置零
function setZeroes(matrix: number[][]): void {
    /**
     * O(1)空间
     * O(mn)时间
     * 把矩阵置0
     * 使用第 0 行和第 0列 进行标记
     * 
     * 先判断第0行和第0列是否需要置0
     * 然后用他们进行标记
     */
    const row = matrix.length
    const col = matrix[0].length
    let hasCol = false
    let hasRow = false
    for(let i=0;i<col;i++){
        if(matrix[0][i]==0){
            hasRow = true
            break
        }
    }
    for(let i=0;i<row;i++){
        if(matrix[i][0]==0){
            hasCol = true
            break
        }
    }

    for(let i=1;i<row;i++){
        for(let j=1;j<col;j++){
            if(matrix[i][j]==0){
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }

    for(let i=1;i<row;i++){
        if(matrix[i][0]!=0) continue
        for(let j=1;j<col;j++){
            matrix[i][j] = 0
        }
    }

    for(let j=1;j<col;j++){
        if(matrix[0][j]!=0) continue
        for(let i=1;i<row;i++){
            matrix[i][j] = 0
        }
    }

    if(hasRow){
        for(let i=0;i<col;i++){
            matrix[0][i] = 0
        }
    }

    if(hasCol){
        for(let i=0;i<row;i++){
            matrix[i][0] = 0
        }
    }
};

// 189. 旋转数组
function rotate(nums: number[], k: number): void {

    function reverse(l:number,r:number){
        while(l<r){
            [nums[l],nums[r]] = [nums[r],nums[l]]
            l++
            r--
        }
    }

    const len = nums.length
    k%=len
    const b_start = len - k
    reverse(0,b_start-1)
    reverse(b_start,len-1)
    reverse(0,len-1)
};

// 56. 合并区间
function merge(intervals: number[][]): number[][] {
    let ans:number[][] = []
    if(intervals.length!=0){
        intervals.sort((a,b)=>a[0]-b[0])
        let last:number[] = intervals[0]
        for(let i=1;i<intervals.length;i++){
            if(last[1]>=intervals[i][0]){
                last[1] = Math.max(intervals[i][1],last[1])
            }else{
                ans.push(last)
                last = intervals[i]
            }
        }
        ans.push(last)
    }
    return ans 
};

// 416. 分割等和子集
function canPartition_dp(nums: number[]): boolean {
    /**
     * 01背包
     * dp[i][j] = max(  dp[i-1][j] , dp[i-1][j-nums[i]] + nums[i]   )
     * 表示有j空间，有i件物品，能取得的最大值
     */
    const sum = nums.reduce((pre,cur)=>pre+cur,0)
    if((sum&1)==1) return false
    const target = sum / 2
    const len = nums.length
    let dp:Array<Array<boolean>> = new Array(len).fill(0).map(v=>new Array(target+1).fill(false))
    dp[0][nums[0]] = true
    for(let i=1;i<len;i++){
        for(let j=0;j<nums[i];j++){
            dp[i][j] = dp[i-1][j]
        }
        for(let j=nums[i];j<=target;j++){
            dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
        }
    }
    return dp[len-1][target]
};
//!记忆化搜索版
function canPartition(nums: number[]): boolean {

    //枚举，定义3个变量用来说明缓存当前的状态
    enum CacheStatus {
        NO_VALUE, //没有缓存值
        TRUE,    //可以
        FALSE   //不行
    }
    //计算nums数组值的和
    const sum = nums.reduce((pre,cur)=>pre+cur,0)
    //判断是不是偶数，奇数直接false
    if((sum&1)==1) return false
    const target = sum / 2
    const len = nums.length
    //生命一个缓存二维数组 len行 target列
    let cache:Array<Array<CacheStatus>> = new Array(len).fill(0).map(v=>new Array(target+1).fill(CacheStatus.NO_VALUE))
    
    /**
     * 搜索函数
     * @param index 搜索开始的nums数组下标
     * @param sum 
     * @return 判断从 index 到最后能否有等于sum的序列 
     */
    function dfs(index:number,sum:number):CacheStatus{
        //要搜索的值<0 或者 开始的下表超出nums的范围 返回 false
        if(sum<0||index>=cache.length||index<0) return CacheStatus.FALSE
        //找到了
        if(sum==0) return CacheStatus.TRUE
        //看看缓存里有没有当前要搜索的值，有直接返回 
        if(cache[index][sum]!=CacheStatus.NO_VALUE) return cache[index][sum]
        //加入当前值和不加入当前值的搜索结果
        const tmp1 = dfs(index+1,sum-nums[index])
        const tmp2 = dfs(index+1,sum)
        //刚才搜索的两个都是false的话当前的值也是false 否则 true
        cache[index][sum] = tmp1==CacheStatus.FALSE&&tmp2==tmp1?CacheStatus.FALSE:CacheStatus.TRUE
        //最后返回本次搜索的结果
        return cache[index][sum]
    }
    //从nums的第一个开始向后搜索有没有等于target的
    return dfs(0,target)==CacheStatus.TRUE
};