题目描述  给定一个已排序的正整数数组 nums ，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。  示例1    输入： nums = [1,3], n = 6 输出： 1 解释： 根据 nums 里现有的组合 [1], [3], [1,3]，可以得出 1, 3, 4。 现在如果我们将 2 添加到 nums 中， 组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。 其和可以表示数字 1, 2, 3, ...

When？什么时候开始写的？  第一次写博客是 2015 年了，在 CSDN 和博客园上面，当时写文章是为了记录 ACM 竞赛的题解，陆陆续续写了几十篇。但是最后还是没有坚持下去，主要还是因为 CSDN 和博客园的体验太差了，写起文章来很难受，又丑又慢。另一个原因是， CSDN 发个文章还需要审核，定制主题自由度也太差。 第二次就是 2017 年暑假了，当时自己建了个人博客，域名是：godweiyang.com。当时的想法是，个人博客好好看，有各种主题，如果会点前端知识，还能自己魔改。个人博客主要更新的就是自然语言处理的知识了，主要都是些论文的阅读赏析。另外还更新一些计算机相关的基础知识，主要...

题目描述  给定一个非空二叉树，返回其最大路径和。 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。  示例1    输入： [1,2,3] 1 / \ 2 3 输出： 6    示例1    输入： [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 输出： 42    题解  这是一道树形 dp 入门题，也就是树上的动态规划。 首先要理解它这个输入什么意思，虽然写代码的时候不用你管，已经给你处理成结构体了。 输入是一个数组，其实是二叉树的层次遍历，也就是从第一层（根结点）开始，往下一层一...

题目描述  给定一个非负整数 n ，计算各位数字都不同的数字 x 的个数，其中 。  示例1    输入： 2 输出： 91 解释： 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。    题解  这题要求所有数位数字都不相同的数字个数，那么我们可以将答案分成不同长度。  方法1  对于长度为 n 的数字，第一位取值有 1~9 一共 9 种情况，而后面 n - 1 位可以从 0~9 中随机取出 n - 1 个不同数字，然后随机排列。因为要和第一位不同，所以后面的数字选择只有 9 种情况，所以方案数是排列数 。 然后一直累和到长度为 ...

题目描述  给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。 （例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。） 返回 A 中好子数组的数目。  示例1    输入： A = [1,2,1,2,3], K = 2 输出： 7 解释： 恰好由 2 个不同整数组成的子数组： [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]    示例2    输入： A = [1,2,1,3,4], K = 3 输出： 3 解释： 恰好由 3 个不同...

题目描述  给你一个正整数数组 nums ，你需要从中任选一些子集，然后将子集中每一个数乘以一个任意整数，并求出他们的和。 假如该和结果为 1 ，那么原数组就是一个「好数组」，则返回 True ；否则请返回 False 。  示例1    输入： nums = [12,5,7,23] 输出： true 解释： 挑选数字 5 和 7 。 5*3 + 7*(-2) = 1    示例2    输入： nums = [29,6,10] 输出： true 解释： 挑选数字 29 , 6 和 10 。 29*1 + 6*(-3) + 10*(-1) = 1    示例3    输入： nums = [3...

论文地址   PaLM: A Hybrid Parser and Language Model[1]   介绍  本文介绍了如何将一个句法分析器融入到神经网络语言模型中，这样在利用了句法信息增强语言模型效果的同时，还可以去掉句法上的监督信号，用来无监督地生成句法树。 其实将句法信息加入到语言模型中地思想之前就有了，比如PRPN（Shen et al.[2]）和ON-LSTM（Shen et al.[3]）。而本文提出了一种新的融入句法信息的方法，相比于之前的两个模型，主要有如下优点：  更加符合直觉、更加轻巧，不需要很复杂的解码算法。 在LSTM中加入的attention信息可以用句法信息来监...

题目描述  给你一个正整数的数组 A（其中的元素不一定完全不同），请你返回可在 一次交换（交换两数字 A[i] 和 A[j] 的位置）后得到的、按字典序排列小于 A 的最大可能排列。 如果无法这么操作，就请返回原数组。  示例1    输入： [3,2,1] 输出： [3,1,2] 解释： 交换 2 和 1    示例2    输入： [1,1,5] 输出： [1,1,5] 解释： 这已经是最小排列    示例3    输入： [1,9,4,6,7] 输出： [1,7,4,6,9] 解释： 交换 9 和 7    示例4    输入： [3,1,1,3] 输出： [1,3,1,3] 解释： 交...

题目描述  给定一个由若干 0 和 1 组成的数组 A ，我们最多可以将 K 个值从 0 变成 1 。 返回仅包含 1 的最长（连续）子数组的长度。  示例1    输入： A = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出： 6 解释： [1,1,1,0,0,1,1,1,1,1,1] A[5] 和 A[10] 从 0 翻转到 1，最长的子数组长度为 6。    示例2    输入： A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出： 10 解释： [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1...

发现leetcode的困难难度做起来还是需要点时间的（还是我太菜了），而且可能大多数人也不能接受，所以明天开始穿插做中等难度题目。   题目描述 给定一个整数数组nums，按要求返回一个新数组counts。数组counts有该性质：counts[i]的值是nums[i]右侧小于nums[i]的元素的数量。  示例输入  [5,2,6,1]  示例输出  [2,1,1,0]  示例解释  5的右侧有2个更小的元素2和1。 2的右侧仅有1个更小的元素1。 6的右侧有1个更小的元素1。 1的右侧有0个更小的元素。  题解 这题没有给数据范围，但是用脚想也知道不能暴力做（ ）。 这题其实有多种解法，这...

闲来无事，为了保证日更，从今天开始每天更新一道LeetCode题解。 做题顺序是这样的：随机选择一题“困难”类型的题目。 因本人ACM退役颇久，代码多有疏漏，望多多见谅。    题目描述：  给定数组 由正整数组成，找到三个互不重叠的子数组的最大和。 每个子数组的长度为 ，我们要使这 个项的和最大化。 返回每个区间起始索引的列表（索引从 0 开始）。如果有多个结果，返回字典序最小的一个。 示例输入： [1,2,1,2,6,7,5,1], 2 示例输出： [0, 3, 5] 示例解释： 子数组 [1, 2], [2, 6], [7, 5] 对应的起始索引为 [0, 3, 5]。 我们也可以取 [...

今天我给大家分享一些我平时自用的软件，有学习的、编程的、娱乐的、工具类的等等。 有些软件是破解版的，去除了广告，都很实用！ 迅雷极速版 迅雷我一直用的是纯净版（极速版），相比于最新的迅雷9，这个版本没有广告和在线视频等没用的功能。  注意会经常弹出来让你更新，千万别点确定，点取消就行了。  界面看起来就很简洁：     下载地址：  【迅雷快速下载】迅雷极速版 1.0.35-ZOL软件下载 QQ影音 QQ影音是腾讯少有的几款良心软件了，没有任何广告，也不会流氓捆绑。 功能也够用了，比如视频转gif、转码、截取视频等常用功能都用了。  QQ影音可以用来作为迅雷的边下边播的播放器，然后就可以舒舒服...

论文地址：Tree Transformer: Integrating Tree Structures into Self-Attention 介绍 之前其实有很多工作将句法信息融入到了RNN中，例如ON-LSTM和PRPN，用来隐式建模句法结构信息，同时提升语言模型的准确率。本文尝试将句法信息融入到Transformer中，用来赋予attention更好的解释性。同时可以无监督的预测出句子的句法树，并且相比于一般的Transformer，语言模型的性能有所提高。 模型结构  上面这张是模型结构，最主要的区别就是在multi-head attention操作基础上新增了一个成分的attentio...

论文地址：Insertion-based Decoding with automatically Inferred Generation Order 介绍 大多数的生成模型（例如seq2seq模型），生成句子的顺序都是从左向右的，但是这不一定是最优的生成顺序。 可能有人要说，反正最终都是生成一个句子，跟生成顺序有啥关系？ 但是大量实验确实表明了从左向右生成不一定是最好的，比如先生成句子中的核心词（出现词频最高的词，或者动词等）可能效果会更好。 于是这篇论文就提出了自动推测最佳的生成顺序，考虑所有顺序的概率，优化概率之和。 但是对于任意一个生成顺序，如何还原原本的句子呢？ 本文又提出了一个相对位...