[leetcode]第二十三部分(146-152)

146. LRU Cache

问题难度: ♣ ♣ ♣ ♣ ♣

问题描述

设计和实现一个LRU(Least Recently Used)缓存的数据结构. 它应该支持以下的操作: getput.

  • get(key): 如果该key存储于缓存中, 获得该键的值(一般为正数), 否则的话返回-1
  • put(key): 如果该key不存在, 设置或者插入该值. 当缓存到达容量极点时, 应该在插入新条目之前使得最近未使用的条目

follow up:
能够在O(1)时间复杂度内实现上述的操作.

示例

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

解题思路

看到O(1)复杂度, 那么直接想到使用一个hash结构(data_dict)来存储key-value的值, 这样就能够在O(1)时间复杂度内实现get(key)了…
但是考虑到put时,需要考虑缓存到容量极点时,也需要在O(1)时间复杂度内完成, 因此需要使用一个类似于栈的结构来存储key最近的访问顺序(visit_list), put的具体逻辑如下:

  • 如果key已经存在, data_dict[key] = value, visit_list.remove(key), visit_list.append(key)
  • 如果key不存在, least_used = visit_list[0], visit_list = visit_list[1:], visit_list.append(key), data_dict.del(least_used), 接着: data_dict[key] = value, visit_list.append(key)

然后remove的时间复杂度为O(n), 显然还是可以改进的.

使用一个hash结构和一个双向链表进行求解, 这样删除节点的时候就可以使得时间复杂度降为O(1)了, 新建一个数据结构Node, 用来记录前驱节点和后序节点.

代码

class LRUCache(object):

    capacity = 0
    data_dict = {}
    visit_list = []


    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.data_dict = dict()
        self.visit_list = list()


    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.data_dict:
            self.visit_list.remove(key)
            self.visit_list.append(key)
            return self.data_dict[key]
        else:
            return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self.data_dict:
            self.visit_list.remove(key)
            self.visit_list.append(key)
            self.data_dict[key] = value
        else:
            if len(self.data_dict) == self.capacity:
                least_used = self.visit_list[0]
                del self.data_dict[least_used]
                self.visit_list = self.visit_list[1:]
            self.data_dict[key] = value
            self.visit_list.append(key)

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

    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.pre = None
        self.next = None

class LRUCache(object):

    capacity = 0
    node_dict = {}
    head = None
    tail = None


    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.node_dict = dict()
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.pre = self.head


    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.node_dict:
            node = self.node_dict[key]
            self._remove(node)
            self._add(node)
            return node.value
        else:
            return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        node = Node(key, value)
        if key in self.node_dict:
            pre_node = self.node_dict[key]
            self._remove(pre_node)
        else:
            if len(self.node_dict) == self.capacity:
                n = self.head.next
                self._remove(n)
                del self.node_dict[n.key]
        self.node_dict[key] = node
        self._add(node)

    def _add(self, node):
        p = self.tail.pre
        p.next = node
        node.pre = p
        node.next = self.tail
        self.tail.pre = node

    def _remove(self, node):
        p = node.pre
        n = node.next
        p.next = n
        n.pre = p

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

147. Insertion Sort List

问题难度: ♣ ♣ ♣

问题描述

使用插入排序对链表进行排序.

Insertion-sort-example-300px.gif

插入排序的图形化表示如上所示. 已经排好序的部分(黑色部分)初始只包含链表中的第一个元素. 每次迭代过程中, 每个元素(红框)都会从输入数据中删除, 然后就地插入到排好序的链表中.

插入算法:

插入算法迭代, 每次重复消费一个输入元素, 然后将其插入到排好序的输出链表中. 在每次迭代中, 插入排序从输入数据中删除元素, 然后在排好序的链表中找到其应该处于的位置, 然后将其插入. 重复这个过程直到不再有输入元素.

示例1

Input: 4->2->1->3
Output: 1->2->3->4

示例2

Input: -1->5->3->4->0
Output: -1->0->3->4->5

解题思路

考察的是插入排序, 需要有一个指针指向未排序的输入数据, 另外一个指针指向已经排好序的输入数据, 然后重复插入的过程即可.

具体说说插入过程, 分两种情况:

  • 当待插入的数最小时, 需要将指针指向待插入的数, 并且将当前指针的next指向原有的头指针
  • 其它情况, 需要两个指针记录它的前序节点和后续节点

代码

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

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return head
        sort, unsort = head, head.next
        sort.next = None
        # 遍历待排序的节点
        while unsort is not None:
            cur = unsort
            unsort = unsort.next
            pre = sort
            after = sort.next
            if pre.val >= cur.val:
                # 待插入值为最小值
                cur.next = sort
                sort = cur
            else:
                # 需要找到待插入点
                while after is not None and after.val < cur.val:
                    pre = pre.next
                    after = pre.next
                pre.next = cur
                cur.next = after
        return sort

