数组的遍历

495.提莫攻击

  1. // 1.从后往前想，每次攻击完必然会持续 duration 的时间，所以一旦 timeSeries 的长度不为零，总是会
  2. // 存在最后一次攻击存在 duration 的时间（对应第 10，11 行代码）
  3. // 2.如果下一次攻击与上一次攻击的间隔时间小于 duration，则攻击时间有重合，重合的攻击时间会被合并到 
  4. // 下一次攻击 duration 中，按照从后往前想的原则，此时只需要记录两次攻击之间的间隔时间就可以了
  5. // （因为下一次攻击的 duration 已经记录了）
  6. // 3.如果下一次攻击与上一次攻击的间隔时间大于 duration，则完整记录 duration
  7. // 4.以此类推，从最后一次攻击一直记录到第一次攻击
  8. /**
  9.  * @param {number[]} timeSeries
  10.  * @param {number} duration
  11.  * @return {number}
  12.  */
  13. var findPoisonedDuration = function(timeSeries, duration) {
  14.     let time = 0
  15.     if(timeSeries.length) { // 记录最后一次攻击的持续时间
  16.         time = duration
  17.     }
  18.     for(let i = 1; i < timeSeries.length; i++) {
  19.         let distance = timeSeries[i] - timeSeries[i - 1]
  20.         time += Math.min(distance, duration)
  21.     }
  22.     return time
  23. };

485.最大连续1的个数

  1. // 打擂台法，连续的个数大的保存，小的丢弃掉，重新记述
  2. /**
  3.  * @param {number[]} nums
  4.  * @return {number}
  5.  */
  6. var findMaxConsecutiveOnes = function(nums) {
  7.     let count = 0, max = 0
  8.     for(let i = 0; i < nums.length; i++) {
  9.         if(nums[i] === 1) {
  10.             count++
  11.         } else {
  12.             if(max < count) {
  13.                 max = count 
  14.             }
  15.             count = 0
  16.         }
  17.     }
  18.       // 这里最后一次如果是最大的不要忘了比较
  19.     return max > count ? max : count
  20. };

字符串

686.重复叠加字符串匹配

  1. /**
  2.  * @param {string} a
  3.  * @param {string} b
  4.  * @return {number}
  5.  */
  6. var repeatedStringMatch = function(a, b) {
  7.     let m = new Map(), res = 1
  8.     // 首先把a中出现的字符统计一下
  9.     for(let i = 0; i < a.length; i++) {
  10.         let t = m.get(a[i])
  11.         m.set(a[i], t ? t + 1 : 1)
  12.     }
  13.     let k = Array.from(m.keys())
  14.     // 如果b中某个字符没有在a里面出现过，返回-1
  15.     for(let i = 0; i < b.length; i++) {
  16.         if (!k.includes(b[i])) {
  17.             return -1
  18.         }
  19.     }
  20.     let s = ''
  21.     // 如果b是s的字串，则s=a的尾部 + [b的一部分] + a的头部
  22.     while(s.length < a.length * 2 + b.length) {
  23.       // a重复res次，判断是否包含b
  24.         s = a.repeat(res++)
  25.         if (s.search(b) > -1) {
  26.             return res - 1
  27.         }
  28.     }
  29.     return -1
  30. };

459.重复的子字符串

  1. /**
  2.  * @param {string} s
  3.  * @return {boolean}
  4.  * s+s 包含了所有移动的字符串
  5.  * 比如abc, abcabc包含了bca cab,移动3次后才有abc;abababab包含了baba abab，移动不到4次就有abab 
  6.  * 所以可以根据s+s去除首尾元素后判断是否包含自身
  7.  */
  8. var repeatedSubstringPattern = function(s) {
  9.     let str = (s + s).slice(1, -1)
  10.     return str.indexOf(s) === -1 ? false : true
  11. };

214. 最短回文串

  1. /**
  2.  * @param {string} s
  3.  * @return {string}
  4.  * 将 s 翻转添加到 s 的前面，但是要去掉 s 末尾 与 s 开头相同的部分
  5.  * s = abc, temp = cba, temp[2] = s[0], res = cbabc
  6.  * s = aac, temp = caa, temp[1-2] = s[0-1], res = caac
  7.  */
  8. var shortestPalindrome = function(s) {
  9.     let temp = s.split('').reverse().join(''), res, i = 0
  10.     for(let i = s.length; i >= 0; i--) {
  11.         if (temp.slice(s.length - i) === s.slice(0, i)) {
  12.             return temp.substring(0, s.length - i) + s
  13.         }
  14.     }
  15.     return ''
  16. };
  17. // 还可以用 KMP 算法

