qypx の blog

存在重复元素2

发表于 2019-12-29 分类于 leetcode

存在重复元素2（难度：简单）

方法：哈希表

维护一个哈希表，里面始终最多包含 k 个元素，当出现重复值时则说明在 k 距离内存在重复元素。每次遍历一个元素则将其加入哈希表中，如果哈希表的大小大于 k，则移除最前面的数字。

复杂度

时间复杂度：O(n)。我们会做 n 次搜索，删除，插入操作，每次操作都耗费常数时间。

空间复杂度：O(min(n,k))。开辟的额外空间取决于散列表中存储的元素的个数，也就是滑动窗口的大小。

代码

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> res = new HashSet<>();
        for(int i = 0; i < nums.length; i++){
            if(res.contains(nums[i]))
                return true; // 因为res的大小维持为k
            res.add(nums[i]);
            if(res.size()>k)
                res.remove(nums[i-k]);   
        }
        return false;
    }
}

存在重复元素

发表于 2019-12-29 分类于 leetcode

存在重复元素（难度：简单）

方法一：哈希表

复杂度

时间复杂度 : O(n)。search() 和 insert() 各自使用 n 次，每个操作耗费常数时间。

空间复杂度 : O(n)。哈希表占用的空间与元素数量是线性关系。

代码

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> res = new HashSet<>();
        for(int num:nums){
            if(res.contains(num))
                return true;
            res.add(num);
        }
        return false;
    }
}

另一种思路：利用Python中的set()，判断所得结果长度与原数组长度的关系

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        set1 = set(nums)
        if len(set1) == len(nums):
            return False
        else:
            return True

方法二：排序

如果存在重复元素，排序后它们应该相邻。

复杂度

时间复杂度 : O(nlogn)。

空间复杂度 : O(1)。这取决于具体的排序算法实现，通常而言，使用 堆排序 的话，是 O(1)。

代码

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0; i < nums.length-1; i++){
            if(nums[i]==nums[i+1])
                return true;
        }
        return false;
    }
}

注：对于一些特定的 n不太大的测试样例，方法一的运行速度可能会比方法二更慢。这是因为哈希表在维护其属性时有一些开销。要注意，程序的实际运行表现和 Big-O 符号表示可能有所不同。Big-O 只是告诉我们在充分大的输入下，算法的相对快慢。因此，在 n不够大的情况下， O(n)的算法也可以比 O(nlogn)的更慢。

数组中的第K个最大元素

发表于 2019-12-29 分类于 leetcode

数组中的第K个最大元素（难度：中等）

方法一：排序

先对数组进行排序，再返回倒数第 k 个元素。

复杂度

时间复杂度：O(nlogn)

空间复杂度：O(1)

这个时间复杂度并不令人满意

代码

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[-k]

方法二：最小堆

建一个只能存K个数字的小顶堆，超过K时候，每加进来一个，堆顶就要弹出一个。数组遍历完，最终堆顶的元素就是第K大的（堆里其他元素都比它还要大）。

复杂度

时间复杂度：O(nlogk). 向大小为 k 的堆中添加元素的时间复杂度为O(logk)，我们将重复该操作 n 次，故总时间复杂度为O(nlogk)。

空间复杂度：O(k).

代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for(int num : nums){
            minHeap.add(num);
            if(minHeap.size()>k)
                minHeap.poll();
        }

        return minHeap.poll();
        
    }
}

方法三：快速选择

详见这里.

复杂度

时间复杂度 : 平均情况O(N)，最坏情况 O(N^2)。

空间复杂度 : O(1)。

移除链表元素

发表于 2019-12-29 分类于 leetcode

移除链表元素（难度：简单）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode cur = dummy;

        while(cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            } else{
                cur = cur.next;
            }
        }

        return dummy.next;
        
    }
}

注：添加虚拟头节点解决头节点是要被删除的情况

快乐数

发表于 2019-12-28 分类于 leetcode

