new Cairo()

Happy reading and coding.

0%

发表于 分类于 阅读次数：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

一、题目要求

实现一个对于正整数和“+, -, *, /, (, )”的计算器。每个表达式都是合法的。乘除法优先级较高。

二、分析

实际只需要一个操作数栈存储带正负号的操作数。遇到括号就递归处理。遇到优先级高的操作符乘除就直接算。

三、实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
nums = [str(a) for a in range(10)]


class Solution:
    def calculate(self, s: str) -> int:        
        return cal(list(reversed(s)))
        

def cal(s):
    stack = []
    op_stack = []
    v, valid = 0, False
    sign = None
    compute_flag = 0

    while s:
        c = s.pop()
        if c == ' ':
            continue

        if c in nums:
            valid = True
            v = v * 10 + int(c)
        else:
            if valid:
                if compute_flag != 1:
                    v = -v if sign == '-' else v  # 加减法直接记录
                stack.append(v)
                if compute_flag == 1:
                    evaluation(stack, op_stack)
            v, valid = 0, False
            if c == '(':
                stack.append( self.calculate(s))
            elif c == ')':
                break
            else:  # ['+', '-', '*', '/']
                compute_flag = 1 if c in ['*', '/'] else 0
                if compute_flag == 1:
                    op_stack.append(c)
                else:
                    sign = c
        # print('stack: {}'.format(stack))
        # print('op_stack: {}'.format(op_stack))
    if valid == True:
        if compute_flag != 1:
            v = -v if sign == '-' else v
        stack.append(v)
        if compute_flag == 1:
            evaluation(stack, op_stack)
    return greedy_evaluation(stack, op_stack)

def helper(op1, op2, sign):
    if sign == '+':
        return op1 + op2
    if sign == '-':
        return op2 - op1
    if sign == '*':
        return op1 * op2
    if sign == '/':
        return op2 // op1 if op2 >= 0 else -(-op2 // op1)  # 除法判断一下

def evaluation(stack, op_stack):
    if len(stack) < 2 or stack[-2] == '(':
        return
    sign = op_stack.pop()
    op1, op2 = stack.pop(), stack.pop()
    res = helper(op1, op2, sign)
    stack.append(res)

def greedy_evaluation(stack, op_stack):
    return sum(stack)
	# 就不用憨憨的再一个一个pop
    # res = None
    # while op_stack:
    #     res = res if res != None else stack.pop(0)
    #     sign = op_stack.pop(0)
    #     op2 = stack.pop(0)
    #     res = helper(op2, res, sign)
    # return res if res != None else stack[0]

有两个点需要注意：

1.不要用pop(0)，因为是O(n)的开销。

2.加减法就不用存储到op栈了，记录操作符的sign然后给操作数修改一下就行。这样最后算的时候直接sum数据栈就行。

3.如果是用2的方法那么对除法要特殊处理，因为整除除法总是向0靠近。

阅读全文 »

发表于 分类于 阅读次数：
本文字数： 1.4k 阅读时长 ≈ 1 分钟

一、题目要求

实现一个对于正整数和“+, -, (, )”的计算器。每个表达式都是合法的。

二、分析

