手写算法: 找到小镇的法官

997. 找到小镇的法官

思路

1. 题意：村民都信任法官，法官不会信任任何人。trust = [[编号, 信任人]]，可以用一个出入度的图模型来表示

2. 那么法官能得到的投票数为 n-1，法官投票数为 0

3. 小镇的人编号是从 1 开始的，所以在构建出入度数组时，根据编号从 1 开始排序，那么数组的长度为 n+1，下标为 0 的永远不会被用上

4. 入度：有多少个节点指向你；

   出度：你指向多少个节点

/**
 * @param {number} n
 * @param {number[][]} trust
 * @return {number}
 */
var findJudge = function(n, trust) {
  const inDegress = new Array(n + 1).fill(0);
  const outDegress = new Array(n + 1).fill(0);

  for (const edge of trust) {
    const [x, y] = edge;
    ++inDegress[y];
    ++outDegress[x];
  }

  for (let i = 1; i <= n; i++) {
    if (inDegress[i] === n - 1 && outDegress[i] === 0) return i;
  }
  return -1;
};

手写题: 实现 React useState 原理

思路

• useState 与 useCallback、useMemo 几乎一致。

• 用哈希表存储所有的 state，用 key 作为唯一的标识，每次 setState 后都要还原 key 值，否则无法找到对应的 key

• 每次 setState 时，都需要使用 createRoot 得到的 root.render()更新视图

function _useState() {
  // 与useMemo一样，用key作为唯一标识
  let key = 0;
  // 存储多个state
  let stateMap = new Map();
  let timer = null;

  return function(initState) {
    const curKey = key;
    const state = stateMap.has(curKey) ? stateMap.get(curKey) : initState;
    const setState = newState => {
      stateMap.set(curKey, newState);
      // 每次setState后，都需要还原key值，因为后面需要重新渲染视图
      key = 0;
      timer && clearInterval(timer);
      timer = setTimeout(update);
    };
    key++;
    return [state, setState];
  };
}

const useState = _useState();
export default useState;

// index.js
// 模拟写一下，更新视图，实际测试会报警告，因为拿不到render()
export default function update() {
  const root = ReactDOM.createRoot(document.getElementById('root'));
  root.render(
    <React.StrictMode>
      <App />
    </React.StrictMode>
  );
}

update();

demo