2020-03-02

1 小时读完 (大约 9630 个字) 0次访问

算法题（三）

　　算法题第三篇数组

数组相关算法

排序算法

十种排序算法

https://www.cnblogs.com/onepixel/articles/7674659.html

冒泡排序

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

无序数组

调整数组顺序使得奇数位于偶数前面(剑指offer21)

设置两个指针，偶数就删除插入尾部，奇数不做处理

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

移动零 283

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

如，输入：[0,1,0,3,12]

输出：[1,3,12,0,0]

注意：不拷贝额外的数组，减少操作次数

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

两数之和

三数之和(15)

给你一个包含n个整数的数组nums，判断nums中是否存在三个元素，使得这三个整数相加为0

例：输入:nums = [-1,0,1,2,-1,-4]

输出：[-1,-1,2],[-1,0,1]

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

最接近的三数之和16

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

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

两个数组的交集

给定两个数组，编写算法计算他们的交集

例：输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

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

四数之和18

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] ：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意顺序返回答案。

例：输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

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

无序整数数组，找出第k大的值215

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。、

例：输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

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))

买卖股票的最佳时机1、2、3、4(121,122,123,188,309)

给定数组prices，第i个元素表示股票第i天的价格

需选择在某一天买入，并在某一天卖出，设计一个算法计算获取的最大利润

例：输入：[7,1,5,3,6,4]

输出：5 在第二天买入，第5天卖出，6-1=5

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

122给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

贪心

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]

123:给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

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]

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

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]

309:给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

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])

连续子数组最大和(53)

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

例：输入：nums = [-2,1,-3,4,-1,2,1-5,4]

输出：6，连续子数组[4,-1,2,1]的和最大，为6

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)

乘积最大子数组(152)

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

例：输入：[2,3,-2,4]

输出：6

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))

组合、组合总和1、2、3（77、39、40、216）

组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

例：输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

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

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

例：输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]

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

40:

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

例：输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

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

组合总和3

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

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

全排列(46、47)

46:给一个不含重复数组，返回其所有可能的全排列

输入:[1,2,3]

输出:[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]

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

47:给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

输入：nums = [1,1,2];

输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

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

子集78、90

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

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

90:给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

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

移除元素(27)

给出一个数组和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的长度

例：输入：nums = [3,2,2,3] val= 3

输出：2,nums = [2,2]

快慢指针

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

下一个排列(31)

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

例：输入 nums = [1,2,3]。这个数是123，找出1，2，3这3个数字排序可能的所有数，排序后，比123大的那个数也就是132

输入 nums = [3,2,1]。这就是1，2，3所有排序中最大的那个数，那么就返回1，2，3排序后所有数中最小的那个，也就是1，2，3 -> [1,2,3]

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

旋转数组(189)

给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数

输入：nums = [1,2,3,4,5,6,7], k = 3

输出：[5,6,7,1,2,3,4]

1
2
3

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)))

最长连续递增子序列(300)

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

例如：输入：[10,9,2,5,3,7,101,18]

输出：4 ，最长递增子序列为[2,5,7,101]

输入：[0,1,0,3,2,3]

输出：4，最长递增子序列为[0,1,2,3]

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)

连续子数组的最大和(剑指offer42)

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

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

数组拼接最小数

只出现过一次的数字(136)

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

例：输入：[2,2,1]

输出：1

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

只出现过一次的数字2(137)

给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现 三次。请你找出并返回那个只出现了一次的元素。

例：输入：[2,2,3,2]

输出：3

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]

缺失的第一个正数(41)

给你一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数

例：输入：[1,2,0]

输出:4

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

颜色分类(75)

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

例：输入：nums = [2,0,2,1,1,0]

输出：[0,0,1,1,2,2]

快排

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

柱状图中最大的矩形(84)

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

输入: [2,1,5,6,2,3]
输出: 10

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

长度最小的子数组(209)

给定一个含有n个正整数和一个正整数target

找出该数组中满足其和大于target的长度最小的连续子数组，并返回其长度

例：nums=[2,3,1,2,4,3], target=7

输出：2

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)

存在重复元素(217)

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

例：输入：[1,2,3,1]

输出：true

输入：[1,2,3,4]

输出：false

1
2
3

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

存在重复元素2(219)

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值至多为 k。

例：输入：nums = [1,2,3,1], k = 3

输出：true

输入：nums = [1,2,3,1,2,3], k = 2

输出：false

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

存在重复元素3（220）

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

例：输入：nums = [1,2,3,1], k = 3, t = 0

输出：true

输入：nums = [1,5,9,1,5,9], k = 2, t = 3

输出：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

寻找重复数字287

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有一个重复的整数，找出这个重复的数。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

例：输入：nums = [1,3,4,2,2]
输出：2

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

数组中重复的数据(442)