快乐数（难度：简单）

方法一：使用“快慢指针”思想找出循环

“快指针”每次走两步，“慢指针”每次走一步，当二者相等时，即为一个循环周期。此时，判断是不是因为1引起的循环，是的话就是快乐数，否则不是快乐数。

代码

class Solution {
    public boolean isHappy(int n) {
        int slow = n;
        int fast = n;
        do{
            slow = helper(slow);
            fast = helper(fast);
            fast = helper(fast);
        } while(slow != fast);
        return slow == 1;
    }

    public int helper(int n){
        int sum = 0;
        while(n>0){
            int re = n%10;
            sum += re*re;
            n = n/10;
        }
        return sum;
    }
}

方法二：递归

不是快乐数的数称为不快乐数(unhappy number)，所有不快乐数的数位平方和计算，最后都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中
已知规律： [1 ~ 4] 中只有 1 是快乐数，[5 ~ ∞] 的数字要么回归到 1 要么回归到 4 或 3
因此仅需在 n > 4 时调用递归

代码

1
2
3

class Solution:
    def isHappy(self, n: int) -> bool:
        return self.isHappy(sum(int(i) ** 2 for i in str(n))) if n > 4 else n == 1

求众数2

发表于 2019-12-28 分类于 leetcode

求众数2（难度：中等）

方法一：

在Python中，先用set()找出所有出现的元素，再使用count()判断出现次数大于n/3的。

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        set1 = set(nums)
        return [s for s in set1 if nums.count(s) > len(nums)//3]

然而时间复杂度不为O(n)。

方法二：Boyer-Moore 投票算法

超过n/3的数最多只能有两个。先选出两个候选人A,B（都令为nums[0]）。遍历数组：

若当前元素等于A，则A的票数++;
若当前元素等于B，则B的票数++；
若当前元素与A，B都不相等，那么检查此时A或B的票数是否减为0：
- 若为0，则当前元素成为新的候选人；
- 若A、B票数均不为0，则A、B两个候选人的票数均减一；

遍历结束后选出了两个候选人，但是这两个候选人是否满足>n//3，还需要再遍历一遍数组，找出两个候选人的具体票数。

复杂度

时间复杂度：O(n)

空间复杂度：O(1)

代码

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        if(len(nums)==0):
            return []
        count1 = 0
        count2 = 0
        candidate1 = nums[0]
        candidate2 = nums[0]
 
        for num in nums:
            if num == candidate1:
                count1 += 1
            elif num == candidate2:
                count2 += 1
            else:
                if count1 == 0:
                    candidate1 = num
                    count1 += 1
                elif count2 == 0:
                    candidate2 = num
                    count2 += 1
                else:
                    count1 -= 1;
                    count2 -= 1;
    
        return set([num for num in [candidate1, candidate2] if nums.count(num) > len(nums)//3]) #加set的原因是避免返回两个相同的数

多数元素

发表于 2019-12-28 分类于 leetcode

多数元素（难度：简单）

注意：这样的元素只存在一个，因为出现次数大于n/2，若存在两个，则数组长度会超过n。

方法一：

在Python中，先用set()找出所有出现的元素，再使用count()判断出现次数大于n/2的。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        set1 = set(nums)
        for s in set1:
            if nums.count(s) > len(nums)//2:
                return s

方法二：

先排序，再返回位于n/2位置的元素。

复杂度

时间复杂度：O(nlogn)。用 Python 和 Java 将数组排序开销都为 O(nlogn)，它占据了运行的主要时间。

空间复杂度：O(1)或O(n)。就地排序或使用线性空间将 nums 数组拷贝，然后再排序。

代码

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]

方法三：Boyer-Moore 投票算法

从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，最后总能找到最多的那个。

复杂度

时间复杂度：O(n)。严格执行了 n 次循环。

空间复杂度：O(1)。

代码

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = nums[0]

        for num in nums:
            if count == 0:
                candidate = num
            if num==candidate:
                count += 1
            else:
                count -= 1
        
        return candidate

寻找峰值

发表于 2019-12-28 分类于 leetcode

寻找峰值（难度：中等）

方法一：线性扫描

利用连续的两个元素 nums[j] 和 nums[j+1] 不会相等这一事实，我们可以从头开始遍历 nums数组，当遇到nums[i] > nums[i+1] ，即可判断 nums[i]为峰值。

注意：不需要判断nums[i]>nums[i-1]。这是由于“遍历会到达第i个元素”本身就说明上一个元素（第i- 1个）不满足 nums[i] > nums[i+1]这一条件，也就说明 nums[i-1] < nums[i]。

复杂度分析

时间复杂度 : O(n)。只进行一次遍历。空间复杂度 : O(1)。只使用了常数空间。

代码

class Solution {
    public int findPeakElement(int[] nums) {
        for(int i = 0; i < nums.length - 1; i++){
            if(nums[i] > nums[i+1])
                return i;
        }
        return nums.length-1;
    }
}

方法二：二分法查找

复杂度分析

时间复杂度 : O(logn)。每一步都将搜索空间减半。空间复杂度 : O(1)。只使用了常数空间。

代码

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length-1;

        while(left < right){
            int mid = (left+right)/2;
            if(nums[mid]>nums[mid+1]) // 往左搜索
                right = mid;
            else if(nums[mid]<nums[mid+1]) // 往右搜索
                left = mid+1;
        }
        return left;
    }
}

