leetcode | JavaScript | 随笔No.1

剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。  

• 1. 输入：[3,4,5,1,2]
  • 输出：1
• 1. 输入：[2,2,2,0,1]
  • 输出：0

var minArray = function (numbers) {
    for (let i = 0; i < numbers.length-1; i++) {
        if (numbers[i] > numbers[i + 1]) {
            return numbers[i + 1];
        }
    }
    return numbers[0];
};

剑指 Offer 12. 矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。

• 1. 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
  • 输出：true
• 1. 输入：board = [["a","b"],["c","d"]], word = "abcd"
  • 输出：false

var exist = function (board, word) {
    var n = board.length;
    var m = board[0].length;

    for (var i = 0; i < board.length; i++) {
        for (var j = 0; j < board[0].length; j++) {
            if (dfs(i, j, 0)) {
                return true;
            }
        }
    }

    function dfs(x, y, k) {
        if (x >= n || y >= m || x < 0 || y < 0 || word[k] !== board[x][y]) {
            return false;
        }
        if (k === word.length - 1) {
            return true;
        }
        var tmp = board[x][y];
        board[x][y] = '-';
        var res = dfs(x + 1, y, k + 1) || dfs(x - 1, y, k + 1) || dfs(x, y + 1, k + 1) || dfs(x, y - 1, k + 1);
        board[x][y] = tmp;
        return res;
    }

    return false;
};

剑指 Offer 14- II. 剪绳子 II

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]k[1]...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

• 输入: 10
• 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

var cuttingRope = function (n) {
    if (n == 2) return 1;
    if (n == 3) return 2;
    if (n == 4) return 4;
    if (n == 5) return 6;
    let res = 1;
    while (n > 4) {
        res %= 1000000007;
        res = (res * 3) % 1000000007;
        n -= 3;
    }
    if (n == 4) res = (res * 4) % 1000000007;
    if (n == 3) res = (res * 3) % 1000000007;
    if (n == 2) res = (res * 2) % 1000000007;
    return res;
};

剑指 Offer 15. 二进制中1的个数

输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

• 输入：00000000000000000000000000001011
• 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

var hammingWeight = function (n) {
    let res = 0;
	while (n) {
		++res;
		n &= n - 1;
	}
	return res;
};

剑指 Offer 16. 数值的整数次方

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

• 1. 输入: 2.10000, 3
  • 输出: 9.26100
• 1. 输入: 2.00000, -2
  • 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25

var myPow = function (x, n) {
    let res = 1.0
    let t = n
    while (n) {
        if (n & 1) { res *= x }
        x *= x;
        n /= 2;
    }
    return t > 0 ? res : 1.0 / res;
};

剑指 Offer 17. 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

• 输入: n = 1
• 输出: [1,2,3,4,5,6,7,8,9]

var printNumbers = function (n) {
    let c = Math.pow(10, n) - 1
    let arr = [...Array(c)].map((k, i) => i + 1);
    return arr
};

剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

• 输入: head = [4,5,1,9], val = 5
• 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

var deleteNode = function (head, val) {
    if (head == null) return head;
    let cur = head
    let pre = new ListNode()
    if (cur.val === val) return head.next

    while (cur.val != val) { pre = cur; cur = cur.next }
    pre.next = pre.next.next
    return head
};

剑指 Offer 20. 表示数值的字符串

• 判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。

var isNumber = function (s) {
    return /^(\+|-)?(((0|[1-9])?[0-9]+\.{0,1})|\.[0-9]+)[0-9]*((e|E)(\+|-)?[0-9])?[0-9]*$/.test(s.trim())
};

205 同构字符串

给定两个字符串 s 和 t，判断它们是否是同构的。

• 输入: s = "egg", t = "add"
• 输出: true

var isIsomorphic = function (s, t) {
    if (s.length !== t.length) return false
    s = s.split('')
    t = t.split('')
    let m = new Map()
    let n = new Map()

    s.forEach((_, i) => {
        m.set(_, t[i])
    })
    t.forEach((_, i) => {
        n.set(_, s[i])
    })
    for (let i = 0; i < t.length; i++) {
        if (m.get(s[i]) != t[i] || n.get(t[i]) != s[i]) return false
    }
    return true
};

206 反转列表

• 输入: 1->2->3->4->5->NULL
• 输出: 5->4->3->2->1->NULL

var reverseList = function (head) {
    let p, q
    p = head
    q = null
    while (p) {
       let t = p.next
       p.next = q
       q = p
       p = t
    }
    return q
};