@luminous/docs
搜索 K

Appearance

On this page

刷题笔记1 ​

1 两数之和 ​

js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = new Map();
    for (let i=0; i<nums.length; i++) {
        let temp = target - nums[i];
        if (map.has(temp)) {
            return [map.get(temp), i];
        }else {
            map.set(nums[i], i);
        }
    }
};

3 无重复字符的最长子串 ​

js
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let set = new Set();
    let j = 0;
    let i = 0;
    let maxLen = 0;
    if (s.length===0) {
        return 0;
    }
    // 循环终止条件: i遍历完整个字符串
    for (i;i<s.length;i++) {
        // 每次遍历都检查set里有无s[i]
        // 如果有就删除s[j], 并递增j
        while (set.has(s[i])) {
            set.delete(s[j]);
            j++;
        }
        // 将s[i]放入set中, 并比较maxLen的值
        set.add(s[i]);
        maxLen = Math.max(maxLen, set.size);
    }
    return maxLen;
};

5 最长回文子串 ​

  • 边界判断: 字符串长度小于2, 直接返回原字符串
  • 初始化变量: start记录当前找到的最长回文串的起始位置, maxLen记录最大回文串的长度
  • 创建一个辅助函数expandAroundCenter
    • 判断左边和右边是否越界
    • 判断左边的字符是否等于右边的字符
    • 若以上条件满足, 则判断是否需要更新最大长度与起始位置, 然后将left--, right++, 继续执行循环
  • 遍历字符串中的每一个字符, 每个位置调用两次expandAroundCenter, 分别检查(i-1,i+1), (i, i+1)
  • 返回子串
js
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (s.length<2) return s;
    let start = 0;
    let maxLen = 1;
    function expandAroundCenter(l, r){
        while (l>=0&&r<s.length&&s[l]===s[r]) {
            if (r-l+1>maxLen) {
                maxLen = r-l+1;
                start = l;
            }
            l--;
            r++;
        }
    }
    for (let i=0; i<s.length;i++) {
        expandAroundCenter(i-1, i+1);
        expandAroundCenter(i, i+1);
    }
    return s.substring(start, start+maxLen);
};

15 三数之和 ​

js
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let result = [];
    // 排序
    nums.sort((a,b)=>a-b);
    // 循环
    for (let i=0; i<nums.length-2; i++) {
        // 第一次去重
        if (i===0 || nums[i-1]!==nums[i]) {
            let start = i+1, end=nums.length-1;
            // 对每一个i, 都对数组开启一次循环
            while (start<end) {
                if (nums[i]+nums[start]+nums[end]<0) {
                    start++;
                }else if (nums[i]+nums[start]+nums[end]>0) {
                    end--;
                }else {
                    result.push([nums[i], nums[start], nums[end]]);
                    start++;
                    end--;
                    // 第二次去重
                    while (start<end && nums[start]===nums[start-1]) {
                        start++;
                    }
                    while (start<end && nums[end]===nums[end+1]) {
                        end--;
                    }
                }
            }
        }
    }
    return result;
};

19 删除链表的倒数第N个节点 ​

简单解法

js
var removeNthFromEnd = function (head, n) {
  let dummy = new ListNode()
  dummy.next = head
  let n1 = dummy;

//   计算链表长度
  let linkLen = 0;
  let tmp = head;
  while (tmp) {
      linkLen++;
      tmp = tmp.next;
  }

// 删除链表节点
  for (let i=0; i<linkLen-n; i++) {
      n1 = n1.next;
  }
  n1.next = n1.next.next;

  return dummy.next
}

双指针解法

