本文最后更新于:3 years ago

两数之和

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum

暴力解法

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(len(nums)):
                if (j==i):
                    break
                else:
                    if  target - nums[i] == nums[j]:
                        return [i,j]

时间复杂度O(n)解法

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {} #key:num value:index
        for index,num in enumerate(nums): 
            another_num = target - nums[index]
            if another_num in hashmap:
                return [hashmap[another_num],index]
            hashmap[num] = index
        return None

两数相加

题目:给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/add-two-numbers

我的解法

首先将l1l2字符串话,接着将每个字符串逆转然后转成int类型,再加sl1sl2相加,然后将相加的结果num转成字符串并逆转。创建一个首节点,然后赋值给r因为r节点需要一直变换,将num迭代并使用enumerate获取索引,将迭代的numint值赋值给r节点的val,判断是不是最后一个索引是的话就退出,不是的话将r.next创建一个节点,再将它赋值给r,进行之后的迭代

# Definition for singly-linked list
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        sl1 = ''
        sl2 = ''
        while l1:
            sl1 += str(l1.val)
            l1 = l1.next
        while l2:
            sl2 += str(l2.val)
            l2 = l2.next
        num = str(int(sl1[::-1]) + int(sl2[::-1]))[::-1]
        first = ListNode()
        r = first
        for index,i in enumerate(num):
            r.val = int(i)
            if (index == len(num)-1): break
            r.next = ListNode()
            r = r.next
        return first
    
'''迭代做法'''
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        sl1 = ''
        sl2 = ''
        while l1:
            sl1 += str(l1.val)
            l1 = l1.next
        while l2:
            sl2 += str(l2.val)
            l2 = l2.next
        num = iter(str(int(sl1[::-1]) + int(sl2[::-1]))[::-1])
        first = ListNode(int(next(num)))
        r = first
        while 1:
            try:
                r.next = ListNode(int(next(num)))
                r = r.next
            except:
                break
        return first

无重复字符的最长子串

题目:给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

解法

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        hashmap = {}
        repeat_index, ans = -1,0
        for index,i in enumerate(s):
            if i in hashmap:
                repeat_index = max(hashmap[i],repeat_index)
            ans = max(ans,index - repeat_index)
            hashmap[i] = index
        return ans;

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

Anaconda使用 Previous
MongoDB安装和python连接 Next