bighippozz / docs Goto Github PK

View Code? Open in Web Editor NEW

3.0 3.0 0.0 1.14 MB

HTML 0.35% Vue 6.06% JavaScript 1.06% TypeScript 92.28% Less 0.25%

docs's People

Contributors

Stargazers

Watchers

docs's Issues

112. 路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

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

思路

这道题目一样就能瞅出题解，一开始我的思路是用自顶而下的思路，将遍历节点的val进行累加，
然后进行一个边界判断(!root.left&&!root.right)当前累加的值跟目标和是否一致然后返回结果。

解答

// 第一遍的代码，感觉好cai
function hasPathSum(root: TreeNode | null, sum: number) {
  let flag = false;
  function loop(root: TreeNode | null, num: number) {
    if (!root) return;
    if (!root.left && !root.right) {
      sum === num + root.val && (flag = true);
    }
    loop(root.left, num + root.val);
    loop(root.right, num + root.val);
  }
  loop(root, 0);
  return flag;
}

// 看到大神写的代码，真是简洁明了啊 
function hasPathSum(root: TreeNode | null, sum: number): boolean {
  if (!root) return false;
  if (!root.left && !root.right) {
    return sum === root.val;
  }
  return (
    hasPathSum(root.left, sum - root.val) ||
    hasPathSum(root.right, sum - root.val)
  );
}
// 时间复杂度：O(N) 其中N是树的节点数，每个节点都会进行访问 
// 空间复杂度：O(H) 其中H是树的高度，在啰嗦一遍进行DFS分析复杂度的时候一定不能忘掉栈的开销最坏的情况下树呈链状，空 
// 间复杂度为O(N)，但是平均情况下，空间复杂度为O(logN)

1209. 删除字符串中的所有相邻重复项 II

删除字符串中的所有相邻重复项 II
给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

本题答案保证唯一。

示例 1：

输入：s = "abcd", k = 2
输出："abcd"
解释：没有要删除的内容。
示例 2：

输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释：
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"
示例 3：

输入：s = "pbbcggttciiippooaais", k = 2
输出："ps"

思路

栈问题还是两个点：
1.什么时机进行入栈，什么时机进行出栈，
2.入栈的数据结构怎样选择？
先回答第二个问题，一开始我直接想到的是用暴力法，使用字符串入栈，直接将字符串依次进行入栈，然后判断栈顶到k-1位元素是否相同，相同的话就将上述的k-1位直接出栈。虽然做出来了但是超级慢。
后来看了别人的解答，发现自己用了最笨的方法(手动滑稽)，这题是将一个描述当前字符串数量的对象入栈，然后最后根据栈中对象生成最终的字符串。
至于什么时候入栈呢？当前栈顶不等于当前遍历的元素进行入栈，什么时候出栈呢？当栈顶描述当前字符串的数量正好等于k就进行出栈。
总结:一定要注意入栈出栈的数据结构超级重要！！！！重要的话说三遍！

解答

function removeDuplicates(s: string, k: number): string {
  const stack: { val: string; count: number }[] = [];
  for (let i = 0; i < s.length; i++) {
    // 获取最新的char
    const val = s[i];
    //  获取当前的stack长度
    const len = stack.length;
    // 当当前的val等于栈顶的元素的时候
    if (len > 0 && val === stack[len - 1].val) {
      // 栈顶的元素进行++
      stack[len - 1].count++;
      // 栈顶的元素的count  === k
      if (stack[len - 1].count === k) {
        stack.pop();
      }
    } else {
      stack.push({ val, count: 1 });
    }
  }
  return stack.reduce((prev, item) => {
    return prev + item.val.repeat(item.count);
  }, "");
}

316. 去除重复字母

去除重复字母
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同

示例 1：

输入：s = "bcabc"
输出："abc"
示例 2：

输入：s = "cbacdcbc"
输出："acdb"

思路

看完题目中最重要的几个信息 1.去除字符串中重复的字母 2.返回的结果需要字典序最小
先看第二个信息，返回的结果需要字典序最小，也就是说当s字符串中出现两个相同的字母要取索引较大的字母，本题的重点所在！
第一个去重就比较简单不再赘述

题解