两个栈，操作数栈存储操作数 + “(“，操作符栈存储其他操作符。数字直接入栈，操作符遇到右括号时将对应的左括号删除并求值，其他符号直接求值。

三、实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
from enum import Enum

State = Enum('State', ('begin', 'num', 'op'))

class Solution:
    def calculate(self, s: str) -> int:
        nums = [str(a) for a in range(10)]
        
        def helper(op1, op2, sign):
            # 顺序不要搞反了
            if sign == '+':
                return op1 + op2
            if sign == '-':
                return op2 - op1
            if sign == '*':
                return op1 * op2
            if sign == '/':
                return op2 / op1
            
        def evaluation():
            if len(stack) < 2 or stack[-2] == '(':
                return
            sign = op_stack.pop()
            op1, op2 = stack.pop(), stack.pop()
            res = helper(op1, op2, sign)
            stack.append(res)

        stack = []
        op_stack = []
        v = 0
        compute_flag = 0
        state = State.begin
        if s[0] in nums:
            state = State.num
        else:
            state = State.op

        i = 0
        while i < len(s):
            c = s[i]
            if c == ' ':
                i += 1
                continue
            if state == State.num:
                if c in nums:
                    v = v * 10 + int(c)
                else:
                    state = State.op
                    stack.append(v)
                    # print('stack: {}'.format(stack))
                    v = 0
                    evaluation()
                    continue
            elif state == State.op:
                if c in nums:
                    state = State.num
                    continue
                else:
                    if c == '(':
                        stack.append(c)
                        compute_flag = 0
                    elif c == ')':
                        last = stack.pop()
                        stack[-1] = last  # 删除倒数第二个元素（对应的左括号）
                        evaluation()
                    else:
                        compute_flag = 1
                        op_stack.append(c)
            else:
                print('illegal state.')
            i += 1
            # print('stack: {}'.format(stack))
            # print('op_stack: {}'.format(op_stack))

        if state == State.num:
            stack.append(v)
        while op_stack:
            evaluation()
        return stack[0]
阅读全文 »

发表于 分类于 阅读次数：
本文字数： 8.1k 阅读时长 ≈ 7 分钟

一、题目要求

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

  • 所有数字（包括 target）都是正整数。
  • 解集不能包含重复的组合。

二、分析

首先利用回溯能够没有遗漏的找到所有的组合，但是这样是会重复的。

我们可以首先对数组升序排列，然后对DFS搜索增加一个index，这样就控制了组合里面数的顺序，确保不会重复。

剪枝，如果当前的选择无法组合，那么当前轮之后的选择直接跳过。

三、思路

1.基础题

阅读全文 »

发表于 分类于 阅读次数：
本文字数： 2.2k 阅读时长 ≈ 2 分钟

一、题目要求

为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。

  • get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
  • put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。

「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
在 O(1) 时间复杂度内执行两项操作？

二、分析

对get操作来说，只需要使用key->value的映射即可在O(1)时间查找。
对put操作来说：

  • 1.因为要根据频率删除元素，所以要更新频率，就需要记录key->freq的映射。
  • 2.因为需要O(1)删除节点，所以需要按照freq排序，即记录freq -> key_list，还需要记录并维护min_freq这个数值，从而直接找到使用频率最低的key的集合。
  • 3.因为题目要求在多个key使用频率相同时按照插入顺序删除最早插入的，但这个key_list不能以O(1)插入和删除，我们这里使用了OrderedDict来存储，其实也可以用Queue是一样的。

三、思路

时间开销：

  • 更新频率，包含 OrderedDict/Queue删除元素、字典取值、OrderedDict/Queue插入元素，均为O(1)。

  • get，涉及到更新频率和字典取值，O(1)。

  • put，涉及到更新频率、字典取值、字典插入、字典/OrderedDict/Queue删除，O(1)。
阅读全文 »

发表于 分类于 阅读次数：
本文字数： 115 阅读时长 ≈ 1 分钟

一、题目要求

给定若干硬币金额和一个总金额，返回能凑出这个总金额的凑法。

二、分析

状态：前个金额的硬币是否凑出总金额j记录在。

初始值：，凑出总金额0只有1种。

递推：已知，如果可以加入第个元素那么由 [加入 + 不加入]的总凑法计算，否则就等于（不加入的凑法）。

返回：。

三、思路

时间复杂度和空间开销都是。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # 前i个硬币总金额为amount的拼法
        dp = [[0 for _ in range(amount + 1)] for _ in range(len(coins) + 1)]
        for i in range(len(coins) + 1):  # 拼出总金额为0 = 1
            dp[i][0] = 1
        for i in range(1, len(coins) + 1):  # 前i个硬币
            for j in range(1, amount + 1):
                # 如果第i个硬币可以加进去
                if j - coins[i - 1] >= 0:
                    # 不加进去的凑法 + 加进去的凑发
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]
                elif j - coins[i - 1] < 0:
                    dp[i][j] = dp[i - 1][j]
        return dp[len(coins)][amount]
阅读全文 »

发表于 分类于 阅读次数：
本文字数： 2.1k 阅读时长 ≈ 2 分钟

一、题目要求

这是一个系列问题。

给定一个股票价格的数组，求在k次交易的限制下最佳收益。（变种为无交易限制、增加交易费用、增加交易冷却时间等）

必须在卖出后才能再次买入。

二、分析

状态：在k次交易限制下，需要求最后一天的收益，那么第i天经过了k次交易当前持有股票时的收益记录为，交易次数就是买入次数。

初始值：如果没有进行过交易，那么肯定不持有股票收益是0，，这时候肯定无法持有股票设置收益为负无穷。我们用记录第一天交易前的状态，很显然。

递推：已经知道之前的状态，如果此次交易之后持有股票，那么可能是之前一天持有的或者是今天买入的；否则可能是前一天就没有持有或者今天卖出。

返回：中最大的一个。

三、思路

阅读全文 »

发表于 分类于 阅读次数：
本文字数： 3.4k 阅读时长 ≈ 3 分钟

一、题目要求

写一个二叉树序列化和反序列化的函数，要求以层序遍历。

