Giter VIP home page Giter VIP logo

algorithm's Introduction

👋 Hi there! I'm Liuqh

“Per aspera ad astra”

I am a front-end developer.


algorithm's People

Contributors

callqh avatar

Stargazers

avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar

Watchers

avatar

algorithm's Issues

二分

二分的本质

二分的本质并不是单调性。

例如：我们平时理解的一个递增的数组区间，我们找一个中间值，只要比中间值小的就是在中点的左边，比中间值大的就是在中点的右边。

二分的本质其实是：我们定义某种性质，这种性质在区间的左半边可以满足，在右半边不满足（反之亦可）。

这种性质的边界可以将这个区间一分为二。我们可以通过寻找到这个边界来进行二分。
难点也就是：如何定义这个性质，性质的边界怎么定位。

模板

image

  • 这里需要注意的是当r=mid-1的时候，mid值在计算的时候l+r就需要+1==>l+r+1，这样才不会陷入死循环

42. 接雨水

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

image

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/volume-of-histogram-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

  • 利用双指针，分层求解
  • 关键点在于：（黑+蓝） - 黑 = 蓝
  • 我们按照色块的高度分层，高度为一块是第一层，高度时第二块是第二层
  • 然后计算出第一层总的块数：黑 + 蓝，这样依次计算出所有层数的个数
  • 然后计算所有黑色块的个数
  • 总后的结果就是 黑+蓝） - 黑 = 蓝

题解

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  // 定义左指针
  let left = 0;
  // 定义右指针
  let right = height.length - 1;
  // 初始化层数
  let heigh = 1;
  // 初始化所有层数的块数之和
  let sum = 0;

  while (left <= right) {
    // 判断左指针对应的数据是否小于层级，如果小于层级的话，就移动左指针
    // 这里需要注意，如果指针对应的数比层级大，指针是不会进行移动的，直到当前的数小于层级为止
    // 所以即时第一个数是2，我们初始层级是1，那么因为2是由两个黑色块堆积出来的，所以在一层肯定也有一个块
    // 所以这时候依然要计算，直到碰到层级大于2再进行移动
    while (left <= right && height[left] < heigh) {
      left++;
    }
    // 判断右指针的数是否小于层级
    while (left <= right && height[right] < heigh) {
      right--;
    }
    // 更新层数的块数之和
    sum += right - left + 1;
    // 更新层级
    heigh += 1;
  }

  // 遍历所有黑色块
  let blackSum = 0;
  height.forEach((n) => (blackSum += n));
  // 返回最终结果 （黑+蓝） - 黑
  return sum - blackSum;
};
  • 时间复杂度：o(n+n) 因为对height进行了两次遍历
  • 空间复杂度：o(1) 都是常量级别的变量

876. 链表的中间结点

876. 链表的中间结点

image

/**
 * 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 middleNode = function(head) {
    let p1 = head, p2 = head;
    while(p2!==null&&p2.next!==null){
        p1 = p1.next;
        p2 = p2.next.next;
    }
    return p1;
};

1006. 笨阶乘

通常，正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如，factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。

相反，我们设计了一个笨阶乘 clumsy：在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操作>符：乘法(*)，除法(/)，加法(+)和减法(-)。

例如，clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。然而，这些运算仍然使用通常的算术运算顺序：我们在任何加、减步骤>之前执行所有的乘法和除法步骤，并且按从左到右处理乘法和除法步骤。

另外，我们使用的除法是地板除法（floor division），所以 10 * 9 / 8 等于 11。这保证结果是一个整数。

实现上面定义的笨函数：给定一个整数 N，它返回 N 的笨阶乘。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/clumsy-factorial
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

  • 利用栈先将第一个数字入栈，然后从第二个数字开始判断下标对应的操作符是什么，进行相应的操作
  • 因为操作步骤是乘除加减，每4轮一个循环，所以通过下标模4的值来判断进行何种操作

题解

/**
 * @param {number} N
 * @return {number}
 */
var clumsy = function (N) {
  // 创建栈，并将第一个数字入栈
  const stack = [N];
  // 从第二个数字的下标开始计算对应的操作符
  const index = 0;
  N--;
  // 遍历
  while (N > 0) {
    if (index % 4 === 0) {
      stack.push(stack.pop() * N);
    } else if (index % 4 === 1) {
      const n = stack.pop();
      // 这里需要注意，因为我们的值需要向下取整，所以要判断相除的结果是正数还是负数
      stack.push(n / N > 0 ? Math.floor(n / N) : Math.ceil(n / N));
    } else if (index % 4 === 2) {
      // 加操作，直接入栈
      stack.push(N);
    } else {
      // 减操作，将数字的相反数入栈
      stack.push(-N);
    }
  }
  // 遍历完成之后就遍历栈结构进行相加
  let res = 0;
  stack.forEach((n) => (res += n));
  return res;
};

