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

李恒道

https://leetcode.cn/problems/h-index/submissions/569715088/?envType=study-plan-v2&envId=top-interview-150
抠边界有点困难，其他还好

var hIndex = function (citations) {
    let maxH = 0;
    citations = citations.sort((a, b) => b-a);
    for (let index = 0; index < citations.length; index++) {
        const num = citations[index];
        if (num > maxH) {
            maxH++;
        }else{
            break
        }

    }
    return maxH
};

李恒道

https://leetcode.cn/problems/insert-delete-getrandom-o1/submissions/569717371/?envType=study-plan-v2&envId=top-interview-150
设计题
很容易就秒了

var RandomizedSet = function () {
  this.cache = new Map();
};

/**
 * @param {number} val
 * @Return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {
  if (this.cache.has(val)) {
    return false;
  }
  this.cache.set(val, true);
  return true;
};

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {
  if (!this.cache.has(val)) {
    return false;
  }
  this.cache.delete(val);
  return true;
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
  return [...this.cache][Math.floor(Math.random() * this.cache.size)][0];
};

李恒道

https://leetcode.cn/problems/find-the-difference/submissions/569718040/?envType=study-plan-v2&envId=programming-skills

func findTheDifference(s string, t string) byte {
    var cache map[int32]int32 = make(map[int32]int32)
    for _, v := range s {
        cache[v]++
    }
    var result byte
    for _, v := range t {
        if cache[v] == 0 {
            result = byte(v)
            break
        }
        cache[v]--
    }
    return result
}

李恒道

https://leetcode.cn/problems/gas-station/submissions/569905538/?envType=study-plan-v2&envId=top-interview-150
我也知道要贪心
但是就是贪不起来...

var canCompleteCircuit = function (gas, cost) {
  for (let index = 0; index < gas.length; index++) {
    let pos = 0;
    let total = 0;
    if (gas[index] < cost[index]) {
      continue;
    }
    while (pos < gas.length) {
      total += gas[(index + pos) % gas.length];
      total -= cost[(index + pos) % gas.length];
      if (total < 0) {
        index = index+pos;
        break;
      }
      pos++;
    }
    if (total >= 0) {
      return index;
    }
  }
  return -1;
};

李恒道

https://leetcode.cn/problems/candy/submissions/569905683/?envType=study-plan-v2&envId=top-interview-150
一眼双遍历

/**
 * @param {number[]} ratings
 * @Return {number}
 */
var candy = function (ratings) {
  const arr = new Array(ratings.length).fill(1);
  const arr2 = new Array(ratings.length).fill(1);
  for (let index = 1; index < ratings.length; index++) {
    const rate = ratings[index];
    const lastRate = ratings[index - 1];
    if (rate > lastRate) {
      arr[index] = arr[index - 1] + 1;
    }
  }
  for (let index = ratings.length - 1; index >= 0; index--) {
    const rate = ratings[index];
    const lastRate = ratings[index + 1];
    if (rate > lastRate) {
      arr2[index] = arr2[index + 1] + 1;
    }
  }
  let total = 0;
  for (let index = 0; index < ratings.length; index++) {
    total += Math.max(arr[index], arr2[index]);
  }
  return total
};

李恒道

https://leetcode.cn/problems/roman-to-integer/submissions/569906117/?envType=study-plan-v2&envId=top-interview-150
简单题
一次秒了

var romanToInt = function (s) {
  const map = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000,
    undefined: 0,
  };
  let total = 0;
  for (let index = 0; index < s.length; index++) {
    const char = s[index];
    if (char == "I" && (s[index + 1] == "V" || s[index + 1] == "X")) {
      total -= map[char];
      total += map[s[index + 1]];
      index++;
    } else if (char == "X" && (s[index + 1] == "L" || s[index + 1] == "C")) {
      total -= map[char];
      total += map[s[index + 1]];
      index++;
    } else if (char == "C" && (s[index + 1] == "D" || s[index + 1] == "M")) {
      total -= map[char];
      total += map[s[index + 1]];
      index++;
    } else {
      total += map[char];
    }
  }
  return total
};

李恒道

https://leetcode.cn/problems/reverse-words-in-a-string/submissions/569906388/?envType=study-plan-v2&envId=top-interview-150
字符串处理题，还算简单

