leetcode 문제 해결 기록(16)-간단

1. 두 갈래 검색 트리 자르기

제목:
두 갈래 검색 트리를 지정하고 최소 경계 L과 최대 경계 R을 지정합니다.두 갈래 검색 트리를 트림하여 모든 노드의 값을 [L, R](R>=L)로 만듭니다.너는 나무의 뿌리 노드를 바꿔야 할 수도 있으니, 결과는 잘린 두 갈래 검색 나무의 새로운 뿌리 노드로 돌아가야 한다.
사고방식: 차례로 처리하면 된다.모든 과목의 나무에 대해 노드의 값이 경계 안에 있는지 판단한다.경계 안에 있으면, 이 루트 노드를 되돌려주고, 좌우 트리를 각각 편집합니다.L보다 작으면 오른쪽 하위 트리의 모든 값이 충족되지 않으므로 왼쪽 하위 트리의 트림 결과를 반환합니다.R보다 크면 오른쪽 하위 트리의 트림 결과가 반환됩니다.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} L
 * @param {number} R
 * @return {TreeNode}
 */
var trimBST = function(root, L, R) {
  if (!root) return root;
  if (root.val < L) return trimBST(root.right, L, R);
  if (root.val > R) return trimBST(root.left, L, R);
  root.left = trimBST(root.left, L, R);
  root.right = trimBST(root.right, L, R);
  return root;
};

2. 두 갈래 나무 중 두 번째로 작은 노드

제목:
비공식적이고 특수한 두 갈래 트리를 지정합니다. 노드마다 정수이고 노드마다 하위 노드의 수량은 2 또는 0만 가능합니다.만약 한 노드에 두 개의 노드가 있다면, 이 노드의 값은 두 개의 노드 중 비교적 작은 것과 같다.
사고방식: 차례로 나무를 처리한다.우선, 루트 노드의 값을 기록합니다.우리는 먼저 명확하게 해야 한다. 만약에 어떤 노드의 하위 노드가 루트 노드의 값과 같지 않다면 이 노드의 나무의 모든 노드의 최소값은 이 하위 노드의 값이고 이 값은 루트 노드의 값보다 더 클 것이다.그래서 이 값은 가능한 결과로 비교해야 한다.
루트 노드의 값과 같으면 먼저 하위 노드가 있는지 판단하고 하위 노드가 undefined로 되돌아오지 않으며 하위 노드가 있으면 귀속 처리합니다.
우리의 목표는 하위 트리에서 루트 노드와 같지 않은 최소값을 찾는 것이다

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findSecondMinimumValue = function(root) {
  if (!root) return -1;
  const search = (root, val) => {
    if (!root) return;
    if (root.val === val) {
      if (!root.left) return;
      const left = search(root.left, val);
      const right = search(root.right, val);
      if (!left || !right) {
        return left || right;
      } else {
        return Math.min(left, right);
      }
    } else {
      return root.val;
    }
  };
  const left = search(root.left, root.val);
  const right = search(root.right, root.val);
  if (!left || !right) {
    return left || right || -1;
  } else {
    return Math.min(left, right);
  }
};

3. 최장 연속 증가 수열

제목:
정렬되지 않은 정수 그룹을 지정하고 가장 길고 연속적인 증가 서열을 찾아 이 서열의 길이를 되돌려줍니다.
사고방식: 반복, 지난번 귀속수열이 시작된 숫자의 하표를 기록하고, 매번 하강을 만날 때마다 하표를 계산한다. 반복이 끝난 후에도 한 번 계산해야 한다는 것을 주의한다.

/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function(nums) {
  let length = 0;
  let index = 1;
  nums.unshift(-Infinity)
  const l = nums.length;
  for (let i = 1; i < l; i++) {
    if (nums[i] <= (nums[i - 1])) {
      length = Math.max(i - index, length);
      index = i;
    }
  }
  return Math.max(l - index, length);
};

4. 답글 문자열 검증 II

