142 篇博文含有标签「LeetCode」

LeetCode——简化路径（辅助栈）

题目描述

解题思路

核心的解题思路就是借助一个栈来辅助我们，遇到空字符串和一个点的则跳过，遇到两个点的则出栈。

AC代码

var simplifyPath = function(path) {
    // 简化路径的核心就是借助辅助栈
    const stack = [];
    // 分割字符串
    const strArr = path.split('/');
    // 遇到空字符串和一个点的直接跳过
    // 遇到两个点则出栈
    const res = [];
    for (let v of strArr) {
        if (v.length === 0 || v === '.') {
            continue;
        }
        if (v === '..') {
            stack.pop();
            continue;
        }
        stack.push(v);
    }
    for (let i = 0; i < stack.length; i++) {
        res.push('/');
        res.push(stack[i]);
    }
    return res.length > 0 ? res.join('') : '/'
};

总结

简化路径的本质就是借助栈这个数据结构的特点对不同的情况进行出栈和入栈，最后返回的就是路径的简化结果，遇到空字符串和一个点的都跳过，遇到两个点的则出栈是本题的核心。

Justin2022年5月4日LeetCode阅读需 1 分钟

LeetCode——回文数（反转比较）

题目描述

解题思路

思路一：反转比较法

回文数的一个特点是正着读和倒着读是一样的，那么我们可以定义一个临时变量来存储目标元素的反转，然后顺序比较每个元素是否相等，相等则返回true，反之false。

var isPalindrome = function(x) {
  // 使用反转对比的方法来判断是否是回文数字
  x = x.toString();
  const temp = x.split('').reverse();
  const xArr = x.split('');

  for (let i = 0; i < xArr.length; i++) {
    if (temp[i] != xArr[i]) {
      return false;
    }
  }
  return true;

};

思路二：使用递归比较首尾元素

首先比较首元素和尾元素是否一致，一致则去掉首尾元素，将其余元素记性递归判断。

var isPalindrome = function(x) {
  // 使用递归判断
  // 递归的介绍条件是输入的x小于等于1
  if (x.toString().length <= 1) {
    return true;
  }
  x = x.toString().split('');
  let start = 0;
  let end = x.length - 1;

  if (x[start] === x[end]) {
    return isPalindrome(x.slice(1,end).join(''))
  } else {
    return false;
  }
};

总结

判断回文数是一道高频考题，思路也比较简单就是根据回文数的特点出发来进行解题。

Justin2022年4月9日LeetCode阅读需 1 分钟

LeetCode——岛屿数量（DFS）

题目描述

解题思路

岛屿数量是一道经典的DFS问题，要想解决这个问题，首先要搞明白下面的几个问题：

RQ1：怎么判断是一个岛屿？

并不是有1的地方就是一个岛屿，一个孤立的岛屿其上下左右都是没有1的，这样的岛屿才能算作一个岛屿，这也就是为什么第一个例子中那么多个1才是一个岛屿的原因，请看下面的例子，这个图中有三个岛屿：

RQ2：DFS如何解决岛屿的数量问题？

第二个问题也就是我们解题的核心，核心思路就一句话假如当前遍历的元素的值是1，就将岛屿数量加1,同时将其上下左右的1都变为0，然后继续循环。

解题代码

var numIslands = function (grid) {
    // 岛屿的数量是一道经典的DFS问题
    let row = grid.length;
    let column = grid[0].length;
    let count = 0;
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < column; j++) {
            if (grid[i][j] === '1') {
                count++;
                dfs(i,j,grid);
            }
        }
    }
    return count;
    function dfs(i,j,grid) {
        if (i < 0 || i >= row || j < 0 || j >= column || grid[i][j] === '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(i+1,j,grid);
        dfs(i,j+1,grid);
        dfs(i-1,j,grid);
        dfs(i,j-1,grid);
    }

};

LeetCode——买卖股票的最佳时机 II（动态规划）