71. 简化路径

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
    // 2个目录之间只能有一个 /
    path = path.replace(/\/+/g, '/')
    let arr = path.split('/')
    for(let i = 0; i < arr.length; i++) {
        // 如果是 ./ 则删除./
        if (arr[i] === '.') {
            arr.splice(i, 1)
            i--
        } else if (arr[i] === '..') {
            // 如果是 ../ 则删除../和前一个
            if (i === 0) {
                arr.splice(i, 1)
                i--
            } else {
                arr.splice(i - 1, 2)
                i -= 2
            }
        }
    }
    let str = arr.join('/')
     // 始终以 / 开头
    if (str[0] !== '/') {
        str = '/' + str
    }
    // 最后一个目录名不能以 / 结尾
    if (str.length > 1 && str[str.length - 1] === '/') {
        str = str.slice(0, -1)
    }
    return str
};

150. 逆波兰表达式求值

/**
 * @param {string[]} tokens
 * @return {number}
 * 遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
 */
var evalRPN = function(tokens) {
    let stack = [], len = tokens.length
    for(let i = 0; i < tokens.length; i++) {
        let temp = Number(tokens[i])
        if (!isNaN(temp)) {
            stack.push(temp)
        } else {
            let y = stack.pop()
            let x = stack.pop()
            // 用括号将数字包裹起来，避免减-1时报错
            stack.push(parseInt(eval(`(${x})${tokens[i]}(${y})`)))
        }
    }
    return stack[0]
};

227. 基本计算器 II

/**
 * @param {string} s
 * @return {number}
 * 跟#150类似
 */
var calculate = function(s) {
    let stack = []
    // 去掉空格
    s = s.replace(/\s+/g, '')
    // 按运算符分开 并保留运算符
    let arr = s.split(/([+\-\*\/])/)
    for(let i = 0; i < arr.length; i++) {
        if (arr[i] !== '/' && arr[i] !== '*') {
            stack.push(arr[i])
        } else {
            // 如果是乘除 就先计算一下
            let x = stack.pop()
            let y = arr[i + 1]
            stack.push(parseInt(eval(`${x}${arr[i]}${y}`)))
            i++
        }
    }
    return eval(stack.join(''))
};

636. 函数的独占时间

/**
 * @param {number} n
 * @param {string[]} logs
 * @return {number[]}
 */
var exclusiveTime = function(n, logs) {
    // stack 如果是start就将 id 入栈，如果是end就出栈
    // pre 前一个状态的位置
    let arr = new Array(n).fill(0), stack = [], pre = 0
    for(let i = 0; i < logs.length; i++) {
        let temp = logs[i].split(':')
        let id = temp[0], status = temp[1], time = temp[2]
        if (status === 'start') {
            // 如果是 start 状态就把时间差加到上一个函数中
            if (stack.length) {
                arr[stack[stack.length - 1]] += time - pre
            }
            pre = time
            stack.push(id)
        } else {
            // 如果是 end 就把时间差加到当前函数上
            arr[id] += time - pre + 1
            pre = Number(time) + 1
            stack.pop()
        }
    }
    return arr
};

394. 字符串解码

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function(s) {
    while(s.includes('[')) {
        s = s.replace(/(\d+)\[([A-Za-z]*)\]/, (match, p1, p2) => {
            return p2.repeat(p1)
        })
    }
    return s
};

链表

203. 移除链表元素

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    if (!head) {
        return head
    }
    head.next = removeElements(head.next, val)
    return head.val === val ? head.next : head
};

19. 删除链表的倒数第 N 个结点

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    if (!head || !head.next) {
        return null
    }
    let p = head, q = head
    // 快指针先走n步
    while(n > 0) {
        p = p.next
        n--
    }
    // 删除的是第一个节点
    if (!p) {
        return head.next
    }
    while(p.next) {
        p = p.next
        q = q.next
    }
    // 删除倒数第n个节点
    q.next = q.next.next
    return head
};

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

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    if (!head || !head.next) {
        return head
    }
    let next = head.next
    head.next = swapPairs(next.next)
    next.next = head
    return next
};