ABGR's questions

我正在一个在线平台上解决一个测试，问题陈述与此类似。

Stuart 必须从一个地方到另一个地方（A->B），他每次可以跳 1 步、2 步或 3 步。A 和 B 之间可以有 n 个阻挡器。

我们需要找出他能做到这一点的方法数量。

我觉得这类似于经典的爬楼梯问题，但区别不大，在爬楼梯问题中，你最终必须到达第 n 级台阶，而在这个特定问题中，你必须走下楼梯，这样可能就是第 n+1 级台阶。我说得对吗？

所以我写的代码是这样的：

function countWays(n) {
    
    if (n < 0) return 0;
    if (n === 0) return 1;
    if (n === 1) return 2; //If you have one stop-over, there's two ways to reach. One is take one jump and then one more. Second is take two jumps at once and reach the destination

    return countWays(n-1) + countWays(n-2) + countWays(n-3);
 
}

console.log(countWays(4))

这没有被接受。所以我想知道这有什么问题。我是否也应该添加基本情况n==2？

if (n === 2) return 4

但这仍然没有任何好处，因为n = 3它会返回6，而从视觉上我可以看到，如果有 3 个中途停留，就会有 7 种方式。

我想问的另一个问题是，

在经典的楼梯案例中，基准情况n === 0是 1。这里还是一样吗？这让我有点困惑，因为当没有更多的台阶可以爬的时候，结果怎么会是 1。另一方面，当n === 1你仍然有一条路可以到达目的地时。

此外，f(3)逻辑和直觉表明应该是：

number of ways to reach first stopover + f(2)

而且number of ways to reach first stopover只有一种方式可以做到这一点（跳一次）。

但是，我不能输入if(n == 1) return 1基本情况，因为这样不正确。假设只有一个中途停留点 (n = 1)，实际上有两种到达方式：

1. 跳 2 步
2. 跳 1 步，然后再跳 1 步。

这也造成了一些混乱。

所以我正在解决这个问题：

给定二叉树的根，返回树的直径的长度。

二叉树的直径是树中任意两个节点之间最长路径的长度。该路径可能经过根，也可能不经过根。

两个节点之间的路径的长度由它们之间的边数表示。

以下是我尝试解决的方法：

var diameterOfBinaryTree = function(root) {

  if (root === null) return 0;
  let max_height = 0;

  function maxDepth(node) {
    if (node === null) return 0;
    var lh = maxDepth(node.left);
    var rh = maxDepth(node.right);

    return 1 + Math.max(lh, rh);
  }

  max_height = Math.max(max_height, maxDepth(root.left) + maxDepth(root.right));

  diameterOfBinaryTree(root.left);
  diameterOfBinaryTree(root.right);

  return max_height
}

现在，这确实有效，除了最长路径不经过根节点的情况。但我确实尝试将这些情况合并在一起，即我确实在树的每个节点上进行迭代：

diameterOfBinaryTree(root.left);
diameterOfBinaryTree(root.right);

我哪里做错了？非常感谢您的帮助。请注意，我确实必须将其从 O(N2) 优化到 O(N)，但现在我只是在尝试蛮力。

失败的测试用例是这棵树：

考虑从 -1 到 -2 的最长路径

我正在解决这个问题：

给定一个具有顶点 A、B、C 和 D 的四面体。一只蚂蚁站在顶点 D 处。蚂蚁不会闲着。它将沿着四面体的某些边缘不断从一个顶点移动到另一个顶点。你的任务是计算蚂蚁从初始顶点 D 到自身的路径数，正好是 n 步。

所以对于输入 2 输出：3

我能够按照以下方式使用递归轻松解决这个问题。但对于大输入（例如 15）来说，由于其时间复杂度，它似乎效率不高。

这可以通过动态编程来解决，但我在当前的方法中没有看到任何记忆范围。也许我需要改变方法。所以感谢任何帮助。

我想用递归+记忆来解决它

var count = 0;
function recursion(n, arr=['d']){
    if(n <=1) return 0;
  
  if(arr.length === n+1 && arr[arr.length-1] ==='d'){
    console.log(arr.join(" -> "))
    count++;
    return;
  }

  if(arr.length > n+1) return;

  for(let el of ['a', 'b', 'c', 'd']){
    if(arr[arr.length-1] != el){
       recursion(n, [...arr, el]);
    }
  }
}
recursion(3)

console.log(count);

所以问题就在这里。对于给定的，n我们需要生成所有有效的括号。

例如，对于n=2可能的输出将是()()，(()))

所以我尝试使用递归和回溯来解决。

我采用两个变量 open_bracket 和 close_bracket 以及 ds 来存储括号。

这是我的递归图看起来像

所以我尝试了这个：

function generatePArenthesis(n, open_bracket=0, close_bracket=0, ds=[]){
    if(open_bracket === n && close_bracket === n){
    console.log(ds.toString());
    return
  }
  
  if(open_bracket < n){
    ds.push('(');
    generatePArenthesis(n, open_bracket+ 1, close_bracket, ds);
  }
  
  if(close_bracket<open_bracket){
    ds.push(')');
    generatePArenthesis(n, open_bracket, close_bracket +1, ds);
  }
  
}

generatePArenthesis(2)

当我干运行这个程序时，n=2它似乎确实产生了上面的递归图。但没有给我正确的输出。我哪里出错了？

我的 App.js 看起来像这样：

import ChildComponent from "./ChildComponent";
import { useState, useMemo, useCallback } from "react";

export default function App() {
  const [pageTitle, setPageTitle] = useState("");
  const [anotherProp, setAnotherProp] = useState(1);

  const handleInputChange = useCallback(
    (e) => {
      setPageTitle(e.target.value);
    },
    [pageTitle]
  );

  const handleIncrement = useCallback(() => {
    setAnotherProp(anotherProp + 1);
  }, [anotherProp]);

  return (
    <div className="App">
      <ChildComponent title={pageTitle} handleInputChange={handleInputChange} />

      <div>
        {anotherProp}
        <input
          type={"button"}
          value={"Increment Count"}
          onClick={handleIncrement}
        />
      </div>
    </div>
  );
}

子组件如下所示：

function ChildComponent({ title, handleInputChange }) {
  console.log("Child Component renders");
  return (
    <>
      <input type="text" onChange={handleInputChange} />
      <h1>{title}</h1>
    </>
  );
}

export default ChildComponent;

因为我已经使用过，所以useCallBack我希望当我单击按钮来增加计数时，我的子组件应该保持不受影响并且不会重新渲染。但我的子组件仍然重新渲染。

你能帮我理解为什么吗？

问题是这样的：

有一个 4 位 PIN 码锁。必须从0-5要解锁的钥匙的数字中选择数字。

我们需要找到所有可能的组合，例如0001, 0002, 0003, 0004，等等。