介绍

买卖股票的最佳时机是一道高频考题，这个题目已经衍生出多个版本，其中尤其是买卖股票的最佳时机I和II是面试中的高频考题，让我们来一起看看该如何解决这类问题吧~

题目描述

解题思路

无论是买卖股票的最佳时机I还是II，动态规划都是解决的好方法，动态规划最重要的就是理解动态方程的含义是什么，下面对动态规划的核心进行介绍：

dp[i][0]：表示的是第i天，手上没有股票获取的最大收益，也就是说赚的钱数。
dp[i][1]：表示的是第i天，手上有股票获取的最大收益。
dp[i][0]的可能性：
- 第i-1天手里也没有股票：dp[i-1][0]
- 第i-1天手里有股票，但是今天卖了：dp[i-1][1] + prices[i]
dp[i][1]的可能性：
- 前一天也有股票，并保持到今天：dp[i-1][1]
- 前一天没有股票，今天买入了：dp[i-1][0] - prices[i]

动态规划到最后一天，是持有股票还是手上没有股票的收益大？

手上没有股票的收益大，因为最后一天持有股票说明还没有变现。

AC代码实现

var maxProfit = function(prices) {
  // 动态规划是解决买卖股票的最佳时机的核心技巧
  // 首先构造一个二维数组dp
  const dp = new Array(prices.length).fill([0,0]);

  // 初始化
  dp[0][0] = 0;
  dp[0][1] = -prices[0];

  // 处理一般情况
  for (let i = 1; i < dp.length; i++) {
    dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
    dp[i][1] = Math.max(dp[i-1][0] - prices[i],dp[i-1][1]);
  }

  return dp[prices.length-1][0];
};

构造二维数组的时候，fill中传入的是一个[0,0]。

买卖股票的最佳时机I和买卖股票的最佳时机II的区别在哪里？

核心的区别就在于下面这行代码上：

买卖股票的最佳时机I

dp[i][1] = Math.max(- prices[i], dp[i - 1][1]);

买卖股票的最佳时机II
dp[i][1] = Math.max(dp[i-1][0] - prices[i],dp[i-1][1]);

这说明什么呢？买卖股票的最佳时机如果今天买入，意味着前面不能有买卖操作，也就是说只能买卖一次，但是买卖股票的最佳时机II则可以多次买入，卖出。

总结

在遇到同一类题目时，一定要对比题目之间的异同点，进行对比记忆。

Justin2022年3月1日LeetCode阅读需 3 分钟

LeetCode——第一个只出现一次的字符（Map）

题目描述

题目主要是让我们找到第一个只出现一次的字符，如果没有并不是返回为空字符串，而是单空格，这个地方容易出错，大家一定要注意。

解题思路

博主原本想使用set来实现的，出现第二次就将其从set中去除，但是这种方法无法应对出现三次或者五次等奇数的情况。，因此后来采用了最简单的方法map遍历，然后将其次数存储到map的value中，key则是每一个单字符。

如果传入的参数是一个空字符串，则染回单空格。
初始化一个map，遍历每一个字符，并更新字符出现的次数。
遍历map的每一个item，如果item[1]等于1，则直接返回item[0]。
如果第三步没有找到符合条件的则返回单空格。

AC代码

var firstUniqChar = function (s) {
  if (s.length === 0) return " "
  const map = new Map();

  for (let v of s) {
    if (map.has(v)) {
      map.set(v,map.get(v) + 1);
    } else {
      map.set(v,1);
    }
  }

  for (let item of map) {
    if (item[1] === 1) {
      return item[0];
    }
  }
  return " "

};

总结

第一次只出现一次的字符，使用map是最直接的能够想到的方法了，通过遍历每一个字符出现的次数便可以知道第一次只出现一次的字符。所以通过这个题目，我们能够巩固对map的基本API的操作。在这里我想要强调一下map和传统的object的区别是什么？map类似于对象，也是键值对的组合，但是传统object的键的范围只能是字符串，而map的键可以使各种类型的值，包括对象都可以当做键，也就是说普通的对象提供了字符串到值的对应关系，而map数据结构则提供了值到值的对应，是一种更加完善的hash结构实现。

