一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
Visa Tracker
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 6636|回复: 155
收起左侧

[Leetcode] LC Python 刷题笔记 有志者事竟成

    [复制链接] |只看干货 |leetcode, 刷题
我的人缘0

升级   43.86%


分享帖子到朋友圈
李浩泉 | 显示全部楼层 |阅读模式
本楼: 👍   94% (35)
 
 
5% (2)   👎
全局: 👍   93% (1224)
 
 
6% (89)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
本帖最后由 李浩泉 于 2020-7-30 23:38 编辑

年过30,饿不死,吃不饱,对于无背景无天赋的普通大陆华裔男性一代移民来说,如果想年薪30万+美金,读MBA可能性不大还费钱,抱领导粗腿可能性也不大,领导自己都没挣30万呢。

唯一的希望就是刷题进大厂,其他的真的看不到什么可行性。

你们泡妞,我刷题
你们电游,我刷题
你们钓鱼,我刷题
你们游行,我刷题
你们看片,我刷题

1800年代,华工在黑暗的矿坑里淘金
1900年代,华工在黑暗的厨房里刷碗
2000年代,华工在黑暗的小屋里做题

不怨天,不怨地,只怪我爸不努力,从我做起,扭转家庭的惯性下滑,徐徐图之,愚公移山。

从12万年薪到30万年薪,中间只隔着1000+道LC算法题。干TM的。

评分

参与人数 23大米 +33 收起 理由
bearcat99 + 1 赞一个
冲动是魔鬼 + 2 给你点个赞!
mcyzzq1989 + 1 赞一个
ttbx + 1 赞一个
咿呀咿呀哟 + 1 赞一个
lilianzcc + 1 赞一个
xwang699 + 1 给你点个赞!
jesshxh + 1 赞一个
sch75971 + 1 给你点个赞!
sevengrain + 1 赞一个

查看全部评分


上一篇:ghc 是什么? 真的有这么火吗?
下一篇:UDP 远程通信 (我的PC 怎么call 你的PC)
我的人缘0

升级   47.29%

paopaoka33251 2020-8-6 13:14:45 | 显示全部楼层
本楼: 👍   41% (5)
 
 
58% (7)   👎
全局: 👍   41% (5)
 
 
58% (7)    👎
天真         
回复

使用道具 举报

我的人缘0

升级   43.86%

 楼主| 李浩泉 2020-7-31 00:19:03 | 显示全部楼层
本楼: 👍   100% (5)
 
 
0% (0)   👎
全局: 👍   93% (1224)
 
 
6% (89)    👎
本帖最后由 李浩泉 于 2020-7-31 00:22 编辑
backtouzhaogong 发表于 2020-7-31 00:10
刷题有点动力挺好的,pregame pump talk细节不用深究,能激发斗志就行。
楼主能透露一下此番刷题的频率和 ...

没有频率,也没有顺序,就是平推,从#1 Two Sum开始,一直到最后的#1533        
Find the Index of the Large Integer。一边WFH,一边等待着机会。目前的工作已经干了6年多,闭着眼睛都知道怎么干。商科背景没学过CS,毕业就干SQL,现在是从SQL转算法coding。我记得一次面试的时候,面试官中国老哥问我会编程吗?我说会SQL,他说SQL不算编程,只是复杂一点的EXCEL。哈哈哈。莫欺少年穷,等着。

评分

参与人数 3大米 +3 收起 理由
咿呀咿呀哟 + 1 赞一个
yanliangwu + 1 赞一个
zea7ot + 1 赞一个

查看全部评分

回复

使用道具 举报

我的人缘0

升级   52%

coronaking2020 2020-7-31 05:13:37 | 显示全部楼层
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   93% (1660)
 
 
6% (112)    👎
欣赏你“不要怂就是干”的态度,爱你

评分

参与人数 1大米 +1 收起 理由
李浩泉 + 1 加油一起干

查看全部评分

回复

使用道具 举报

我的人缘0

升级   9%

backtouzhaogong 2020-7-31 00:10:25 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   99% (545)
 
 
0% (1)    👎
刷题有点动力挺好的,pregame pump talk细节不用深究,能激发斗志就行。
楼主能透露一下此番刷题的频率和顺序吗?
回复

使用道具 举报

我的人缘0

升级   43.86%

 楼主| 李浩泉 2020-7-31 00:15:16 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (1224)
 
 
6% (89)    👎
本帖最后由 李浩泉 于 2020-7-31 00:59 编辑

算法第一计:Brute Force 暴力搜索 - 字典法

简单直接,直接For Loop循环,构筑临时的dic{}存储过程中的变量。

Time complexity 时间复杂度 : Because, for each element, I try to find its complement by looping through the rest of array which takes O(n) time. Therefore, the time complexity is O(n^2).

Space complexity 空间复杂度:O(1)

# 1 Two Sum

直接上循环,把每次的值装入临时创建的字典,直到找到答案,最后返回。

[Python] 纯文本查看 复制代码
'''
Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
'''

nums = [2, 7, 11, 15]
target = 9

def twoSum(nums, target):
    dic = {}
    for i, num in enumerate(nums):
        n = target - num
        if n not in dic:
            dic[num] = i
        else:
            return [dic[n], i]

print(twoSum(nums,target))






回复

使用道具 举报

我的人缘0

升级   78.5%

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   99% (356)
 
 
0% (1)    👎
加油加油💪
回复

使用道具 举报

我的人缘0

升级   0.57%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (577)
 
 
0% (1)    👎
李浩泉 发表于 2020-07-30 09:19:03
没有频率,也没有顺序,就是平推,从#1 Two Sum开始,一直到最后的#1533        
Find the Index of the Large Integer。一边WFH,一边等待着机会
我最近一直在刷SQL😂😂
回复

使用道具 举报

我的人缘0

升级   43.86%

 楼主| 李浩泉 2020-7-31 02:39:55 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (1224)
 
 
6% (89)    👎
本帖最后由 李浩泉 于 2020-7-31 03:18 编辑

算法第二计:Two Pointers 双指针 (包括:左右指针法,快慢指针法 - 弗洛伊德的乌龟(slow 指针)和兔子(fast 指针))

左右指针法:

# 167 Two Sum II - Input array is sorted
# 1099 Two Sum Less Than K

Complexity analysis

Time complexity : Each of the n elements is visited at most once, thus the time complexity is O(n).

Space complexity : I only use two indexes, the space complexity is O(1).

I can apply brute force directly to get O(n^2) time and O(1) space. But I do not make use of the property where the input array is sorted. 如果可以sorting的话,就可以考虑使用左右双指针来节约时间。这类题如果不用双指针,直接上两个嵌套的loop循环,面试一定会被challange。当使用左右指针法的时候,记得用while loop,不用再用for loop了。

[Python] 纯文本查看 复制代码
'''
Given an array A of integers and integer K, return the maximum S such that there exists i < j with A[i] + A[j] = S and S < K. If no i, j exist satisfying this equation, return -1.

 

Example 1:

Input: A = [34,23,1,24,75,33,54,8], K = 60
Output: 58
Explanation: 
We can use 34 and 24 to sum 58 which is less than 60.
'''

A = [34,23,1,24,75,33,54,8]
K = 60

def twoSumLessThanK(A, K):
    n = -1
    A.sort()
    left, right = 0, len(A) -1
    while left < right:
        if A[left] + A[right] < K:
            n = max(n, A[left] + A[right])
            left += 1
        else:
            right -= 1
    return n

print(twoSumLessThanK(A, K))


回复

使用道具 举报

我的人缘0

升级   43.86%

 楼主| 李浩泉 2020-7-31 03:18:32 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (1224)
 
 
6% (89)    👎
本帖最后由 李浩泉 于 2020-7-31 04:01 编辑

左右指针法:

# 167 Two Sum II - Input array is sorted

[Python] 纯文本查看 复制代码
'''
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
'''

numbers = [2,7,11,15]
target = 9

def twoSum(numbers,target):
    left = 0
    right = len(numbers) - 1
    while left < right:
        if numbers[left] + numbers[right] == target:
            return [left+1,right+1]
        elif numbers[left] + numbers[right] < target:
            left += 1
        elif numbers[left] + numbers[right] > target:
            right -= 1
                
print(twoSum(numbers,target))

回复

使用道具 举报

我的人缘0

升级   65.57%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (1315)
 
 
2% (35)    👎
lz有群吗 ds转码+1
回复

使用道具 举报

我的人缘0

升级   43.86%

 楼主| 李浩泉 2020-7-31 03:58:46 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (1224)
 
 
6% (89)    👎
本帖最后由 李浩泉 于 2020-7-31 04:36 编辑

快慢指针法:

# 141. Linked List Cycle

这道题是有典故的,称为:弗洛伊德的乌龟(slow 指针)和兔子(fast 指针),和薛定谔的猫差不多一样有名。1960年代提出来的,距今差不多已经60年了。罗伯特·W·弗洛伊德,美国计算机科学家,1978年图灵奖得主,14岁高中毕业,芝加哥大学少年班,17岁大学毕业,26岁卡耐基梅隆大学计算机副教授,32岁斯坦福正教授,唯一的只有本科学历的教授!

Complexity analysis

Time complexity : Let me denote n as the total number of nodes in the linked list. To analyze its time complexity, I consider the following two cases separately.

  • List has no cycle: The fast pointer reaches the end first and the run time depends on the list's length, which is O(n).
  • List has a cycle: I break down the movement of the slow pointer into two steps, the non-cyclic part and the cyclic part, the worst case time complexity is O(N+K), which is O(n).


Space complexity : O(1). I only use two nodes (slow and fast) so the space complexity is O(1).

[Python] 纯文本查看 复制代码
'''

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

 

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

'''

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = head
        fast = head
        while fast and fast.next :
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                return True
        return False


当然如果不用双指针,这道题也有其解法,比如:

[Python] 纯文本查看 复制代码
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        while head:
            if head.val == 'I LOVE MEIZI':
                return True
            else:
                head.val = 'I LOVE MEIZI'
            head = head.next
        return False


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表