算法题（三）

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        // 相邻元素两两对比
                var temp = arr[j+1];        // 元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
} 

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

function shellSort(arr) {
    var len = arr.length;
    for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        // 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
        for (var i = gap; i < len; i++) {
            var j = i;
            var current = arr[i];
            while (j - gap >= 0 && current < arr[j - gap]) {
                 arr[j] = arr[j - gap];
                 j = j - gap; 
            }
            arr[j] = current;
        }
    }
    return arr;
}

function mergeSort(arr) {
    var len = arr.length;
    if (len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    var result = [];

    while (left.length>0 && right.length>0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}

function partition(arr, left ,right) {     // 分区操作
    var pivot = left,                      // 设定基准值（pivot）
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }        
    }
    swap(arr, pivot, index - 1);
    return index-1;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

var len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量

function buildMaxHeap(arr) {   // 建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}

function heapify(arr, i) {     // 堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;

    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function heapSort(arr) {
    buildMaxHeap(arr);

    for (var i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // 输入数据的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // 输入数据的最大值
      }
    }

    // 桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;   
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

    // 利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 对每个桶进行排序，这里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                      
        }
    }

    return arr;
}

function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue + 1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;

    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }

    return arr;
}

var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        l=0
        h=len(nums)
        while l < h:
            if nums[l] % 2 == 0:
                nums.append(nums.pop(l))
                h-=1
            else:
                l+=1
        return nums

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        i = 0
        for num in nums:
            if num != 0:
                nums[i] = num
                i += 1
        for j in xrange(i, len(nums)):
            nums[j] = 0

const twoSum = function (nums, target) {
    // 解题思路：从无序数组中找到两个值，查找表方法记录，使两个值之和等于target
    /**
     * 查找表
     * @type {Map}
     */
    let m = new Map(),
    const len = nums.length;
    for (let i = 0; i < len; i++) {
        if (m.has(nums[i])) {
            return [m.get(nums[i]), i]
        }
        m.set((target - nums[i]), i)
    }
};

【输入】 [1,2,3,4,5]
【输出】 True

【输入】 [0,0,1,2,5]
【输出】 True

var isStraight = function (nums) {
  let numberOfZero = 0;
  nums.sort((a, b) => a - b);
  let numsCount = 5;
  for (let i = 0; i < numsCount - 1; i++) {
    if (nums[i] === 0) {
      numberOfZero++;
    } else if (nums[i] === nums[i + 1]) {
      return false;
    }
  }
  return nums[4] - nums[numberOfZero] < 5;
};

    var threeSum = function (nums) {
      const result = [];
      nums.sort((a, b) => a - b);
      for (let i = 0; i < nums.length; i++) {
        // 跳过重复数字
        if (i && nums[i] === nums[i - 1]) { continue; }
        let left = i + 1;
        let right = nums.length - 1;
        while (left < right) {
          const sum = nums[i] + nums[left] + nums[right];
          if (sum > 0) {
            right--;
          } else if (sum < 0) {
            left++;
          } else {
            result.push([nums[i], nums[left++], nums[right--]]);
            // 跳过重复数字
            while (nums[left] === nums[left - 1]) {
              left++;
            }
            // 跳过重复数字
            while (nums[right] === nums[right + 1]) {
              right--;
            }
          }
        }
      }
      return result;
    }

class Solution:
  	def threeSum(self, nums: List[int]) -> List[List[int]]:
      	nums.sort()
        ans = []
        seen = set()
        n = len(nums)
        for i in range(n):
          	a = nums[i]
            if a in seen: 
              	continue
            seen.add()
            d = {}
            for j in range(i+1,n):
              	b = nums[j]
                if b in d and (not(ans) or (ans[-1][0]!= a or ans[-1][2] != b)):
                  	ans.append((a,-a-b,b))
                else:
                  	d[-a-b] = 0
        return ans

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        nearest = 10 ** 7

        for i in range(n - 2):
            lo, hi = i + 1, n - 1
            # 双指针
            while lo < hi:
                total = nums[i] + nums[lo] + nums[hi]
                if total == target:
                    return total
                elif total < target:
                    lo += 1
                else:
                    hi -= 1
                # 直接根据"最近"的定义取结果
                nearest = min(nearest, total, key=lambda x: abs(x - target))
        
        return nearest

