【当前排名67359】挑战leetcode进入前1w名

李恒道

https://leetcode.cn/problems/multiply-strings/submissions/590550128/
模拟题秒了，有点脏
但是凭感觉写的乘法还是蛮自豪的

const addNum = (str1, str2) => {
  let maxLen = Math.max(str1.length, str2.length);
  while (str1.length !== maxLen) {
    str1 = "0" + str1;
  }
  while (str2.length !== maxLen) {
    str2 = "0" + str2;
  }
  let extra = 0;
  let ans = "";
  for (let index = maxLen - 1; index >= 0; index--) {
    const num1 = str1[index] ? str1[index].charCodeAt() - 48 : 0;
    const num2 = str2[index] ? str2[index].charCodeAt() - 48 : 0;
    let total = num1 + num2 + extra;
    extra = Math.floor(total / 10);
    total = total - extra * 10;
    ans = total + ans;
  }
  if(extra!==0){
    ans="1"+ans
  }
  return ans;
};

const add = (num, times) => {
  let timeNum = num;
  let result = "0";
  for (let index = 0; index < 32; index++) {
    if (times & (1 << index)) {
      result = addNum(result, timeNum);
    }
    timeNum = addNum(timeNum, timeNum);
  }
  return result;
};

/**
 * @param {string} num1
 * @param {string} num2
 * @Return {string}
 */
var multiply = function (num1, num2) {
  if(num1=="0"||num2=="0"){
    return "0"
  }
  let last = "";
  for (let index = 0; index < num2.length; index++) {
    if (last !== "") {
      last += "0";
    }
    const times = num2[index].charCodeAt() - 48;
    last = addNum(last, add(num1, times));
  }
  return last
};

李恒道

https://leetcode.cn/problems/valid-number/submissions/590566702/
感觉这题挺烂的
懒得思考了
直接对着测例硬编码过去了

var isNumber = function (s) {
  const isNum=(pos)=>{
    const code = s[pos]?.charCodeAt();
    if (code >= 48 && code <= 57 ) {
      return true;
    }
    return false
  }
  let pAndnPos=-1
  let pAndnNum = 0;
  let dot = 0;
  let dotPos=-1;
  let eNum=0;
  let ePos=-1;
  for (let index = 0; index < s.length; index++) {
    const char = s[index];
    if (char == "+" || char == "-") {
      if(s[index-1]=="+"||s[index-1]=="-"){
        return false
      }
      if(s[index+1]=="+"||s[index+1]=="-"){
        return false
      }
      pAndnPos=index
      pAndnNum++;
    }
    if (char == "e"||char == "E") {
      eNum++
      ePos=index;
    }
    if (char == ".") {
      dot++;
      dotPos=index
    }
    const code = char.charCodeAt();
    if (code >= 97 && code <= 122 && code !== 101) {
      return false;
    }
    if (code >= 64 && code <= 90 && code !== 69) {
      return false;
    }
  }
  if(dot>1||eNum>1){
    return false
  }
  if(ePos!==-1){
    if(!isNum(ePos+1)&&s[ePos+1]!='+'&&s[ePos+1]!='-'){
      return false
    }
    if(!isNum(ePos-1)&&s[ePos-1]!='.'){
      return false
    }
  }
  if(pAndnPos!==-1){
    if(!isNum(pAndnPos+1)&&s[pAndnPos+1]!=='.'){
      return false
    }
    if(!isNum(pAndnPos+1)&&s[pAndnPos+1]=='.'&&pAndnPos!=0){
      return false
    }
    if(isNum(pAndnPos+1)&&isNum(pAndnPos-1)){
      return false
    }
  }
  if(dotPos!==-1){
    if(!isNum(dotPos+1)){
      if(!isNum(dotPos-1)){
        return false
      }
    }
  }
  if(ePos!==-1&&dotPos!==-1&&ePos<dotPos){
    return false
  }
  // if(ePos!==-1&&pAndnPos!==-1&&ePos<pAndnPos){
  //   return false
  // }
  return true
};