给定一个整数数组a，其中有些元素出现了两次而有些元素出现了一次，找出所有出现两次的元素

输入：[4,3,2,7,8,2,3,1]

输出：[2,3]

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

寻找峰值162

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

例：输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5

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

多数元素(169)

波义尔摩尔投票算法

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

求众数(229)

给定一个大小为n的整数组，找出其中所有出现超过n/3次的元素

输入：[3,2,3]

输出：[3]

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]

有序数组

在排序数组中查找元素的第一个和最后一个位置34

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

例：输入：nums = [5,,7,7,8,8,10],target = 8

输出：[3,4]

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        res = [-1, -1]

        l, r = 0, len(nums) - 1
        while l < r:
            mid = l + (r - l) // 2  # 向左取整
            if nums[mid] < target:  # 首先考虑一定不存在解的区间，则有+1（或者-1）
                l = mid + 1
            else:
                r = mid
        if not nums or nums[l] != target:  # 用例中有nums = [] 的情况
            return res
        res[0] = l
        
        l, r = r, len(nums) - 1
        while l < r:
            mid = l + (r - l + 1) // 2  # 向右取整
            if nums[mid] > target:
                r = mid - 1
            else:
                l = mid
        res[1] = r
        return res

搜索插入位置35

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

例：输入:[1,3,5,6],5

输出：2

输入：[1,3,5,6],2

输出：1

二分法查找

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums)
        while low < high:
            mid = low + (high - low)//2
            if nums[mid] > target:
                high = mid
            elif nums[mid] < target:
                low = mid +1
            else:
                return mid
        return low

合并区间(56)

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

例：输入：[1,3],[2,6],[8,10],[15,18]

输出：[1,6],[8,10],[15,18]

先排序，然后判断是否合并区间

class Solution:
    def merge(self,intervals:List[List[int]])->List[List[int]]:
        if intervals == []:
           return []
        intervals.sort(key = lambda x:x[0])
        ##前一个合并区间
        pre = intervals[0]
        res = []
        for i in range(1,len(intervals)):
            if intervals[i][0] <= pre[1]:
               ##合并，更新pre结束位置
               if intervals[i][1] > pre[1]:
                  pre[1] = intervals[i][1]
            else
               res.append(pre)
               pre = intervals[i]
        ##最后一个没有加进去
        res.append(pre)
        return res

插入区间(57)

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠

例：输入：intervals = [1,3],[6,9],newInterval = [2,5]

输出：[[1,5],[6,9]]

class Solution:
     def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        intervals.append(newInterval)
        intervals = sorted(intervals, key=lambda x: x[0])

        merge = [intervals[0]]
        for i in range(1, len(intervals)):
            mergeleft = merge[-1][0]
            mergeright = merge[-1][1]
            interleft = intervals[i][0]
            interright = intervals[i][1]
            if interleft > mergeright:
                merge.append(intervals[i])
            else:
                merge[-1][1] = max(mergeright, interright)
        return merge

删除有序数组的重复项(26)

删除有序数组中重复的元素，在原数组上进行操作，

def removeDuplicates(nums):
  	if not nums:
      	return 0
    index = 1
    for i in range(len(nums)-1):
      	if nums[i] != nums[i+1]:
          	nums[index] = nums[i+1]
            index +=1
    return index

删除有序数组的重复项2(80)

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素最多出现两次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

例：输入：[1,1,1,2,2,3]

输出：[1,1,2,2,3]

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for e in nums:
            if i < 2 or e != nums[i - 2]:
                nums[i] = e
                i += 1

        return i

合并排序数组(88)

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

输出：[1,2,2,3,5,6]

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i, j, k = m-1, n-1, m+n-1
        while i >=0 and j >= 0:
            if nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1
        while j >= 0:
            nums1[k] = nums2[j]
            j -= 1
            k -= 1

汇总区间(228)

给定一个无重复元素的有序整数数组，返回恰好覆盖数组中所有数组的最小有序区间范围列表，

例：nums = [0,1,2,4,5,7]

输出：[“0->2”,”4->5”,”7”]

nums = [0,2,3,4,6,8,9]

输出：[“0”,”2->4”,”6”,”8->9”]

class Solution:
  	def summaryRange(self, nums: List[int]) -> List[str]:
      	li = []
        i = 0
        while i < len(nums):
          	j = i + 1;
            while j < len(nums) and nums[j] == nums[i] + j - i:
              	j += 1
            li.append(str(nums[i]) if i == j-1 else str(nums[i]) + '->' + str(nums[j-1]))
            i = j
        return li

寻找右区间436

给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都不同。

区间 i 的右侧区间可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化。

返回一个由每个区间 i 的右侧区间的最小起始位置组成的数组。如果某个区间 i 不存在对应的右侧区间，则下标 i 处的值设为 -1 。