function removeDuplicateLetters(s: string): string {
  const stack: string[] = []; /** 栈 */
  const len = s.length; 
  for (let i = 0; i < len; i++) {
    const char = s.charAt(i);
    /** 进行去重操作 */
    if (stack.includes(char)) continue;
    /** 栈必须有元素，栈顶不能大于当前char 栈顶元素不能小于之后出现与当前重复的元素的索引 */
    while (
      stack.length &&
      stack[stack.length - 1] > char &&
      s.indexOf(stack[stack.length - 1], i) > i
    ) {
      /** 进行出栈操作 */
      stack.pop();
    }
    // 将当前的字符串进行入栈
    stack.push(char);
  }
  return stack.join("");
}

1021. 删除最外层的括号

有效括号字符串为空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。

如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。

对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。

示例 1：

输入："(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。
示例 2：

输入："(()())(())(()(()))"
输出："()()()()(())"
解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。
示例 3：

输入："()()"
输出：""
解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。

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

思路

当栈为空的时候，入栈的第一个'('添加特殊标记。围绕这个思路进行思考。
栈只是一种**，先入后出，具有缓存性，一定不要死记硬背模板，数字字符串数组都可以模拟栈的**。
遇见栈的问题，首先先判断什么时机进行入栈，出栈，然后设计入栈的数据结构，在判断在出栈入栈的时候做什么事情，再者使用变量保存某一时机的状态，然后与出栈的元素进行比较作相应的逻辑判断。

解答

/**
 * @param {string} S
 * @return {string}
 */
var removeOuterParentheses = function(S: string) {
  let res = "";
  let opened = 0;
  for (let c of S) {
    if (c === "(" && opened++ > 0) res += c;
    if (c === ")" && opened-- > 1) res += c;
  }
  return res;
};

1190. 反转每对括号间的子串

给出一个字符串 s（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，您的结果中不应包含任何括号。

示例 1：

输入：s = "(abcd)"
输出："dcba"
示例 2：

输入：s = "(u(love)i)"
输出："iloveu"
示例 3：

输入：s = "(ed(et(oc))el)"
输出："leetcode"
示例 4：

输入：s = "a(bcdefghijkl(mno)p)q"
输出："apmnolkjihgfedcbq"

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

思路

1.什么时机进行入栈，什么时机进行出栈？
这道题的显而易见就是在 '(' ')' 进行出栈入栈操作，但是这道题的难点并不是在出栈入栈的时机上，而是入栈一个''字符串，然后对栈顶元素进行累加，这是这道题的关键所在！并不是按照正常的逻辑保存当前遍历之后累加的字符串然后进行入栈操作。
2.入栈的数据结构是什么样子？
将字符串进行入栈
总结：有时候并不需要保存当前遍历累加的字符串，而是直接操作栈顶元素

function reverseParentheses(s: string): string {
  // 初始化栈顶元素 方便进行累加
  const stack = [""];
  // 遍历所以元素
  for (const char of s) {
    // 遇到 '(' 入栈，只将 '' 入栈方便后续的累加
    if (char === "(") {
      stack.push("");
    } else if (char === ")") {
      // 弹出当前的栈顶元素
      const last = stack.pop() as string;
      // 翻转字符串
      const temp = last
        .split("")
        .reverse()
        .join("");
      console.log(temp);
      // 对栈顶元素进行累加
      stack[stack.length - 1] += temp;
    } else {
      // 对栈顶元素进行累加
      stack[stack.length - 1] += char;
    }
  }
  return stack.join("");
}

二叉树遍历

二叉树所有的搜索方法