Justin2022年2月22日LeetCode阅读需 2 分钟

LeetCode——最长公共子序列（动态规划）

题目描述

解题思路

动态规划是解决这个题目的方法之一，动态规划之所以能够解决这个问题，关键在于构建dp[i][j]，这里的dp[i][j]表示的是第一个字符串从0到i和第二个字符串从0到j之间的最长公共子序列的长度，明白这个含义之后，就方便后续的理解了。

假如，我们在比较第一个字符串的第i个元素和第二个字符串的第j个元素的时候，有两种情况：

要比较的字符相等
- dp[i][j] = dp[i-1][j-1] + 1
要比较的字符不相等
- dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])

AC代码

var longestCommonSubsequence = function(text1, text2) {
  // 使用表格法解决最长公共子序列
  let row,column;
  if (text1.length > text2.length) {
    row = text2.length + 1;
    column = text1.length + 1;
  } else {
    row = text1.length + 1;
    column = text2.length + 1;
    let temp = text1;
    text1 = text2;
    text2 = temp;
  }

  // 首先进行填零操作
  const dp = [];
  for (let i = 0; i < row; i++) {
    dp[i] = new Array(column).fill(0)
  }

  // 从第一行的第一列开始进行遍历
  for (let i = 1; i < row; i++) {
    for (let j = 1; j < column; j++) {
      if (text1[j-1] === text2[i-1]) {
        dp[i][j] = dp[i-1][j-1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
      }
    }
  }

  return dp[row-1][column-1];

};

上述的代码有以下几个易错点

哪个字符串的长度长，哪个字符串的长度+1做列。
如果是text2比较长，text1和text2需要进行交换。
构造二维数组的时候fill中填入的一定要是一个常量，否则可能会出错。

启示

做了很多道动态规划的题目，我们可以发现一个动态规划的核心就是搞懂dp[i][j]，只要能够搞懂这个关键变量代表的是什么含义，那么题目往往能够迎刃而解。

Justin2022年2月11日LeetCode阅读需 2 分钟

LeetCode——下一个排列（降序重排法）

题目描述

解题思路

第一步：从右往左倒着找看是否有降序元素的存在

如果有降序元素的存在则进行标记，可以设置一个变量来帮助我们标记。加入nums[right] > nums[right-1]，我们此时要记录这个right-1的位置后续有用，如果没有降序元素的存在，则直接进行升序排列即可，不用再看下面的步骤了，直接返回。

第二步：从降序位置往后的所有元素进行一次升序排列

第三步：对升序排列的数组进行遍历找到第一个比right元素大的元素，进行交换

第四步：交换后进行二次升序排列。

AC代码

var nextPermutation = function(nums) {
  // 下一个排列要求的是原地排序
  let flag = false;
  let right = nums.length - 1;
  // 第一步：从右往左进行遍历，查找是否有降序元素的存在
  while (right) {
    if (nums[right] > nums[right-1]) {
      flag = true;
      right--;
      break;
    } else {
      right--;
    }
  }

  if (flag) {
    const sorted = nums.splice(right + 1).sort((next,pre) => next - pre);
    // 找到排序好的数组的第一个比nums[right]的元素，然后进行交换
    let temp;
    for (let i = 0; i < sorted.length; i++) {
      if (sorted[i] > nums[right]) {
        temp = i;
        break;
      }
    }
    let t = nums[right];
    nums[right] = sorted[temp];
    sorted[temp] = t;
    // 对sorted进行二次排序
    sorted.sort((next,pre) => next - pre);
    // 进行拼接
    nums.push(...sorted);
  } else {
    nums.sort((next,pre) => next - pre)
  }

};

总结

下一个排列这个题目是一道高频考题，核心思路就是理解整个题目的意思，难点不在写代码上，难点在理解这个思路上，只要我们能够安装上文介绍的解题思路进行解题，很快就能解决这个问题，本题的可能不好想，因为倒序本身就不符合常规思维，但是多加练习就能理解的。

参考文献

HOT100——下一个排列（JS实现）

Justin2022年2月9日LeetCode阅读需 2 分钟

LeetCode——删除链表的倒数第N个节点（快慢指针）

题目描述

解题思路

删除链表的倒数第N个结点，有很多种解法，本次我们重点介绍的是快慢指针法，快慢指针在解决链表问题的时候，通常能够快速解决问题，这主要取决于快慢指针的特点。

快慢指针为什么能够找到链表的倒数第N个节点

假设一个链表有五个节点，我们想要删除倒数第2个节点，我们首先让快指针、从第一个节点的位置触发，走2+1个节点，我们能够发现此时快指针有两种情况，一是走到了null，二是走到了倒数倒数第2个节点，此时我们分情况讨论：

快指针走到了null，此时如果还没有走完n + 1个节点
- 让满秩阵继续走完剩余的节点数量，然后返回慢指针即可。
快指针走到了倒数第N个节点
- 此时快慢指针同时继续走，一旦快指针走到了null，删除慢指针的下一个节点，然后返回头指针即可。

解题代码

var removeNthFromEnd = function(head, n) {
  // 删除链表的倒数第N个节点是一个典型的双指针问题
  let slow = head;
  let fast = head;
  let temp = head;
  // 第一步：让快指针先走n步
  let count = n+1;
  while (count && fast) {
    fast = fast.next;
    count--;
  }
  if (!fast && count) {
    while (count) {
      slow = slow.next;
      count--;
    }
    return slow;
  }
  while (fast) {
    fast = fast.next;
    slow = slow.next;
  }
  let stemp = slow.next.next;
  slow.next = stemp;
  return temp;
};

题目反思

删除链表的倒数第N个节点，快慢指针是一种经典的方法，快慢指针不仅能够解决这道题目，在面试中还经常考查到判断链表是否由环，这个也是快慢指针的经典应用，因此，在解决问题的时候，我们一定要学会举一反三，寻找规律。

Justin2022年1月30日LeetCode阅读需 2 分钟

LeetCode——螺旋矩阵（上下左右四指针辅助法）

题目描述

解题思路

首先定义四个指针，指向如下图所示：

按照顺时针进行遍历，分别是从左到右、从上到下、从右到左、从下到上的思路。
一轮循环后让左指针+1，继续下一轮循环，需要注意的是每次移动指针的时候，都需要注意指针是否越界。

var spiralOrder = function(matrix) {
  // 螺旋矩阵的核心是使用四个指针来辅助遍历
  // 首先是初始条件的判断，如果矩阵的长度为0，则返回空数组
  if (matrix.length === 0) return [];

  // 定义四个指针
  let left = 0;
  let top = 0;
  let right = matrix[0].length - 1;
  let bottom = matrix.length - 1;

  // 定义最终返回的结果
  const res = [];

  // 开始遍历
  while (1) {
    // 主要是按照顺时针进行遍历
    // 第一步：从左到右
    for (let i = left; i <= right; i++) {
      res.push(matrix[top][i])
    }
    // 第二步：从上到下
    top++;
    if (top > bottom) break;
    for (let i = top; i <= bottom; i++) {
      res.push(matrix[i][right]);
    }
    // 第三步：从右到左
    right--;
    if (right < left) break;
    for (let i = right; i >= left; i--) {
      res.push(matrix[bottom][i])
    };
    // 第四步：从下到上
    bottom--;
    if (bottom < top) break;
    for (let i = bottom; i >= top; i--) {
      res.push(matrix[i][left])
    }
    // 第五步：也是最容易被遗忘的一步
    left++;
    if (left > right) break;
  }

  return res;

};

题目反思

螺旋矩阵和顺时针打印矩阵是同一道题目，这个题目既出现在了剑指Offer中，也出现在了很多面试场合中，因此这个题目我们一定要搞懂，本质就是指针辅助加条件判断。

Justin2022年1月15日LeetCode阅读需 2 分钟

LeetCode——删除字符串中的所有相邻重复项（用栈实现打牌思路）

题目描述

这道题从题目的名字上看是删除字符串中的所有相邻重复项，其实通俗的讲就是消消乐的思想，有两个相邻一致的则消除，消除一对后如果还有则继续消除。

解题思路

本题的实现可以使用打牌思路，类似题目有最长回文串，这道题目是使用集合来实现打牌思路，但是本题是通过栈来实现打牌思路，首先遍历每一个字符，如果栈中有元素，且栈的最后一个元素和这个元素的值相等，则栈进行pop，反之push进栈，最后返回栈对应的字符串。

var removeDuplicates = function(s) {
  // 这道题目的思想类似于打牌的思路，区别在于本题是通过栈来实现打牌思路
  // 有机会可以将这道题目和最长回文串这道题目进行归纳总结
  const stack = [];

  for (let i = 0; i < s.length; i++) {
    if (stack.length && stack[stack.length - 1] === s[i]) {
      stack.pop();
    } else {
      stack.push(s[i]);
    }
  }
  return stack.join('');

};

题目反思

使用打牌思路来解决问题已经不是一次出现了，也是面试官常考的题目，但是却不容易被想到，因此我们可以通过归纳总结的方式来对这类题目进行记忆。

Justin2022年1月9日LeetCode阅读需 2 分钟

题目描述​

解题思路​

AC代码​

总结​

题目描述​

解题思路​

思路一：反转比较法​

思路二：使用递归比较首尾元素​

总结​

题目描述​

解题思路​

RQ1：怎么判断是一个岛屿？​

RQ2：DFS如何解决岛屿的数量问题？​

解题代码​

同类对比​

介绍​

题目描述​

解题思路​

AC代码实现​

买卖股票的最佳时机I和买卖股票的最佳时机II的区别在哪里？​

总结​

题目描述​

解题思路​

AC代码​

总结​

题目描述​

解题思路​

AC代码​

启示​

题目描述​

解题思路​

第一步：从右往左倒着找看是否有降序元素的存在​

第二步：从降序位置往后的所有元素进行一次升序排列​

第三步：对升序排列的数组进行遍历找到第一个比right元素大的元素，进行交换​

第四步：交换后进行二次升序排列。​

AC代码​

总结​

参考文献​

题目描述​

解题思路​

快慢指针为什么能够找到链表的倒数第N个节点​

解题代码​

题目反思​

题目描述​

解题思路​

题目反思​

题目描述​

解题思路​

题目反思​

题目描述

解题思路

AC代码

总结

题目描述

解题思路

思路一：反转比较法

思路二：使用递归比较首尾元素

总结

题目描述

解题思路

RQ1：怎么判断是一个岛屿？

RQ2：DFS如何解决岛屿的数量问题？

解题代码

同类对比

介绍

题目描述

解题思路

AC代码实现

买卖股票的最佳时机I和买卖股票的最佳时机II的区别在哪里？

总结

题目描述

解题思路

AC代码

总结

题目描述

解题思路

AC代码

启示

题目描述

解题思路

第一步：从右往左倒着找看是否有降序元素的存在

第二步：从降序位置往后的所有元素进行一次升序排列

第三步：对升序排列的数组进行遍历找到第一个比right元素大的元素，进行交换

第四步：交换后进行二次升序排列。

AC代码

总结

参考文献

题目描述

解题思路

快慢指针为什么能够找到链表的倒数第N个节点

解题代码

题目反思

题目描述

解题思路

题目反思

题目描述

解题思路

题目反思