qypx の blog

机会是留给有准备的人的.

发表于 分类于

单调递增的数字（难度：中等）

1

方法：

2
代码
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        s = list(str(N))
        i = 1
        while i<len(s) and s[i-1] <= s[i]:
            i += 1
        while 0 < i < len(s) and s[i-1] > s[i]:
            s[i-1] = str(int(s[i-1])-1)
            i-=1
        s[i+1:] = '9'*(len(s)-i-1)
        return int(''.join(s))

3
复杂度

时间复杂度：O(D)。其中 D≈logN，N 是数字的长度。 空间复杂度：O(D)。

发表于 分类于

移掉K位数字（难度：中等）

1

方法：单调栈

维护一个递增栈，但当前元素小于栈顶元素，则移掉栈顶元素。

思路

转自

作者：monkeybing 链接：https://leetcode-cn.com/problems/remove-k-digits/solution/cyu-yan-zhan-shi-xian-tan-xin-suan-fa-by-monkeybin/ 来源：力扣（LeetCode）

本题采用贪心思路：

  1. 如果字符串按照数字大小升序排列，只需要删除最后K个字符即可；
  2. 如果非升序排列，需要从前到后遍历，删除字符串中每个逆序排列的字符。由于是从前到后遍历，所以先删除的一定是高位的数字，可以保证删除后得到的最终数字最小。

举例来说：如果字符串num = "123456789", k = 3，我们只需要删除最后3个数字，得到"123456". 如果字符串num = "1432219", k = 3，需要从前到后遍历查找逆序数字，进行删除，第一个逆序数字为'4'，第二个逆序数字为'3'，第三个逆序数字为第二个'2'，最后得到"1219"。

所以可以采用栈实现，每次遍历，判断如果栈非空，且当前数字大于栈顶数字，且k还有剩余（不为0），将栈顶数字出栈。最后将当前数字入栈。 如果遍历完成后，k仍有剩余，则依次将栈顶数字出栈。最后栈中保存的数字即为所求。按照从栈底到栈顶输出即可。 注意：特判场景，如果最后所有数字均出栈，即栈为空，需要返回"0"。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        if not num or k <=0:
            return num
        
        stack = []
        for c in num:
            while stack and k > 0 and stack[-1] > c:
                stack.pop()
                k -= 1
            stack.append(c)
        
        while k > 0:
            stack.pop()
            k -= 1

        if not stack:
            return '0'
        
        return str(int(''.join(stack)))
2
复杂度

时间复杂度：O(n).

空间复杂度：O(n).

发表于 分类于

转自：

作者：labuladong 链接：https://leetcode-cn.com/problems/non-overlapping-intervals/solution/tan-xin-suan-fa-zhi-qu-jian-diao-du-wen-ti-by-labu/ 来源：力扣（LeetCode）

什么是贪心算法呢？贪心算法可以认为是动态规划算法的一个特例，相比动态规划，使用贪心算法需要满足更多的条件（贪心选择性质），但是效率比动态规划要高。

比如说一个算法问题使用暴力解法需要指数级时间，如果能使用动态规划消除重叠子问题，就可以降到多项式级别的时间，如果满足贪心选择性质，那么可以进一步降低时间复杂度，达到线性级别的。

什么是贪心选择性质呢，简单说就是：每一步都做出一个局部最优的选择，最终的结果就是全局最优。注意哦，这是一种特殊性质，其实只有一部分问题拥有这个性质。

比如你面前放着 100 张人民币，你只能拿十张，怎么才能拿最多的面额？显然每次选择剩下钞票中面值最大的一张，最后你的选择一定是最优的。

然而，大部分问题明显不具有贪心选择性质。比如打牌，对手出对儿三，按照贪心策略，你应该出尽可能小的牌刚好压制住对方，但现实情况我们甚至可能会出王炸。这种情况就不能用贪心算法，而得使用动态规划解决，参见前文动态规划解决博弈问题。

发表于 分类于

无重叠区间（难度：中等）

1

转自：

