bighippozz / docs Goto Github PK

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);
  }, "");
}

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("");
}

// 采用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;
}
// 啰嗦几句 自顶向下这样理解，从根部向叶节点进行遍历，

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("");
}

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);
}

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();

/**
 * @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;
};
 

// 二叉树结构
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,
      ];
}; 

// 第一遍的代码，感觉好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)