// 参数依次为目标数组、选取元素数目、目标和
const search = (arr, count, sum) => {
  // 计算某选择情况下有几个 1，也就是选择元素的个数
  const getCount = num => {
    let count = 0
    while(num) {
      num &= (num - 1)
      count++
    }
    return count
  }

  let len = arr.length, bit = 1 << len, res = []
  
  // 遍历所有的选择情况
  for(let i = 1; i < bit; i++){
    // 满足选择的元素个数 === count
    if(getCount(i) === count){
      let s = 0, temp = []

      // 每一种满足个数为 N 的选择情况下，继续判断是否满足 和为 M
      for(let j = 0; j < len; j++){
        // 建立映射，找出选择位上的元素
        if(i & 1 << (len - 1 -j)) {
          s += arr[j]
          temp.push(arr[j])
        }
      }

      // 如果这种选择情况满足和为 M
      if(s === sum) {
        res.push(temp)
      }
    }
  }

  return res
}

var intersection = function(nums1, nums2) {
    // 根据数组大小交换操作的数组
    if(nums1.length < nums2.length) {
        const _ = nums1;
        nums1 = nums2;
        nums2 = _;
    }
    const nums1Set = new Set(nums1);
    const resSet = new Set();
    // for(const n of nums2) {
    //     nums1Set.has(n) && resSet.add(n);
    // }
    // 循环 比 迭代器快
    for(let i = nums2.length - 1; i >= 0; i--) {
        nums1Set.has(nums2[i]) && resSet.add(nums2[i]);
    }
    return Array.from(resSet);
};

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        inter = set(nums1) & set(nums2)
        l = []
        for i in inter:
            l += [i] * min(nums1.count(i), nums2.count(i))  
        return l

var intersect = function (nums1, nums2) {
// hash法
  const [hash,res] = [new Map(),[]]
  nums1.forEach(el=>{
    if (hash.has(el)) {
      hash.set(el, hash.get(el) + 1)
    } else {
      hash.set(el, 1)
    }
  })
  nums2.forEach(el=>{
    const hashKey = hash.get(el)
    if (hash.has(el)) {
      res.push(el)
      if (hashKey > 1) {
        hash.set(el, hashKey - 1)
      } else {
        hash.delete(el)
      }
    }
  })
  return res
}

let p1 = 0
let p2 = 0
let res = []
nums1 = nums1.sort((a, b) => a - b)
nums2 = nums2.sort((a, b) => a - b)
while (p1 < nums1.length && p2 < nums2.length) {
    if (nums1[p1] == nums2[p2]) {
       res.push(nums1[p1])
       p1++
       p2++
     } else if (nums1[p1] < nums2[p2]) {
       p1++
     } else {
       p2++
     }
 }
 return res

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
      	nums.sort()
        n = len(nums)
        res = []
        for i in range(n):
            if i > 0 and nums[i] == nums[i - 1]: continue
            for k in range(i+1, n):
                if k > i + 1 and nums[k] == nums[k-1]: continue
                p = k + 1
                q = n - 1

                while p < q:
                    if nums[i] + nums[k] + nums[p] + nums[q] > target: q -= 1
                    elif nums[i] + nums[k] + nums[p] + nums[q] < target: p += 1
                    else:
                        res.append([nums[i], nums[k], nums[p], nums[q]])
                        while p < q and nums[p] == nums[p + 1]: p += 1
                        while p < q and nums[q] == nums[q - 1]: q -= 1
                        p += 1
                        q -= 1
        return res

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