作者：labuladong 链接：https://leetcode-cn.com/problems/non-overlapping-intervals/solution/tan-xin-suan-fa-zhi-qu-jian-diao-du-wen-ti-by-labu/ 来源：力扣（LeetCode）

本文解决一个很经典的贪心算法问题 Interval Scheduling（区间调度问题）。给你很多形如 [start, end]的闭区间，请你设计一个算法，算出这些区间中最多有几个互不相交的区间。 举个例子，intvs = [[1,3], [2,4], [3,6]]，这些区间最多有 2 个区间互不相交，即 [[1,3], [3,6]]，你的算法应该返回 2。注意边界相同并不算相交。

这个问题在生活中的应用广泛，比如你今天有好几个活动，每个活动都可以用区间 [start, end] 表示开始和结束的时间，请问你今天最多能参加几个活动呢？显然你一个人不能同时参加两个活动，所以说这个问题就是求这些时间区间的最大不相交子集。

方法：贪心算法

思路
  1. 从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
  2. 把所有与 x 区间相交的区间从区间集合 intvs 中删除。
  3. 重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。
1
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0)
            return 0;
        
		// 按区间的end升序排列
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[1] - b[1];
            }
        });

        int count = 1;
        int x_end = intervals[0][1];
        for(int[] intv:intervals){
            int start = intv[0];
            if(x_end <= start){
                count++;
                x_end = intv[1];
            }
        }
        return intervals.length - count;
    }
}
复杂度

时间复杂度：O(nlogn). 排序需要O(nlogn)的时间。

空间复杂度：O(1). 不需要额外空间。

2

发表于 分类于

判断子序列（难度：简单）

3

方法一

利用Python切片，对s中的每个字符，若在t中，下一步比较index+1开始的字符串

1
2
3
4
5
6
7
8
9
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        for i in s:
            if i in t:
                t = t[t.index(i)+1:]
            else:
                return False
        return True
1

方法二：双指针

若相等，两个指针都往前移，若不等，快指针往前移。最后比较慢指针与s的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        p1 = 0
        p2 = 0
        while p1 < len(s) and p2 < len(t):
            if s[p1] == t[p2]:
                p1 += 1
            p2 += 1
        
        if p1 == len(s):
            return True
        return False
2

发表于 分类于

缺失的第一个正数（难度：困难）

4

方法一（空间复杂度不满足要求）

遍历一遍数组，将元素装入HashSet，再从1开始，判断元素是否在HashSet中，若不存在，则该数为缺失的第一个正数。

复杂度

时间复杂度：O(n).

空间复杂度：O(n).

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num:nums){
            if(!set.contains(num))
                set.add(num);
        }

        int n = 1;
        while(true){
            if(set.contains(n))
                n++;
            else
                return n;
        }
    }
}
1

方法二

思路

通过预处理保证数组中的数全为正数，遍历数组，当读到数字 a 时，替换索引a 处元素的符号为负数。最后返回正数所对应的索引。

算法
  • 首先检查1是否存在于数组中。如果没有，则已经完成，1 即为答案。
  • 若1在数组中，则可将负数，零，和大于 n 的数替换为 1 。
  • 遍历数组。当读到数字 a 时，替换索引a 处元素的符号。（即若数组中出现1，改变nums[1]的符号；若出现2，改变nums[2]的符号） 注意重复元素：只能改变一次符号。由于遇到数字n时，没有下标 n ，则使用索引0 处的元素来保存是否存在数字 n。
  • 返回结果：
    • 从1开始遍历数组。返回第一个正数元素的下标。
    • 如果 nums[0] > 0，则返回 n 。
    • 如果之前的步骤中没有发现 nums 中有正数元素，则返回n + 1。
复杂度

时间复杂度：O(n).所有的操作一共只会遍历长度为 N 的数组 4 次。

空间复杂度：O(1).只使用了常数的空间。