例：输入：intervals = [[1,2]]
输出：[-1]
解释：集合中只有一个区间，所以输出-1。

输入：intervals = [[3,4],[2,3],[1,2]]
输出：[-1, 0, 1]
解释：对于 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间[3,4]具有最小的“右”起点，在原数组中索引为0;
对于 [1,2] ，区间[2,3]具有最小的“右”起点，在原数组中索引为1。

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
      	n = len(intervals)
        res = [-1] * n
        dic = {}
        for i, v in enumerate(intervals):
            dic[v[0]] = i
        start = sorted(dic.keys())
        for i, v in enumerate(intervals):
            l, r = 0, n - 1
            while l <= r:
                mid = (l + r) >> 1
                if v[1] > start[mid]:
                    l = mid + 1
                else:
                    r = mid - 1
            if l < n:
                res[i] = dic[start[l]]

        return res

和为s的连续正数序列(剑指offer57)

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

例：输入：target = 9

输出：[[2,3,4],[4,5]]

双指针滑动窗口

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        n = target//2+1 
        nums = list(range(1,n+1)) 
        left,right = 0,0 
        sums,res = 0,[]
        while right<len(nums):
            sums+=nums[right] 
            right+=1 
            while sums>=target:
                if sums==target:
                    res.append(nums[left:right]) 
                sums-=nums[left] 
                left+=1 
        return res

多维数组

最大正方形(221)

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

例：输入：matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]

输出：4

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        m, n = len(matrix), len(matrix[0]) 
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if matrix[i - 1][j - 1] == '1':
                    dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
        return max(map(max, dp)) ** 2

最大矩形(85)

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

例：输入：matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]

输出：6

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if len(matrix) == 0:
            return 0
        res = 0
        m, n = len(matrix), len(matrix[0])
        heights = [0] * n
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '0':
                    heights[j] = 0
                else:
                    heights[j] = heights[j] + 1
            res = max(res, self.largestRectangleArea(heights))
        return res
   
    def largestRectangleArea(self, heights):
        heights.append(0)
        stack = []
        res = 0
        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                s = stack.pop()
                res = max(res, heights[s] * ((i - stack[-1] - 1) if stack else i))
            stack.append(i)
        return res

单词搜索(79)

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例：输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”

输出：true

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        l,w = len(board),len(board[0])
        l_word = len(word)
        def dfs(a,b,index,hel):
            if a<0 or b<0 or a>=l or b>=w or board[a][b]!=word[index] or (a,b) in hel:
                return False
            elif board[a][b]==word[index] and index==len(word)-1:
                return True
            return dfs(a+1,b,index+1,hel+[(a,b)]) or dfs(a-1,b,index+1,hel+[(a,b)]) or dfs(a,b+1,index+1,hel+[(a,b)]) or dfs(a,b-1,index+1,hel+[(a,b)])
        
        for i in range(l):
            for j in range(w):
                if board[i][j] == word[0]:
                    if dfs(i,j,0,[]):
                        return True
        return False

岛屿数量

深度优先与广度优先都可以。DFS（深度优先搜索）：

从一个为1的根节点开始访问，从每个相邻1节点向下访问到顶点（周围全是水），依次访问其他相邻1节点到顶点

BFS（广度优先搜索）：从一个为1的根节点开始访问，每次向下访问一个节点，直到访问到最后一个顶点

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or len(grid) == 'o': return 0
        row, columns = len(grid), len(grid[0])
        count = 0
        for i in range(row):
            for j in range(columns):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j, row, columns)
                    count += 1
        return count

    def dfs(self, grid: List[List[str]], i: int, j: int, row: int, columns: int):
        if i >= row or i < 0 or j >= columns or j < 0 or grid[i][j] == '0': return
        grid[i][j] = '0'
        self.dfs(grid, i - 1, j, row, columns)
        self.dfs(grid, i, j - 1, row, columns)
        self.dfs(grid, i + 1, j, row, columns)
        self.dfs(grid, i, j + 1, row, columns)

岛屿最大面积

class Solution:
    def helper(self,grid,i,j):
        
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j]==0:
            return 0
        grid[i][j]=0
        count=1
        tmp = [[1,0],[-1,0],[0,1],[0,-1]]
        for x,y in tmp:
            dx = x+i
            dy = y+j
            count+=self.helper(grid,dx,dy)
        
        return count
 
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        res = 0 
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]==1:
                    
                    tmp = self.helper(grid,i,j)
                    res = max(tmp,res)
        return res

三角形路径之和(120)

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

例：输入：[[2],[3,4],[6,5,7],[4,1,8,3]]

输出：11，2–3–5–1

