2、配列と並べ替え

1、三数字の和ー*
n個の整数を含む配列numsが与えられ、a+b+c=0となるように、numsに3つの要素a,b,cが存在するか否かが判断される.条件を満たし、繰り返さないすべての三元グループを見つけます.

var threeSum = function (nums) {
    nums.sort((a, b) => a - b);
    const res = []
    for (let i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) { //    
            continue
        }
        let j = i + 1,
            k = nums.length - 1
        if(nums[i] > 0) return res;
        let target = -nums[i]
        while (j < k) {
            if (nums[j] + nums[k] === target) {
                res.push([nums[i], nums[j], nums[k]])
                j++
                k--
                //        
                while (j < k && nums[j] == nums[j - 1]) j++
                while (j < k && nums[k] == nums[k + 1]) k--
            } else if (nums[j] + nums[k] > target) {
                k--
            } else {
                j++
            }
        }
    }
    return res
};

let threeSum = function(nums) {
    let res = [];
    let length = nums.length;
    nums.sort((a, b) => a - b);
    if (nums[0] <= 0 && nums[length - 1] >= 0) {
        for (let i = 0; i < length - 2; i++) {
            let j = i + 1;
            let k = length - 1;
            while (j < k) {
                if (nums[i] + nums[j] + nums[k] === 0) {
                    res.push([nums[i], nums[j], nums[k]]);
                    while (j < k && nums[j] === nums[j + 1]) {
                        j++;
                    }
                    while (j < k && nums[k] === nums[k - 1]) {
                        k--;
                    }
                    j++;
                    k--;
                } else if (nums[i] + nums[j] + nums[k] < 0) {
                    j++;
                } else {
                    k--;
                }
            }
            while (i < length - 2 && nums[i] === nums[i + 1]) {
                i++;
            }
        }
    }
    return res;
};

2、島の最大面積—*
いくつかの0および1を含む非空の2次元配列gridが与えられ、1つの島は4つの方向(水平または垂直)の1(土地を表す)からなる組合せである.2次元マトリクスの4つのエッジが水に囲まれていると仮定できます.

var maxAreaOfIsland = function (grid) {
  const rowlen = grid.length;
  const collen = grid[0].length;
  let max = 0;

  function checkAround(i, j, tmp) {
    grid[i][j] = 0;
    while ((i + 1) < rowlen && grid[i + 1][j] === 1) {
      tmp++;
      tmp = checkAround(i + 1, j, tmp);
    }
    while ((j + 1) < collen && grid[i][j + 1] === 1) {
      tmp++;
      tmp = checkAround(i, j + 1, tmp);
    }
    while ((i - 1) > -1 && grid[i - 1][j] === 1) {
      tmp++;
      tmp = checkAround(i - 1, j, tmp);
    }
    while ((j - 1) > -1 && grid[i][j - 1] === 1) {
      tmp++;
      tmp = checkAround(i, j - 1, tmp);
    }
    return tmp;
  }
  for (let i = 0; i < rowlen; i++) {
    for (let j = 0; j < collen; j++) {
      if (grid[i][j] === 1) {
        const tmax = checkAround(i, j, 1);
        max = max > tmax ? max : tmax;
      }
    }
  }
  return max;
};

var maxAreaOfIsland = function(grid) {
    var ans = 0
    var row = grid.length
    var col = grid[0].length
    //    dfs   
    var dfs = function(x, y){
        if(x < 0 || x >= row || y < 0 || y >=col || grid[x][y] == 0){
            return 0
        }
        grid[x][y] = 0
        return 1 + dfs(x, y + 1) + dfs(x, y - 1) + dfs(x + 1, y) + dfs(x - 1, y)
    }
    for(var i = 0; i < row; i++){
        for(var j = 0; j < col; j++){
            ans = Math.max(ans, dfs(i, j))
        }
    }
    return ans
};

3、回転ソート配列の検索—*
昇順で並べ替えられた配列が予め未知の点で回転していると仮定する.(例えば、配列[0,1,2,4,5,6,7]は[4,5,6,7,0,1,2]になることがある).指定されたターゲット値を検索し、配列にターゲット値が存在する場合はインデックスを返します.そうでない場合は-1を返します.