var reverseWords = function (s) {
  let result = "";
  let word = "";
  for (let index = 0; index < s.length; index++) {
    const char = s[index];
    if (char !== " ") {
      word += char;
    } else {
      if (s[index - 1] !== undefined && s[index - 1] !== " ") {
        if(result==""){
          result = word
        }else{
          result = word + " " + result;
        }
        word=""
      }
    }
  }
  if(word!==""){
    result = word + (result==""?"": " " + result)
  }
  return result
};

李恒道

https://leetcode.cn/problems/largest-1-bordered-square/submissions/570102367/
需要进行状态的缓存，还是挺复杂的

var largest1BorderedSquare = function (grid) {
    const right = new Array(grid.length).fill(0).map(() => new Array(grid[0].length).fill(0))
    const down = new Array(grid.length).fill(0).map(() => new Array(grid[0].length).fill(0))
    for (let index = 0; index < grid.length; index++) {
        for (let indey = grid[0].length-1; indey>=0; indey--) {
            if (grid[index][indey] == 0) {
                right[index][indey] = 0
            } else {
                right[index][indey] = (right[index][indey + 1] ?? 0) + 1
            }
        }
    }

    for (let index = grid.length - 1; index >= 0; index--) {
        for (let indey = 0; indey <grid[0].length; indey++) {
            if (grid[index][indey] == 0) {
                down[index][indey] = 0
            } else {
                down[index][indey] = (down[index + 1]?.[indey] ?? 0) + 1
            }
        }
    }
    let ans = 0;
    for (let index = 0; index < grid.length; index++) {
        for (let indey = 0; indey < grid[0].length; indey++) {
            if (grid[index][indey] == 0) {
                continue;
            }
            let pos = 0;
            while (true) {
                if ((index + pos) >= grid.length || (indey + pos) >= grid[0].length) {
                    break;
                }
                if (right[index][indey] >= (pos + 1) && down[index][indey] >= (pos + 1) && right[index + (pos)][indey] >= (pos + 1) && down[index][indey + (pos)] >= (pos + 1)) {
                    ans = Math.max(ans, pos + 1)
                }
                pos++;
            }
        }
    }
    return ans*ans
};

李恒道

https://leetcode.cn/problems/closest-subsequence-sum/submissions/570104234/
没猜到是分治，没想到最后合并还可以利用双指针
我想用二分秒来着，虽然也是Nlog，但是编写的困难度高太多了

var minAbsDifference = function (nums, goal) {
    const sum = (start, end) => {
        const result = []
        const dfs = (index, total) => {
            if (index >= end) {
                result.push(total);
                return;
            }
            dfs(index + 1, total)
            dfs(index + 1, total + nums[index])
        }
        dfs(start,0)
        return result
    }
    const arr1 = sum(0, Math.floor(nums.length / 2));
    const arr2 = sum(Math.floor(nums.length / 2), nums.length);
    arr1.sort((a, b) => a - b);
    arr2.sort((a, b) => a - b);
    let l = 0;
    let r = arr2.length - 1;
    let result = Number.MAX_SAFE_INTEGER;
    while (l < arr1.length && r >= 0) {
        const sum = arr1[l] + arr2[r];
        result = Math.min(result, Math.abs(sum - goal));
        if (sum > goal) {
            //r小一点
            r--;
        } else {
            //l大一点
            l++;

        }
    }
    return result;
};

李恒道

https://leetcode.cn/problems/freedom-trail/submissions/570104763/
缓存dfs秒了！

var findRotateSteps = function (ring, key) {
    const map = new Map()
    for (let index = 0; index < ring.length; index++) {
        const char = ring[index];
        if (map.has(char)) {
            (map.get(char)).push(index)
        } else {
            map.set(char, [index])
        }
    }
    const calcStep = (x, y) => {
        const methodA = Math.abs(x - y)
        return Math.min(methodA, ring.length - methodA)
    }
    const cache=new Map()
    const dfs = (pos, index) => {
        const flag=`${pos} ${index}`
        if(cache.has(flag)){
            return cache.get(flag)
        }
        if(index>=key.length){
            return 0
        }
        const nextArr = map.get(key[index])
        let result = Number.MAX_SAFE_INTEGER
        for (let nextIndex = 0; nextIndex < nextArr.length; nextIndex++) {
            const nextPos = nextArr[nextIndex];
            const step = calcStep(pos, nextPos);
            result = Math.min(result, step + 1 + dfs(nextPos, index + 1))
        }
        cache.set(flag,result)
        return result
    }
    return dfs(0, 0)
};