中等难度-未分类问题

来源于leetcode题库3,31,48,56,146,208,215,238,399

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

题目描述
- 给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例 1:

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

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

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

enumerate() 函数
- 用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。

普通for循环
i = 0
seq = ['one', 'two', 'three']
for element in seq:
... print i, seq[i]
... i +=1
...
输出：
0 one
1 two
2 three

for循环使用enumerate函数
seq = ['one', 'two', 'three']
for i, element in enumerate(seq):
...print i, element
...
输出：
0 one
1 two
2 three

题解：

class Solution:
    #以字符串的值为key，以下标为value
    def lengthOfLongestSubstring(self, s: str) -> int:
        #初始化
        start,res,newdic=-1,0,{}
        #按循环顺序，把s中的元素挨个放到新的newdic里去
        for i,c in enumerate(s):
            #如果c已经在newdic中且下标比start大
            if c in newdic and newdic[c]>start:
                start=newdic[c]#重新定位start指针
                newdic[c]=i#给这个重复字母赋上顺序值
            #newdic里还没有这个重复字母，且不需要重新定位指针
            else:
                newdic[c]=i
                res=max(res,i-start)   #更新最大子串长度   
        return res

31.

题目描述
- 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
  如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
  必须原地修改，只允许使用额外常数空间。
示例

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

题解

48.旋转图像

题目描述
- 给定一个 n × n 的二维矩阵表示一个图像。
  将图像顺时针旋转 90 度。
  说明：
  你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例

给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

题解

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        '''
        分层平移的策略，左上角坐标为(pos1,pos1),右上角(pos1,pos2)
                     左下角作为(pos2,pos1),右下角(pos2,pos)
        '''
        pos1,pos2 = 0,len(matrix)-1
        while   pos1<pos2:
            add = 0
            while   add < pos2-pos1: # 有偏移量
                #左上角为0块，右上角为1块，右下角为2块，左下角为3块
                temp = matrix[pos2-add][pos1]
                matrix[pos2-add][pos1] = matrix[pos2][pos2-add]
                #3 = 2
                matrix[pos2][pos2-add] = matrix[pos1+add][pos2]
                #2 = 1
                matrix[pos1+add][pos2] = matrix[pos1][pos1+add]
                #1 = 0
                matrix[pos1][pos1+add] = temp
                #0 = temp
                add = add+1
            pos1 = pos1+1
            pos2 = pos2-1

56.合并区间

题目描述
- 给出一个区间的集合，请合并所有重叠的区间。
示例

示例 1:
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

题解
- 来源于题解区大佬莲子熊猫

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 本题要点为先按左边界排序
        if len(intervals) == 0:
            return []
        res = []
        # 先按区间左边界值由小到大排序
        intervals.sort(key=lambda x: x[0])  
        for inter in intervals:
            # 如果结果集最后一个元素的右边界比新加入区间的左边界小，直接加入结果集
            if len(res) == 0 or res[-1][1] < inter[0]:  
                res.append(inter)
            else:  # 否则，说明新加入的和结果集最后一个区间有重合，更新区间右边界即可
                res[-1][1] = max(res[-1][1], inter[1])
        return res

146.LRU缓存机制

题目描述
- 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。
  获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
  写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
示例

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得关键字 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得关键字 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

题解
- 来源于题解区大佬liye

