Leetcode 算法面试冲刺 实战 六(数组与循环)(十三)

2133-Jammy

发表文章数:226

首页 » 算法 » 正文

768 · 杨辉三角

给一整数 n, 返回杨辉三角的前 n 行

Leetcode 算法面试冲刺 实战 六(数组与循环)(十三)
每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和,这也是组合数的性质之一。即 C(n+1,i)=C(n,i)+C(n,i-1)。

def calcYangHuisTriangle(self, n):
        # write your code here
        if n <= 0: return []
        elif n == 1: return [[1]]
        elif n == 2: return [[1], [1, 1]]
        
        li = [[1], [1, 1]]
        for i in range(2, n):
            temp = [1]
            for j in range(1, i):
                temp.append(li[i-1][j-1] + li[i-1][j])
            temp.append(1)
            li.append(temp)
        return li

边界问题一开始又忘记考虑了。
Leetcode 算法面试冲刺 实战 六(数组与循环)(十三)
看到了一个优秀的答案,非常秀:

def calcYangHuisTriangle(self, n):
        # write your code here
        res = [[1] * i for i in range(1,n+1)]
        for row in range(2,n):
            for col in range (1,row):
                res[row][col] = res[row-1][col-1] + res[row-1][col]
        return res

767 · 翻转数组

原地翻转给出的数组 nums

Leetcode 算法面试冲刺 实战 六(数组与循环)(十三)

def reverseArray(self, nums):
        # write your code here
        left, right = 0, len(nums) - 1
        while left <= right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
        return nums
    

我又没有特殊情况,蠢死

Leetcode 算法面试冲刺 实战 六(数组与循环)(十三)
看到了一个答案用for循环做的:

def reverseArray(self, nums):
        # write your code here
        n = len(nums)
        for i in range(n//2):
            nums[i], nums[n-i-1] = nums[n-i-1], nums[i]
        return nums

539 · 移动零

给一个数组 nums 写一个函数将 0 移动到数组的最后面,非零元素保持原数组的顺序。
Leetcode 算法面试冲刺 实战 六(数组与循环)(十三)
我一开始写的代码,虽然把0都排序到了后面,但是非0的顺序改变了。

def moveZeroes(self, nums):
        # write your code here
        if not nums: return
        left, right = 0, len(nums) - 1
        while left <= right:
            while (left < right) and (nums[left] != 0): left += 1
            while (left < right) and (nums[right] == 0): right -= 1
            if left == right: break
            nums[left], nums[right] = nums[right], nums[left]
        return nums

Leetcode 算法面试冲刺 实战 六(数组与循环)(十三)

def moveZeroes(self, nums):
        # write your code here
        zero, nonzero = 0, 0
        n = len(nums)
        while nonzero < n - 1 and zero < n - 1:
            while nonzero < n - 1 and nums[nonzero] == 0: nonzero += 1
            while zero < n - 1 and nums[zero] != 0: zero += 1
            if zero < nonzero:
                nums[zero], nums[nonzero] = nums[nonzero], nums[zero]
            elif nonzero == n - 1 or zero == n - 1: break
            elif zero > nonzero: nonzero += 1

总结:这道题想了很久,关于指针的问题。而且代码的健壮性也不好,打了很多次的补丁。
Leetcode 算法面试冲刺 实战 六(数组与循环)(十三)
看了下官方答案,确实写的很简单:

def moveZeroes(self, nums):
        left, right = 0, 0
        while right < len(nums):
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1

思路就是left如果指向非0,他们俩是相等的情况,互换等于不变。当left指向0,right指向非0,然后互换,进行了调换。
本质就是两个同时出发,同时前进,但是right如果遇到0,就多走一步,所以right永远比left先到终点。因为right遇到0,跳过,所有right和left互换,就是把前面非0,和后面的0 进行了调换。

479 · 数组第二大数

在数组中找到第二大的数。
Leetcode 算法面试冲刺 实战 六(数组与循环)(十三)

import heapq
class Solution:
    """
    @param nums: An integer array
    @return: The second max number in the array.
    """
    
    def secondMax(self, nums):
        # write your code here
        que = []
        heapq.heapify(que)
        for num in nums:
            heapq.heappush(que, num)
            if len(que) > 2:
                heapq.heappop(que)
        return que[0]
            

总结:用了大顶堆的方法,第一次用,之前看《算法之美》从老师那里学来的,这次再具体说下大顶堆的一些工作原理。
Leetcode 算法面试冲刺 实战 六(数组与循环)(十三)
本题是我们求在一个数据流中的第 KK 大元素。所谓数据流,即是说我们写的算法需要支持 add() 函数;在力扣后台评测程序中会多次调用add()函数,每次调用都会向我们写的算法中添加一个元素。而题目要求的就是在每次 add() 之后,整个数据流(包括初始化的元素和所有 add 进来的元素)中的第 KK 大元素。

先说一个最暴力的解法:我们底层数据结构使用数组实现,当每次调用 add() 函数时,向数组中添加一个元素,然后调用 sort() 函数进行排序,返回排序后数组的第 KK 个数字。该做法在每次调用 add() 函数时的时间复杂度为 O(K*log(K))O(K∗log(K)) ,该时间复杂度太高,当 KK 很大 / add()调用次数太多的时候,一定会超时。

从上面的分析中,我们已经看出来了,使用数组的核心问题是:数组自身不带排序功能,只能用 sort() 函数,导致时间复杂度过高。

因此我们考虑使用自带排序功能的数据结构——堆。

在大根堆(图一)中,父节点的值比每一个子节点的值都要大。在小根堆(图二)中,父节点的值比每一个子节点的值都要小。

Leetcode 算法面试冲刺 实战 六(数组与循环)(十三)
题的操作步骤如下:

使用大小为 KK 的小根堆,在初始化的时候,保证堆中的元素个数不超过 KK 。
在每次 add() 的时候,将新元素 push() 到堆中,如果此时堆中的元素超过了 KK,那么需要把堆中的最小元素(堆顶)pop() 出来。
此时堆中的最小元素(堆顶)就是整个数据流中的第 KK 大元素。
问答:

为什么使用小根堆?
因为我们需要在堆中保留数据流中的前 KK 大元素,使用小根堆能保证每次调用堆的 pop() 函数时,从堆中删除的是堆中的最小的元素(堆顶)。
为什么能保证堆顶元素是第 KK 大元素?
因为小根堆中保留的一直是堆中的前 KK 大的元素,堆的大小是 KK,所以堆顶元素是第 KK 大元素。
每次 add() 的时间复杂度是多少?
每次 add() 时,调用了堆的 push() 和 pop() 方法,两个操作的时间复杂度都是 log(K)log(K).

class KthLargest(object):

    def __init__(self, k, nums):
        """
        :type k: int
        :type nums: List[int]
        """
        self.k = k
        self.que = nums
        heapq.heapify(self.que)

    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        heapq.heappush(self.que, val)
        while len(self.que) > self.k:
            heapq.heappop(self.que)
        return self.que[0]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

看了一个答案,是打擂台的方法:

def secondMax(self, nums):
        # write your code here
        maxValue = max(nums[0], nums[1])
        secValue = min(nums[0], nums[1])
        
        for i in xrange(2, len(nums)):
            if nums[i] > maxValue:
                secValue = maxValue
                maxValue = nums[i]
            elif nums[i] > secValue:
                secValue = nums[i]
                
        return secValue

235 · 分解质因数

将一个整数分解为若干质因数之乘积。
Leetcode 算法面试冲刺 实战 六(数组与循环)(十三)
Leetcode 算法面试冲刺 实战 六(数组与循环)(十三)

class Solution:
    """
    @param num: An integer
    @return: an integer array
    """
    def primeFactorization(self, num):
        # write your code here
        li = []
        return self.derive(num, li)

    def derive(self, num, li):
        for n in range(2, num):
            if num % n == 0:
                li.append(n)
                return self.derive(num // n, li)
        li.append(num)
        return li

总结:我用了递归的方法,但是后面大数过不去。
Leetcode 算法面试冲刺 实战 六(数组与循环)(十三)
官方答案:
解题思路:
先求得一个质数数组,然后从小到大遍历该数组,若题目所给整数能够被某质数整除,则将该数加入答案值数组。

算法流程:
从小到大遍历[2,up],若num能够被i整除则循环除以i直到不能被整除,每次除以i都向答案值数组增加一个i,因为是从小到大遍历,则必定只有质数能被取为因数
up一般设定为sqrt(num),因为一个数大于其根号的质因数最多只有一个,那么遍历其根号内的数可以将时间复杂度减小至根号n,若遍历完prime后该数不为1,则其值为最后一个质因数
复杂度分析:
时间复杂度:O(sqrt(num))O(sqrt(num))
因为在该过程中,每个数都要被遍历常数次。而这个常数值随着数字增大骤减,基本等同于线性值

空间复杂度:O(1)O(1)
因为答案值只需要存num的所有质因数即可,一个[1,1e9]范围内的数,质因数个数不会超过32个,因此空间复杂度为常数复杂度。

def primeFactorization(self, num):
        up = int(num**0.5 + 1)
        ans = []
        for i in range(2,up):
            while num % i == 0:
                num /= i
                ans += [i]
        # 若最后剩余数不为1,则为最后一个质因数
        if num != 1:
            ans += [int(num)]
        return ans

拜师教育学员文章:作者:2133-Jammy, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Leetcode 算法面试冲刺 实战 六(数组与循环)(十三)》 发布于2022-01-25

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录