二、分析

对二叉树来说层序遍历即BFS，使用队列即可，因为没有环所以不需要记录visited。在反序列化的时候首先把字符串转化为TreeNode数组，然后层序遍历root恢复子节点连接，用一个指针记录数组的行进步数。

三、思路

1. 本题，层序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

import queue


class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        res = []
        q = queue.Queue()
        if not root:
            return res
        def traverse(root):
            if not root:
                res.append('null')
                return 
            res.append(str(root.val))
            q.put(root.left)
            q.put(root.right)
            while not q.empty():
                cur = q.get()
                traverse(cur)
        traverse(root)
        while res[-1] == 'null': res.pop()
        ret = '[' + ','.join(res) + ']'
        print(ret)
        return ret
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        data = data[1:-1].split(',')
        data = [TreeNode(int(i)) if i != 'null' else None for i in data]
        q = queue.Queue()
        root, i = data[0], 1
        q.put(root)
            
        while not q.empty() and i < len(data):
            cur = q.get()
            if cur:
                cur.left = data[i]
                i += 1
                q.put(cur.left)
                if i < len(data):
                    cur.right = data[i] 
                    i += 1
                    q.put(cur.right)
        return root

        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

2. jump game

BFS加判断：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from queue import Queue


class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        n = len(arr)
        if not arr or start >= n or start < 0:
            return False
        if len(arr) == 1:
            return arr[0] == 0
        visited = [False for _ in range(n)]
        visited[start] = True
        q = Queue()
        q.put(start)

        while not q.empty():
            cur = q.get()
            if arr[cur] == 0:
                return True
            left = cur - arr[cur]
            right = cur + arr[cur]
            # print(left, right)
            for each in [left, right]:
                if each < 0 or each >= n:
                    continue
                if not visited[each]:
                    visited[each] = True
                    q.put(each)
                    # print(list(q.queue))
                    if arr[each] == 0:
                        return True
        return False
阅读全文 »

发表于 分类于 阅读次数：
本文字数： 127 阅读时长 ≈ 1 分钟

一、题目要求

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

二、分析

状态：前i个元素是否能找到一个子集其和等于sum/2。前个是否能够等于记录在。

初始值：

递推：已知，如果可以加入第个元素那么由 [加入or不加入]决定，如果加入当前元素不合法那么就等于。

返回：。

三、思路

时间复杂度和空间开销都是，S是sum/2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def canPartition(self, nums):
        target = sum(nums)
        n = len(nums)
        if target % 2 != 0:
            return False
        target = target // 2
        # 前n个数字能否组成和为target
        dp = [[False for _ in range(target + 1)] for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][0] = True

        for i in range(1, n + 1):  # 前n个数
            for j in range(1, target + 1):  # 和为1到target
                if j - nums[i - 1] >= 0:  # 可以选择第i个数字
                    dp[i][j] = (
                        dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
                    )
                else:
                    dp[i][j] = dp[i - 1][j]
        return dp[n][target]
阅读全文 »

发表于 分类于 阅读次数：
本文字数： 534 阅读时长 ≈ 1 分钟

一、题目要求

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

二、分析

用递归的DFS搜索，终止条件是临时数组长度足够，当前所有选择是指针j之后的所有数字中选择一个继续递归，递归完成后回溯，取消该数字的选择。

如果当前临时数组把后续所有数字都加上都无法满足条件则跳出当前搜索。

三、思路

每次记录答案复杂度为，这种情况下递归本身的时间复杂度为。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        ans = []
        def add(res, i):
            if len(res) == k:  # 获得一组答案
                ans.append(res.copy())            
                return 
            for j in range(i + 1, n + 1):  # 遍历所有选择
                if len(res) + (n - i) < k:  # 剪枝
                    return
                res.append(j)
                print(res)
                add(res, j)  # DFS
                res.pop(-1)

        add([], 0)
        return ans
阅读全文 »

发表于 分类于 阅读次数：
本文字数： 1.3k 阅读时长 ≈ 1 分钟

BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding

Google AI Language在2018.10发布的论文，提出一种预训练语言模型，在十多个NLP任务中取得了SOTA的效果。

1.现有的LM

两种使用语言模型的方法：

Feature-based，Word2Vec、Glove、ELMo，把预训练好的语言模型当做一个feature加到word embedding中。

fine-tuning，OpenAI-GPT，尽量不改动预训练的语言模型，加输出层并在下游的任务上fine-tune。

他们的共同点：

1.在预训练的时候用的是同一个目标函数；