148. Sort List

问题难度: ♣ ♣ ♣

问题描述

O(n log n)的时间复杂度和常数空间复杂度下队链表进行排序.

示例1

Input: 4->2->1->3
Output: 1->2->3->4

示例2

Input: -1->5->3->4->0
Output: -1->0->3->4->5

解题思路

常用排序算法有很多, 插入排序, 选择排序, 堆排序, 快速排序, 冒泡排序, 归并排序, 桶排序等等. 它们的时间复杂度有些不相同. 而题干中要求时间复杂度为O(nlogn), 在这里选择归并排序.

归并排序的核心思想是: 分治策略, 分而治之.

分为两个阶段: 第一个阶段将数组切割成无数小数组, 然后再将有序的序列合并在一起.

回到链表的题目: 针对链表, 其实核心是找到中心点, 那么这里就需要使用到三个指针: slow/fast以及pre, 先将链表分割成一个一个的节点,再将其连接起来即可.

代码

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

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        slow, fast, pre = head, head, head
        while fast is not None and fast.next is not None:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        pre.next = None
        return self.merge(self.sortList(head), self.sortList(slow))

    def merge(self, l1, l2):
        dummy = ListNode(-1)
        cur = dummy
        while l1 is not None and l2 is not None:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        if l1 is not None:
            cur.next = l1
        if l2 is not None:
            cur.next = l2
        return dummy.next

149. Max Points on a Line

问题难度: ♣ ♣ ♣ ♣ ♣

问题描述

给定2维平面上的n个点,找到位于相同直线上最大的点数.

示例1

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

示例2

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

解题思路

总的说来, 需要有一个嵌套:

针对当前节点, 从下一个节点开始:

计算斜率值(有两种特殊情况: 两个点重合和平行于y轴), 然后使用一个dict存储起斜率的计数.

特别注意一点: 如果直接使用除法的话, 可能会牺牲精度, 可以直接使用两个数均除以最大公约数之后的值.

代码