实例

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
      #自底向上
        dp = triangle
        m = len(triangle)
        
        for i in range(m-1,-1,-1):
            if i<m-1:
                for j in range(len(triangle[i])):
                    dp[i][j] += min(dp[i+1][j],dp[i+1][j+1])
        return dp[0][0]   

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        #自底向上
        dp = triangle[-1]
        m = len(triangle)
        
        for i in range(m-1,-1,-1):
            if i<m-1:
                for j in range(len(triangle[i])):
                    dp[j] = min(dp[j],dp[j+1]) + triangle[i][j]
        return dp[0]

顺时针打印数组(54，剑指offer29)

给你一个m*n的矩阵，请按照顺时针螺旋顺序，打印矩阵中的所有元素

如：输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]

输出：[1,2,3,6,9,8,7,4,5]

思路：取首行，去除首行后，对矩阵翻转来创建新的矩阵，
再递归直到新矩阵为[],退出并将取到的数据返回

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ret = []
        if matrix == []:
            return ret
        ret.extend(matrix[0]) # 上侧
        new = [reversed(i) for i in matrix[1:]]
        if new == []:
            return ret
        r = self.spiralOrder([i for i in zip(*new)])
        ret.extend(r)
        return ret

顺时针生成数组(59)

def generateMatrix(self,n: int) -> List[List[int]]:
  	ans = [[0]*n for _ in range(n)]
    op = itertools.cycle([(0,1),(1,0),(0,-1),(-1,0)])
    d = next(op)
    x,y = [0,0]
    for k = range(1,n**2+1):
      	ans[x][y] = k
        i,j = x+d[0], y+d[1]
        if not 0<= i < n or not 0<=j<n or ans[i][j]:
          	d = next(op)
            x,y = x+d[0], y+d[1]
        else:
          	x,y = i,j
    
    return ans

有序矩阵中第 K 小的元素378

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        lo, hi = matrix[0][0], matrix[-1][-1]
        while lo < hi:
            mid = (lo + hi) // 2
            if sum(bisect.bisect(row, mid) for row in matrix) < k:
                lo = mid + 1
            else:
                hi = mid
        return lo

旋转数组

搜索旋转排序数组目标值33、81

旋转有序数组是分段有序的，给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的索引，否则返回 -1 。

例：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

class Solution:
   def search(self,nums,target):
       lo,hi = 0,len(nums)-1
       while lo < hi:
          mid = (lo + hi)//2
          if(nums[0] > target) ^ (nums[0]>nums[mid]) ^ (target>nums[mid]):
             lo = mid + 1
          else 
             hi = mid
       return lo if lo == hi and target == nums[lo] else -1

81:如果数组中有重复元素，编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        lo, hi = 0, len(nums)-1
        while lo <= hi:
            mid = (lo+hi) >> 1
            if nums[mid] == target:
                return True
            while lo<mid and nums[lo]==nums[mid]:
                lo += 1
            if nums[lo] <= nums[mid]: # 左侧有序
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:                     # 右侧有序，因为下落点在左侧
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return False

搜索旋转排序数组最小值153、154

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

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

如果数组中有重复元素，

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

# IT

算法题（三）

数组相关算法

排序算法

无序数组

调整数组顺序使得奇数位于偶数前面(剑指offer21)

移动零 283

两数之和

三数之和(15)

最接近的三数之和16

四数之和18

无序整数数组，找出第k大的值215

买卖股票的最佳时机1、2、3、4(121,122,123,188,309)

连续子数组最大和(53)

乘积最大子数组(152)

组合、组合总和1、2、3（77、39、40、216）

全排列(46、47)

子集78、90

移除元素(27)

下一个排列(31)

旋转数组(189)

最长连续递增子序列(300)

连续子数组的最大和(剑指offer42)

数组拼接最小数

只出现过一次的数字(136)

只出现过一次的数字2(137)

缺失的第一个正数(41)

颜色分类(75)

柱状图中最大的矩形(84)

长度最小的子数组(209)

存在重复元素(217)

存在重复元素2(219)

存在重复元素3（220）

寻找重复数字287

数组中重复的数据(442)

寻找峰值162

多数元素(169)

求众数(229)

有序数组

在排序数组中查找元素的第一个和最后一个位置34

搜索插入位置35

合并区间(56)

插入区间(57)

删除有序数组的重复项(26)

删除有序数组的重复项2(80)

合并排序数组(88)

汇总区间(228)

寻找右区间436

和为s的连续正数序列(剑指offer57)

多维数组

最大正方形(221)

最大矩形(85)

单词搜索(79)

岛屿数量

岛屿最大面积

三角形路径之和(120)

顺时针打印数组(54，剑指offer29)

顺时针生成数组(59)

有序矩阵中第 K 小的元素378

旋转数组

搜索旋转排序数组目标值33、81

搜索旋转排序数组最小值153、154

喜欢这篇文章？打赏一下作者吧

评论

本文章阅读量：

目录

链接

分类

标签云

最新文章

归档

标签

Your browser is out-of-date!