leetcode闯关:①–⑤

  • Post author:
  • Post category:其他



leetcode官网:

官方网站

.

*



1

两数之和

.



① 题目

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

示例:

给定 nums = [2, 7, 11, 15], target = 9 
因为 nums[0] + nums[1] = 2 + 7 = 9 
所以返回 [0, 1]



② 思考

从一个列表里面查找两个有特定关系的数,也就是知道了一个数,求另一个对应数的位置,如果不存在对应的数就下一位。

1>用一般的遍历可以做,而且可以找出来全部的,简单,但是时间复杂度为O(n^2),会超时。

2>联想到哈希表。哈希表中一个key值对应表中一个地址,且哈希表里面的数不重复,在python语言中,就类似于一个字典

dict={}

,一个key对应一个value,若key不在表中,就添加新的元素,若key在表中,可直接查询到value。在这个实例中,key就是对应的另一个数,value就是这个数的地址。

时间复杂度:

科普

.

哈希表:

哈希表

.



③ 源码

class Solution(object):    
	def twoSum(self, nums, target):
		another = {}        
		for i, n in enumerate(nums):            
			another_n = target - n            
			if another_n in another:                
				return(another[another_n], i)            
			another[n] = i        
		return None

凑巧,最近在看SECOND目标识别的源码,其中在生成体素数据时,就用到了哈希表。



2

两数相加

.



① 题目


两数相加

.粘贴出来太麻烦了



② 思考

链表还真是第一次接触,python里面原来真的没有这个东西。先了解一下什么是链表

链表定义

.

在程序中,一般都是通过一个指针访问地址,才能得到地址存放的数值。一个链表每个节点(node)上,包含两个域,第一域存放了一个数值,第二域存放了指针下一次要指向的地址,也就是说要访问一个链表的话,只能按顺序进行访问,不能打乱顺序。在c语言中,可以使用一个

typedef struct XXX

来定义,就像一个套娃,一个数套着一个数,python中也是用套娃实现的。



③ 答案

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        re = ListNode(0)                # 新建ListNode
        r = re                          # 考虑为什么要把re给到r,因为在循环过程中,r永远指向re的最后一位,re是总的
        carry = 0                       # 进位
        while l1 or l2:                 # x,y中只要有一个还有值,就一直计算
            x = l1.val if l1 else 0     # 没有值就给0
            y = l2.val if l2 else 0     # 没有值就给0
            s = carry+x+y               # 这一位的和
            carry = s//10               # 进位
            r.next = ListNode(s % 10)   # 创建一个新的ListNode,专门存放余位
            r = r.next                  # 套娃,r指向了原本r里面的一层,就是代表上一层已经处理好了,指向这一位的next了
            if l1 != None:              # l1还没结束,下一位,结束了的话就留在原地
                l1 = l1.next
            if l2 != None:              # l2还没结束。下一位,结束了的话就留在原地
                l2 = l2.next
        if carry > 0:                   # 最后一位还有进位,那就多加一位
            r.next = ListNode(1)
        return re.next                  # re的第一位是0,所以不要第一位了,只要next里的部分

在pycharm进行调试时,需要自己对

ListNode

进行定义,这里参考了

这里

.



3

无重复字符的最长子串

.



① 思考

这种题目的共性:从一整串数据里面拿出有一定规律的一个字串,都可以用滑动窗口法。

滑动窗口法:左边一个指针,右边一个指针,读取两个指针中间的数据,需要满足一定的规律,就找到了满足要求的字串。



② 源码

class Solution1:
    def lengthOfLongestSubstring(self, s):
        # 哈希集合,记录每个字符是否出现过
        occ = set()
        n = len(s)
        # 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指针向右移动一格,移除一个字符,一直右移到删掉了s[rk + 1]对应的字符,就可以开始右边界右移了
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                # 不断地移动右指针
                occ.add(s[rk + 1])
                rk += 1
            # 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1)
        return ans

