基础数据结构与算法题(日常)

/**
 * 20.有效的括号
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    let item = s[i];
    if (item === "(" || item === "{" || item === "[") {
      stack.push(item);
    } else {
      let current = stack[stack.length - 1];
      if (
        (item === ")" && current === "(") ||
        (item === "}" && current === "{") ||
        (item === "]" && current === "[")
      ) {
        stack.pop();
      } else {
        return false;
      }
    }
  }

  return stack.length === 0;
};

console.log(isValid("(){}"));
console.log(isValid("()[}"));

/**
 * 删除字符串中的所有相邻重复
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function (s) {
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    let start = s[i];
    if (stack.length > 0) {
      if (start === stack[stack.length - 1]) {
        stack.pop();
      } else {
        stack.push(start);
      }
    } else {
      stack.push(start);
    }
  }
  return stack.join("");
};

/**
 * 简化路径
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function (path) {
  let stack = [];
  let arr = path.split("/");
  arr.forEach((item) => {
    if (item === "..") {
      stack.pop();
    } else if (item && item !== ".") {
      stack.push(item);
    }
  });
  return stack.length ? (str = "/" + stack.join("/")) : "/";
};

var RecentCounter = function () {
  this.queue = [];
};

/**
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function (t) {
  this.queue.push(t);
  while (this.queue[0] < t - 3000) {
    this.queue.shift();
  }
  return this.queue.length;
};

let a = { key: "3" };
let b = { key: "2" };
let c = { key: "0" };
let d = { key: "-4" };
a.next = b;
b.next = c;
c.next = d;
d.next = b;

var hasCycle = function (head) {
  let a = head,
    b = head;
  while (a !== null && a.next !== null) {
    b = b.next;
    a = a.next.next;
    if (a === b) return true;
  }
  return false;
};
console.log(hasCycle(a));

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function (node) {
  node.val = node.next.val;
  node.next = node.next.next;
};

/**
 * 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) {
  if (!head) {
    return head;
  }
  let cur = head;
  while (cur.next) {
    if (cur.val == cur.next.val) {
      cur.next = cur.next.next;
    } else {
      cur = cur.next;
    }
  }
  return head;
};