제목: 비어 있지 않은 문자열 s 을 지정하고 최대 문자를 삭제합니다.회문 문자열이 될 수 있는지 판단합니다.
사고방식: 문자를 삭제할 수도 있고, 왼쪽 문자를 삭제할 수도 있고, 오른쪽 문자를 삭제할 수도 있기 때문에 분기 처리를 합니다.논리를 복용하기 위해 삭제 횟수를 기록하고 이중 바늘로 실현할 수 있다

/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function(s) {
  const valdate = (s, count) => {
    let left = 0;
    let right = s.length - 1;
    while (left < right) {
      if (count > 1) return false;
      if (s[left] === s[right]) {
        left++;
        right--;
      } else {
        if (!count) {
          return (
            valdate(s.slice(left + 1, right + 1), 1) ||
            valdate(s.slice(left, right), 1)
          );
        } else {
          return false;
        }
      }
    }
    return true;
  };
  return valdate(s, 0);
};

5. 야구 경기

제목:
너는 지금 야구 경기 기록원이다.각 문자열은 다음 네 가지 유형 중 하나일 수 있는 문자열 목록을 지정합니다. 1.정수(1라운드의 득점): 당신이 이번 라운드에서 얻은 포인트 수를 직접 표시합니다.2. "+"(한 라운드의 득점): 이번 라운드가 얻은 득점은 지난 두 라운드의 유효 라운드 득점의 총체임을 나타낸다.3. "D"(한 라운드의 득점): 이번 라운드가 얻은 득점이 전 라운드 유효 라운드의 득점의 두 배임을 나타낸다.4. "C"(한 작업, 이것은 한 라운드의 점수가 아닙니다): 마지막 유효 라운드의 점수가 무효이고 제거되어야 합니다.
매 라운드의 조작은 영구적이어서 전 라운드와 후 라운드에 영향을 미칠 수 있다.너는 네가 모든 라운드에서 득점한 총계를 되돌려야 한다.
예 1:
입력: ['5','2','C','D','+'] 출력: 30 해석: 1라운드: 5점을 받을 수 있습니다.총계: 5.2라운드: 너는 2점을 받을 수 있다.총계: 7.작업 1: 2라운드의 데이터가 잘못되었습니다.총계: 5.3라운드: 10점을 받을 수 있습니다 (2라운드 데이터는 삭제되었습니다).총 수: 15.4라운드: 너는 5+10=15점을 받을 수 있다.총 수: 30.예 2:
입력: ['5','-2','4','C','D','9','+','+'] 출력: 27 해석: 1라운드: 5점을 받을 수 있습니다.총계: 5.2라운드: 너는 -2점을 받을 수 있다.총 수: 3.3라운드: 너는 4점을 받을 수 있다.총계: 7.작업 1: 3라운드의 데이터가 잘못되었습니다.총 수: 3.4라운드: 당신은 -4점을 얻을 수 있습니다 (3라운드 데이터는 삭제되었습니다).총계: -1.5라운드: 너는 9점을 받을 수 있다.총 수: 8.6라운드: 너는 -4+9=5점을 받을 수 있다.총수는 13이다.7라운드: 9+5=14점을 받을 수 있다.총수는 27이다.참고:
입력 목록의 크기는 1과 1000 사이입니다.목록의 각 정수는 -30000과 30000 사이입니다.
사고방식: 하나의 수조를 만들고 매번 유효한 라운드의 득점을 저장하며 마지막으로 수조를 누적하면 된다

/**
 * @param {string[]} ops
 * @return {number}
 */
var calPoints = function(ops) {
  const scores = [];
  for (const s of ops) {
    switch (s) {
      case "+":
        scores.push(
          (scores[scores.length - 1] || 0) + (scores[scores.length - 2] || 0)
        );
        break;
      case "D":
        scores.push((scores[scores.length - 1] || 0) * 2);
        break;
      case "C":
        scores.pop();
        break;
      default:
        scores.push(+s);
    }
  }
  return scores.reduce((res, i) => res + i, 0);
};