class Solution2(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        st = {}     # 这个字典key是字符,value是字符截止到j最后出现的位置
        i, ans = 0, 0
        for j in range(len(s)):
            if s[j] in st:
                i = max(st[s[j]], i)
            ans = max(ans, j - i + 1)
            st[s[j]] = j + 1
        return ans;

class Solution3:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        last_pos = {}
        left_pos = -1
        ans = 0
        if len(s) == 0:
            return 0
        for i in range(len(s)):
            if s[i] in last_pos:
                left_pos = max(left_pos, last_pos[s[i]])
                last_pos[s[i]] = i
            else:
                last_pos[s[i]] = i
            ans = max(ans, i - left_pos)
        return ans

第一种方法,滑动窗口,用哈希表,一旦发现窗口里面有重复就从左指针开始检测重复的位置,然后移动左指针直到没有重复,记录长度。

第二种方法,使用了一个哈希表,或者说字典,记录了重复内容上一次出现的位置,直接左指针移到这个位置,节约了时间,但增加了内存。

第三种方法,自己写的,和第二种一样。



4

寻找两个正序数组的中位数

.



① 思考

中位数指的是一个数组从小到大排列后,在中间位置的数,既第(m+n)/2个数,同时题目要求,时间复杂度要是O(logn),如果将两个数组合并再找中位数,时间复杂度不符合要求,存在log,应该考虑到使用二分法查找。

二分法:每次取一半直到这个一半的数为1,说明下次再取就可以取到要取的数了。如要求8个数的中位数。先取2个小的,再取1个,就取走3个了,接下来的两个数取平均,就是中位数。



② 源码

# 首先看题目要求,时间复杂度要求为log(m+n),则联想到使用二分法,使用一般遍历方法时时间复杂度为m+n
# 但是在两个数列中,二分法有变形
# 求中值点,可以方便的联想到求中间位置的数,也就是求target=(m+n)/2,或者target=(m+n)/2+1这两个位置上的数
# 开始二分,l1和l2分别拿出第k/2个数,不够的话,用min(target // 2, len(nums1)),拿出直到最后一位数,比较拿出来的数大小
# 小的那一个数列的前这么多位肯定都是属于target位置之前的,去掉,同时target也减小这么多位,因为拿出去了一部分,剩下的再拿出去的话,就要少拿这么多个
# 直到把一个数列拿空了,或者target = 1,就是下一次拿的数中的某个数了
class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        def findTargetElement(nums1, nums2, target):
            while True:
                if len(nums1) == 0:
                    return nums2[target - 1]
                if len(nums2) == 0:
                    return nums1[target - 1]
                if target == 1:
                    return min(nums2[0], nums1[0])
                pos1 = min(target // 2, len(nums1)) - 1
                pos2 = min(target // 2, len(nums2)) - 1
                if nums1[pos1] >= nums2[pos2]:
                    nums2 = nums2[pos2 + 1:]
                    target -= pos2 + 1
                else:
                    nums1 = nums1[pos1 + 1:]
                    target -= pos1 + 1

        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        len_all = len(nums1) + len(nums2)
        left = (len_all + 1) // 2
        right = (len_all + 2) // 2
        return (findTargetElement(nums1, nums2, left) + findTargetElement(nums1, nums2, right)) / 2



5

最长回文子串

.



① 思考

1>使用滑动窗口法:每个窗口判断第一个点和最后一个点是否相等,再第二个与倒数第二个,依次判断是否对称回文,时间复杂度较高

2>遍历中心点,求臂长: 以每一个点为中心点,求该点的对称臂长,返回最大臂长

3>动态规划:若最长回文子串满足要求,则该字串的每一个字串都是一个回文子串,这样就符合动态规划的思想,递推或者分治。



② 源码

# 由于回文子串是一个嵌套着一个,里面的是回文子串,外面的才哟可能,因此考虑使用动态规划
# 东该规划就是递推或者分治,使用递推或者递归都可以,

class Solution(object):
    # 递归方法,反复调用地思想,从长到短
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        import numpy as np
        n = len(s)
        dp = - np.ones((n, n))
        if n == 0:
            return ""
        if n == 1:
            return s

        def is_true(lens, pos, s, dp):
            if lens == 1:
                dp[pos, pos + lens - 1] = 1
            if lens == 2:
                if s[pos] == s[pos + lens - 1]:
                    dp[pos, pos + lens - 1] = 1
            if lens > 2:
                if (is_true(lens -2, pos + 1, s, dp) == 1 and s[pos] == s[pos + lens - 1]):
                    dp[pos, pos + lens - 1] = 1
            return dp[pos, pos + lens - 1]

        for lens in range(n, 0, -1):
            for pos in range(n - lens + 1):
                if is_true(lens, pos, s, dp) == 1:
                    return s[pos:pos + lens]

        # # 递推方法,从短到长,遍历全部
        # print(dp)
        # for lens in range (n, 0, -1):
        #     for pos in range(n - lens + 1):
        #         if dp[pos, pos+lens-1] == 1:
        #             return s[pos:pos+lens]

    # def longestPalindrome(self, s: str) -> str:
    #     n = len(s)
    #     dp = [[False] * n for _ in range(n)]
    #     ans = ""
    #     # 枚举子串的长度 l+1
    #     for l in range(n):
    #         # 枚举子串的起始位置 i,这样可以通过 j=i+l 得到子串的结束位置
    #         for i in range(n):
    #             j = i + l
    #             if j >= len(s):
    #                 break
    #             if l == 0:
    #                 dp[i][j] = True
    #             elif l == 1:
    #                 dp[i][j] = (s[i] == s[j])
    #             else:
    #                 dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
    #             if dp[i][j] and l + 1 > len(ans):
    #                 ans = s[i:j+1]
    #     return ans

实验结果发现:递归的时间比递推的时间要长,但是两者都是可行的,leetcode上递归会超时。

参考:以上的题目均来自于leetcode官网

官网

.



版权声明:本文为themasterbi原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。