2、数组与排序

1、三数字之和—*

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

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的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

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<N;i++){
        if(map[i]==0){
            search(M,i,map);
            count++;
        }
    }
    return count;   
};
function search(M,i,map){
    map[i] = 1;
    for(let j = 0;j<map.length;j++){
        if(i==j){
            continue;
        }else{
            if(M[i][j]==1&&map[j]==0){
                search(M,j,map)
            }
        }
    }
}

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