2.使用单向语言模型学习语言表示。其中，GPT在预训练的时候，预测下一个词只使用其左侧的上下文，相当于使用了Transformer的Decoder的结构。而ELMo等语言模型虽然得到了双向表示，但是是两个独立的目标函数下得到的双向表示直接拼接起来。

2.亮点

阅读全文 »

发表于 分类于 阅读次数：
本文字数： 5.6k 阅读时长 ≈ 5 分钟

七篇和KBQA多多少少有些相关的论文，有些精读有些只是略读。

1.《Improving Natural Language Inference Using External Knowledge in the Science Questions Domain》

在NLI（自然语言推理）任务中，提出一种结合知识库的方法。

已有的引入外部知识的方法，无非是：

1.引入事实（facts），包含实体以及他们之间的关系；

2.引入词法信息，比如一个实体的所有同义词；

3.引入常识，比如所有涉及到的concept组成的subgraph。

提出的使用外部知识的方法：

text-only，graph-only，text-and-graph

Text-Based Model：把Hypothesis和Premise的文本作为输入的一个多层分类模型。

阅读全文 »

发表于 分类于 阅读次数：
本文字数： 2.3k 阅读时长 ≈ 2 分钟

一、《Fusionnet: fusing via fully-aware attention with application to machine comprehension》

1、主要内容

2017年11月的论文，国立台湾大学学生在MSR实习时产出。

最近的MRC模型的核心创新点就是如何让问题q和上下文c的内容进行深度的交互，但是这些模型受制于学习能力、计算能力的限制通常只利用了部分信息。

图像识别领域的研究认为不同层次的表示代表着不同的信息，而这一认识在MRC中也是适用的。

提出了一种能够利用和融合问题和答案中不同层次信息的模型。

核心概念：融合，history-of-word

核心问题：

a.说以往的模型只利用了部分信息，那么它们分别利用了哪些信息如何利用的，可否进行一下分析？

给定两个包含信息的向量集A和B（比如Q和C的词向量集合或者更高级向量表示的集合），利用A的信息更新B或者利用B的信息更新A的过程叫做融合（fusion），以往的模型大多都是在设计这个融合的过程。

下图是论文关于问题1的一个陈述，包含了主要的几种信息融合的方式以及以往模型的做法，其中矩形一般是各种RNN网络，箭头指向的集合代表被融合的集合。融合的过程一般用注意力机制实现。

阅读全文 »

发表于 分类于 阅读次数：
本文字数： 3k 阅读时长 ≈ 3 分钟

变分推断（三）：指数族变分推断

一、坐标更新公式在指数族下的变换

之前的博文中讨论了GMM中的变分推断和CAVI算法，这篇文章中，把它推广到更一般的情况，也就是分布是指数分布族（exponential family）的情况。

指数分布族，是对常见分布的性质经过总结和泛化归纳出来的一类分布，具有形如形式的概率密度函数/概率质量函数。其中，T(x)是充分统计量（能够完全表征一个概率分布的所有量）。

可以用指数族来简化CAVI中坐标更新的公式，我们假定完全条件概率(complete conditional)为如下的指数族形式：

那么利用平均场假设，可对坐标更新公式做如下变换：

所以对当前变分参数，我们只需将其更新到其隐变量对应的条件概率的期望参数即可。

二、条件共轭模型

带局部变量和全局变量的条件共轭模型是指数族模型的一种重要的特例。

在这里局部变量指的是只对某个数据点起作用的变量，而全局变量指的是对所有数据都起作用的变量。比如，在之前的GMM模型中，描述K个高斯分布均值的变量就是全局变量，而描述第i个数据点属于哪个模型的变量就是局部变量。

阅读全文 »

发表于 分类于 阅读次数：
本文字数： 2.4k 阅读时长 ≈ 2 分钟

变分推断（二）：贝叶斯高斯混合模型

以高斯混合模型（Mixture of Gaussians model，GMM）为例，推导变分推断的公式和CAVI算法的过程。

一、联合概率计算

GMM中观察数据来自于K个独立的高斯分布，每个分布的均值为，one-hot向量指示每个数据点来自哪个分布，超参数固定。隐变量为，下面是其先验值：

由贝叶斯定理，能够计算出联合概率：

根据联合概率进行求和、积分可以推导出观测数据x的边缘概率的计算公式，但是这个公式没有解析解，计算的复杂度是。

二、GMM中的CAVI

下面计算变分概率，其中是变分参数，由这些参数决定变分分布q：

  • 0.首先，可以得到ELBO的计算公式，是关于的函数：
  • 1.由上一节中推导出的CAVI隐变量更新公式，下面带入GMM计算cluster indicator隐变量的参数更新公式，注意在此时是不变的：
阅读全文 »