【leetcode】-精选top面试

56. 合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]

输出: [[1,6],[8,10],[15,18]]

解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]

输出: [[1,5]]

解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

通过次数72,050提交次数174,657

知识点：列表排序

a = [[8,10],[1,3],[2,6],[15,18]]

a.sort(key=lambda x: x[0]) # 此处的x就是每一个区间元素，默认用首元素排序，此处可以不写

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []
        intervals.sort()  # 按照首元素升序排列
        merged = []
        merged.append(intervals[0])
        for lst in intervals[1:]:
            if lst[0] > merged[-1][1]:
                merged.append(lst)
            else:
                merged[-1][1] = max(lst[1], merged[-1][1])
        return merged

# 复习 列表去重
a = [1,5,8,3,2,1,5]
b = sorted(set(a), key=a.index)
b

[1, 5, 8, 3, 2]

c = list(set(a))
c.sort(key=a.index)
c

[1, 5, 8, 3, 2]

d= list(set(a)).sort(key=a.index)  # 但是这样输出为空
d

1. 两数之和

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

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

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

方法1知识点：列表排序，反求索引，列表重复值不同索引 NlogN

方法2知识点：利用哈希表记录元素和索引，然后直接查target-当前值是否在dict中。O(N)O(N)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        lst = sorted(nums)
        l, r = 0, len(lst)-1
        
        while l < r:
            if lst[l] + lst[r] == target:
                if lst[l] == lst[r]:
                    res = [x for x in range(len(nums)) if nums[x] == lst[l]]  # 重复值索引
                    return res[:2]
                else:
                    return [nums.index(lst[l]), nums.index(lst[r])]
            elif lst[l] + lst[r] < target:
                l += 1
            else:
                r -= 1

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return []
        back_dict = {}

        for i in range(len(nums)):  # 记录数值和索引
            if back_dict.get(nums[i], -1) == -1:
                back_dict[nums[i]] = [i]
            else:
                back_dict[nums[i]].append(i)
        # print(back_dict)
        for num in nums:  # 可以归并到上面的循环中
            if back_dict.get(target - num, -1) == -1:
                continue
            elif num != target-num:
                print(num, 'here')
                return [back_dict[num][0], back_dict[target-num][0]]
            elif len(back_dict[num]) > 1:
                return [back_dict[num][0], back_dict[num][1]]

2. 两数相加

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

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

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

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8

原因：342 + 465 = 807

知识点：链表。亮点：root的首元素实际上没有意义，只是为了开创，返回从next开始，好处是避免头部进位的讨论，简化代码。

解惑：链表赋值类似于list，数值是共享的,内存也是共享的。就是别名而已。

# 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:
        carry = 0
        root = ListNode(0)
        temp = root

        while l1 or l2:
            a = b = 0
            if l1:
                a = l1.val
                l1 = l1.next
            if l2:
                b = l2.val
                l2 = l2.next
            s = (a+b+carry) % 10
            carry = (a+b+carry) // 10
            node = ListNode(s)
            temp.next = node
            temp = node            
            
        if carry != 0:
            node = ListNode(carry)
            temp.next = node
                    
        return root.next

3. 无重复字符的最长子串

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

示例 1:

输入: “abcabcbb”

输出: 3

解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

思路1：方法一采用了动规的方法：状态转移：如果当前字符不在前一字符所在的窗口，则max加一，否则在前一窗口找到当前char的索引截断。

思路2：方法一种需要判断char是否在某个子字符串中，造成复杂度增加，考虑用哈希表和一个ignore抵达索引来换取时间。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        res = ret = 1
        for i in range(1, len(s)):
            if s[i] in s[i-res: i]:
                res = res - (1+ s[i-res: i].index(s[i])) + 1                
            else:
                res += 1
                ret = max(ret, res)
        return ret

class Solution(object):
    def lengthOfLongestSubstring(self, s: str) -> int:
        ignore_str_index_end = -1
        dic = {}        
        max_length = 0  

        for i, c in enumerate(s):
            # 索引都会大于等于0，新字符的索引为-1，否则为已经出现
            # 第二个条件是因为ignore机制已经截断了重复char以及之前的char
            if dic.get(c, -1) != -1 and dic[c] > ignore_str_index_end:
                ignore_str_index_end = dic[c]  # 无效推进
                dic[c] = i
            else:
                dic[c] = i
                max_length = max(i - ignore_str_index_end, max_length)
        return max_length