算法题1020

/**

• @param {number[][]} matrix

• @return {void} Do not return anything, modify matrix in-place instead.

• n维数组旋转 90 度算法
  */
  export const rotate = function (matrix: number[][]) {
  let n = matrix.length

  // matrix[x][y] => matrix[y][n - 1 - x]
  const changeItem = (num: number, x: number, y: number, rodateTime: number, isOnce?: boolean) => {
  // 终止条件
  rodateTime++
  if (num === matrix[x][y] && !isOnce && rodateTime > 4) return

   let space = matrix[y][n - 1 - x]
  
   matrix[y][n - 1 - x] = num
   changeItem(space, y, n - 1 - x, rodateTime)
  1
  2
  3
  4

  }

  for (let j = 0; j < Math.floor(n / 2); j++) {
  let rodateTime = 0;
  for (let i = j; i < n - 1 - j; i++) {
  changeItem(matrix[j][i], j, i, rodateTime, true)
  rodateTime = 0
  }
  }

  return matrix
  };

// ((())) 暴力解法找到所有的夸号组合
export const findkhByQuery = (num: number = 3) => {
/**
* arr.push()
* 怎样组合呢？ (())()
* ( + )()()
* 思路：一个夸号去移动
*
* ()()() 取出第1个 从 0 移动到 最后一位
* let str = ‘(’
* )()() 发现 不管第一个如何移动 只有第一次才行 移动到右边后发现有首位是 右夸号结束移动
*
* (()() 取出第2个 ‘)’ 从 0 移动到 最后一位
* let str = ‘)’
*
* (()() 取出第3个 ‘)’ 从 0 移动到 最后一位
* let str = ‘(’
*
*
* value
*/
let initStr = ‘’;
let arr = []
for (let i = 0; i < num; i++) {
initStr += “()”
}
let n = initStr.length
let map: any = {}

const isValid = (str: string): boolean => {
    if (!str || str[0] === ')') {
        return false
    }

    let stack = []
    for (let i = 0; i < str.length; i++) {
        if (str[i] === '(') {
            stack.push('(')
        }
        if (str[i] === ')') {
            let x = stack.pop()
            if (!x) {
                return false
            }
        }
    }

    if (stack.length == 0) {
        return true
    }

    return false
}

// 可以再套一个循环 用于决定要 去几个字符串 
for (let k = 0; k < num * 2; k++) {

    for (let i = 0; i < num * 2; i++) {
        // 从 0 移动到最后一位
        // let val = initStr[i]
        // 取出需要拿出来的字符串
        let val = initStr.slice(0, k + 1)
        console.log(val, 'val');

        // 取到切割剩下的
        // 'abcdef' abc cde 
        let newStr = initStr.slice(k + 1, n)

        for (let j = 0; j < num * 2; j++) {
            let moveRes = newStr.slice(0, j) + `${val}` + newStr.slice(j, n)
            // debugger

            // debugger
            if (!map[moveRes]
                && isValid(moveRes)
            ) {
                map[moveRes] = moveRes
                arr.push(moveRes)
            }
            // arr.push(moveRes)
        }
    }
}
console.log(arr, 'arr');
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

}

// console.log(findkhByQuery(3));

/**

• @param {string} s
• @return {string[][]}
• 回文字串
• 思路：列出所有的字串

*/
var partition = function (s: string) {
let arr: string[][] = []
arr.push(s.split(‘’))

for (let i = 0; i < s.length; i++) {
    let subitem: string[] = []
    for (let j = i + 1; j < s.length; j++) {

        let val = s.substring(i, j + 1)

        if (val.split('').reverse().join('') === val) {
            /* 
            如何做到自动补全的功能？ abcde bcd => a,bcd,e
            * abacd_aba => ,aba,c,d,_,aba,
            * abacd_abaDDC => ,aba,c,d,_,aba,D,D,C
            * 切掉空的
            */
            let ns = s.replace(val, `,${val},`)
            // 去掉首尾的，号
            if (ns.startsWith(',')) {
                ns = ns.substring(1, ns.length)
            } else if (ns.endsWith(',')) {
                ns = ns.substring(0, ns.length - 1)
            }
            let resItem: any[] = []

            // aba,cd_,aba => aba,c,d,_,aba
            ns.split(',').forEach(item => {
                if (item !== val) {
                    resItem = [...resItem, ...item.split('')]
                } else {
                    resItem.push(item)
                }
            })
            subitem = resItem

        }
    }
    if (subitem.length) {
        arr.push(subitem)
    }
}


return arr
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

};

console.log(partition(“fff”));

// 模板字符串替换
const template =

return template
1

[0,-1,1]
[1]

f( [1, 2, 3] ) = f([1, 2]) 和 3 的排列
f( [1, 2]) = f([1]) 和 2 的排列
f( [1] ) = [1]

思路：f(12345) = f(1234) 和 5 组合起来的数组
1
2
3
4
5
6
7
8

const dfs = (a: number[]): any[] => {
    let n = a.length
    if (n == 1) {
        return [a]
    }

    let res: any[] = []
    let fontArr = a.slice(0, n - 1) // [1, -1]
    let lastStr = a.slice(n - 1, n)[0] //  0

    dfs(fontArr)?.forEach(it1 => {
        // [1, -1] [-1, 1] 中 使用 0 来移动位置
        for (let i = 0; i < it1.length + 1; i++) {
            res.push([...it1.slice(0, i), lastStr, ...it1.slice(i, it1.length)])
        }
    })

    return res
}

return dfs(nums)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21