倬倬吃三碗
0%

基础算法笔记

发表于 更新于 分类于

双指针

image-20220727183840528

LC141.环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220727184138242

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head is None:
            return False
        slow = head
        fast = head
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

LC881.救生艇

给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回 承载所有人所需的最小船数 。

示例 1：

输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)
示例 2：

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)
示例 3：

输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/boats-to-save-people
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220728124543088

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int i = 0;
        int j = people.length - 1;
        int res = 0;
        while(i <= j){
            if(people[i] + people[j] <= limit){
                i++;
            }
            j--;
            res++;
        }
        return res;
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        if people is None or len(people) == 0:
            return 0
        people.sort()
        i = 0
        j = len(people) - 1
        res = 0
        while(i <= j):
            if people[i]+people[j] <= limit:
                i = i + 1
            j = j - 1
            res = res + 1
        return res

二分查找法

image-20220728143833720

LC704.二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220728143910644

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        } 
        return -1;
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if nums == None or len(nums) == 0:
            return -1
        left,right = 0, len(nums)-1
        while(left <= right):
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        return -1

LC35.搜索插入位置

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

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220728144511472

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int searchInsert(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return 0;
        }

        int left = 0;
        int right = nums.length - 1;

        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return nums[left] < target ? left + 1 : left;
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if nums == None or len(nums) == 0:
            return 0
        left = 0
        right = len(nums)
        while(left < right):
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid
            else:
                left = mid + 1
        return left