js
/**
 * 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) {
  let dummy = new ListNode()
  dummy.next = head
  let n1 = dummy
  let n2 = dummy
  for (let i = 0; i <= n; i++) {
    n2 = n2.next
  }
  while (n2 != null) {
    n2 = n2.next
    n1 = n1.next
  }
  n1.next = n1.next.next
  return dummy.next
}

20 有效的括号 ​

stack数据结构: 先进后出, 羽毛球筒

  • 创建一个哈希表, 把括号配对放入
  • 利用arr的push方法和pop方法, 都是从一个地方进出的特性, 模拟一个stack
  • for循环遍历字符, 对于每一个字符,
    • 如果它是一个左括号, 就从哈希表里取出它对应的右括号, 把它push进stack里
    • 否则, pop出最后进入stack的字符, 如果这个字符不等于当前字符, 则返回false
  • 最后返回stack是否为空
js
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let map = new Map();
    map.set('(', ')');
    map.set('[', ']');
    map.set('{', '}');
    let stack = [];
    for (let i=0; i<s.length; i++) {
        if (map.has(s[i])) {
            stack.push(map.get(s[i]));
        } else {
            if (stack.pop()!==s[i]) return false
        }
    }
    return stack.length===0
};

21 合并两个有序链表 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    let cur = new ListNode()
    let dummy = cur
    while (list1!==null && list2!==null) {
        if (list1.val<list2.val) {
            cur.next = list1;
            list1 = list1.next;
        } else {
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next;
    }
    if (list1) {
        cur.next = list1
    }
    if (list2) {
        cur.next = list2
    }
    return dummy.next
};

24 交换链表中的节点 ​

image.png 画个图更好理解, 这个题可以充分说明虚拟头结点在解决链表问题时的重要性

js
/**
 * 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) {
    let dummy = new ListNode()
    dummy.next= head
    let cur = dummy
    while (cur.next!==null && cur.next.next!==null) {
        let n1 = cur.next;
        let n2 = cur.next.next;
        cur.next = n2
        n1.next = n2.next
        n2.next = n1
        cur = n1
    }
    return dummy.next
};

49 字母异位词分组 ​

法1

js
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const map = new Map();
    for (const str of strs){
        let array = Array.from(str);
        array.sort();
        let key = array.toString();
        let value = map.get(key) ? map.get(key) : new Array();
        value.push(str);
        map.set(key, value); 
    }
    const result = [];
    for (const item of map){
        result.push(item[1]);
    };
    return result;
};

法2 image.png

js
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const map = new Map()
    
    for (const str of strs){
        let characters = Array(26).fill(0)
        for (let i=0; i<str.length; i++) {
            let ascii = str.charCodeAt(i) - 97
            characters[ascii]++
        }
        let key = characters.join("")
        if (!map.has(key)) {
            map.set(key, [str])
        }else {
            let tmp = map.get(key)
            tmp.push(str)
            map.set(key, tmp)
        }
    }

    const result = [];
    for (const item of map){
        result.push(item[1]);
    };
    return result;
};

704 二分查找 ​

查找指定元素的位置, 并返回索引, 使用O(lgN)的时间复杂度处理

js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left = 0
    let right = nums.length-1
    while (left<=right) {
        let mid = left+Math.floor((right-left)/2)
        if (nums[mid]<target) {
            left = mid+1
        }else if (nums[mid]===target) {
            return mid
        }else {
            right = mid-1
        }
    }
    return -1
};

53 最大子数组和 ​

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let max = nums[0] // 最大子数组和
    let memo = [] // 每次遍历元素后抉择出来的当前最大子序和
    memo[0] = nums[0]
    for (let i=1; i<nums.length; i++) {
        memo[i] = Math.max(memo[i-1]+nums[i], nums[i])
        max = Math.max(max, memo[i])
    }
    return max
};

54 螺旋矩阵 ​

image.png

  • 如果数组为空, 返回空数组
  • 定义四个边界, 以及当前方向
  • 开始while循环
    • 循环条件: left<=right && top<=bottom
    • 顺序: 右下上左, 每次对边界进行相应处理, 并将路径上的字符添加进result数组内
  • 循环结束后, 返回result
js
/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    if (matrix.length===0) return []
    let direction = 'right'
    let left = 0
    let right = matrix[0].length-1
    let top = 0
    let bottom = matrix.length-1
    let res = []

    while (left<=right && top<=bottom) {
        // 右下左上
        if (direction==='right') {
            for (let i=left; i<=right;i++) {
                res.push(matrix[top][i])
            }
            top++
            direction = 'down'
        } else if (direction==='down') {
            for (let i=top; i<=bottom;i++) {
                res.push(matrix[i][right])
            }
            right--
            direction = 'left'
        } else if (direction==='left') {
            for (let i=right; i>=left;i--) {
                res.push(matrix[bottom][i])
            }
            bottom--
            direction = 'up'
        } else if (direction==='up') {
            for (let i=bottom; i>=top;i--) {
                res.push(matrix[i][left])
            }
            left++
            direction = 'right'
        }
    }
    return res
};

55 跳跃游戏 ​

正向动态规划 up-to-bottom

image.png

  • 状态转移方程: 递归
  • 使用-1, 0, 1来标记状态转移方程
  • 基本情况: memo[len-1]=1
js
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    let len = nums.length
    let memo = Array(len).fill(0)
    memo[len-1] = 1
    function jump(position) {
        if (memo[position]===1) return true
        if (memo[position]===-1) return false
        let jumpSteps = Math.min(nums[position]+position, len-1) // 2
        for (let i=position+1; i<=jumpSteps; i++) { // 1, 2
            let tempRes = jump(i)
            if (tempRes) {
                memo[i] = 1
                return true
            }
        }
        memo[position] = -1
        return false
    }
    let result = jump(0)
    return result
};

反向动态规划 bottom-to-up

js
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    let len = nums.length
    let memo = Array(len).fill(0)
    memo[len-1] = 1
    // 反向动态规划
    let i = len - 2
    for (i; i>=0; i--) {
        let maxJump = Math.min(i+nums[i], len-1)
        for (let j=i+1; j<=maxJump; j++) {
            if (memo[j]===1) {
                memo[i] = 1
                break
            }
        }
    }
    return memo[0]===1
};

贪心

js
var canJump = function(nums) {
    let maxJump = nums.length - 1
    for (let i=nums.length-2; i>=0; i--) {
        if (i+nums[i]>=maxJump) {
            maxJump=i
        }
    }
    return maxJump===0
};

56 合并区间 ​

image.png

cur数组记录当前合并的最大区间, 每次遍历后, 如果发现不需要更新区间, 就把cur的值push到result里, 并将当前遍历到的interval赋值给cur, 以进行下一轮判断

js
/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    // 边界判断
    if (intervals.length<2) return intervals
    // 排序
    intervals.sort((arr1, arr2) => arr1[0] - arr2[0])
    // 初始化
    let cur = intervals[0]
    let result = []
    // 循环
    for (let interval of intervals) {
        if (cur[1]>=interval[0]) {
            cur[1] = Math.max(cur[1], interval[1]) // 更新区间
        }else {
            result.push(cur)
            cur = interval
        }
    }
    if (cur.length!==0) result.push(cur)
    return result
};

62 不同路径 ​

典型的动态规划问题

  • 机器人只能向下或者向右移动一步
  • 状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  • 基本情况是当横坐标或纵坐标为0时，只有1种路径, 不能越界
js
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  let dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i == 0 || j == 0) dp[i][j] = 1;//基本case
      else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1];
};

66 加一 ​

js
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    for (let i=digits.length-1;i>=0;i--) {
        if (digits[i]!==9) {
            digits[i]++
            return digits
        }else {
            digits[i]=0
        }
    }
    return [1, ...digits]
};

70爬楼梯 ​

  • 状态转移方程: memo[i] = memo[i-1] + memo[i-2]
  • 基本情况: memo[1] = 1, memo[2] = 2
js
var climbStairs = function(n) {
    const memo = []
    memo[1] = 1 // 爬1级台阶有1种爬法
    memo[2] = 2 // 爬2级台阶有2种爬法: 迈一步 or 迈两步
    for (let i=3; i<=n; i++) {
        memo[i] = memo[i-1] + memo[i-2]
    }
    return memo[n]
};

73 矩阵置为0 ​

image.png

算法要求in-place, 因此先标记第一行/列原本有无0的情况, 再使用第一行和第一列来标记整个矩阵的为0情况, 最后处理

js
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
    let firstRowHasZero = false
    let firstColHasZero = false
    // 检查第一列有无0
    for (let i=0; i<matrix.length; i++) {
        if (matrix[i][0]===0) firstColHasZero=true
    }
    // 检查第一行有无0
    for (let i=0; i<matrix[0].length; i++) {
        if (matrix[0][i]===0) firstRowHasZero=true
    }
    // 用第一行和第一列记录其余矩阵的含0情况
    for (let i=1; i<matrix.length; i++) {
        for (let j=1; j<matrix[0].length; j++) {
            if (matrix[i][j]===0) {
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }
    // 处理矩阵除第1行,第1列的剩余部分
    for (let i=1; i<matrix.length; i++) {
        for (let j=1; j<matrix[0].length; j++) {
            if (matrix[i][0]===0 || matrix[0][j]===0) {
                matrix[i][j] = 0
            }
        }
    }
    // 根据firstRowHasZero, firstColHasZero处理第一行和第一列
    if (firstRowHasZero) {
        for (let i=0; i<matrix[0].length; i++) {
            matrix[0][i]=0
        }
    }
    if (firstColHasZero) {
        for (let i=0; i<matrix.length; i++) {
            matrix[i][0]=0
        }
    }
};

78 子集⭐ ​

回溯法

image.png

js
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const result = []
    function backtrack(start, cur) {
        result.push([...cur])
        for (let i=start; i<nums.length;i++) {
            cur.push(nums[i])
            backtrack(i+1, cur)
            cur.pop()
        }
    }
    backtrack(0, [])
    return result
};

83 删除排序链表中的重复元素 ​

js
/**
 * 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 deleteDuplicates = function(head) {
    let dummy = new ListNode()
    dummy.next = head
    let cur = head
    while (cur!==null && cur.next!==null) {
        if (cur.val === cur.next.val) {
            cur.next = cur.next.next
        }else {
            cur = cur.next
        }
    }
    return dummy.next
};

上次更新于: