本文介绍: 有个技巧,若想熟悉语言写法可以照着其它语言题解,写目标语言代码比如有C/C++的题解,写Python算法,这样同时可以对比两种语言,并熟悉Python代码中API的使用,并且可以增强代码迁移能力语言只是一种实现工具,不被语言束缚也是一种自由。给你一个严格递增排列数组 nums ,请你 原地 删除重复出现元素,使每个元素出现一次返回删除数组的新长度。,我想,h 指数的基本思想是:论文发的越多,不一定代表水平越高,而是发的越多,也要引用的越多才行,

有个技巧,若想熟悉语言的写法可以照着其它语言的题解,写目标语言的代码比如有C/C++的题解,写Python算法,这样同时可以对比两种语言,并熟悉Python代码中API的使用,并且可以增强代码迁移能力,语言只是一种实现工具,不被语言束缚也是一种自由。

1. 合并两个有序数组

题目链接合并两个有序数组leetcode
题目描述
给你两个按 非递减顺序 排列整数数组 nums1 和 nums2,另有两个整数 mn ,分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列
注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度m + n,其中前 m元素表示合并元素,后 n元素为 0 ,应忽略nums2 的长度为 n 。

解题思路
(1) 排序法。将nums2添加nums1并排序,但这样的做法未利用nums1与nums2非递减的特性时间复杂度排序的时间复杂度

O

(

(

m

+

n

)

l

o

g

2

(

m

+

n

)

)

O((m+n)log_2(m+n))

O((m+n)log2(m+n))空间复杂度认为是快排的空间复杂度

O

(

l

o

g

2

(

m

+

n

)

)

O(log_2(m+n))

O(log2(m+n))
(2) 双指针法。新建一个数组sorted用来存储然后nums1指向新数组的内容,用双指针比较nums1和nums2各元素的大小存储sorted数组中

Python3

排序
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1[m:] = nums2
        nums1.sort()
指针
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1, p2 = 0,0
        index_bound1, index_bound2 = m-1,n-1 # 数组下标索引边界,这和长度区别
        sorted = []
        while p1 <= index_bound1 or p2 <= index_bound2:
            # 1.若有某一数组下标出界,表明该数组已判断完成,应存另一数组的值
            if p1 > index_bound1:
                sorted.append(nums2[p2])
                p2 += 1
            elif p2 > index_bound2:
                sorted.append(nums1[p1])
                p1 += 1
            # 2.比较两数大小,存更小的,以确保是非递减序列
            elif (nums1[p1] <= nums2[p2]):
                sorted.append(nums1[p1])
                p1 += 1
            else:
                sorted.append(nums2[p2])
                p2 += 1
        nums1[:] = sorted

2. 移除元素

题目描述
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出长度后面的元素。
题目归纳:
即要将数值中值等于val的元素全部移除,并且不能使用额外的数组空间

解题思路
指针法。left指针从数组起点向右,right指针从数组终点向左,若nums[left]与val相等,就不断的将nums[left]的值与nums[right]的值交换,保证数组在[0,left]的纯洁性。

Python3

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            if(nums[left] == val): # swap,将等于val放到数组后面去
                nums[left],nums[right] = nums[right],nums[left]
                right -= 1
            else:
                left += 1
        return left

3. 删除有序数组中的重复元素

题目描述
给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数
考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以通过
更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
题目归纳:
首先分析有序数组的特点
由于数组有序,且非严格递增
故对于任意 i < j,若有nums[i] = nums[j]
则有任意i <= k <= j,nums[i] = nums[k] = nums[j]
利用上述特点,使用快慢指针进行删除重复元素

解题思路
快慢指针法。慢指针用来指向第一个(可能)遇到重复元素的位置处,而快指针寻找新元素,当快指针找到新元素,把新元素赋值给慢指针处做替换

Python3

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow_p = 1 # 数组若只有一个元素,则下标为0, 这样的数组中不会有重复
        for fast_p in range(1, len(nums), 1):
            if(nums[fast_p-1] != nums[fast_p]): # 快指针找到新元素,利用了任意i <= k <= j,nums[i] = nums[k] = nums[j]特性
                nums[slow_p] = nums[fast_p]
                slow_p += 1 # slow_p的增加是有条件的,要找到不相同的元素
        return slow_p

7. 买卖股票的最佳时机

题目链接买卖股票的最佳时机 – leetcode
题目描述
给定个数prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票,并选择未来的某一个不同的日子 卖出该股票设计一个算法计算你所能获取最大利润。返回你可以从这笔交易获取最大利润。如果你不能获取任何利润,返回 0 。
题目归纳:
先买后卖是常规操作,即做多。而先将股票卖出,后买入同样数量股票归还于他人,即做空这道题目不考虑做空考虑做空简单,把股票价格数组反转一下,还是先买后卖,就变成“做空”了这道题目等价于:给定数组,求数组中的两个数字间的最大差值。在实际中,相当于你只能各一次,减法只有一次,解这道题目,代入感不要太强,不要真的以为自己在买股票然后傻乎乎的去一个个的从左到右遍历,并且假设自己知道明天的股票价格,你是开了上帝之眼,知道整个股票价格数组的!用爬山类比:相当于记录从山脚到山顶的高程

解题思路
(1) 记录当前遇到min_price 即最低股价
(2) 记录 当前收益 = (当前股价 – 最低股价) ,与最大收益做比较更新最大收益
(3) 返回最大收益

Python3

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        inf = int(1e9) # 10^9
        min_price = inf
        max_profit = 0 # 第一天收益为0
        for price in prices:
            max_profit = max(price - min_price, max_profit) # 这样可以求得全局的最大收益
            min_price = min(price, min_price)
        return max_profit

8. 买卖股票的最佳时机Ⅱ

题目链接买卖股票的最佳时机Ⅱ – leetcode
题目描述
给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。返回 你能获得的 最大 利润 。
题目归纳:
与上一题的区别:同一天也可以买和卖,并且可以在多天多次买卖,其它条件前面那道题一致,只能有一只股票。也等价于:给定数组,可以多次差值(只能后减前),求数组中的最大 差值总和。用爬山类比:相当于记录从山脚到山顶的高程差之和,即所有上坡高度之和。

解题思路:
(1) 若明天股价大于今天股价,可以卖出。
(2) 只要有股价上涨,就可以卖出。

Python3

贪心
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 贪心解法
        sum_profit = 0
        n = len(prices)
        print(prices[-1]) # 注意python中这样写是没有数组越界的警告的,而是数组的第size-1个元素
        for i in range(1, n): # (1,n)而不是(0,n)
            sum_profit += max(0, prices[i] - prices[i-1]) # 只要有股价上涨,就可以卖出。
        return sum_profit
动态规划

这题的动态规划算法必须学会,这是解下一步的股票题的基础。



11. H 指数

题目描述
给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论文引用次数计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义:h 代表“高引用次数” ,一名科研人员的 h 指数是指,他(她)至少发表h论文,并且每篇论文至少被引用h 次。如果该 h 有多种可能的值,h 指数是最大的那个。
题目归纳:
H-index Wiki,我想,h 指数的基本思想是:论文发的越多,不一定代表水平越高,而是发的越多,也要引用的越多才行,引用数认为是发表数认为是,即有质有量 h 指数才高,可以看出原始的 h 指数有个缺点,如果论文发的少引用的多,h 指数也不会很高,也就是有质无量的 h 指数低,无质无量无质有量自然就更低了,这里把两个量的量纲统一了,就得到了下面的图。
H-index from wiki

解题思路:
(1) 排序法。将数组citations从高到底排列,h不断增加,直到引用数 h 无法增大,则返回 h 。对应上图,就是寻找到虚线数据分布的“分界点”,在papers(citations)坐标轴上的值。
(2) 计数排序法。

Python3

排序

时间复杂度

O

(

n

l

o

g

2

n

)

O(nlog_{2}{n})

O(nlog2n)

n

n

n为数组citations长度
空间复杂度

O

(

l

o

g

2

n

)

O(log_{2}{n})

O(log2n)

n

n

n为数组citations长度

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        sorted_citation = sorted(citations, reverse = True)
        # python里可以用分号在一行分割语句曾经python为了阅读简便性,抛弃了分号,现在又拿回来了,会不会有一天,这些语言来一个大一统,赋值号居然还有:=,=这两种写法,想出:=的人我很好奇他个人的精神状态
        h = 0; i = 0; n = len(citations)
        while i < n and sorted_citation[i] > h:
            h += 1
            i += 1
        return h
计数排序

【排序算法】计数排序 – bilibili
计数排序是一种非比较排序,比较排序的复杂度下限是O(nlogn)已经得到过论文证明。

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        # 新建维护个数组citation_papers,来记录当前引用次数的论文有多少
        # 对于论文i引用次数citations[i]超过论文发表数len(citations)的情况,将其按总论文发表数len(citations)计算即可,这样排序的数的大小范围就可以降低至[0,n=len(citations)]
        # 从而计数排序的时间复杂度,就降低至O(n)。现实中,一个学者一辈子能发表的论文数量顶天了也就百来篇,再夸张点,一千篇,不需要考虑n是无穷增长的,这点大小对计数排序是恰到好处的,因为计数排序就适合范围不大的排序。
        n = len(citations); H_papers = 0 # H_papers: 符合H指数的论文数
        citation_papers = [0] * (n+1) # 生成计数排序数组,用到python的扩充操作,此数组下标为citation,数组内容为paper数量
        
        # 计算计数排序数组
        for c in citations:
            if c >= n:             # 引用次数超过论文发表数,引用次数按发表论文数计算
                citation_papers[n] += 1
            else:
                citation_papers[c] += 1

        # 倒序遍历
        for citation in range(n, -1, -1): # (-1, n] step = -1,实际上的下标范围即[0,n]
            H_papers += citation_papers[citation]
            if citation <= H_papers:
                return citation

        return 0
二分查找

原文地址:https://blog.csdn.net/weixin_44327736/article/details/134210625

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_44514.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除!

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注