// 二叉树结构
export class TreeNode<T = any> {
  val: T;
  left: TreeNode<T> | null;
  right: TreeNode<T> | null;
  constructor(val: T, left: TreeNode<T>, right: TreeNode<T>) {
    this.val = val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}
type Logger = typeof logger;
/**
 * 打印node
 * @param val treeNode
 */
function logger(val: TreeNode) {
  console.log(val.val);
}

/**
 * 层次遍历
 * @param {TreeNode} tree
 * @param {Function} callback
 */
export function LevelOrder({
  tree,
  callback = logger,
}: {
  tree: TreeNode;
  callback?: Logger;
}) {
  const queue = [tree];
  while (queue.length) {
    const len = queue.length;
    for (let i = 0; i < len; i++) {
      const current = queue.shift() as TreeNode;
      callback(current);
      current?.left && queue.push(current.left);
      current?.right && queue.push(current.right);
    }
  }
}

/**
 * 先序遍历 递归
 * @param {TreeNode} tree
 * @param {Function} callback
 */
export function PreOrder(tree: TreeNode | null, callback: Function = logger) {
  if (!tree) {
    return;
  }
  callback(tree);
  PreOrder(tree.left, callback);
  PreOrder(tree.right, callback);
}

/**
 * 中序遍历 递归
 * @param {TreeNode} tree
 * @param {Function} callback
 */
export function InOrder(tree: TreeNode | null, callback: Function = logger) {
  if (!tree) {
    return;
  }
  InOrder(tree.left, callback);
  callback(tree);
  InOrder(tree.right, callback);
}

/**
 * 后序遍历 递归
 * @param {TreeNode} tree
 * @param {Function} callback
 */
export function PostOrder(tree: TreeNode | null, callback: Function = logger) {
  if (!tree) {
    return;
  }
  PostOrder(tree.left, callback);
  PostOrder(tree.right, callback);
  callback(tree);
}

/**
 * 先序遍历 非递归
 * @param {TreeNode} tree
 * @param {Function} callback
 */
export function PreOrder2(tree: TreeNode | null, callback: Function = logger) {
  const stack = [];
  while (tree || stack.length) {
    while (tree) {
      callback(tree);
      stack.push(tree);
      tree = tree.left;
    }
    tree = stack.pop() as TreeNode;
    tree = tree.right;
  }
}

/**
 * 中序遍历 非递归
 * @param {TreeNode} tree
 * @param {Function} callback
 */
export function InOrder2(tree: TreeNode | null, callback: Function = logger) {
  const stack = [];
  while (tree || stack.length) {
    while (tree) {
      stack.push(tree);
      tree = tree.left;
    }
    tree = stack.pop() as TreeNode;
    callback(tree);
    tree = tree.right;
  }
}

/**
 * 后序遍历 非递归
 * @param {TreeNode} tree
 * @param {Function} callback
 */
export function PostOrder2(tree: TreeNode | null, callback: Function = logger) {
  const stack = [];
  let pre = null;
  while (stack.length || tree !== null) {
    while (tree) {
      stack.push(tree);
      tree = tree.left;
    }
    tree = stack.pop() as TreeNode;
    if (tree.right === null || tree.right === pre) {
      callback(tree);
      pre = tree;
      tree = null;
    } else {
      stack.push(tree);
      stack.push(tree.right);
      tree = tree.right.left;
    }
  }
}

/**
 * 利用语法糖
 * 先序、中序以此类推
 * @param {TreeNode} tree
 * @return {number[]}
 */
export const postorderTraversal = function(tree: TreeNode | null): number[] {
  return tree === null
    ? []
    : [
        ...postorderTraversal(tree.left),
        ...postorderTraversal(tree.right),
        tree.val,
      ];
};

设计循环队列

思路

1.队尾不能与队头重叠，队尾永远追不上队头
2.队头可以与队尾重叠，这种情况下队列中只剩一个元素
3.利用求余数来进行指针的移动

class Queue<T> {
  len: number;
  head: number;
  tail: number;
  queue: Array<T>;

