ABGR's questions

Eu estava resolvendo um teste em uma plataforma online e o problema era parecido com este.

Stuart tem que ir de um lugar para outro (A-> B) e ele pode pular 1 passo, 2 passos ou 3 passos de cada vez. Pode haver n número de paradas entre A e B.

Precisamos descobrir quantas maneiras ele pode fazer isso.

Eu sinto que isso é similar ao problema clássico de subir escadas com pouca diferença de que lá você finalmente tinha que chegar ao n-ésimo degrau, enquanto neste problema em particular você tem que descer, o que faz provavelmente n+1 degrau. Estou certo?

Então o código que escrevi é este:

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))

Isso não foi aceito. Então, estou apenas me perguntando o que há de errado nisso. Eu deveria ter adicionado base case para n==2também?

if (n === 2) return 4

Isso ainda não adianta nada, pois n = 3retornaria 6, enquanto visualmente posso ver que haveria 7 maneiras se houvesse 3 paradas.

Outra pergunta que quero fazer é:

No caso clássico de escada, o caso base para n === 0seria 1. Ainda seria o mesmo aqui? Isso me confunde um pouco, pois quando não há mais degraus para subir, como o resultado pode ser 1. Por outro lado, aqui, quando n === 1você ainda tem um caminho que deve seguir para chegar ao destino.

Além disso, f(3)a lógica e a intuição dizem que deveria ser:

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

E number of ways to reach first stopoverseria apenas um, já que só há uma maneira de fazer isso (dando um salto).

No entanto, não posso colocar if(n == 1) return 1no caso base, pois seria incorreto. Digamos que há apenas uma parada (n = 1), na verdade há duas maneiras de chegar:

1. Pular 2 passos
2. Pule 1 passo e depois mais um.

Então isso também está criando um pouco de confusão.

Então, estou trabalhando neste problema :

Dada a raiz de uma árvore binária, retorne o comprimento do diâmetro da árvore.

O diâmetro de uma árvore binária é o comprimento do caminho mais longo entre quaisquer dois nós de uma árvore. Este caminho pode ou não passar pela raiz.

O comprimento de um caminho entre dois nós é representado pelo número de arestas entre eles.

Veja como tentei resolver:

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
}

Agora, isso funciona, exceto aparentemente no caso em que o caminho mais longo não passa pelo nó raiz. Mas tentei incorporar esses casos, ou seja, itero em cada nó da árvore:

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

Onde estou errando? Agradeço qualquer ajuda. Observe que preciso otimizar isso de O(N2) para O(N), mas por enquanto estou apenas tentando a força bruta.

O caso de teste para o qual falha é esta árvore:

Considere o caminho mais longo nas passagens de -1 a -2

Eu estava resolvendo este problema:

Dado um tetraedro com vértices A, B, C e D. Uma formiga está no vértice D. A formiga não fica parada. Ele continuará se movendo de um vértice para outro ao longo de alguma aresta do tetraedro. Sua tarefa é contar o número de maneiras pelas quais a formiga pode ir do vértice inicial D até si mesma em exatamente n passos.

Então, para entrada 2 Saída: 3

Consegui resolver isso confortavelmente usando recursão da seguinte maneira. Mas não parece muito eficiente para uma entrada grande, digamos, 15, devido à sua complexidade de tempo.

Isso pode ser resolvido através de programação dinâmica, mas não vejo nenhum escopo de memoização na minha abordagem atual. Talvez eu precise mudar a abordagem. Então aprecio qualquer ajuda.

Eu gostaria de resolver isso usando recursão + memoização

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);

Então aqui está o problema. Para um dado, nprecisamos gerar todos os parênteses válidos.

Por exemplo, para n=2a saída possível será ()(),(()))

Então tentei resolver usando recursão e retrocesso.

Pego duas variáveis, open_bracket e close_bracket junto com um ds para armazenar os parênteses.

Aqui está meu diagrama recursivo parecido

Então com isso eu tentei isso:

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)

quando executo este programa, n=2ele parece produzir o diagrama recursivo acima. Mas não me dá a saída correta. Onde estou cometendo erro?

Eu tenho App.js que se parece com isto:

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>
  );
}

O componente filho se parece com isto:

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

export default ChildComponent;

Desde que usei, useCallBackespero que, ao clicar no botão para aumentar a contagem, meu componente filho permaneça inalterado e não seja renderizado novamente. Mas meu componente filho ainda é renderizado novamente.

Você pode me ajudar a entender por quê?

O problema é assim:

Existe um bloqueio de PIN de 4 dígitos. Os dígitos devem ser escolhidos entre os dígitos 0-5da chave para desbloquear.

Precisamos encontrar todas as combinações possíveis 0001, 0002, 0003, 0004, como e assim por diante.