function firstMissingPositive(ary) {
  // 首选过滤到非整数
  ary = ary.filter(a => a > 0)
  // 判断正数数组是否为空
  if(ary.length) {
    // 先排序，从小到大排序
    ary.sort((a, b) => a - b)
    // 如果第一个元素不是 1 直接返回 1
    if (ary[0] !== 1) return 1
    
    // 遍历，只要下一个元素和当前当前元素的差值 > 1, 说明输出元素就是当前元素值 +1
    for (let i = 0; i < ary.length; i++) {
      if (ary[i + 1] - ary[i] > 1) {
        return ary[i] + 1
      }
    }
    // 如果数组是连续的正正数 如：[1,2,3]
    return ary.pop() +  1
  }
  return 1
}

输入：nums = [10,2]
输出："210"

输入：nums = [3,30,34,5,9]
输出："9534330"

function getMaxNumber(arr) {
  return arr.reduce((acc = '', cur) => 
     Math.max(+`${acc}${cur}`, +`${cur}${acc}`)
	);
}

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
      	if len(nums) == 1: return nums[0]
        mid = int(len(nums) // 2)
        left, right, mids = [], [], []
        for i in range(len(nums)):
            if nums[i] > nums[mid]:
                left.append(nums[i])
            elif nums[i] < nums[mid]:
                right.append(nums[i])
            else:
                mids.append(nums[i])
        if len(left) >= k:
            return  self.findKthLargest(left, k)
        elif len(mids) >= k - len(left):
            return nums[mid]
        else:
            return self.findKthLargest(right, k - len(left) - len(mids))

输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

var canPlaceFlowers = function (flowerbed, n) {
    flowerbed.unshift(0);
    flowerbed.push(0);
    for (let i = 1; i < flowerbed.length - 1; i++) {
        if (flowerbed[i - 1] === 0 && flowerbed[i] === 0 && flowerbed[i + 1] === 0) {
            flowerbed[i] = 1; // 种花！
            n--;
        }
    }
    return n <= 0;
};

输入：nums = [1,2,1,2,6,7,5,1], k = 2
输出：[0,3,5]
解释：子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。
也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更小。

输入：nums = [1,2,1,2,1,2,1,2,1], k = 2
输出：[0,2,4]

// 单个子数组的最大和
var maxSumOfOneSubarray = function(nums, k) {
    let ans = [];
    let sum1 = 0, maxSum1 = 0;
    for (let i = 0; i < nums.length; ++i) {
        sum1 += nums[i];
        if (i >= k - 1) {
            if (sum1 > maxSum1) {
                maxSum1 = sum1;
                ans = [i - k + 1];
            }
            sum1 -= nums[i - k + 1];
        }
    }
    return ans;
};

// 两个子数组的最大和
const maxSumOfTwoSubarrays = (nums, k) => {
    const ans = [0, 0];
    let sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
    let sum2 = 0, maxSum12 = 0;
    for (let i = k; i < nums.length; ++i) {
        sum1 += nums[i - k];
        sum2 += nums[i];
        if (i >= k * 2 - 1) {
            if (sum1 > maxSum1) {
                maxSum1 = sum1;
                maxSum1Idx = i - k * 2 + 1;
            }
            if (maxSum1 + sum2 > maxSum12) {
                maxSum12 = maxSum1 + sum2;
                ans[0] = maxSum1Idx;
                ans[1] = i - k + 1;
            }
            sum1 -= nums[i - k * 2 + 1];
            sum2 -= nums[i - k + 1];
        }
    }
    return ans;
}

// 三个子数组的最大值
const maxSumOfThreeSubarrays = (nums, k) => {
    const ans = [0, 0, 0];
    let sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
    let sum2 = 0, maxSum12 = 0, maxSum12Idx1 = 0, maxSum12Idx2 = 0;
    let sum3 = 0, maxTotal = 0;
    for (let i = k * 2; i < nums.length; ++i) {
        sum1 += nums[i - k * 2];
        sum2 += nums[i - k];
        sum3 += nums[i];
        if (i >= k * 3 - 1) {
            if (sum1 > maxSum1) {
                maxSum1 = sum1;
                maxSum1Idx = i - k * 3 + 1;
            }
            if (maxSum1 + sum2 > maxSum12) {
                maxSum12 = maxSum1 + sum2;
                maxSum12Idx1 = maxSum1Idx;
                maxSum12Idx2 = i - k * 2 + 1;
            }
            if (maxSum12 + sum3 > maxTotal) {
                maxTotal = maxSum12 + sum3;
                ans[0] = maxSum12Idx1;
                ans[1] = maxSum12Idx2;
                ans[2] = i - k + 1;
            }
            sum1 -= nums[i - k * 3 + 1];
            sum2 -= nums[i - k * 2 + 1];
            sum3 -= nums[i - k + 1];
        }
    }
    return ans;
}

const pairsArray = (nums, sum) => {
  const result = [];
  const sortedNums = nums.sort((a, b) => a - b);
  for (let i = 0; i < sortedNums.length; i++) {
    let left = i;
    let right = sortedNums.length - 1;
    while (left < right) {
      if (sortedNums[left] + sortedNums[right] > sum) {
        right -= 1;
      } else if (sortedNums[left] + sortedNums[right] < sum) {
        left += 1;
      } else {
        result.push([sortedNums[left], sortedNums[right]]);
        break;
      }
    }
  }
  return result;
};

class Solution:
    def maxProfit(self,prices:List[int])-> int:
        min_p,max_v = float('inf'),0
        for p in prices:
            min_p = min(min_p,p)
            max_v = max(max_v,p-min_p)
        return max_v

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                ans += prices[i] - prices[i-1]
        return ans

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        n = len(prices)
        dp = [[0]*2 for _ in range(n)]
        # dp[i][0]表示第i天不持有股票, dp[i][1]表示第i天持有股票
        dp[0][0], dp[0][1] = 0, - prices[0]
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
        return dp[n-1][0]

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
        dp = [0] * 5 
        dp[1] = -prices[0]
        dp[3] = -prices[0]
        for i in range(1, len(prices)):
            dp[1] = max(dp[1], dp[0] - prices[i])
            dp[2] = max(dp[2], dp[1] + prices[i])
            dp[3] = max(dp[3], dp[2] - prices[i])
            dp[4] = max(dp[4], dp[3] + prices[i])
        return dp[4]

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
        dp = [[0] * (2*k+1) for _ in range(len(prices))]
        for j in range(1, 2*k, 2):
            dp[0][j] = -prices[0]
        for i in range(1, len(prices)):
            for j in range(0, 2*k-1, 2):
                dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] - prices[i])
                dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1] + prices[i])
        return dp[-1][2*k]

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0:
            return 0
        dp = [[0] * 4 for _ in range(n)]
        dp[0][0] = -prices[0] #持股票
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], max(dp[i-1][3], dp[i-1][1]) - prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][3])
            dp[i][2] = dp[i-1][0] + prices[i]
            dp[i][3] = dp[i-1][2]
        return max(dp[n-1][3], dp[n-1][1], dp[n-1][2])

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i]= nums[i] + max(nums[i-1], 0)
        return max(nums)

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        B = nums[::-1]
        for i in range(1, len(nums)):
            nums[i] *= nums[i - 1] or 1
            B[i] *= B[i - 1] or 1
        return max(max(nums),max(B))

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        path = []
        def backtrack(n, k, StartIndex):
            if len(path) == k:
                res.append(path[:])
                return
            for i in range(StartIndex, n-(k-len(path)) + 2):
                path.append(i)
                backtrack(n, k, i+1)
                path.pop()
        backtrack(n, k, 1)
        return res

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
      	candidates.sort()
        n = len(candidates)
        res = []
        def helper(i, tmp_sum, tmp):
            if tmp_sum > target or i == n:
                return 
            if tmp_sum == target:
                res.append(tmp)
                return 
            helper(i,  tmp_sum + candidates[i],tmp + [candidates[i]])
            helper(i+1, tmp_sum ,tmp)
        helper(0, 0, [])
        return res

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
      	if not candidates:
            return []
        candidates.sort()
        n = len(candidates)
        res = []
        
        def backtrack(i, tmp_sum, tmp_list):
            if tmp_sum == target:
                res.append(tmp_list)
                return 
            for j in range(i, n):
                if tmp_sum + candidates[j]  > target : break
                if j > i and candidates[j] == candidates[j-1]:continue
                backtrack(j + 1, tmp_sum + candidates[j], tmp_list + [candidates[j]])
        backtrack(0, 0, [])    
        return res

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []  #存放结果集
        path = []  #符合条件的结果
        def findallPath(n,k,sum,startIndex):
            if sum > n: return  #剪枝操作
            if sum == n and len(path) == k:  #如果path.size() == k 但sum != n 直接返回
                return res.append(path[:])
            for i in range(startIndex,9-(k-len(path))+2):  #剪枝操作
                path.append(i)
                sum += i 
                findallPath(n,k,sum,i+1)  #注意i+1调整startIndex
                sum -= i  #回溯
                path.pop()  #回溯
        
        findallPath(n,k,0,1)
        return res