144. 二叉树的前序遍历

思路

  • 前序遍历其实没什么难点，只需要知道按照根节点、左节点、右节点即LDR的形式进行遍历就好了

题解

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
  // 创建接收结果的数组
  const ret = [];
  // 递归函数
  const innerPreorder = (root) => {
    // 节点为空直接返回
    if (!root) return;
    // 将根节点的值放入数组中
    ret.push(root.val);
    // 递归遍历左节点
    innerPreorder(root.left);
    // 递归遍历右节点
    innerPreorder(root.right);
  };
  // 调用递归
  innerPreorder(root);
  // 返回结果
  return ret;
};

206. 反转链表

206. 反转链表

image

/**
 * 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 reverseList = function(head) {
    let p = head;
    let prev = null;
    while(p!==null){
        const tmp = p.next;
        p.next = prev;
        prev = p;
        p = tmp;
    }
    return prev;
};

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

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

image

/**
 * 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 dumy = new ListNode(-1)
    dumy.next = head;
    let p1=dumy,p2=dumy;

    while(n!==0){
        n--;
        p2=p2.next;
    }
    while(p2.next!==null){
        p1 = p1.next;
        p2 = p2.next
    }
    p1.next = p1.next.next;
    return dumy.next;
};

680. 验证回文字符串 Ⅱ

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: "aba"
输出: True
示例 2:

输入: "abca"
输出: True
解释: 你可以删除c字符。
注意:

字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-palindrome-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

  • 因为回文字符是符合对称原则的
  • 所以我们可以利用双指针，不断比较首尾的字符是否相同
  • 如果相同就缩小指针的空间
  • 遇到不同的时候就尝试跳过左侧的值，验证该区间是否符合回文特征
  • 然后尝试跳过右侧的值，验证是否符合回文特征
  • 主要有一个符合就满足题意
  • 否则就返回false
/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function(s) {
    let l = 0;
    let r = s.length -1;
   // 指针的值相同，缩小区间
    while(l<r&&s[l]===s[r]){
        l++;
        r--;
    }
   // 遇到不同的就尝试分别跳过左侧或者右侧的值
   //  验证跳过该值的区间是否符合回文特征
    if(isPalindrome(l+1,r)) return true;
    if(isPalindrome(l,r-1)) return true;

    // 验证回文
    function isPalindrome(l,r){
        while(l<r){
            if(s[l]!==s[r]) return false;
            l++;
            r--;
        }
        return true;
    }
   // 否则则返回false
    return false;
};

150. 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

image

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation

思路

  • 遇到这种数学计算之类的，有计算的优先级，可以考虑使用栈来完成
  • 针对这道题，我们只需要进行这样两步就好
    1. 判断该字符是否为数字，如果是数字就入栈
    2. 不是数字，就判断是那个操作符，然后将栈中的栈顶和栈顶后面的一个元素弹出进行对应操作
    3. 最后剩下的就是逆波兰表单式的值
/**
 * 判断当前字符是否为数字
 * @param {string} token 判断该字符是否为标识符
 * @returns boolean
 */
const isNumber = (token) => {
  return !(token === "+" || token === "-" || token === "*" || token === "/");
};
/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function (tokens) {
  const len = tokens.length;
  // 创建栈
  const stack = [];
  // 遍历字符串
  for (let i = 0; i < len; i++) {
    const t = tokens[i];
    // 判断是否为数字
    if (isNumber(t)) {
      // 是 - 入栈
      stack.push(parseInt(t));
    } else {
      // 否 - 进行对应的标识符操作
      const n2 = stack.pop();
      const n1 = stack.pop();
      if (t === "+") {
        stack.push(n2 + n1);
      } else if (t === "-") {
        stack.push(n2 - n1);
      } else if (t === "*") {
        stack.push(n2 * n1);
      } else {
        stack.push(n2 / n1 > 0 ? Math.floor(n2 / n1) : Math.ceil(n2 / n1));
      }
    }
  }
  // 返回结果
  return stack.pop();
};

88. 合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

 

示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array

思路：

  • 这道题的重点是要将nums1给整合成一个有序的数组，而不是让我们新建一个数组进行返回
  • 利用双指针，从每个数组的最后一位向前进行比较
  • 如果谁指针指向的数字大，就赋值给nums1扩展后的最后一个数字，然后将该指针缩小，将扩展后的最后一位缩小

