leetcodeブラシ記録(1)-中等

1.四数の和
タイトル:
n個の整数を含む配列numsとターゲット値targetを与え、numsにa+b+c+dの値がtargetと等しいように4つの要素a,b,c,dが存在するかどうかを判断する.条件を満たし、繰り返さないすべての四元グループを見つけます.
注意:
答えに重複する四元グループを含めてはいけません.
考え方:前の三数の和と似ていて、もう一つのループを包みます.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
  nums.sort((a, b) => a - b)
  let res = []
  let len = nums.length
  for (let i = 0; i < len - 3; i++) {
    if(nums[i] === nums[i - 1]) continue
    for (let j = i + 1; j < len - 2; j++){
      if(res.length > 0){
        let res0 = res[res.length - 1][0]
        let res1 = res[res.length - 1][1]
        if(res0 === nums[i] && res1 === nums[j]) continue
      }
      let left = j + 1
      let right = len - 1
      while(left < right){
        let sum = nums[i] + nums[j] +　nums[left] + nums[right]
        if (sum === target) {
          res.push([nums[i], nums[j], nums[left], nums[right]])
          left++
          while(nums[left] === nums[left - 1]) left++
        } else if (sum < target) {
          left++
        } else {
          right--
        }
      }
    }
  }
  return res
};

2.チェーンテーブルの最後からN番目のノードを削除する
タイトル:チェーンテーブルを指定し、チェーンテーブルの最後からn番目のノードを削除し、チェーンテーブルのヘッダノードに戻ります.
アイデア:ノードを1つの配列に入れて、配列の下付きの特性を利用してノードを削除します

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
  const res = [];
  let node = head;
  while (node) {
    res.push(node);
    node = node.next;
  }
  if(n===res.length)return head.next
  res[res.length - 1 - n].next = res[res.length - n].next;
  return head;
};

ダブルポインタ:ダブルポインタ法の考え方は、速いポインタを先にn回走って、それから2つのノードを同時に走って、最後のノードまで走って、このように遅いポインタの位置は最後からN番目のノードの前のノードです

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
  const node = new ListNode(1);
  node.next = head;
  let slow = node;
  let fast = node;
  while (n--) {
    fast = fast.next;
  }
  while (fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return node.next;

};

3.かっこ生成
タイトル:数字nは括弧を生成する対数を表し、可能なすべての有効な括弧の組み合わせを生成するために関数を設計してください.
考え方:ここで注意しなければならないのは有効カッコの定義です.いずれの位置に対しても、左側の左かっこは右かっこより少なくないに違いありません.

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesisA = (left, right, pre, res) => {
  if (!pre) {
    generateParenthesisA(--left, right, "(", res);
  } else if (left == right) {
    generateParenthesisA(--left, right, `${pre}(`, res);
  } else if (!left && right == 1) {
    res.push(`${pre})`);
  } else if (!left) {
    generateParenthesisA(left, --right, `${pre})`, res);
  } else {
    generateParenthesisA(--left, right, `${pre}(`, res);
    generateParenthesisA(++left, --right, `${pre})`, res);
  }
  return res;
};
var generateParenthesis = function (n) {
  if (!n) return [];
  const left = n;
  const right = n;
  return generateParenthesisA(left, right, "", []);
};

配列を変えるとテールで再帰できます

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesisA = (left, right, pre, res) => {
  if (!pre) {
    return generateParenthesisA(--left, right, "(", res);
  } else if (left == right) {
    return generateParenthesisA(--left, right, `${pre}(`, res);
  } else if (!left && right == 1) {
    return [`${pre})`];
  } else if (!left) {
    return generateParenthesisA(left, --right, `${pre})`, res);
  } else {
    return generateParenthesisA(
      --left,
      right,
      `${pre}(`,
      res
    ).concat(generateParenthesisA(++left, --right, `${pre})`, res));
  }
};
var generateParenthesis = function (n) {
  if (!n) return [];
  const left = n;
  const right = n;
  return generateParenthesisA(left, right, "");
};

4.両交換チェーンテーブルのノード
タイトル:
1つのチェーンテーブルが与えられ、2つのチェーンテーブルが隣接するノードを交換し、交換後のチェーンテーブルを返します.
単純にノード内部の値を変えるのではなく、実際にノード交換を行う必要があります.
考え方:交換して再帰する

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
  const node = head;
  if (head && head.next) {
    head = head.next;
    node.next = swapPairs(head.next);
    head.next = node;
  }
  return head;
};

5.次の配列
タイトル:
次の配列を取得する関数を実装するには、アルゴリズムは、与えられた数値シーケンスを辞書シーケンスの次のより大きな配列に再配列する必要がある.
次のより大きな配列が存在しない場合は、数値を最小の配列(すなわち昇順配列)に再配列します.
追加の定数空間のみを使用できるように、その場で修正する必要があります.
以下に、入力が左側の列にあり、対応する出力が右側の列にある例を示します.1,2,3  →  1,3,2 3,2,1  →  1,2,3 1,1,5  →  1,5,1
構想:配列の最小値は昇順配列であり、最大値は降順配列である.ある配列の次の配列は、実は後ろから前へ、ある数を見つけて、その前の数はそれより小さいです.(この数の後ろの数が降順排雷であることを説明します)そして、この数の右側からそれより大きい数の中の最小者(実は昇順配列の次の数)を見つけて、交換して、交換した後、後ろの数に対して昇順配列をすればいいです.後ろの数はすでに降順配列なので、ミラー交換を1つするだけです

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
  const length = nums.length;
  for (let j = length - 1; j >= 1; j--) {
    if (nums[j] > nums[j - 1]) {
      for (let i = length - 1; i >= j; i--) {
        if (nums[i] > nums[j - 1]) {
          [nums[i], nums[j - 1]] = [nums[j - 1], nums[i]];
        for (let k = j; k < (j + length - 1) / 2; k++) {
          [nums[k], nums[length - 1+j - k]] = [nums[length - 1 +j- k], nums[k]];
        }
        return nums;
        }
      }
      break;
    }
  }
  return nums.sort((a, b) => a - b);
};