let func = (arr) => {
  let len = arr.length
  let res = [] // 所有排列结果
  
  let arrange = (tempArr, leftArr) => {
    if (tempArr.length === len) { // 这里就是递归结束的地方
      // res.push(tempArr) // 得到全排列的每个元素都是数组
      res.push(tempArr.join('')) // 得到全排列的每个元素都是字符串
    } else {
      leftArr.forEach((item, index) => {
        let temp = [].concat(leftArr)
        temp.splice(index, 1)
        // 此时，第一个参数是当前分离出的元素所在数组；第二个参数temp是传入的leftArr去掉第一个后的结果
        arrange(tempArr.concat(item), temp) // 这里使用了递归
      })
    }
  }
  arrange([], arr)
  return res
}
console.log('结果：', func(['A', 'B', 'C', 'D']))

class Solution:
   def permute(self,nums:List[int])->List[List[int]]:
       res = []
       def backtrack(nums,tmp):
           if not nums:
               res.append(tmp)
               return 
           for i in range(len(nums)):
               backtrack(nums[:i]+nums[i+1],tmp+[nums[i]])
       backtrack(nums,[])
       return res

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
      	# res用来存放结果
        if not nums: return []
        res = []
        used = [0] * len(nums)
        def backtracking(nums, used, path):
            # 终止条件
            if len(path) == len(nums):
                res.append(path.copy())
                return
            for i in range(len(nums)):
                if not used[i]:
                    if i>0 and nums[i] == nums[i-1] and not used[i-1]:
                        continue
                    used[i] = 1
                    path.append(nums[i])
                    backtracking(nums, used, path)
                    path.pop()
                    used[i] = 0
        # 记得给nums排序
        backtracking(sorted(nums),used,[])
        return res

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
      	res = []  
        path = []  
        def backtrack(nums,startIndex):
            res.append(path[:])  #收集子集，要放在终止添加的上面，否则会漏掉自己
            for i in range(startIndex,len(nums)):  #当startIndex已经大于数组的长度了，就终止了，for循环本来也结束了，所以不需要终止条件
                path.append(nums[i])
                backtrack(nums,i+1)  #递归
                path.pop()  #回溯
        backtrack(nums,0)
        return res

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
       	res = []  #存放符合条件结果的集合
        path = []  #用来存放符合条件结果
        def backtrack(nums,startIndex):
            res.append(path[:])
            for i in range(startIndex,len(nums)):
                if i > startIndex and nums[i] == nums[i - 1]:  #我们要对同一树层使用过的元素进行跳过
                    continue
                path.append(nums[i])
                backtrack(nums,i+1)  #递归
                path.pop()  #回溯
        nums = sorted(nums)  #去重需要排序
        backtrack(nums,0)
        return res