  constructor(len: number) {
    this.len = len;
    this.head = -1;
    this.tail = -1;
    this.queue = [];
  }
  enQueue(value: T) {
    if (this.isFull()) {
      return false;
    }
    if (this.isEmpty()) {
      this.head = 0;
    }
    this.tail = (this.tail + 1) % this.len;
    this.queue[this.tail] = value;
    return true;
  }
  deQueue() {
    if (this.isEmpty()) {
      return false;
    }
    if (this.head === this.tail) {
      this.head = this.tail = -1;
    } else {
      this.head = (this.head + 1) % this.len;
    }
    return true;
  }
  isEmpty() {
    return this.head === -1;
  }
  isFull() {
    return this.head === (this.tail + 1) % this.len;
  }
}

const queue = new Queue(3);

queue.enQueue(10);
queue.enQueue(10);
queue.enQueue(10);
queue.deQueue();
queue.deQueue();

227. 基本计算器 II

问题

实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数，+， - ，，/ 四种运算符和空格。整数除法仅保留整数部分。
示例 1:
输入: "3+22"
输出: 7
示例 2:
输入: " 3/2 "
输出: 1
示例 3:
输入: " 3+5 / 2 "
输出: 5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/basic-calculator-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

最容易想到的就是 * / 优先 + - 其次就是就是栈系列问题的基本思路：
1.什么时机进行入栈什么时机进行出栈？两种情况：一个是选择数字进行入栈，另一种是选择运算符进行入栈
选择数字入栈的时候进行处理入栈出栈，仔细思考比如 1 + 5 * 6 当我们遍历到 5 的时候我们进行处理运算或者入栈，正好也有一个棘手的问题我们无法预料后面的数字和运算符，可能有的人会说怎么可能，我们可以利用栈的缓存性到达5（还是刚刚的例子1+5*6）的时候处理 1 的逻辑，但是你会发现选择遍历到运算符的时候进行处理入栈或者出栈不是更好嘛。

2.入栈的时应该放入什么样的数据结构？
按照刚刚的逻辑我们只需要将当前的字符串转为数字入栈即可。
总结 : 遍历到运算符的时候我们并不是处理当前的运算符进行入栈出栈操作，而是操控上一个运算符，这样做的根本目的还是我们可以拿到运算符左右的数字，只要理解这一点这题基本上就理解了，还是要注意一点，我们要设置一个变量来保存我们当前的数字。

题解

function calculate(s: string) {
  if (!s.length) return 0;
  const len = s.length;
  const NUMBERS = /[0-9]/;// 匹配数字
  const WHITESPACE = /\s/; // 匹配空格
  let currentString = ""; //保存当前的字符串可以说是没有转成数字的字符串
  let currentFunc = "+"; //保存当前的运算规则
  const stack: number[] = [];
  // 注意这里 i <= len 由于操作的是上一次的运算符，所以我们要多遍历一次，这个不难理解
  for (let i = 0; i <= len; i++) {
    // charAt() api当索引超出字符串长度的时候就会返回空 ''
    const char = s.charAt(i);
    if (WHITESPACE.test(char)) continue;

    if (NUMBERS.test(char)) {
      currentString += char;
      continue;
    }
    switch (currentFunc) {
      case "+":
        stack.push(+currentString);
        break;
      case "-":
        stack.push(-currentString);
        break;
      case "*":
        stack.push((stack.pop() as number) * +currentString);
        break;
      case "/":
        // 知识点：字符串转为数字类型的有那几种方法？
        // parseInt(str) -> 输入''空的话会返回NaN
        // parseFloat(str) -> 输入'' 返回NaN
        // ( str | 0)   -> 输入''返回 0,返回规则是向下取舍 (10.9 | 0) => 10
        // Number(str)  -输入''返回 0
        stack.push(((stack.pop() as number) / +currentString) | 0);
        break;
    }
    currentFunc = char;
    currentString = "";
  }
  return stack.reduce((a, b) => a + b, 0);
}

剑指 Offer 55 - I. 二叉树的深度

剑指 Offer 55 - I. 二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

提示：

节点总数 <= 10000

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

思路

认真的进行debugger，看看遍历树的顺序。

解答

// 采用BFS
function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  const queue = [root];
  let count = 0;
  while (queue.length) {
    const len = queue.length;
    count++;
    for (let i = 0; i < len; i++) {
      const current = queue.shift();
      current?.left && queue.push(current.left);
      current?.right && queue.push(current.right);
    }
  }
  return count;
}

// 使用DFS 自底向上
function maxDepthDFS(root: TreeNode | null): number {
  if (!root) return 0;
  const left = maxDepthDFS(root.left);
  const right = maxDepthDFS(root.right);
  return Math.max(left + 1, right + 1);
}

// 自顶向下 
function forEachTree(root: TreeNode | null) {
  let ans = 0;
  function loop(root: TreeNode | null, sum: number) {
    if (!root) return;
    if (!root.left && !root.right) {
      ans = Math.max(ans, sum);
    }
    loop(root.left, sum + 1);
    loop(root.right, sum + 1);
  }
  loop(root, 1);
  return ans;
}
// 啰嗦几句 自顶向下这样理解，从根部向叶节点进行遍历，

bighippozz / docs Goto Github PK

docs's People

Contributors

Stargazers

Watchers

docs's Issues

思路

解答

思路

解答

思路

题解

思路

解答

思路

二叉树所有的搜索方法

思路

问题

思路：

题解

思路

解答

Recommend Projects

Recommend Topics

Recommend Org