精华内容
下载资源
问答
  • leetcode高频100题
    2021-08-23 15:52:49

    1 问题描述

    自定义一个栈结构,,实现入栈、出栈、找出栈顶、使用常数时间找出栈中数据的最小值功能。

    2 代码实现

    这一题还是比较简单的,如果是在python环境下,使用List表示栈,那栈的写入与弹出只需要用到.append.pop操作即可,而且时间复杂度均为1,但是,如果想要使用常数时间找到栈的最小值,那就需要用空间换时间,我们可以在栈写入与弹出时,存储对应时刻的最小值:

    写入阶段:

    非常好理解,我们只需要每次都比较写入的值与最小值的大小即可,最新写入的值小,那最小值就是它;

    弹出阶段:

    也很简单,如果弹出的值不是最小值,那最小值不变,如果弹出的值是最小值,该怎么办呢?

    我们可以存储一个最小值队列,对写入阶段进行一个修改即可,具体方法是,如果写入阶段后进的值比其前一个写入的最小值相等或更小,那就将这个值视为是当前栈的最小值,随着栈的写入与弹出,动态维护这个队列,那队列中的最后一个元素始终是其对应当前栈的最小值。

    class MinStack:
    
        def __init__(self):
            """
            initialize your data structure here.
            """
            self.ms = []
            self.msize = 0
            self.base = -1
            self.top_idx = -1
            self.min_ms = []
    
    
        def push(self, val: int) -> None:
            self.ms.append(val)
            self.top_idx += 1
            self.msize += 1
    
            if (self.top_idx == 0) or (self.min_ms[-1] >= val):
                self.min_ms.append(val)
    
    
        def pop(self) -> None:
            if self.msize > 0:
                if self.min_ms[-1] == self.ms[self.top_idx]:
                    del self.min_ms[-1]
    
                del self.ms[self.top_idx]
                self.top_idx -= 1
                self.msize -= 1
    
    
        def top(self) -> int:
            if self.top_idx >= 0:
                return self.ms[self.top_idx]
            else:
                print('The stack has no element.')
    
    
        def getMin(self) -> int:
            if self.msize > 0:
                return self.min_ms[-1]
                # return min(self.ms)
            else:
                print('The stack has no element.')
    
    
    # Your MinStack object will be instantiated and called as such:
    # obj = MinStack()
    # obj.push(val)
    # obj.pop()
    # param_3 = obj.top()
    # param_4 = obj.getMin()
    

    这里额外存储了栈的顶部、底部以及栈的尺寸索引,方便后续有其他需求时进行改造。

    时间复杂度均为 O ( 1 ) O(1) O(1),空间复杂度为 O ( n ) O(n) O(n).

    更多相关内容
  • 2020高频面试算法整理 leetcode ,18个大类,80+到常见算法。 1.热身|1)查找唯一数字|2)查找N/2数字|3)判断数字是否存在|4)合并二叉树|5)泡鸡蛋问题|2.互联网公司最常见的面试算法有哪些?|3.TOP INTERVIEW ...
  • Leetcode高频100题刷题记录之——两数求和 暴力破解与哈希求解个人实现,附官方题解代码。

    LeetCode高频100题刷题记录之——两数求和

    终于开始刷LeetCode了,还没有系统学习过数据结构,导致第一题做出来就很垃圾,只会使用暴力求解,还使用了巨多判断来试图简化计算过程,结果是计算量没有省不说,还严重增加了调试成本。

    但是毕竟刚开始,接受自己是个菜鸡的事实也不丢人嘿嘿,因此记录一下用python实现两数求和的过程,包括暴力破解和哈希表查找法,不得不说,哈希表在处理这种问题时真的很有优势,刚刚接触哈希表,后续再不断学习吧!

    1 暴力破解法

    1.1 思路

    做题的时候看到要求尽可能复杂度小于 O ( N 2 ) O(N^2) O(N2),但是暴力破解基本上不可能实现,只能尽可能想办法降低到侠义的 O ( N 2 ) O(N^2) O(N2)以下,其实算法复杂度从大 O O O计算法来说还是 O ( N 2 ) O(N^2) O(N2)

    输入:nums: List[int], target: int

    输出:result: List[int],预定义result为None

    具体思路是:

    Step1:判断target是正还是非正;

    Step2:构建六个空list,分别存储nums中等于0,等于target,等于target/2,以及根据正负号判断其在不同区间内的nums的索引;

    Step3:判断target是否为0,若是,进一步判断nums中为0的数是否有两个,若有,则输出前两个作为result,结束程序;若无,转Step4

    Step4:判断是否存在nums中有为0与target的数,若存在,输出这两种情况各自的第一个数的索引作为result,结束程序;若无,转Step5

    Step5:判断nums中是否存在有两个以上数值为target/2的数,若存在,则输出符合条件的前两个数的索引为result,结束程序;若不存在,则转Step6

    Step6:判断nums中处于①(0, target/2)与②(target/2, target)(target为正)或处于①(target, target/2)与②(target/2, 0)(target为负)的数的存在情况,若①②都存在,遍历两组的数据,若能找到①+②=target的数,取出对应索引,作为result的值,结束程序;若①或②不存在,或者不满足①+②=target,转Step7

    Step7:判断nums中处于①(target, +∞)与②(-∞, 0)(target为正)或处于①(-∞, target)与②(0, +∞)(target为负)的数的存在情况,若①②都存在,遍历两组的数据,若能找到①+②=target的数,取出对应索引,作为result的值,若①或②不存在,或者不满足①+②=target,报错,结束程序。

    1.2 Python代码

    代码可在Leetcode中直接运行。

    class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            result = None
            neg_idx = []    # 存储nums中数值小于0(target为正)或小于target(target为负)的数
            pos_idx = []    # 存储nums中大于target(target为正)或大于0(target为负)的数
    
            small_idx = []  # 储存nums中大于0但小于target/2的数
            large_idx = []  # 存储nums中大于target/2但小于target的数
    
            zero_idx = []   # 存储nums中为0的数
            half_idx = []   # 存储nums中为target/2的数
            equal_idx = []  # 存储nums中为target的数
    
            if target > 0:          # target为正的情况
                for i in range(len(nums)):
                    if nums[i] == 0:
                        zero_idx.append(i)
                    elif nums[i] == target:
                        equal_idx.append(i)
                    elif nums[i] == target/2:
                        half_idx.append(i)
                    elif nums[i] < 0:
                        neg_idx.append(i)
                    elif nums[i] < target/2:
                        small_idx.append(i)
                    elif nums[i] < target:
                        large_idx.append(i)
                    else:
                        pos_idx.append(i)
            
            else:  # target <=0的情况
                for j in range(len(nums)):
                    if nums[j] == 0:
                        zero_idx.append(j)
                    elif nums[j] == target:
                        equal_idx.append(j)
                    elif nums[j] == target/2:
                        half_idx.append(j)
                    elif nums[j] > 0:
                        pos_idx.append(j)
                    elif nums[j] > target/2:
                        large_idx.append(j)
                    elif nums[j] > target:
                        small_idx.append(j)
                    else:
                        neg_idx.append(j)
    
            if (target == 0) & (len(zero_idx) >= 2):
                result = [zero_idx[0], zero_idx[1]]
                return result
            elif (len(zero_idx) > 0) & (len(equal_idx) > 0):  # 判断是不是有简单结果1存在
                result = [zero_idx[0], equal_idx[0]]
                return result
            elif len(half_idx) >= 2:
                result = [half_idx[0], half_idx[1]]
                return result
            elif (len(neg_idx) > 0) & (len(pos_idx) > 0):
    
                for sub_i in neg_idx:
                    if result is not None:
                        break
    
                    for sub_j in pos_idx:
                        if nums[sub_i] + nums[sub_j] == target:
                            result = [sub_i, sub_j]
                            break
                if result is not None:
                    return result
            if result is None:
                if (len(small_idx) > 0) & (len(large_idx) > 0):
                    for sub_i in small_idx:
                        if result is not None:
                            break
    
                        for sub_j in large_idx:
                            if nums[sub_i] + nums[sub_j] == target:
                                result = [sub_i, sub_j]
                                break
                    if result is not None:
                        return result
                    else:
                        raise ValueError("数组中没有和为target的两个数!")
                else:
                    raise ValueError("数组中没有和为target的两个数!")
    

    1.3 算法评价

    判断过程过多,容易出错,过于冗余,虽然理论上可以减少一点计算量,但计算值过多时性能优势不明显。时间复杂度为 O ( N 2 ) O(N^2) O(N2)

    2 哈希表实现

    2.1 思路分析

    计算target与nums的差,再以差为key创建字典,判断时进行索引,方法较为简单,不做算法说明了。

    2.2 代码

    class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            result = None
    
            len_nums = range(len(nums))
            keys = [target - nums[i] for i in len_nums]  # 散列函数构造,以target与nums中每个数的差作为key
            nums_dict = dict(zip(keys, len_nums))  # 根据key与值建立对应的哈希表,在python中是字典
            
            for i in len_nums:
                if nums[i] in nums_dict.keys():
                    if i != nums_dict[nums[i]]:
                        result = [nums_dict[nums[i]], i]
                        return result
                        break
            if result is None:
                raise ValueError("nums中没有符合条件的两个数!")
    

    对比官方题解,发现我的代码真的太繁琐了,官方的代码非常整洁,真的强。

    下面是官方题解,思路值得学习。

    class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            hashtable = dict()
            for i, num in enumerate(nums):
                if target - num in hashtable:
                    return [hashtable[target - num], i]
                hashtable[nums[i]] = i
            return []
        
    #  作者:LeetCode-Solution
    #  链接:https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
    #  来源:力扣(LeetCode)
    #  著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    
    展开全文
  • LeetCode高频100题刷题记录之——电话号码的字母组合

    LeetCode高频100题刷题记录之——电话号码的字母组合

    解法1

    根据ASCII码表进行查表,不自己计算字符,然后每增加一个字符,扩充返回列表的结果数目为原来的l(新数字包含的字母数目)倍:

    class Solution:
        def letterCombinations(self, digits: str) -> List[str]:
            result = []
            if len(digits) > 0:
                for s in digits:
                    a = len(result)
                    if a == 0:
                        result = self.getcode(s)
                    else:
                        newcode = self.getcode(s)
                        result = result*len(newcode)
                        for i in range(len(result)):
                            result[i] = result[i] + newcode[i//a]
            return result
    
    
        def getcode(self, s: str) -> List[str]:  # 查表
            if ord(s) <= 55:
                baseord = ord('2')+47+(ord(s)-ord('2'))*3
                if s == '7':
                    lennum = 4
                else:
                    lennum = 3
            elif s == '8':
                baseord = ord('8') + 60
                lennum = 3
            elif s == '9':
                baseord = ord('9') + 62
                lennum = 4
            return [chr(baseord + i) for i in range(lennum)]
    

    解法2

    用递归回溯的方法,将所有可能存成一个哈希表,对所有可能的组合进行递归遍历:(参考自leetcode中相关题解,非原创!!!)

    class Solution:
        def letterCombinations(self, digits: str) -> List[str]:
            result = []
            if len(digits) > 0:
                cond = {
                    "2": "abc" ,
                    "3": "def" ,
                    "4": "ghi" ,
                    "5": "jkl" ,
                    "6": "mno" ,
                    "7": "pqrs",
                    "8": "tuv" ,
                    "9": "wxyz",
                }
                def backcheck(now, nextdigits):
                    if len(nextdigits) == 0:
                        result.append(now)
                    else:
                        for code in cond[nextdigits[0]]:
                            backcheck(now + code, nextdigits[1:])
                backcheck('', digits)
            return result
    
    展开全文
  • LeetCode高频100题刷题记录之——盛水最多的容器 python实现

    LeetCode高频100题刷题记录之——盛水最多的容器

    1 问题描述

    假设在 x x x轴上有若干条直线,高度为 h h h,因此,我们可以拥有若干个数据点 ( x i , h i ) (x_i,h_i) (xi,hi),以任意两条直线作为一个水桶的两边,二者之间的垂直距离( x x x轴的差)为水桶底面的长度,则水桶的深度由最短边长决定,找到可以使水桶容量最大的两条直线,算出二者围成的最大面积。

    图像来自leetcode官方题解(链接:https://leetcode-cn.com/problems/container-with-most-water/)

    2 代码实现

    太久没刷题了,基础知识都忘得差不多了,导致完全没有想到使用双指针来解决,如果能把双指针思想记在心里,那很容易就能找到答案。

    具体来说,这些直线是按照顺序排列的,他们的 x x x轴坐标有明显的顺序之差,我们可以定义左右指针,分别指向直线数据list的两端,这时,我们可以计算得到一个初始面积,这个面积是桶的底面最长时候的结果,由于每两根直线之间的距离都是1,接下来,我们只需要不断缩短底面长度,就可以知道在底面长度不同时的最大面积是多少,最终就可以获取所有直线能够围成的最大面积的长度。

    那么如何知道不同底面长度时最大的桶高呢?非常简单,每次缩短底面长度时判断一下两端直线的长度,假如直线较短,那从这边缩短肯定比从右边缩短能够获得更长的底面长度,因此只需要用双指针不断往中间靠拢,留下来的每一阶段的面积一定是当前桶底长度中最大的。

    class Solution:
        def maxArea(self, height: List[int]) -> int:
    
            l     = len(height)
            left  = 0
            right = l-1
            area  = min(height[left], height[right]) * (right-left)
            while (left != right):
                if height[left] < height[right]:
                    left += 1
                else:
                    right -= 1
                
                area = max(area, min(height[left], height[right]) * (right-left))
            
            return area
    

    时间复杂度 O ( n ) O(n) O(n),只需要遍历所有桶高一次,空间复杂度 O ( 1 ) O(1) O(1)

    展开全文
  • LeetCode高频100题刷题记录之——汉明距离 Brian Kernighan 算法与移位计算法实现
  • LeetCode高频100题刷题记录之——两数相加 中等难度
  • LeetCode高频100题刷题记录之——买卖股票的最佳时机 时间复杂度为O(n)
  • leetcode高频面试内部结对编程资源 下面是我可以召集的进行结对编程会议的过程的记录。 :) 结对编程会话前的电子邮件 模板化电子邮件在结对编程会话发生的当天发送(周二/周四@下午 1 点,周日@上午 10 点) 模板...
  • LeetCode高频100题刷题记录之——二叉树直径
  • LeetCode高频100题刷题记录之——两个升序链表合并与排序
  • LeetCode高频100题刷题记录之——比特位计数 动态规划方法求解
  • ------------------------------- #9 (338) 比特位计数 -------------------------------------------------------------------------------- #10 (347) 前K个高频元素 -----------------------------------------...
  • 原文:https://blog.csdn.net/weixin_38896998/article/details/88810177 ,转化为pdf和png格式
  • leetcode高频面试黑手党 这本书的重点是记录黑手党的每周讨论。 我们注重谈论人们感兴趣的面试问题和技术话题。编码问题通常来自面试中的高频算法。 如果您有兴趣了解更多关于任何成员的信息,请单击 。
  • LeetCode Hot100 每日刷题笔记
  • 力扣(LeetCode) 相比其他编程平台有着很多优势: **各大知名公司面试真题:**对于求职者在这上面训练更具有针对性,目前国内一些公司面试时直接从在这上面出题。 **大中小企业都在使用:**常常会直接或者间接...
  • LeetCode Hot100 大厂习题热度前10解法。 每日更新~
  • Leetcode 高频考题整理

    2021-03-06 18:58:33
    All Problems )【leetcode】高频题目整理_所有题目汇总篇( High Frequency Problems, All Problems )_Liber-coder的博客-CSDN博客_leetcode高频题 目录 1,经典模拟过程 2,C语言字符串 3,链表 4,树 5,各大排序 ...
  • leetcode Top100题

    2022-05-17 07:30:04
    leetcode Top100 整理,用于热点快速翻阅。
  • LeetCode题100

    千次阅读 2022-02-11 16:43:32
    通往【LeetCode - 两数之和】的任意门 解法一:暴力解 采用两层for循环,第一次层循环选取第一个数,第二次循环选取第二个数,第二层循环找到符合的数则直接返回结果。 时间复杂度:O(n^2) 空间复杂度:O(1) ...
  • Leetcode编程题:高频题100

    千次阅读 2019-08-30 17:08:18
    前 K 个高频元素 中等 394* 字符串解码 中等 399* 除法求值 中等 406* 根据身高重建队列 中等 416* 分割等和子集 中等 437* 路径总和 III 简单 ...
  • #1 (2) 两数相加 -------------------------------------------------------------------------------- #2(3) 无重复字符的最长字串 ---------------------------------------------------------------------...
  • Leetcode高频100题刷题记录之——有效的括号 python代码实现,附思路解析。
  • LeetCode 100题

    2022-02-09 10:21:18
  • LeetCode高频题目(100)汇总-Java实现

    万次阅读 2017-08-23 19:03:06
    LeetCode高频题目(100)汇总-Java实现目录第01-50【Leetcode-easy-1】 Two Sum【Leetcode-easy-2】 Add Two Numbers【Leetcode-easy-3】 Longest Substring Without Repeating Characters【Leetcode-easy-5】 ...
  • LeetCode高频100题刷题记录之——反转链表 迭代法与递归法的python实现
  • LeetCode高频100题刷题记录之——爬楼梯 附字节笔试施加额外条件的实现推导。
  • LeetCode高频100题刷题记录之——三数之和
  • LeetCode高频100题刷题记录之——消失的数 哈希表实现法。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,093
精华内容 2,837
关键字:

leetcode高频100题

友情链接: PCA+数据.zip