题解

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
   let p1 = m - 1;
   let p2 = n - 1;
   let last = m + n -1;

   while(p1 >=0 && p2>=0){
       if(nums1[p1] > nums2[p2]){
           nums1[last] = nums1[p1];
           p1--
       }else{
           nums1[last]  = nums2[p2]
           p2--
       }
       last--;
   }
  // 如果第二个数组还有剩余元素没有进行比较，就逐个将元素放入数组1中
   while(p2>=0){
       nums1[last--] = nums2[p2--];
   }
   return nums1;
};

74. 搜索二维矩阵

思路

第一种：两个二分搜索

  • 第一个二分搜索，需要检索出目标值所处的行，也就是返回的是一个数组的下标
  • 第二个二分搜索，是在第一个搜索的结果数组中进行二分搜索，看是否能找到目标值

第二种：先转换成一维数组，在进行二分搜索

  • 遍历数组转换成一维
  • 对一维数组进行二分查找

题解

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    // 第一个二分搜索，查找出目标值可能所处的行数组
    const binarySearch = (nums)=>{
        let low = 0;
        let height = nums.length - 1;
        while(low < height){
            let mid = Math.floor((low + height)/2);
            if(nums[mid][0] > target){
                height = mid - 1;
            }else if(nums[mid][nums[mid].length - 1] < target){
                low = mid + 1;
            }else {
                return low = mid;
            }
        }
        return low
    }
    // 第二个二分搜索，对第一个搜索出的数组进行二分搜索
    const binarySearchResult = (nums)=>{
        let left = 0;
        let right = nums.length - 1;
        while(left <= right){
            let mid = Math.floor((left+right)/2);
            if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                return true;
            }
        }
        return false;
    }
    const index = binarySearch(matrix);

    return binarySearchResult(matrix[index]);
};

反转部分链表

反转前N个链表：从链表第一个节点开始，翻转1-n个节点。
明确这个递归函数的作用： 返回反转后的last节点。

let next = null
function reverseN(head, n) {
// 说明已经是需要反转的最后一个节点。
// 记录最后一个节点的 后驱节点
  if (n === 1) {
    next = head.next
    return head
  }
  const last = reverseN(head.next, n - 1)
  head.next.next = head
  head.next = next
  return last
}

image

餐前阅读

坚持下去的事情，等过了一段时间回头看肯定觉得会很牛逼。

1. 两数之和

描述

给定一个整数数组 nums  和一个整数目标值 target，请你在该数组中找出 和为目标值 的那   两个   整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

提示：

  • 2 <= nums.length <= 103
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum

思路

  1. 创建字典表 Map，来存储每个出现过的元素：key 为数字， val 为下标 { n : index}
  2. 遍历数组查询（需求值 = 目标值 - 当前值），是否出现在字表中
    1. 是：直接返回字典表中存储的需求值的下标和当前下标 [m.get(n), i]
    2. 否： 将当前值存入字典表中

题解

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  // 创建字典表
  const m = new Map();
  // 遍历数组
  for (let i = 0; i < nums.length; i++) {
    // 获取当前值
    const n = nums[i];
    // 获取需要的值，即当前值相加可以获得target的数字
    const t = target - n;
    // 如果有就返回对应下标数组
    if (m.has(t)) {
      return [m.get(t), i];
    }
    // 否则将当前值和下标放入字典
    m.set(n, i);
  }
};

复杂度分析

假设数组的长度为 n：

  • 时间复杂度：O(n) 在最坏的情况下需要遍历完整个数组
  • 空间复杂度：O(n-1) 在最坏的情况字典表中需要存放 0（n-1）个数字

22. 链表中倒数第k个节点

22. 链表中倒数第k个节点

image

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let p1 = head;
    let p2 = head;
    for(let i = 0; i < k; i++){
        p2 = p2.next;
    }
    while(p2!==null){
        p2 = p2.next;
        p1 = p1.next;
    }
    return p1;
};

912. 排序数组

题目描述

给你一个整数数组 nums，请你将该数组升序排列。

 

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
 

提示：
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-an-array

88. 合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2合并到 nums1 中，使 nums1成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

 

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

 

提示：
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
109 <= nums1[i], nums2[i] <= 109

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array

98. 验证二叉搜索树

思路一

  • 二叉搜索树满足中序遍历的结果数组是一个升序数组
  • 所以我们可以先进行中序遍历，然后再判断数组是否为升序

题解

var isValidBST = function (root) {
  // 中序遍历
  const ret = [];
  const inorder = root => {
    if (!root) return [];
    if (root.left) inorder(root.left);
    ret.push(root.val);
    if (root.right) inorder(root.right);
  };
  inorder(root);
  // 判断中序遍历的结果是否为升序
  let tmp = ret.pop();
  while (ret.length) {
    const n = ret.pop();
    if (n >= tmp) return false;
    tmp = n;
  }
  return true;
};