李恒道

https://leetcode.cn/problems/permutation-sequence/submissions/590574873/
一次过hard题！
数字的数量刨分

function factorial(n) {
  if (n === 0 || n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}
var getPermutation = function (n, k) {
  const arr = new Array(n + 1).fill(false);
  const dfs = (n, k) => {
    if(n<1){
      return ""
    }
    let childNum = factorial(n - 1);
    for (let index = 1; index < arr.length; index++) {
      const num = index;
      const status = arr[index];
      if (status) {
        continue;
      }
      if (k <= childNum) {
        arr[index] = true;
        return `${index}` + dfs(n - 1, k);
      } else {
        //大于
        k -= childNum;
      }
    }
  };
  return dfs(n,k)
};

李恒道

https://leetcode.cn/problems/remove-duplicates-from-sorted-list/submissions/590586599/

简单题
炸了

var deleteDuplicates = function (head) {
    if(head==null){
        return null
    }
  let node = {};
  ret = node;
  while (head != null) {
    if (node.val !== head.val) {
      node.next = {
        next: null,
        val: head.val,
      };
      head=head.next;
      node=node.next;
    }else{
      head=head.next;
    }
  }
  return ret.next
};

李恒道

https://leetcode.cn/problems/restore-ip-addresses/submissions/590588548/
dfs一次过

var restoreIpAddresses = function (s) {
  let ans = [];
  const dfs = (pos, block, str) => {
    if (pos == s.length) {
      if (block == 4) {
        ans.push(str);
      } else {
        return;
      }
    }
    if (block >= 4) {
      return;
    }
    let num = "";
    for (let index = 0; index < 3; index++) {
      num +=s[pos + index];
      if (parseInt(num) > 255) {
        break;
      } else {
        dfs(pos + index + 1, block + 1, str == "" ? `${num}` : str + "." + num);
      }
      if(num=="0"){
        break;
      }
    }
  };
  dfs(0, 0, "");
  return ans
};

李恒道

https://leetcode.cn/problems/subsets-ii/submissions/590589695/
tag大法好

var subsetsWithDup = function (nums) {
  nums.sort((a,b)=>a-b)
  const arr = [];
  const ans = [];
  const cache = new Map();
  const dfs = (i) => {
    if (i >= nums.length) {
      const tag = arr.join(" ");
      if (cache.has(tag)) {
        return;
      }
      cache.set(tag, true);
      ans.push([...arr]);
      return;
    }
    dfs(i + 1, arr);
    arr.push(nums[i]);
    dfs(i + 1, arr);
    arr.pop();
  };
  dfs(0)
  return ans;
};

李恒道

https://leetcode.cn/problems/my-calendar-i/submissions/590594518/
依靠gpt的avl模板打过了

class AVLTree {
  constructor(compare) {
    this.root = null;
    this.compare = compare || ((a, b) => a - b);
  }

  getHeight(node) {
    return node ? node.height : 0;
  }

  getBalanceFactor(node) {
    return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
  }

  rightRotate(y) {
    let x = y.left;
    let T2 = x.right;

    x.right = y;
    y.left = T2;

    y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1;
    x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1;

    return x;
  }

  leftRotate(x) {
    let y = x.right;
    let T2 = y.left;

    y.left = x;
    x.right = T2;

    x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1;
    y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1;

    return y;
  }

  insert(node, key) {
    if (!node) return new Node(key);

    if (this.compare(key, node.key) < 0) {
      node.left = this.insert(node.left, key);
    } else if (this.compare(key, node.key) > 0) {
      node.right = this.insert(node.right, key);
    } else {
      return node;
    }

    node.height =
      1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));

    let balance = this.getBalanceFactor(node);

    if (balance > 1 && this.compare(key, node.left.key) < 0) {
      return this.rightRotate(node);
    }

    if (balance < -1 && this.compare(key, node.right.key) > 0) {
      return this.leftRotate(node);
    }

    if (balance > 1 && this.compare(key, node.left.key) > 0) {
      node.left = this.leftRotate(node.left);
      return this.rightRotate(node);
    }

    if (balance < -1 && this.compare(key, node.right.key) < 0) {
      node.right = this.rightRotate(node.right);
      return this.leftRotate(node);
    }

    return node;
  }

  insertKey(key) {
    this.root = this.insert(this.root, key);
  }

  findGreater(node, key, result) {
    if (!node) return;

    if (this.compare(node.key, key) > 0) {
      result.push(node.key);
      this.findGreater(node.left, key, result);
    }

    this.findGreater(node.right, key, result);
  }

  findSmaller(node, key, result) {
    if (!node) return;

    if (this.compare(node.key, key) < 0) {
      result.push(node.key);
      this.findSmaller(node.right, key, result);
    }

    this.findSmaller(node.left, key, result);
  }

  getGreaterThan(key) {
    let result = [];
    this.findGreater(this.root, key, result);
    return result;
  }

  getSmallerThan(key) {
    let result = [];
    this.findSmaller(this.root, key, result);
    return result;
  }
}

