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

李恒道

https://leetcode.cn/problems/peak-index-in-a-mountain-array/submissions/588536794/?envType=study-plan-v2&envId=primers-list
标准二分法的故事

func peakIndexInMountainArray(arr []int) int {
    var l int
    var r int = len(arr) - 1
    for l != r {
        center := l + int((r-l)/2)
        next := center + 1
        if arr[center] > arr[next] {
            r = center
        } else {
            l = next
        }
    }
    return l
}

李恒道

https://leetcode.cn/problems/transpose-matrix/submissions/588536961/?envType=study-plan-v2&envId=primers-list
数组翻转

func transpose(matrix [][]int) [][]int {
    ans := make([][]int, len(matrix[0]))
    for i := range ans {
        ans[i] = make([]int, len(matrix))
    }
    for i := 0; i < len(matrix); i++ {
        for y := 0; y < len(matrix[0]); y++ {
            ans[y][i] = matrix[i][y]
        }
    }
    return ans
}

李恒道

https://leetcode.cn/problems/powx-n/submissions/588537136/?envType=study-plan-v2&envId=top-interview-150
一眼位运算乘法
不过懒得优化了

var myPow = function (x, n) {
  if (n < 0) {
    n = n * -1;
    x = 1 / x;
  }
  let num = x;
  let ans = 1;
  for (let index = 0; index < 32; index++) {
    if ((n & (1 << index)) !== 0) {
      ans = ans * num;
    }
    num = num * num;
  }
  return ans;
};

李恒道

https://leetcode.cn/problems/binary-search-tree-iterator/submissions/588537224/?envType=study-plan-v2&envId=top-interview-150
看到h一开始以为是重链刨分
想了一下重链不太符合空间要求
应该就是根据高度构造了
试了一下一次过

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 */
var BSTIterator = function (root) {
  this.stack = [];
  while (root !== null) {
    this.stack.push(root);
    root = root.left;
  }
};

/**
 * @Return {number}
 */
BSTIterator.prototype.next = function () {
  const item = this.stack.pop();
  let root = item.right;
  while (root !== null) {
    this.stack.push(root);
    root = root.left;
  }
  return item.val;
};

/**
 * @return {boolean}
 */
BSTIterator.prototype.hasNext = function () {
  if (this.stack.length == 0) {
    return false;
  }
  return true;
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * var obj = new BSTIterator(root)
 * var param_1 = obj.next()
 * var param_2 = obj.hasNext()
 */

李恒道

https://leetcode.cn/problems/sort-integers-by-the-power-value/submissions/588537770/
秒了

const getRank = (num) => {
    if (num == 1) {
      return 0;
    }
    if (num % 2 == 0) {
      return getRank(num / 2) + 1;
    } else {
      return getRank(3 * num + 1) + 1;
    }
  };
var getKth = function (lo, hi, k) {
  const arr = new Array(hi - lo + 1).fill(0).map((v, index) => lo + index);
  arr.sort((a, b) => {

    a1=getRank(a);
    b1=getRank(b);
    if(a1==b1){
        return a-b
    }
    return a1-b1
  });
  return arr[k-1]

};

李恒道

https://leetcode.cn/problems/clone-graph/submissions/588649523/?envType=study-plan-v2&envId=top-interview-150
dfs秒了

var cloneGraph = function (node) {
    const cache = new Map()
    const cloneDfs = (node) => {
        if(node==null){
            return null
        }
        if (cache.has(node.val)) {
            return cache.get(node.val)
        }
        const newNode = {
            val: node.val,
            neighbors: [],
        }
        cache.set(node.val,newNode)

        for (let index = 0; index < node.neighbors.length; index++) {
            const neighbor = node.neighbors[index];
            newNode.neighbors.push(cloneDfs(neighbor))
        }
        return newNode
    }
    return cloneDfs(node)
};

李恒道

https://leetcode.cn/problems/insert-interval/submissions/588668749/?envType=study-plan-v2&envId=top-interview-150
狂写判断

var insert = function (intervals, newInterval) {
    let newInter = [...newInterval];
    let isInsert = false;
    let ans = []
    for (let index = 0; index < intervals.length; index++) {
        const interval = intervals[index];
        if ((interval[0] > newInter[0] && interval[0] < newInter[1])
            || (interval[1] > newInter[0] && interval[1] < newInter[1])
            || (interval[0] <= newInter[0] && interval[1] >= newInter[1])
            || (interval[1] == newInter[0])
            || (interval[0] == newInter[1])) {
            newInter[0] = Math.min(interval[0], newInter[0])
            newInter[1] = Math.max(interval[1], newInter[1])
        } else if (!isInsert && interval[0] > newInter[1]) {
            ans.push(newInter)
            ans.push(interval)
            isInsert = true
        } else {
            ans.push(interval)
        }
    }
    if (!isInsert) {
        ans.push(newInter)
    }
    return ans

};

李恒道

https://leetcode.cn/problems/sqrtx/submissions/588671482/?envType=study-plan-v2&envId=top-interview-150
二分法秒了

var mySqrt = function (x) {
    let l = 0;
    let r = x;
    let ans = x;
    while (l != r) {
        let c = l + Math.floor((r - l) / 2)
        if (c * c <= x&&c!=0) {
            ans = c;
            l = c + 1;
        } else {
            r = c
        }
    }
    return ans
};

李恒道

https://leetcode.cn/problems/simplify-path/submissions/588714181/?envType=study-plan-v2&envId=top-interview-150
堆栈秒

var simplifyPath = function (path) {
  const stack = [];
  let str = "";
  if(path[path.length-1]!=='/'){
    path+="/"
  }
  for (let index = 1; index < path.length; index++) {
    const char = path[index];
    if (char == "/" && str !== "") {
      if (str != ".") {
        if (str == "..") {
          stack.pop();
        } else {
          stack.push(str);
        }
      }
      str = "";
    } else {
      if(char!=='/'){
        str += char;
      }
    }
  }
  return '/'+stack.join('/')
};

李恒道

https://leetcode.cn/problems/permutations-ii/submissions/588930894/
回溯题，秒了

var permuteUnique = function (nums) {
  const swap = (a, b) => {
    const temp = nums[b];
    nums[b] = nums[a];
    nums[a] = temp;
  };
  const ans = [];
  const cache = new Map();
  const dfs = (i) => {
    if (i == nums.length - 1) {
      const tag = nums.join(" ");
      if (cache.has(tag) ) {
        return;
      }
      cache.set(tag, true);
      ans.push([...nums]);
      return;
    }
    for (let index = i; index < nums.length; index++) {
      swap(i, index);
      dfs(i + 1);
      swap(i, index);
    }
  };
  dfs(0);
  return ans;
};