class Solution:
  def removeElement(self, nums: List[int], val: int) -> int:
    	i = 0
      for j in range(len(nums)):
        	if nums[j] != val:
            	nums[i] = nums[j]
              i += 1
      return i

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
				i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i+1]:
            i -= 1

        # i<0时已经为最大的排列
        if i >= 0:
            j = len(nums) - 1
            while j >= 0 and nums[j] <= nums[i]:
                j -= 1

            nums[i], nums[j] = nums[j], nums[i]

        l = nums[i+1:]
        l.reverse()
        nums[i+1:] = l 

class Solution:
  	def rotate(self, nums:List[int], k:int)-> None:
      	nums[: ] = (nums[i] for i in range(-(k % len(nums)),len(nums)-k % len(nums)))

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1 for _ in range(n)]
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        dp[0], max_sum = nums[0], nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1] + nums[i], nums[i])
            max_sum = max(max_sum, dp[i])
        return max_sum

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        a = 0
        for num in nums:
            a = a ^ num
        return a

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(0,len(nums)-3,3):
            if nums[i]!=nums[i+1]:
                return nums[i]
        return nums[-1]

class Solutioon:
  	def firstMissingPositive(self,nums:List[int])-> int:
      	nums = set(nums)
        for j in range(1, 2 ** 31 - 1):
          	if j not in nums:
              	return j

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        ans, s, hs = 0, [0], [0, *heights, 0]
        for i, h in enumerate(hs):
            while hs[s[-1]] > h:
                ans = max(ans, (i - s[-2] - 1) * hs[s.pop()])
            s.append(i)
        return ans