var search = function (nums, target) {
  const len = nums.length;
  let idx = -1;
  const checkMatch = function (head, tail) {
    if (idx > -1 || head > tail) return;
    const headVal = nums[head];
    const tailVal = nums[tail];
    const half = Math.floor((head + tail) / 2);
    const halfVal = nums[half];
    if(halfVal === target) idx = half;
    if(headVal === target) idx = head;
    if(tailVal === target) idx = tail;
    if(headVal < halfVal) {
      if(target < halfVal && target > headVal) {
        checkMatch(head+1, half-1)
      } else {
        checkMatch(half+1, tail-1)
      }
    } else if(halfVal < tailVal) {
      if(target > halfVal && target < tailVal) {
        checkMatch(half+1, tail-1)
      } else {
        checkMatch(head+1, half-1)
      }
    }
  }
  checkMatch(0, len - 1);
  return idx;
};

let search = function(nums, target) {
    let l = 0;
    let r = nums.length - 1;
    while (l <= r) {
        let m = Math.floor((l + r) / 2);
        if (nums[m] === target) {
            return m;
        } else  if (nums[m] > target) {
            if (nums[m] > nums[r] && nums[l] > target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        } else {
            if (nums[m] < nums[r] && nums[r] < target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
    }
    return -1;
};

4、最長連続増分シーケンス
並べ替えられていない整数配列を指定し、最も長く連続したインクリメントシーケンスを見つけます.

var findLengthOfLCIS = function (nums) {
  const len = nums.length;
  for (let i = len - 1; i > 0; i--) {
    nums[i] = nums[i] - nums[i - 1];
  }
  nums[0] = 1;
  let res = 0;
  let max = 0;
  for (let i = 0; i < len; i++) {
    if (nums[i] > 0) {
      res++;
    } else {
      max = Math.max(res, max);
      res = 1;
    }
  }
  max = Math.max(res, max);
  return max;
};

var findLengthOfLCIS = function(nums) {
    if (nums.length === 0) {
        return 0
    }
    let res = 0,
        count = 1
    for (let i = 1; i < nums.length; ++i) {
        if (nums[i] > nums[i - 1]) {
            ++count
        } else {
            res = Math.max(res, count)
            count = 1
        }
    }
    return Math.max(res, count)
};

5、配列中のK番目の最大要素
ソートされていない配列にk番目の最大要素が見つかります.配列ソート後のk番目の最大要素であり、k番目の異なる要素ではないことに注意してください.

var findKthLargest = function(nums, k) {
    nums = nums.sort((a, b) => a - b)
    return nums[nums.length - k]
};

var findKthLargest = function(nums, k) {
    //    ，k         
    let rank = 1
    let num = nums[0]
    const bigger = []
    const less = []
    nums.shift()
    while(nums.length > 0) {
        const value = nums.pop()
        if (num < value) {
            bigger.push(value)
            rank++
        } else if (num >= value){
            less.push(value)
        }
    }
    if (rank === k) return num
    if (rank > k) {
        return findKthLargest(bigger, k)
    }
    else if (rank < k) {
        return findKthLargest(less, k - rank)         
    }
};

6、最長連続シーケンス
並べ替えられていない整数配列を指定し、最長連続シーケンスの長さを見つけます.要求アルゴリズムの時間的複雑度はO(n)である.

var longestConsecutive = function (nums) {
  // nums's value as array's key, array’s value as longest
  const len = nums.length;
  if (len < 2) return len;
  const map = {};
  let max = 1;
  for (let i = 0; i < len; i++) {
    const key = nums[i];
    if (!map[key]) { //          ，       ；      
      map[key] = 1;
      if (map[key - 1]) {
        const total = map[key - 1] + 1;
        map[key] = total;
        map[key - map[key - 1]] = total;
        max = Math.max(map[key], max);
      }
      if (map[key + 1]) {
        const total = map[key + 1] + map[key];
        map[key + map[key + 1] - total + 1] = total;
        map[key + map[key + 1]] = total;
        max = Math.max(total, max);
      }
    }
  }
  return max;
};

var longestConsecutive = function(nums) {
  if (!nums || !nums.length) return 0;
  let map = {};
  const filterNums = [];
  for (let i = 0; i < nums.length; i++) {
    if (!map[nums[i]]) {
      map[nums[i]] = 1;
      filterNums.push(nums[i]);
    }
  }
  let maxConseq = 0;
  for (let i = 0; i < filterNums.length; i++) {
    let maxNow = 0;
    let current = filterNums[i];
    if (map[current]) {
      maxNow++;
      map[current] = 0;
      let forward = current + 1;
      while (map[forward]) {
        map[forward] = 0;
        maxNow++;
        forward++;
      }
      let backward = current - 1;
      while (map[backward]) {
        map[backward] = 0;
        maxNow++;
        backward--;
      }
    }
    maxConseq = Math.max(maxConseq, maxNow);
  }
  return maxConseq;
};

var longestConsecutive = function(nums) {
    var recordMap = new Map();
    var max = 0;
    for(var num of nums) {
        if (recordMap.get(num) != null) {
            continue;
        }
        var left =  recordMap.get(num - 1) == null ? 0 : recordMap.get(num - 1);
        var right =  recordMap.get(num + 1) == null ? 0 : recordMap.get(num + 1);
        var inNum = left + right + 1;
        recordMap.set(num,inNum);
        recordMap.set(num - left, inNum);
        recordMap.set(num + right, inNum);
        max = Math.max(max, inNum);
    }
    return max;
};

7、k番目の配列[1,2,3,…,*n*]の集合が与えられ、そのすべての要素はnを共有している.種の配列nとkが与えられ、k番目の配列が返される.
8、モーメンツ—*
クラスの中学生間の友人関係を表すN*Nの行列Mを与えた.M[i][j]=1であれば、i番目とj番目の学生が互いに友人関係であることが知られていることを示し、そうでなければ知らない.すべての学生の既知のモーメンツの総数を出力しなければなりません.

var findCircleNum = function (M) {
  const len = M.length;
  let nums = 0;
  var setCicle = function (i, j) {
    if (i < 0 || j < 0 || i >= len || j >= len || M[i][j] === 0) {
      return;
    }
    M[i][j] = 0;
    for(let m = i; m < len; m++) {
      setCicle(i, m)
    }
    for(let n = 0; n <= j; n++) {
      setCicle(n, j)
    }
  }
  for (let i = 0; i < len; i++) {
    for (let j = i; j < len; j++) {
      if (M[i][j] === 1) {
        setCicle(i, j);
        nums++
      }
    }
  }
  return nums;
};

var findCircleNum = function(M) {
    let map = new Array(M[0].length).fill(0);
    let N = M.length;
    let count = 0;
    for(let i =0;i

9、合併区間
10、雨を受ける—*
配列を与えて、数値は高さを表して、配列が収容することができるどれだけの水を求めます.

var trap = function (height) {
    let maxIdx = 0;
    let max = 0;
    let sum = 0;
    let fullSum = 0;
    for(let i = 0; i < height.length; i++) {
        if(height[i] > max) {
            maxIdx = i;
            max = height[i];
        }
        sum += height[i];
    }
    let tmpIdx = 0;
    let tmpVal = 0;
    for(let i = 0; i <=maxIdx; i++) {
        if(height[i] > tmpVal) {
            fullSum += tmpVal * [i - tmpIdx];
            tmpIdx = i;
            tmpVal = height[i];
        }
    }
    fullSum += max;
    tmpIdx = height.length - 1;
    tmpVal = 0;
    for(let i = height.length - 1; i >= maxIdx; i--) {
        if(height[i] >= tmpVal) {
            fullSum += tmpVal * [tmpIdx - i];
            tmpIdx = i;
            tmpVal = height[i];
        }
    }
    return fullSum - sum;
};

var trap = function(height) {
    let res = 0, left = 0, right = height.length - 1, leftMax = 0, rightMax = 0
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) leftMax = height[left]
            else res += leftMax - height[left]
            left++
        } else {
            if (height[right] >= rightMax) rightMax = height[right]
            else res += rightMax - height[right]
            right--
        }
    }
    return res
};