leetcode 문제 기록 (1) - 간단

1. 두 갈래 나무의 모든 경로

제목:
두 갈래 나무를 정해서 뿌리 노드에서 잎 노드까지의 모든 경로를 되돌려줍니다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
사고방식: 귀속이나 교체가 모두 가능하며, 지난 라운드의 값을 기록하면 된다

/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function (root) {
  if (!root) return [];
  const str = `${root.val}`;
  const res = [];
  if (!root.left && !root.right) {
    return [str];
  }
  binaryTreePathsDeep(root.left, str, res);
  binaryTreePathsDeep(root.right, str, res);
  return res;
};
var binaryTreePathsDeep = (root, str, res) => {
  if (!root) return;
  str += `->${root.val}`;
  if (!root.left && !root.right) {
    res.push(str);
  }
  if (root.left) {
    binaryTreePathsDeep(root.left, str, res);
  }
  if (root.right) {
    binaryTreePathsDeep(root.right, str, res);
  }
};

/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function (root) {
 if (!root) return [];
  const stack = [];
  const res = [];
  stack.push({
    str: "",
    node: root,
  });
  while (stack.length) {
    const item = stack.shift();
    const str = item.str ? `${item.str}->${item.node.val}` : `${item.node.val}`;
    if (!item.node.left && !item.node.right) {
      res.push(str);
    } else {
      if (item.node.left) {
        stack.push({
          str,
          node: item.node.left,
        });
      }
      if (item.node.right) {
        stack.push({
          str,
          node: item.node.right,
        });
      }
    }
  }
  return res;
};

/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function (root, str) {
  if (!root) return [];
  str = str ? `${str}->${root.val}` : `${root.val}`;
  const res = [];
  if (!root.left && !root.right) {
    return [str];
  }
  return binaryTreePaths(root.left, str).concat(
    binaryTreePaths(root.right, str)
  );
};

2. 여러분 더하기

제목: 비음정수num를 정하고 결과가 한 자릿수가 될 때까지 각 위치의 숫자를 반복해서 덧붙인다.
진급: 당신은 순환이나 귀속을 사용하지 않고 O(1) 시간의 복잡도 내에서 이 문제를 해결할 수 있습니까?
사고방식: 우선 귀속 또는 순환

var addDigits = function(num) {
  const s = `${num}`;
  let res = 0;
  for (const i of s) {
    res += +i;
  }
  return res < 10 ? res : addDigits(res);
};

그리고 진급을 시도해 보세요.
귀속이나 순환을 사용하지 않는다면 관찰해야 한다.
네 자리 수 abcd를 가정하면 abcd는 각각 한 자리의 숫자이다.그러면 이 수는 a*1000+b*100+c*10+d*1을 표시할 수도 있고, a*999+a+b*99+b+c*9+c+d를 표시할 수도 있으며, 마지막으로 우리는 a+b+c+d를 얻었다.
이게 무슨 뜻이죠?이 수가 9에 대한 나머지 결과는 a+b+c+d, 즉 여러분의 합이다.즉, a+b+c+d가 첫 번째 결과다.같은 이치로, 이것은 우리가 다시 9를 취하면 결국 결과이다.
설령 결과가 0이라고 하더라도 결과는 9라는 작은 문제가 있다.그래서 우리는 0에 대해 특별히 처리해야 한다.아래와 같은 두 가지.

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function(num) {
    if(!num)return 0
  return num%9 || 9;
};

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function(num) {
return (num-1)%9 +1
};

3.못난이

제목:
주어진 수가 추수인지 아닌지를 판단하는 프로그램을 작성합니다.
추수는 질인수2, 3, 5만 포함하는 정수다.
사고방식: 우리는 결과를 2, 35로 나누었다. 만약에 하나의 결과가 정수이고 값이 1보다 크면 추수가 아니다.안 그러면 못난이야.

/**
 * @param {number} num
 * @return {boolean}
 */
const a = [2, 3, 5];
var isUgly = function (num) {
  if (!num) return false;
  let count = 0;
  a.forEach((i) => {
    if (!(num % i)) {
      num /= i;
      count++;
    }
  });
  if (num == 1) return true;
  if (!count) return false;
  return isUgly(num);
};

4. 숫자 부족

제목: 0, 1, 2, ..., n 중 n개의 수를 포함하는 서열을 정하고 0을 찾아라...n에는 시퀀스에 나타나는 그 수가 없습니다.
사고방식: 우리는 직접 화해를 구하고 순서대로 상감할 수 있는데, 결과는 바로 부족한 그 수이다.

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
 const sum = (0 + nums.length)*(nums.length+1) / 2;
  return nums.reduce((sum, i) => {
    return sum - i;
  }, sum);
};

5. 첫 번째 잘못된 버전

제목:
당신은 제품 매니저입니다. 현재 한 팀을 이끌고 새로운 제품을 개발하고 있습니다.불행하게도, 당신의 제품의 최신 버전은 품질 검사를 통과하지 못했다.모든 버전은 이전 버전을 바탕으로 개발되었기 때문에 잘못된 버전 이후의 모든 버전은 틀렸다.
만약에 n개의 버전이 있다고 가정하면 [1,2,..., n], 이후에 모든 버전이 잘못된 첫 번째 버전을 찾아내고 싶습니다.
boolisBadVersion (version) 인터페이스를 호출하여 버전 번호version이 단원 테스트에서 오류가 발생했는지 판단할 수 있습니다.첫 번째 오류 버전을 찾기 위해 함수를 실행합니다.API 호출 횟수를 최소화해야 합니다.
생각: 우선, 우리 먼저 간단한 것, 즉 순서대로 두루 훑어보자

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        while(n){
            if(!isBadVersion(n)){
                return n+1
            }
            n--
        }
        return 1
    };
};

단점은 시간의 복잡도가 너무 높다는 것이다. 온이다.
이런 검색은 사실 가장 좋은 것은 이분법이고 시간 복잡도는log2이다.이것은 정렬 수조가 어떤 수를 찾는 것과 유사하다

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
            if (n == 1) return n;
    let left = 1;
    if(isBadVersion(left))return left
    while (n!==left+1) {
      const middle = Math.floor((left + n) / 2);
      if (isBadVersion(middle)) {
        n = middle;
      } else {
        left = middle;
      }
    }
    return n;
    };
};