class Solution:
  	def minSubArrayLen(self, target:int,nums: List[int])-> int:
      	i, ans = 0, len(A) + 1
        for j in range(len(A)):
          	s -= A[j]
            while s <= 0:
              	ans = min(ans,j-i+1)
                s += A[i]
                i += 1
        return ans % (len(A)+1)

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
      	return not (len(nums)==len(set(nums)))

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
      	nums_len = len(nums)
        if nums_len <= 1:
            return False
        nums_dict = {}
        for i in range(nums_len):
            if nums[i] in nums_dict:
                if i-nums_dict[nums[i]] <= k:
                    return True
            nums_dict[nums[i]] = i
        return False

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
      	ls = [[nums[i], i] for i in range(len(nums))]
        ls.sort(key=lambda x: x[0])
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if ls[j][0] - ls[i][0] > t:
                    break
                if abs(ls[j][1] - ls[i][1]) <= k:
                    return True
        return False

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
      	lo, hi = 1, len(nums)-1
        while lo < hi:
            mid = (lo + hi) // 2
            if sum(i<=mid for i in nums) <= mid:
                lo = mid + 1
            else:
                hi = mid
        return lo

class Solution:
  	def findDuplicates(self, nums:List[int])-> List[int]:
      	res = []
        for x in nums:
          	if nums[abs(x-1)] < 0:
              	res.append(abs(x))
            else:
              	nums[abs(x)-1] *= -1
        return res

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
      	lo, hi = 0, len(nums)-1
        while lo < hi:
            mid = (lo+hi) // 2
            mid2 = mid + 1
            if nums[mid] < nums[mid2]:
                lo = mid2
            else:
                hi = mid
        return lo

def majorityElement(self, nums):
  	count = 0
    candidate = None
    for num in nums:
      	if count == 0:
          	candidate = num
        count += (1 if num == candidate else -1)
    return candidate

class Solution:
  	def majorityElement(self, nums:List[int]) -> Lisr[int]:
      	count1, count2, candidate1, candidate2 = 0,0,0,1
        for n in nums:
          	if n == candidate1:
              	count1 += 1
            elif n == candidate2:
              	count2 += 1
            elif count1 == 0:
              	candidate1, count1 = n,1
            elif count2 == 0:
              	candidate2, count2 = n,1
            else:
              	count1, count2 = count1 - 1,count2 - 1
        return [n for n in (candidate1,candidate2)
                if nums.count(n) > len(nums) // 3]

输入：deck = [1,2,3,4,4,3,2,1]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]

输入：deck = [1,1,1,2,2,2,3,3]
输出：false
解释：没有满足要求的分组。

var hasGroupsSizeX = function (deck) {
  if (!deck.length || deck.length === 1) return false;
  let obj = {};
  for (let i of deck) {
    obj[i] = !obj[i] ? 1 : ++obj[i];
  }
  const sizeArr = Object.values(obj);
  const minSize = Math.min.apply(null, sizeArr);
  for (let i = 2; i <= minSize; i++) {
    if (sizeArr.every(key => !(key % i))) return true;
  }
  return false;
};