# Definition for a point.
# class Point(object):
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution(object):
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        def gcd(a, b):
            return a if b == 0 else gcd(b, a%b)
        res = 0
        for i in range(len(points)):
            now_point = points[i]
            duplicate = 1
            slop_dict = dict()
            for j in range(i+1, len(points)):
                another_point = points[j]
                if now_point.x == another_point.x and now_point.y == another_point.y:
                    duplicate += 1
                else:
                    dx = now_point.x - another_point.x
                    dy = now_point.y - another_point.y
                    d = gcd(dy, dx)
                    slop = "_".join([str(dy//d), str(dx//d)])
                    cnt = 1
                    if slop in slop_dict:
                        cnt += slop_dict[slop]
                    slop_dict[slop] = cnt
            res = duplicate if duplicate > res else res
            for slop in slop_dict:
                cnt = slop_dict[slop]
                res = cnt + duplicate if cnt + duplicate > res else res
        return res

150. Evaluate Reverse Polish Notation

问题难度: ♣ ♣ ♣

问题描述

计算一个逆波兰表达式表示的数学值.

有效的操作符包括: +,-,*,/. 每个操作数可以是一个整数或者另一个表达式.

注意:

  • 两个整数之间的除法需要去掉整数部分
  • 给定的逆波兰式都是有效的, 也就是说所有的公式都可以得到一个结果并且不会出现除数为0的操作.

示例1

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

示例2

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

示例3

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

解题思路

使用一个栈结构, 从前向后遍历, 遇到操作符则将前面两个数取出来进行运算, 将运算结果push进栈, 遍历到数组结尾结束即可.

代码

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        stack = []
        for i in range(len(tokens)):
            num = tokens[i]
            if num in ["+", "-", "*", "/"]:
                if len(stack) < 2:
                    return 0
                # 如果是运算符. 将前两个数弄出来
                num_2 = stack.pop()
                num_1 = stack.pop()
                if num == "+":
                    stack.append(num_1 + num_2)
                elif num == "-":
                    stack.append(num_1 - num_2)
                elif num == "*":
                    stack.append(num_1 * num_2)
                else:
                    #如果有负数,需要特殊处理下
                    flag = 1
                    if num_1 < 0:
                        flag = -1
                        num_1 *= -1
                    if num_2 < 0:
                        flag *= -1
                        num_2 *= -1
                    tmp = num_1 / num_2
                    if flag < 0:
                        tmp *= -1
                    stack.append(tmp)
            else:
                stack.append(int(num))
        return stack.pop()

151. Reverse Words in a String

问题难度: ♣ ♣ ♣

问题描述

给定一个输入的字符串, 逐个单词翻转字符串.

示例

Input: "the sky is blue",
Output: "blue is sky the".

注意:
– 一个单词的定义为: 一个非空字符串的序列
– 输入字符串前后均可能包含空字符串, 但是,翻转之后的字符串的前后不能包含空字符串
– 需要在翻转字符串中将两个单词之间的多个空格减少到一个空格

延伸: 对于C程序员, 尝试在O(1)的空间复杂度内就地解决这个问题.

解题思路

最简单直接的方法: 可以直接用python中内置的split函数进行分割, 然后再join起来.

另外一种方法: 先将整个字符串进行翻转, 再逐个翻转单词.

例如: the sky is blue 先变成: eulb si yks eht, 再变成: blue is sky the.

首先, 将整个字符串翻转非常简单: 使用一个store_idx标识当前需要替换的末尾位置, 也是两个指针:

首先, 如果遇到空格, 我们先直接跳过, 如果遇到非空格, 判断一下store_idx是否为0, 如果为0表示这是一个首单词,前面不用加空格; 反之, 表示非首单词, 应该将store_idx对应的字符设置为空, 并且向前移动一步;然后再往前走, 直到遇到第一个空格为止, 这表明从start_idx - (j-i)start_idx-1的字符需要翻转. 接下来继续循环即可.

始终记住: start_idx中存储的是上一个有效单词的后一个位置, 而ij则标识当前字符串的位置.

代码

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        arr = s.split()
        arr.reverse()
        return " ".join(arr)


    def reverseWordsInPlace(self, s):
        """
        :type s: str
        :rtype: str
        """
        def reverse(s, i, j):
            #print s, i, j
            while i < j:
                # 交换首尾的字符
                tmp_i = s[i]
                tmp_j = s[j]
                s = s[:i] + tmp_j + s[i+1:j] + tmp_i + s[j+1:]
                i += 1
                j -= 1
            return s
        s = reverse(s, 0, len(s)-1)
        n = len(s)
        store_idx = 0
        i = 0
        while i < n:
            if s[i] != ' ':
                if store_idx != 0:
                    s = s[:store_idx] + " " + s[store_idx+1:]
                    store_idx += 1
                j = i
                while j < len(s) and s[j] != ' ':
                    s = s[:store_idx] + s[j] + s[store_idx + 1:]
                    j += 1
                    store_idx += 1
                s = reverse(s, store_idx - (j-i), store_idx-1)
                i = j
            else:
                i += 1
        return s[:store_idx] 
sl = Solution()
s = " the sky is   blue"
print(sl.reverseWords(s))
print(sl.reverseWordsInPlace(s))
blue is sky the
blue is sky the

152. Maximum Product Subarray

问题难度: ♣ ♣ ♣

问题描述

给定一个整数数组nums, 找到数组中有最大乘积的连续子数组(至少包含一个数字).

示例1

Input: [2,3,-2,4]
Output: 6
解释: [2,3]有最大的乘积 6.

示例2

Input: [-2,0,-1]
Output: 0
解释: 结果不为 2, 因为 [-2,-1] 不是一个子数组.

解题思路

暴力破解法是: 找到数组的所有连续子数组, 然后计算其乘积, 记录最大值即可, 但是时间辅助度有点高, 为O(n).

动态规划法: 针对当前值, 可能有两个操作: 第一是继续与之前的乘起来, 第二是放弃之前的, 从现在开始, 由于0和负数的存在, 那么只存储一个最大值显然是不合适的.可能与之前的最大值和最小值都有关系(如果是负数的话,应该要选择最小值.) 因此, 我们在这里需要使用到两个数组,l[i]s[i]分别存储包含nums[i]的最大值和最小值, 很明显, 每次更新两个数组只需要比较l[i-1] * nums[i]/s[i-1] * nums[i]/nums[i]的值分别更新两个数组即可.

最后的最后, 需要维护一个res来记录所有出现过的最大值.

代码

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def getMin(x, y, z):
            if x <= y and x <= z:
                return x
            if y <= x and y <= z:
                return y
            return z
        def getMax(x, y, z):
            if x >= y and x >= z:
                return x
            if y >= x and y >= z:
                return y
            return z
        if len(nums) == 0:
            return 0
        res = nums[0]
        l = [0 for _ in range(len(nums))]
        s = [0 for _ in range(len(nums))]
        l[0], s[0] = nums[0], nums[0]
        for i in range(1, len(s)):
            num = nums[i]
            l_num = l[i-1] * num
            s_num = s[i-1] * num
            min_num = getMin(num, l_num, s_num)
            max_num = getMax(num, l_num, s_num)
            #print num, l_num, s_num, min_num, max_num
            s[i] = min_num
            l[i] = max_num
            if max_num > res:
                res = max_num
        #print s, l
        return res
s = Solution()
nums = [2,3,-2,4]
print(s.maxProduct(nums))
nums = [-2,0,-1]
print(s.maxProduct(nums))
6
0
打赏

mickey

记录生活,写给几十年后的自己。