LC162.寻找峰值

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

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

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

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-peak-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220827033256691

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findPeakElement(int[] nums) {
        if(nums == null || nums.length == 0){
            return -1;
        }

        int l = 0;
        int r = nums.length - 1;
        while(l < r){
            int mid = l + (r - l) / 2;
            if(nums[mid] > nums[mid + 1]){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        if nums is None or len(nums) == 0:
            return -1

        l = 0
        r = len(nums) - 1
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] > nums[mid + 1]:
                r = mid
            else:
                l = mid + 1
        return l

LC74.探索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-a-2d-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220827140029780

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0){
            return false;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int l = 0;
        int r = row * col - 1;
        while(l <= r){
            int mid = l + (r-l)/2;
            int element = matrix[mid/col][mid%col];
            if(element == target){
                return true;
            }else if (element > target){
                r = mid - 1; 
            }else{
                l = mid + 1;
            }
        }
        return false;
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if matrix is None or len(matrix) == 0:
            return False
        
        row = len(matrix)
        col = len(matrix[0])
        l = 0
        r = row * col - 1
        while l <= r:
            m = l + (r-l)//2
            element = matrix[m//col][m%col]
            if element == target:
                return True
            elif element > target:
                r = m - 1
            else:
                l = m + 1
        return False

滑动窗口

image-20220827141540045

LC209.长度最小的子数组

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

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

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

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-size-subarray-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220827142655844

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int i = 0;
        int j = 0;
        int result = nums.length + 1;
        int total = 0;
        while(j < nums.length){
            total += nums[j];
            j++;
            while(total >= target){
                result = Math.min(result,j - i);
                total -= nums[i];
                i++;
            }
        }
        return result == nums.length+1 ? 0: result;
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if nums is None or len(nums) == 0:
            return 0
        result = len(nums) + 1
        total = 0
        i,j = 0,0
        while j < len(nums):
            total += nums[j]
            j += 1
            while total >= target:
                result = min(result,j - i)
                total -= nums[i]
                i += 1
        return 0 if result == len(nums)+1 else result

LC1456.定长字串种元音的最大数目

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为（a, e, i, o, u）。

示例 1：

输入：s = “abciiidef”, k = 3
输出：3
解释：子字符串 “iii” 包含 3 个元音字母。
示例 2：

输入：s = “aeiou”, k = 2
输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母。
示例 3：

输入：s = “leetcode”, k = 3
输出：2
解释：”lee”、”eet” 和 “ode” 都包含 2 个元音字母。
示例 4：

输入：s = “rhythms”, k = 4
输出：0
解释：字符串 s 中不含任何元音字母。
示例 5：

输入：s = “tryhard”, k = 4
输出：1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220827151934833

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int maxVowels(String s, int k) {
        if (s == null || s.length() == 0 || s.length() < k){
            return 0;
        }
        HashSet<Character> set = new HashSet<>();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');
        int res = 0;
        int count = 0;
        for(int i = 0; i < k; i++){
            char temp = s.charAt(i);
            if(set.contains(temp)){
                count++;
            }
        }
        res = Math.max(res,count);
        for(int i = k; i < s.length(); i++){
            char out = s.charAt(i - k);
            char in = s.charAt(i);
            if(set.contains(out)){
                count--;
            }
            if(set.contains(in)){
                count++;
            }
            res = Math.max(res,count);
        }
        return res;
        }
    }

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        if s is None or len(s) == 0 or len(s) < k:
            return 0
        hashset = set(['a','e','i','o','u'])
        res = 0
        count = 0
        for i in range(0,k):
            if s[i] in hashset:
                count = count + 1
        res = max(res,count)

        for i in range(k,len(s)):
            out = s[i-k]
            inc = s[i]
            if out in hashset:
                count = count - 1
            if inc in hashset:
                count = count + 1
            res = max(res,count)
        return res

递归

image-20220828215758213

image-20220828215810146

LC509.斐波拉契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fibonacci-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220828223442929

Java

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int fib(int n) {
        if(n < 2){
            return n == 1? 1:0;
        }
        int sum = fib(n - 1) + fib(n - 2);
        return sum;
    }
}

Python3

1
2
3
4
5
6
class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return 0 if n == 0 else 1
        m = self.fib(n - 1) + self.fib(n - 2)
        return m

LC206.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：

输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220828224353476

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        while(head != null && head.next != null){
            ListNode dnext = dummy.next;
            ListNode hnext = head.next;
            dummy.next = hnext;
            head.next = hnext.next;
            hnext.next = dnext;
        }
        return dummy.next;
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        while head is not None and head.next is not None:
            dnext = dummy.next
            hnext = head.next
            dummy.next = hnext
            head.next = hnext.next
            hnext.next = dnext
        return dummy.next

LC344.反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = [“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]
示例 2：

输入：s = [“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220828225749633

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void reverseString(char[] s) {
        if(s == null || s.length == 0){
            return;
        }

        recursion(s, 0, s.length - 1);
    }

    public void recursion(char[] s, int left, int right){
        if(left >= right){
            return;
        }
        recursion(s, left + 1, right - 1);
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        self.recursion(s,0,len(s) - 1)

    def recursion(self, s, left, right):
        if left >= right:
            return
        self.recursion(s,left + 1, right - 1)
        s[left],s[right] = s[right],s[left]

分治法

image-20220829113531468

LC169.多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/majority-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220829115030118

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int majorityElement(int[] nums) {
        return getMajority(nums, 0, nums.length - 1);
    }
    private int getMajority(int[] nums, int left, int right){
        if(left == right){
            return nums[left];
        }
        int mid = left + (right-left)/2;
        int leftMajority = getMajority(nums, left, mid);
        int rightMajority = getMajority(nums, mid+1, right);

        if(leftMajority == rightMajority){
            return leftMajority;
        }

        int leftCount = 0;
        int rightCount = 0;
        for(int i = left; i <= right; i++){
            if(nums[i] == leftMajority){
                leftCount++;
            }else if(nums[i] == rightMajority){
                rightCount++;
            }
        }
        return leftCount > rightCount ? leftMajority : rightMajority;
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return self.getMajority(nums, 0, len(nums)-1)
    
    def getMajority(self, nums, left, right):
        if left == right:
            return nums[left]
        
        mid = left + (right - left)//2
        leftMajority = self.getMajority(nums,left,mid)
        rightMajority = self.getMajority(nums,mid+1,right)
        if leftMajority == rightMajority:
            return leftMajority

        leftCount = 0
        rightCount = 0
        for i in range(left, right+1):
            if nums[i] == leftMajority:
                leftCount += 1
            elif nums[i] == rightMajority:
                rightCount += 1
        return leftMajority if leftCount > rightCount else rightMajority

LC53.最大子数组和

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

子数组 是数组中的一个连续部分。

示例 1：

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

输入：nums = [1]
输出：1
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220829123903219

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    // Leetcode 53. Maximum Subarray
    // Divide & COnquer
    // N is the size of nums
    // Time Complexity: O(N)
    // Space Complexity: O(logN)
    public int maxSubArray(int[] nums) {
        return getMax(nums, 0, nums.length - 1);
    }

    private int getMax(int[] nums, int l, int r) {
        if (l == r) {
            return nums[l];
        }
        int mid = l + (r-l)/2;
        int leftSum = getMax(nums, l, mid);
        int rightSum = getMax(nums, mid+1, r);
        int crossSum = crossSum(nums, l, r);
        return Math.max(crossSum, Math.max(leftSum, rightSum));
    }

    private int crossSum(int[] nums, int l, int r) {
        int mid = l + (r-l)/2;
        // from mid to leftmost
        int leftSum = nums[mid];
        int leftMax = leftSum;
        for (int i = mid - 1; i >= l; i--) {
            leftSum += nums[i];
            leftMax = Math.max(leftMax, leftSum);
        }

        // from mid+1 to rightmost
        int rightSum = nums[mid+1];
        int rightMax = rightSum;
        for (int i = mid + 2; i <= r; i++) {
            rightSum += nums[i];
            rightMax = Math.max(rightMax, rightSum);
        }

        return leftMax + rightMax;
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    # Leetcode 53. Maximum Subarray
    # Divide And Conquer
    # N is the size of nums
    # Time Complexity: O(N)
    # Space Complexity: O(logN)
    def maxSubArray(self, nums: List[int]) -> int:
        return self.getMax(nums, 0, len(nums)-1)
    
    def getMax(self, nums, l, r):
        if l == r:
            return nums[l]
        mid = l + (r-l)//2
        leftSum = self.getMax(nums, l, mid)
        rightSum = self.getMax(nums, mid+1, r)
        crossSum = self.crossSum(nums, l, r)
        return max(leftSum, rightSum, crossSum)
    
    def crossSum(self, nums, l, r):
        mid = l + (r-l)//2
        # from mid to leftmost
        leftSum = nums[mid]
        leftMax = leftSum
        for i in range(mid-1, l-1, -1):
            leftSum += nums[i]
            leftMax = max(leftMax, leftSum)
        
        # from mid to rightmost
        rightSum = nums[mid+1]
        rightMax = rightSum
        for i in range(mid+2, r+1):
            rightSum += nums[i]
            rightMax = max(rightMax, rightSum)
        
        return leftMax + rightMax

回溯法

image-20220830123819084

LC22.括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：

输入：n = 1
输出：[“()”]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220830125449102

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtracking(n,result,0,0,"");
        return result;
    }

    private void backtracking(int n, List<String> result, int left, int right,String str){
        if(right > left){
            return;
        }
        if(left == n && right == n){
            result.add(str);
            return;
        }
        if(left < n){
            backtracking(n, result, left+1, right, str+"(");
        }
        if(right < left){
            backtracking(n, result, left, right+1, str+")");
        }
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        self.backtracking(n,result,0,0,"")
        return result
    
    def backtracking(self,n,result,left,right,s):
        if right > left:
            return
        if (left == n and right == n):
            result.append(s)
            return
        if left < n:
            self.backtracking(n,result,left+1,right,s+"(")
        if right < left:
            self.backtracking(n,result,left,right+1,s+")")

LC78.子集

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

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

示例 1：

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

输入：nums = [0]
输出：[[],[0]]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220830125432298

image-20220830131216375

image-20220830131244644

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for (int i = 1; i <= nums.length; i++) {
            backtracking(nums, result, i, 0, new ArrayList<>());
        }
        return result;
    }
    private void backtracking(int[] nums, List<List<Integer>> result, int length, int index, List<Integer> subset) {
        if (subset.size() == length) {
            result.add(new ArrayList<>(subset));
            return;
        }
        for(int i = index; i < nums.length; i++) {
            subset.add(nums[i]);
            backtracking(nums, result, length, i+1, subset);
            subset.remove(subset.size()-1);
        }

    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]: 
        result = [[]]
        for i in range(1,len(nums)+1):
            self.backtracking(nums,result,i,0,[])
        return result
    def backtracking(self,nums,result,length,index,subset):
        if len(subset) == length:
            result.append(subset[:])
            return
        for i in range(index,len(nums)):
            subset.append(nums[i])
            self.backtracking(nums,result,length,i+1,subset)
            subset.pop()