class ListNode:
    # 用哈希表和双链表实现
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap = {}
        # 新建两个节点 head 和 tail
        self.head = ListNode()
        self.tail = ListNode()
        # 初始化链表为 head <-> tail
        self.head.next = self.tail
        self.tail.prev = self.head

    # 因为get与put操作都可能需要将双向链表中的某个节点移到末尾，所以定义一个方法
    def move_node_to_tail(self, key):
            # 先将哈希表key指向的节点拎出来，为了简洁起名node
            #      hashmap[key]                               hashmap[key]
            #           |                                          |
            #           V              -->                         V
            # prev <-> node <-> next         pre <-> next   ...   node
            node = self.hashmap[key]
            node.prev.next = node.next
            node.next.prev = node.prev
            # 之后将node插入到尾节点前
            #                 hashmap[key]                 hashmap[key]
            #                      |                            |
            #                      V        -->                 V
            # prev <-> tail  ...  node                prev <-> node <-> tail
            node.prev = self.tail.prev
            node.next = self.tail
            self.tail.prev.next = node
            self.tail.prev = node

    def get(self, key: int) -> int:
        if key in self.hashmap:
            # 如果已经在链表中了久把它移到末尾（变成最新访问的）
            self.move_node_to_tail(key)
        res = self.hashmap.get(key, -1)
        if res == -1:
            return res
        else:
            return res.value

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            # 如果key本身已经在哈希表中了就不需要在链表中加入新的节点
            # 但是需要更新字典该值对应节点的value
            self.hashmap[key].value = value
            # 之后将该节点移到末尾
            self.move_node_to_tail(key)
        else:
            if len(self.hashmap) == self.capacity:
                # 去掉哈希表对应项
                self.hashmap.pop(self.head.next.key)
                # 去掉最久没有被访问过的节点，即头节点之后的节点
                self.head.next = self.head.next.next
                self.head.next.prev = self.head
            # 如果不在的话就插入到尾节点前
            new = ListNode(key, value)
            self.hashmap[key] = new
            new.prev = self.tail.prev
            new.next = self.tail
            self.tail.prev.next = new
            self.tail.prev = new

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

208.

题目描述
- 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true

题解
- 来源于题解区大佬powcai

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.lookup = {}
        

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        tree = self.lookup
        for a in word:
            if a not in tree:
                tree[a] = {}
            tree = tree[a]
        # 单词结束标志
        tree["#"] = "#"
        

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        tree = self.lookup
        for a in word:
            if a not in tree:
                return False
            tree = tree[a]
        if "#" in tree:
            return True
        return False
        

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        tree = self.lookup
        for a in prefix:
            if a not in tree:
                return False
            tree = tree[a]
        return True
        



# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

215.数组中第k个最大元素

题目描述
- 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
题解

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 堆排序
        def adjust_heap(idx, max_len):
            left = 2 * idx + 1
            right = 2 * idx + 2
            max_loc = idx
            if left < max_len and nums[max_loc] < nums[left]:
                max_loc = left
            if right < max_len and nums[max_loc] < nums[right]:
                max_loc = right
            if max_loc != idx:
                nums[idx], nums[max_loc] = nums[max_loc], nums[idx]
                adjust_heap(max_loc, max_len)
        
        # 建堆
        n = len(nums)
        for i in range(n // 2 - 1, -1, -1):
            adjust_heap(i, n)
        #print(nums)
        res = None
        for i in range(1, k + 1):
            #print(nums)
            res = nums[0]
            nums[0], nums[-i] = nums[-i], nums[0]
            adjust_heap(0, n - i)
        return res

238.除自身以外数组的乘积

题目描述
- 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例

输入: [1,2,3,4]
输出: [24,12,8,6]

题解
- 来源于题解区大佬krahets

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        '''
        res数组列为乘积形式(当前位置数字不相乘可以等价为乘1)
        res[0] =  1  *  nums[1]  *  nums[2]  ...  *  nums[n-1]
        res[1] =  nums[0]  *  1  *  nums[2]  ...  *  nums[n-1]
        ...
        res[n-1] = nums[0]  *  nums[1]  ...  *  nums[n-2]  *  1
        经过上述排列可发现矩阵主对角线上全为1，分别计算矩阵的上三角和下三角，并存储值
        '''
        res, p, q = [1], 1, 1
        for i in range(len(nums) - 1): # 下三角
            p *= nums[i]
            res.append(p)
        for i in range(len(nums) - 1, 0, -1): # 上三角
            q *= nums[i]
            res[i - 1] *= q
        return res

399.

题目描述
示例
题解