// 使用示例

var MyCalendar = function () {
  this.tree = new AVLTree((a, b) => a.left - b.left);
};

/**
 * @param {number} startTime
 * @param {number} endTime
 * @Return {boolean}
 */
MyCalendar.prototype.book = function (startTime, endTime) {
  const lefts = this.tree.getSmallerThan({
    left: startTime,
  });
  const rights = this.tree.getSmallerThan({
    left: endTime ,
  });
  for (let index = 0; index < lefts.length; index++) {
    const left = lefts[index];
    if (left !== undefined) {
      if (left.right >= startTime) {
        return false;
      }
    }
  }
  for (let index = 0; index < rights.length; index++) {
    const right = rights[index];
    if (right !== undefined) {
      if (right.left <= endTime && right.left >= startTime) {
        return false;
      }
      if (right.right <= endTime && right.right >= startTime) {
        return false;
      }
      if (right.left <= startTime && right.right >= endTime) {
        return false;
      }
    }
  }

  this.tree.insertKey({
    left: startTime,
    right: endTime - 1,
  });
  return true;
};

李恒道

https://leetcode.cn/problems/sudoku-solver/submissions/590541196/
dfs炸了

var solveSudoku = function (board) {
  const next = (x, y) => {
    if (y >= board.length) {
      return [x + 1, 0];
    } else {
      return [x, y + 1];
    }
  };
  const line = new Array(9).fill(0).map(() => new Map());
  const row = new Array(9).fill(0).map(() => new Map());
  const block = new Array(9).fill(0).map(() => new Map());
  const setChar = (index, indey, char, status = true) => {
    line[index].set(char, status);
    row[indey].set(char, status);
    block[Math.floor(index / 3) * 3 + Math.floor(indey / 3)].set(char, status);
  };
  const getUseNumber = (x, y) => {
    const list = [];
    for (let index = 1; index <= 9; index++) {
      const num = index + "";
      if (line[x].get(num) == true) {
        continue;
      }
      if (row[y].get(num) == true) {
        continue;
      }
      if (block[Math.floor(x / 3) * 3 + Math.floor(y / 3)].get(num) == true) {
        continue;
      }
      list.push(num);
    }
    return list;
  };
  let ans = false;
  const dfs = (x, y) => {
    if (x == board.length) {
      ans = true;
      return;
    }
    const char = board[x][y];
    if (char == ".") {
      const list = getUseNumber(x, y);
      const [nextX, nextY] = next(x, y);
      for (let index = 0; index < list.length; index++) {
        const num = list[index];
        board[x][y] = num;
        setChar(x, y, num);
        dfs(nextX, nextY);
        if (ans == true) {
          break;
        }
        setChar(x, y, num, false);
        board[x][y] = ".";
      }
    } else {
      const [nextX, nextY] = next(x, y);
      dfs(nextX, nextY);
    }
  };

  for (let index = 0; index < board.length; index++) {
    for (let indey = 0; indey < board[0].length; indey++) {
      const char = board[index][indey];
      if (char == ".") {
        continue;
      }
      setChar(index, indey, char);
    }
  }
  dfs(0, 0);
};