最长重复子数组

发表于 2019-12-28 分类于 leetcode

最长重复子数组（难度：中等）

方法：动态规划

作者：LeetCode 链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zui-chang-zhong-fu-zi-shu-zu-by-leetcode/ 来源：力扣（LeetCode）

设 dp[i][j]为 A[i:] 和 B[j:] 的最长公共前缀，那么答案为所有 dp[i][j] 中的最大值 max(dp[i][j])。若 A[i] == B[j]，状态转移方程为 dp[i][j] = dp[i + 1][j + 1] + 1，否则为 dp[i][j] = 0。

复杂度分析

时间复杂度：O(M*N)，其中 M和 N是数组 A 和 B 的长度。空间复杂度：O(M*N)，即为数组 dp 使用的空间。

代码

class Solution {
    public int findLength(int[] A, int[] B) {
        int[][] dp = new int[A.length+1][B.length+1]; // 长度加1是为了后面的dp[i+1][j+1]
        int res = 0;
        for(int i = A.length-1; i>=0; i--){
            for(int j = B.length-1; j>=0; j--){
                if(A[i] == B[j])
                    dp[i][j] = dp[i+1][j+1] + 1;
                res = Math.max(res,dp[i][j]);
            }
        }
        return res;
    }
}

最大连续1的个数

发表于 2019-12-27 分类于 leetcode

最大连续1的个数（难度：简单）

方法一：一次遍历

复杂度分析

时间复杂度：O(N)。N是数组的长度。
空间复杂度：O(1)，仅仅使用了 count 和 maxCount。

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = 0
        maxcount = 0
        for num in nums:
            if num == 0:
                maxcount = max(maxcount, count)
                count = 0
            else:
                count += 1
        return max(maxcount,count)

方法：哈希表

复杂度

代码

方法一：哈希表

复杂度

代码

方法二： 排序

复杂度

代码

方法一：排序

复杂度

代码

方法二：最小堆

复杂度

代码

方法三：快速选择

复杂度

方法一：使用“快慢指针”思想找出循环

代码

方法二：递归

代码

方法一：

方法二：Boyer-Moore 投票算法

方法一：

方法二：

复杂度

代码

方法三：Boyer-Moore 投票算法

复杂度

代码

方法一：线性扫描

复杂度分析

代码

方法二：二分法查找

复杂度分析

代码

方法：动态规划

方法一：一次遍历

方法二：排序