24. 两两交换链表中的节点

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val, next) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.next = (next===undefined ? null : next)
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode} head
  10.  * @return {ListNode}
  11.  */
  12. var swapPairs = function(head) {
  13.     if (head === null || head.next === null) {
  14.         return head
  15.     }
  16.     let last = head.next
  17.     head.next = swapPairs(last.next)
  18.     last.next = head
  19.     return last
  20. };

1000瓶药水，1瓶有毒药，几只小白鼠能够找出？

  • 二分法
    • 1000、500、250、125、62、31、15、7、3、2、1
    • 10只老鼠
  • 二进制法
    • 通过每位数表示某老鼠，可以得到对应实验结果

000=0
001=1
010=2
011=3
100=4
101=5
110=6
111=7
每位数表示一只老鼠，0-7表示8个瓶子。即将1，3，5，7号瓶子的药混合取样给鼠1吃，2，3，6，7号瓶子混合取样给老鼠2吃……死鼠相应的位标为1。如鼠1死了，鼠2没死，鼠3死了，那么就是101=5号瓶子有毒。N只老鼠的量程为2^N，1000只瓶子位于2^9 ~ 2^10，即10只小鼠可以测1000瓶水。

烧一根不均匀的绳，从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢？

  • 获取半小时
    • 两端绳子燃烧即时半小时
  • 获取十五分钟
    • 取两根绳子，第一根从一段燃烧，另二根从两端同时燃烧。当第二根燃尽的时候，将第一根剩余绳子从两端燃烧，第一根绳子剩余从两端燃烧耗尽所需要的时间就是15分钟。

只有两个无刻度的水桶，一个可以装6L水，一个可以装5L水，如何在桶里装入3L的水?

  1. 先将5L的桶装满，将5L的桶的水倒入6L的桶中。这时5L的桶是空的，6L的桶中有5L的水
  2. 再将5L的桶装满，倒入6L的桶中。这时5L的桶有4L的水，6L的桶是满的
  3. 将6L的桶中的水倒掉，5L的桶的水倒入6L的桶中。这时5L的桶是空的，6L的桶中有4L的水
  4. 将5L的桶装满，倒入6L的桶中。这时5L的桶还有3L的水，6L的桶是满的。

122. 买卖股票的最佳时机 II

  1. /**
  2.  * @param {number[]} prices
  3.  * @return {number}
  4.  */
  5.  // 贪心简单些
  6. var maxProfit = function(prices) {
  7.     let res = 0
  8.     let n = prices.length
  9.     for (let i = 1; i < n; i++) {
  10.         res += Math.max(0, prices[i] - prices[i - 1])
  11.     }
  12.     return res
  13. };

4. 寻找两个正序数组的中位数

  1. /**
  2.  * @param {number[]} nums1
  3.  * @param {number[]} nums2
  4.  * @return {number}
  5.  */
  6.  // 先合并数组，然后找中位数
  7. var findMedianSortedArrays = function(nums1, nums2) {
  8.     var list = nums1.concat(nums2).sort((a, b) => a - b)
  9.     var n = list.length
  11.     if (list.length === 1) {
  12.         return list[0]
  13.     }
  14.     if (n % 2 === 0) {
  15.         return (list[n / 2] + list[n / 2 - 1] ) / 2
  16.     } else {
  17.         return list[~~(n / 2)]
  18.     }
  19. };

剑指 Offer 29. 顺时针打印矩阵

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
 // 模拟
var spiralOrder = function(matrix) {
    if(!matrix.length || !matrix[0].length) return [];

    let left = 0, right = matrix[0].length - 1, top = 0, bottom = matrix.length - 1, result = [];

    while(true) {
        // 从左到右，以 left 开始，right 结束
        for(let i = left; i <= right; i++)
            result.push(matrix[top][i]);
        if(++top > bottom) break; // 该行遍历完，向下移动一行，如果上边边界大于下边边界了，遍历完成，跳出

        // 从上到下遍历，以 top 开始，bottom结束
        for(let j = top; j <= bottom; j++)
            result.push(matrix[j][right]);
        if(--right < left) break; // 该列遍历完，向左移动一行，如果右边边界小于左边边界了，遍历完成，跳出

        // 从右到左遍历，以 right 开始，left 结束
        for(let i = right; i >= left; i--)
            result.push(matrix[bottom][i]);
        if(--bottom < top) break; // 该行遍历完，向上移动一行，如果下边边界小于上边边界了，遍历完成，跳出

        // 从下到上遍历，以 bottom 开始，top 结束
        for(let j = bottom; j >= top; j--)
            result.push(matrix[j][left]);
        if(++left > right) break; // 该列遍历完，向右移动一行，如果左边边界大于右边边界了，遍历完成，跳出
    }

    return result;
};