2019-04-02学习4 分钟读完 (大约 572 个字)

Leetcode-3 无重复字符的最长子串 Python

1. 题目

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

示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

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

2. 解题思路

2.1 朴素解法，暴力搜索

为了枚举给定字符串的所有子字符串，我们需要枚举它们开始和结束的索引。假设开始和结束的索引分别为 $i$ 和 $j$ 。那么我们有 $0 \leq i \lt j \leq n $ ,$0≤i<j≤n $（这里的结束索引 j 是按惯例排除的）。因此，使用 $i$ 从0到n - 1,n−1 以及 j 从 i+1 到 n 这两个嵌套的循环，我们可以枚举出 s 的所有子字符串。

要检查一个字符串是否有重复字符，我们可以使用集合。我们遍历字符串中的所有字符，并将它们逐个放入 set 中。在放置一个字符之前，我们检查该集合是否已经包含它。如果包含，我们会返回 false。循环结束后，我们返回 true。

2.2 滑动窗口

利用python 的字典，或者java中的Map<Character, Integer> map
存储每个字符出现位置的索引。
使用变量end来记录上次该字符出现的位置长度，删掉从该字符前一次出现，及其以前的重复出现，也可以理解成不重复字符串的开始位置；
使用变量m来记录不重复字符出现的最大长度；
each是遍历字符串的当前index

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0 : return 0
        end = 0
        dic = {}
        m = 0
        for each in range(len(s)):
            if s[each] in dic :
                end = max(end,dic[s[each]]+1)
            dic[s[each]] = each
            m = max(m,each-end+1)
            
        return m

第二种理解思路：
求无重复字符的最长子串的长度，从头到尾遍历字符串时（索引index），考虑到无重复字符，我们先把字符逐个放到容器set中，并更新最长子串的长度，如果遇到了重复字符，即当前遍历的字符在set中，则要从set中删除重复字符，包括这个重复字符前面的所有字符，也就是从当前子串的最左边（left）开始删除，直到删除重复字符

3. 总结/分类

字符串，滑动窗口

2019-04-01学习2 分钟读完 (大约 355 个字)

Leetcode-2 两数相加（Add Two Numbers）

1. 题目

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

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

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

2. 解题思路

简单题，注意链表操作和进位即可

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

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

        head = ans = ListNode(0)
        is_carry = False
        while l1 != None and l2 != None:

            num = l1.val + l2.val
            if is_carry:
                num = num + 1
            if num >= 10:
                num = num % 10
                is_carry = True
            else:
                is_carry = False
            ans.next = ListNode(num)
            ans = ans.next
            l1 = l1.next
            l2 = l2.next

        while l1 != None:
            if is_carry:
                if l1.val + 1 >= 10:
                    ans.next = ListNode((l1.val + 1) % 10)
                    is_carry = True
                else:
                    ans.next = ListNode(l1.val + 1)
                    is_carry = False

            else:
                ans.next = ListNode(l1.val)
            l1 = l1.next
            ans = ans.next

        while l2 != None:
            if is_carry:
                if l2.val + 1 >= 10:
                    ans.next = ListNode((l2.val + 1) % 10)
                    is_carry = True
                else:
                    ans.next = ListNode(l2.val + 1)
                    is_carry = False
            else:
                ans.next = ListNode(l2.val)
            l2 = l2.next
            ans = ans.next

        if is_carry:
            ans.next = ListNode(1)
            is_carry = False
            ans = ans.next

        res = []
        while head != None:
            res.append(head.val)
            head = head.next

        # return "".join([""+str(each) for each in res])[:-1]
        return res[1:]

3. 总结/分类

链表操作

2019-04-01学习2 分钟读完 (大约 319 个字)

Leetcode -1 两数之和（Two Sum）

1. 题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

2. 解题思路

2.1 朴素解法（暴力遍历）

通过两次循环，每次循环遍历列表，这种算法的时间复杂度是 O(n^2)

2.2 哈希存储

思路：利用hash表，key：当前值，value：索引
解题方法：遍历数组时，查询hash表中，是否存在target - nums[i]。
若有，返回当前索引和存在的key的value；
若不存在，则将当前值和索引存入hash表中
python中的字典就是天然hash表；c++中的unorder_map；
Java中HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();

代码如下：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_hash = {}
        for each in range(len(nums)):
            dif = target - nums[each]
            if dif in nums_hash:
                return [nums_hash[dif], each]
            else:
                nums_hash[nums[each]] = each

3. 总结/分类

数据结构的巧妙利用

2019-03-135 分钟读完 (大约 725 个字)

leetcode - 904 水果成篮

在一排树中，第 i 棵树产生 tree[i] 型的水果。
你可以从你选择的任何树开始，然后重复执行以下步骤：

Leetcode-3 无重复字符的最长子串 Python

1. 题目

2. 解题思路

2.1 朴素解法，暴力搜索

2.2 滑动窗口

3. 总结/分类

Leetcode-2 两数相加（Add Two Numbers）

1. 题目

2. 解题思路

3. 总结/分类

Leetcode -1 两数之和（Two Sum）

1. 题目

2. 解题思路

2.1 朴素解法（暴力遍历）

2.2 哈希存储

3. 总结/分类

leetcode - 904 水果成篮

链接

分类

最新文章

归档

标签