代码
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
43
44
45
46
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        if(nums.length == 0)
            return 1;
        
        // 查看数组中是否包含1
        int contains = 0;
        for(int i = 0; i < n; i++){
            if(nums[i]==1){
                contains += 1;
                break;
            }
        }
        if(contains==0)
            return 1;

        // 替换小于等于0的数及大于n的数为1
        for(int i = 0; i<n; i++){
            if(nums[i]<=0 || nums[i] > n)
                nums[i] = 1;
        }

        // 遍历数组
        for(int i=0; i<n; i++){
            int a = Math.abs(nums[i]);
            if(a==n)
                nums[0] = -Math.abs(nums[0]);
            else
                nums[a] = -Math.abs(nums[a]);
        }

        // 返回结果（索引0处要单独判断，因为若数组中未出现n,则nums[0]处的值会为正数，但不该返回索引0）
        for(int i = 1; i < n; i++){
            if(nums[i]>0)
                return i;
        }
        
        if(nums[0]>0)
            return n;
            
        return n+1;

    }
}
3

发表于 分类于

寻找重复数（难度：中等）

1

方法一：排序

复杂度

时间复杂度：O(nlog(n))。

空间复杂度：O(1) (or O(n))，在这里，我们对 nums 进行排序，因此内存大小是恒定的。如果我们不能修改输入数组，那么我们必须为 nums 的副本分配线性空间，并对其进行排序。

代码
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        for(int i = 1; i < nums.length; i++){
            if(nums[i]==nums[i-1])
                return nums[i];
        }
        return -1;
    }
}
2

方法二：集合（哈希表）

复杂度

时间复杂度：O(n)

空间复杂度：O(n)

代码
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int findDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num : nums){
            if(set.contains(num))
                return num;
            set.add(num);
        }
        return -1;
    }
}
3

发表于 分类于

缺失数字（难度：简单）

3

方法一：数学方法

用序列[0,1,...,n]的和减去给定的nums的和，可得到缺失的数字。

复杂度

时间复杂度：O(n)。

空间复杂度：O(1)。

代码
1
2
3
4
5
6
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        sum1 = sum(range(0,len(nums)+1)) # 0,1,...,n 序列的和(或用高斯求和公式)
        sum2 = sum(nums)

        return sum1 - sum2
1

高斯求和有溢出风险

方法二：位运算（异或运算）

先得到[0,1,...,n]的异或值，再将结果对数组nums中的每一个数进行一次异或运算，最终的异或结果即为这个缺失的数字。

在编写代码时，由于[0,1,...,n]恰好是这个数组的下标加上 n，因此可以用一次循环完成所有的异或运算。

复杂度

时间复杂度：O(n)。假设异或运算的时间复杂度是常数的。

空间复杂度：O(1)。

代码
1
2
3
4
5
6
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        res = len(nums) # 一开始初始化为n
        for i in range(0,len(nums)):
            res ^=  i ^ nums[i]
        return res
2

发表于 分类于

回文链表（难度：简单）

1

思路

使用快慢指针找到中点，对链表前半部分进行翻转。

复杂度

时间复杂度：O(n)

空间复杂度：O(1)

代码
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null || head.next==null)
            return true;
        
        ListNode slow = head, fast = head;
        ListNode pre = head, prepre = null;

        // 一遍遍历实现翻转前半部分
        while(fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next; // 若链表长度为偶数，则fast最后会指向null，若为奇数，fast最后会指向最后一个元素
            pre.next = prepre;
            prepre = pre;
        }
        // 循环结束后，若为偶数，slow指向后半部分第一个元素，若为奇数，slow指向中间的那个元素

        if(fast != null)
            slow = slow.next;
        
        while(pre!=null && slow!=null){
            if(pre.val != slow.val)
                return false;
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }
}
2
20191229-214756

发表于 分类于

翻转二叉树（难度：简单）

1

方法： 递归

复杂度

时间复杂度：O(n). 每个节点只被访问了一次。

空间复杂度：最坏情况下栈内需要存放 O(h)个方法调用，其中 h是树的高度。由于 h∈O(n)，可得出空间复杂度为 O(n)。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null)
            return root;
        TreeNode temp = invertTree(root.left);
        root.left = invertTree(root.right);
        root.right = temp;

        return root;
    }
}
2
0%