李恒道

https://leetcode.cn/problems/number-of-recent-calls/submissions/590601467/
线段树

class Node {
  left;
  right;
  val = 0;
  lazy = 0;
}
class SegmentTreeDynamic {
  root;
  constructor() {
    this.root = new Node();
  }
  update(node, start, end, l, r, val) {
    if (l <= start && end <= r) {
      node.val += (end - start + 1) * val;
      node.lazy += val;
      return;
    }
    let mid = (start + end) >> 1;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) this.update(node.left, start, mid, l, r, val);
    if (r > mid) this.update(node.right, mid + 1, end, l, r, val);
    this.pushUp(node);
  }
  pushUp(node) {
    node.val = node.left.val + node.right.val;
  }
  query(node, start, end, l, r) {
    if (l <= start && end <= r) return node.val;
    let mid = (start + end) >> 1,
      ans = 0;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) ans += this.query(node.left, start, mid, l, r);
    if (r > mid) ans += this.query(node.right, mid + 1, end, l, r);
    return ans;
  }
  pushDown(node, leftNum, rightNum) {
    if (node.left == null) node.left = new Node();
    if (node.right == null) node.right = new Node();
    if (node.lazy == 0) return;
    node.left.val += node.lazy * leftNum;
    node.right.val += node.lazy * rightNum;
    node.left.lazy += node.lazy;
    node.right.lazy += node.lazy;
    node.lazy = 0;
  }
}

var RecentCounter = function () {
  this.tree = new SegmentTreeDynamic();
};

/**
 * @param {number} t
 * @Return {number}
 */
RecentCounter.prototype.ping = function (t) {
  this.tree.update(this.tree.root, 1, 10 ** 9, t, t, 1);
  return this.tree.query(this.tree.root, 1, 10 ** 9, t - 3000, t);
};

李恒道

https://leetcode.cn/submissions/detail/590601467/
线段树

class Node {
  left;
  right;
  val = 0;
  lazy = 0;
}
class SegmentTreeDynamic {
  root;
  constructor() {
    this.root = new Node();
  }
  update(node, start, end, l, r, val) {
    if (l <= start && end <= r) {
      node.val += (end - start + 1) * val;
      node.lazy += val;
      return;
    }
    let mid = (start + end) >> 1;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) this.update(node.left, start, mid, l, r, val);
    if (r > mid) this.update(node.right, mid + 1, end, l, r, val);
    this.pushUp(node);
  }
  pushUp(node) {
    node.val = node.left.val + node.right.val;
  }
  query(node, start, end, l, r) {
    if (l <= start && end <= r) return node.val;
    let mid = (start + end) >> 1,
      ans = 0;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) ans += this.query(node.left, start, mid, l, r);
    if (r > mid) ans += this.query(node.right, mid + 1, end, l, r);
    return ans;
  }
  pushDown(node, leftNum, rightNum) {
    if (node.left == null) node.left = new Node();
    if (node.right == null) node.right = new Node();
    if (node.lazy == 0) return;
    node.left.val += node.lazy * leftNum;
    node.right.val += node.lazy * rightNum;
    node.left.lazy += node.lazy;
    node.right.lazy += node.lazy;
    node.lazy = 0;
  }
}

var RecentCounter = function () {
  this.tree = new SegmentTreeDynamic();
};

/**
 * @param {number} t
 * @Return {number}
 */
RecentCounter.prototype.ping = function (t) {
  this.tree.update(this.tree.root, 1, 10 ** 9, t, t, 1);
  return this.tree.query(this.tree.root, 1, 10 ** 9, t - 3000, t);
};