##复杂度

  • 时间复杂度：o(n+m) n为树的深度，m为中序遍历结果数组的长度
  • 空间复杂度：o(n) n为树的深度

思路二

  • 从题意可以知道，左子树的根节点值应该是在 [ 最小值，上一个根节点的val ]，右子树的根节点值应该是在[ 上一个根节点的val, 最大值 ]
  • 最小值就是下不封顶，我们可以把它设置为 -Infinity
  • 同理，最大值也是上不封顶，所以我们可以把他设置为Infinity

题解

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    const inner = (root,lower,upper)=>{
        if(!root) return true;
        // 判断当前的值是否处于当前的区间内 （小，大），注意需要是个开区间
        if(root.val <= lower || root.val >= upper){
            return false;
        }
        return inner(root.left,lower,root.val)&&inner(root.right,root.val,upper)
    }
    // 调用递归函数，初始化区间为+-无穷，保证树的第一个根节点始终在区间内
    return inner(root,-Infinity,Infinity);
};

125. 验证回文串

描述

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:

输入: "race a car"
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

  • 利用双指针不断比较左指针和右指针的值是否相同
/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    let l = 0;
    let r = s.length - 1;
    const ans = s.toUpperCase();
    while(l < r){

        while(/[^A-Za-z0-9]/.test(ans[l])){
             l++
        }
        while(/[^A-Za-z0-9]/.test(ans[r])) {
            r--
        }
        if(l<r&&ans[l] !== ans[r]){
             return false;
        }

        l++;
        r--;
    }
    return true;
};

141. 环形链表

141. 环形链表

image

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let fast = head,slow = head;
    const dumy = new ListNode();
    dumy.next = head;
    while(fast!==null && fast.next!==null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast) {
            return true;
        }
    }
    return false;
};

二叉树层序遍历

层序遍历BFS

  1. 利用队列来存放每层的节点
  2. 通过遍历队列中的值，不断通过入队出队来维护每层的节点数据
  3. 在每次遍历队列时，将队列中的值遍历取出，存放到结果数组中（每次遍历队列都是二叉树一层的数据）
  4. 取出的同时，将该节点的左右子节点存到队列中，直到左右子节点为空，队列为空结束遍历。

代码

var levelOrder = function(root) {
    if(!root) return [];
    const q = [root];
    const result = [];
    let depth = 0;
    while(q.length){
        const size = q.length;
        result[depth]=[];
        for(let i =0;i<size;i++){
            const node = q.shift();
            result[depth].push(node.val);
            if(node.left) q.push(node.left)
            if(node.right) q.push(node.right)
        }
        depth++;
    }
    return result;
};

92. 反转链表 II

给你单链表的头节点 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 

示例 1：
image

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

21. 合并两个有序链表

合并两个有序链表

image

/**
 * 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 p1 = list1, p2 = list2;
    let dumy = new ListNode(-1),root = dumy;

    while(p1!=null&&p2!=null){
        if(p1.val<p2.val){
            dumy.next = p1;
            p1=p1.next;
        } else {
            dumy.next = p2;
            p2=p2.next;
        }
        dumy = dumy.next;
    }

    if(p1!=null) dumy.next = p1;
    if(p2!=null) dumy.next = p2;
    return root.next;
};

160. 相交链表

160. 相交链表
image

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let p1 = headA, p2 = headB;
    while(p1!==p2){
        if(p1===null){
            p1 = headB;
        }else{
            p1 = p1.next;
        }
        if(p2 === null){
            p2 = headA;
        }else {
            p2 = p2.next;
        }
    }
    return p1;
};

94. 二叉树的中序遍历

思路

  • 中序遍历的顺序就是左节点、根节点、右节点
  • 这里有个注意点就是二叉搜索树，就是左节点小于根节点，右节点大于根节点的二叉树。满足这个条件的树，中序遍历的结果是个单调递增的数组

题解一：递归

var inorderTraversal = function(root) {
    const ret = [];
    const inorder = root=>{
        if(!root) return;
        inorder(root.left);
        ret.push(root.val);
        inorder(root.right);
    }
    inorder(root)
    return ret;
};

时间复杂度：o(n）n是树的深度，递归的时候需要维护一个递归栈
空间复杂度：o(n) n是树的深度

题解二：迭代

  • 利用一个栈来模拟递归栈
  • 中序遍历的顺序因为是LDR，所以我们在模拟栈的时候的顺序应该是先把所有的左节点入栈，左节点全部入栈之后，弹出栈顶元素，将该栈顶元素的val记录，然后将该栈顶元素的右节点的所有子节点进行遍历入栈
var inorderTraversal = function (root) {
  if (!root) return [];
  // 模拟栈
  const stack = [];
  // 结果数组
  const ret = [];
  // 指针
  let p = root;
  // 遍历栈
  while (stack.length || p) {
    // 将左右左节点入栈
    while (p) {
      stack.push(p);
      p = p.left;
    }
    // 弹出栈顶
    const d = stack.pop();
    // 记录栈顶的值
    ret.push(d.val);
    // 将指针指向栈顶元素的右节点，在下一轮迭代的时候将右节点的所有子节点入栈
    p = d.right;
  }
  // 返回结果
  return ret;
};

142. 环形链表 II

142. 环形链表 II

image

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let fast = head,slow = head;
    while(fast!==null&&fast.next!==null){
        fast = fast.next.next;
        slow = slow.next;
        if(slow===fast){
            break;
        }
    }
    // 没有环
    if(fast===null || fast.next===null){
        return null;
    }

    slow = head;
    while(slow!==fast){
        slow = slow.next;
        fast = fast.next;
    }

    return slow;
};

86. 分隔链表

86. 分隔链表

image

/**
 * 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} x
 * @return {ListNode}
 */
var partition = function(head, x) {
    let dumy1 = new ListNode(-1),p1 = dumy1;
    let dumy2 = new ListNode(-2),p2 = dumy2;

    let p = head;
    while(p!==null){
        if(p.val<x){
            dumy1.next = p;
            dumy1 = dumy1.next;
        }else{
            dumy2.next = p;
            dumy2 = dumy2.next;
        }
        // 断开原链表中每个节点的next，防止出现循环链表
        const tmp = p.next;
        p.next = null;
        p = tmp;
    }
    dumy1.next = p2.next;
    return p1.next;
};

145. 后序遍历

思路

  • 遍历顺序为 左节点、右节点、根节点即LRD

题解一：递归

var postorderTraversal = function(root) {
    const ret = [];
    const postorder = root=>{
        if(!root) return;
        postorder(root.left);
        postorder(root.right);
        ret.push(root.val)
    }
    postorder(root)
    return ret;
};

时间复杂度：o(n)
空间复杂度：o(n)

题解二：迭代

  • 这里我们可以借用前序遍历的迭代写法，因为前序遍历是DLR，后续遍历是LRD，可以看到我前序遍历倒过来RLD与后序遍历很接近
  • 通过前序遍历的变形（变为先将左节点入栈，再将右节点入栈）变为DRL，这样我们在将栈逐个弹出即可得到后序遍历的结果
var postorderTraversal = function (root) {
  if (!root) return [];
  // 结果数组
  const ret = [];
  // 临时接受变形的前序遍历结果
  const tmp = [];
  // 模拟栈
  const stack = [root];
  // 遍历栈
  while (stack.length) {
    // 取出栈顶元素
    const d = stack.pop();
    // 压入根元素 D
    tmp.push(d.val);
    // 左节点入栈，因为要先执行右节点
    if (d.left) stack.push(d.left);
    // 右节点后入栈
    if (d.right) stack.push(d.right);
  }
  // 经过上面遍历出来的 DRL的结果，我们这里输出为LRD
  while (tmp.length) {
    ret.push(tmp.pop());
  }
  // 返回结果
  return ret;
};

常见排序

快速排序

快排整体采用的是分治的方法，分为三步实现：

  1. 确定临界点（即对比值）x，一般是数组左侧的值q[l]、数组右侧的值q[r]、中间值q[(r+l)/2]以及随机四种；
  2. 根据临界值来划分出区间。区间左侧是<x,右侧是>=x；（难点）

image

3. 递归对区间进行操作

Code

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    quick_sort(nums,0,nums.length-1);
    return nums;
};

function quick_sort(nums,left,right){
    if(left>=right) return;
   // 找到临界值，定义左右指针
    let x = nums[left], i=left-1,j=right+1;
   // 根据临界值划分区间
    while(i<j){
        do{i++}while(nums[i]<x);
        do{j--}while(nums[j]>x);
        if(i<j){
            const tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
    quick_sort(nums,left,j);
    quick_sort(nums,j+1,right);
}

纠结的点

  1. 指针的左右起点为什么要分别+1，-1？
    • 因为我们每次都要先移动，在进行判断。所以刚开始的时候要把指针放到数组区间的两边
  2. 其他关于边界值的一些判断
    • 通过背模板来解决，这就是比较优雅的快排模板

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.