673. 最长递增子序列的个数

题目描述 给定一个未排序的整数数组,找到最长递增子序列的个数。 示例 1: 输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列,分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。 示例 2: 输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1,并且存在5个子序列的长度为1,因此输出5。 注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – Top-down 这道题目是第300题的升级,那道题目仅要求找出最长递增子序列(LIS)的长度,而这道题目需要统计LIS有多少个。为了求出数组nums的LIS个数,我们先要求得最长递增子序列的长度maxLen。然后扫描nums数组,统计LIS长度为maxLen的个数。 首先我们实现一个函数,求数组nums的LIS的长度(参考300题的Top-down解法)。我们定义函数lengthOfLIS(int[] nums, int n),表示计算数组nums前n个元素(n从1开始,包含第n个且必须使用第n个元素)能够形成LIS的长度。例如我们有nums = [1,2,3,2,2],那么lengthOfLIS(nums, 4) = 2而不是3,因为我们必须使用nums[4]。 为了求num前n个元素的LIS,我们可以使用递归来解决。对于长度n,我们向前寻找某一元素i,使其满足nums[n] > nums[i](递增的定义),然后递归调用lengthOfLIS(nums, i),即求解nums数组前i个元素的LIS。代码如下: 下一步,我们定义函数count(int[] nums, int n)用于计算nums前n个元素(n从1开始,包含第n个且必须使用第n个元素)构成的LIS长度为maxLen的递增子序列数量。它会调用上面实现的函数lengthOfLIS(nums, n)。在这里我们举一个例子,nums = [1,3,2,4,5],则 count(nums,…

Read more

300. 最长上升子序列

题目描述 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。说明: 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗? 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/longest-increasing-subsequence著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – O(n^2) 这是一道经典的dp题目,大体上有两种解法,第一种是dp(时间复杂度O(n^2));第二种是dp+二分搜索(时间复杂度O(nlogn)),我们先介绍O(n^2)的解法。而第一种dp还可以分为Bottom-up和Top-down两种实现方式。 Bottom-up 我们定义数组dp[|nums|],dp[i]表示使用nums数组前i个元素且必须使用nums[i],能够构成的最长递增子序列的长度。那么有dp[i] = max(dp[j]) + 1, 其中nums[i] > nums[j], j < i,如果找不到这样的j,那么dp[i] = 1。 如果形象的描述算法的执行过程那就是使用双重循环,外循环使用变量i指向nums数组的每个元素,然后内循环用变量j扫描0~i。当nums[i] > nums[j]时,更新prev = max(prev, dp[j])。当内层循环扫描完毕,更新dp[i] = perv + 1。当双重循环执行完毕,dp数组中的最大值就是nums的最长递增子序列。 Top-down 自顶向下的思路使用递归来实现,我们定义一个辅助函数LIS(nums, curr),表示从nums数组的前curr个元素(包含curr)寻找LIS,并返回LIS的长度。那么我们需要利用更小的子问题求解当前问题,所以在for循环中又递归调用LIS。 为了避免重复求解,我们使用数组int[] cache记录求解过问题的答案。现在我们只需要循环的调用LIS函数,将各种问题的规模都交给LIS函数来求解,最大值就是数组nums的LIS。 全部代码如下: 解法2 – O(nlogn) 解法2是一个神奇的解法,我们一边读取nums数组,一边维护一个由nums形成的递增子序列 –…

Read more

241. 为运算表达式设计优先级

题目描述 给定一个含有数字和运算符的字符串,为表达式添加括号,改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, – 以及 * 。 示例 1: 输入: “2-1-1” 输出: [0, 2] 解释: ((2-1)-1) = 0 (2-(1-1)) = 2 示例 2: 输入: “2*3-4*5″ 输出: [-34, -14, -10, -10, 10] 解释: (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/different-ways-to-add-parentheses著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 这道题目采用分治法来解决,题目要求实现函数diffWaysToCompute,输入算数表达式input,输出不同的括号组合产生的计算结果列表ans。首先,我们扫描input寻找操作符即+、-和*。如果在input中找不到任何一个运算符,那么它就是操作数,我们将它转化为数字类型,加入到ans中返回即可。否则,input是包含运算符的表达式,情况变得复杂。 如果遇到了操作符,则将input分割成左右两部分,左右两部分可能还是一个计算表达式,我们继续将它送给函数diffWaysToCompute递归的处理,得到左右两部分返回值leftOpnds与rightOpnds。我们将leftOpnds和rightOpnds按照操作符optr做笛卡尔积,将运算结果加入到ans中就完成了对运算符的处理,我们编写了函数calculate(char optr, List leftOpnds, List rightOpnds)来实现这个功能。 举一个例子,对于表达式input = “2*3-4*5″,先处理第一个运算符*,将input分割成左右两个表达式”2″和”3-4*5″。假设我们已经知道了”3-4*5″能产生结果列表[-5, -17](后面会说怎么算出来的)。那么将2与[-5, -17]做乘法就能得到[-10,…

Read more

140. 单词拆分 II

题目描述 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。 说明: 分隔时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。 示例 1: 输入:s = “catsanddog”wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]输出:[  “cats and dog”,  “cat sand dog”] 示例 2: 输入:s = “pineapplepenapple”wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]输出:[  “pine apple pen apple”,  “pineapple pen apple”,  “pine applepen apple”]解释: 注意你可以重复使用字典中的单词。 示例 3: 输入:s = “catsandog”wordDict = [“cats”, “dog”, “sand”, “and”,…

Read more

挂载OpenWrt系统到外部设备

背景 一般路由器提供的跟分区“/”比较小,当安装几个软件后就会导致磁盘空间不足,为了扩容我们可以挂载外部的存储设备,例如U盘、SD卡、移动硬盘等。下面我以GL.iNet-AR750路由器为例,演示如何挂载外部SD卡。首先你需要确保你的外部设备被正确的分区,我的SD卡上面被分了3个分区,分别存储SWAP、系统和其他文件。如果没有被正确的分区,请安装fdisk然后分区。SWAP需要文件系统类型为swap、存储文件的文件系统选择ext4。下面是我已经分区好后的设备名称以及他们的用途: /dev/sda1 SWAP SWAP /dev/sda2 / 系统 /dev/sda3 /mnt/sda3 其他 我们首先用mount命令查看已经挂载的设备和挂载点: 可以看到目前跟分区“/”由设备/dev/mtdblock6挂载,我们接下来需要把它替换成/dev/sda2。 操作 1. 安装依赖 opkg update opkg install fdisk (可选,如果你没有分区) opkg install block-mount 2. 拷贝系统到SD卡 注意,/mnt/sda2是你SD卡上用来存储系统的路径,依据你的实际情况修改。 3. 编辑ROM上的fstab文件 使用命令vi /etc/config/fstab修改文件的内容,这个fstab存储在路由器的ROM上而不是SD卡上。下面是我的路由器上面fstab中的内容,按照你自己的情况编辑,确保option target ‘/mnt/sda2’下面的option enabled设置为1,并且把挂载到/mnt/sda2的目录更改为/,然后增加两个option。然后删除swap和另一个mount配置,只保留global和挂载到/mnt/sda2的那一个配置。 修改前: 修改后: 如果你不小心搞坏了fstab文件,可以使用命令block detect > /etc/config/fstab来重新生成。 4. 重启后修改SD卡的fstab文件 重启后,修改的fstab将会生效。注意,现在我们有了两份fstab文件,一份存储在路由器的ROM中,另一份存储在SD卡中。系统首先读取ROM上的fstab文件来挂载块设备,然后会读取SD卡的fstab挂载块设备。因此当系统启动完成后,我们还需要修改SD卡的/etc/config/fstab文件。 修改前: 修改后: 然后再次重启系统,我们的修改已经彻底完成。使用df -h命令查看一挂载的分区和容量: 使用free命令查看SWAP: 5. 优化 – 修改swappness 我们希望当内存容量达到很高的阈值才使用swap,以防止系统因为频繁换页导致卡顿。修改文件/etc/sysctl.conf,追加vm.swappiness =…

Read more

139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明: 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1: 输入: s = “leetcode”, wordDict = [“leet”, “code”]输出: true解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。 示例 2: 输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。注意你可以重复使用字典中的单词。 示例 3: 输入: s = “catsandog”, wordDict =…

Read more

120. 三角形最小路径和

题目描述 给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如,给定三角形: [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。 说明: 如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/triangle 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 这道题目使用dp来求解,通过之前求得小规模的问题计算更大规模的问题。题目提到“每一步只能移动到下一行中相邻的结点上”,我们把题目给定的样例按照最左端对其,我们将这个数组记为triangle。 [ [2], [3,4], [6,5,7], [4,1,8,3] ] 我们在triangle数组中找一个比较general的case,对于元素8,它的上一行只有5和7能够走到8。也就是说当元素处于第i行第j列时(i,j从0计数),只能从i-1, j-1与i-1, j的位置走来。我们就可以定义数组dp[i][j]表示自顶向下走到第i, j位置时最小路径和,有dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]。 需要注意一点的是越界处理。当i=0,j=0时,自顶向下只有triangle[0][0]一个元素,取dp[i][j] = trangle[i][j];当j=0时,dp[i-1][j-1]是越界的,取dp[i][j] = dp[i-1][j] + triangle[i][j];当j=i时,dp[i-1][j]是越界的,取dp[i][j] = dp[i-1][j-1] + triangle[i][j]。 在实现时,我们采用Bottom-up的解法,声明与triangle数组同型(大小一致)的数组dp,递增变量i,j,将变量带入公式循环更新dp数组,最终的答案为min(dp[dp.length – 1])。在实现中,为了避免扫描dp[dp.length – 1]来求最小值,我们使用临时变量来存储当前遇到的最小值。 解法1优化 题目提到“如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。”,下面我们就来优化解法1的空间复杂度。通过观察dp公式,可以看出dp[i][j]仅依赖于dp[i-1][j-1]与dp[i-1][j]。那我们可以声明大小为dp[2][|triangle|]的数组,循环使用dp[0]与dp[1]。dp[0]表示上一轮计算结果,dp[1]表示本轮计算结果,当完成一轮迭代后交换dp[0]与dp[1]。

Read more

70. 爬楼梯

题目描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 示例 1: 输入: 2输出: 2解释: 有两种方法可以爬到楼顶。 1 阶 + 1 阶 2 阶 示例 2: 输入: 3输出: 3解释: 有三种方法可以爬到楼顶。 1 阶 + 1 阶 + 1 阶 1 阶 + 2 阶 2 阶 + 1 阶 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/climbing-stairs著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 这是一道简单的DP题目,是DP的应用之一 – 计数。给定一个台阶数目n,我们可以从n-1节台阶跳一步到达第n节;也可以从n-2跳两步到达第n节。我们把到达第n节台阶的爬楼梯方法记为dp[n],那么有dp[n] = dp[n-1]…

Read more

Java线程池概述

内容提要 最近,在公司做了几次技术分享,将slides上的内容整理成博客。本文的主要内容包括如下几个部分: 背景 Java线程池类型 线程池参数与使用实例 ThreadPoolExecutor实现 总结 本文将主要讲解ThreadPoolExecutor的使用、参数解释以及内部实现,对于ScheduedThreadPoolExecutor与ForkJoinPool只会简单提及。 一、背景 我们为什么需要使用线程池,直接new Thread岂不是很方便?如果我们在编写Demo或者开发个小型的Java应用程序,那么这种方法的确没什么问题。但是如果我们在开发大型的企业级应用,那么直接创建线程是一种糟糕的实践,会造成如下问题: 直接new Thread使创建线程的代码分散在项目各个地方,不利于维护(指代码上的) 当你的Runnable执行完毕线程无法复用造成资源浪费 直接new Thread不遍于控制线程的数量(启动多少个线程不受限制,想new就new) 那么这些问题有什么缺点呢?对于第一条是显然的。对于第二条,你可能以为创建线程的代价和创建一个对象的代价差不多,但除了创建对象外,还可能会在OS层面创建线程(这取决于JVM实现)。线程是一种宝贵的资源(每个线程有自己的调用栈、PC、IR),频繁创建销毁开销很大。对于第三条,创建大量的线程显而易见会带来昂贵的调度开销,要知道线程调度需要做保留现场、恢复现场等一些列操作。 二、Java线程池类型 为了实现不同类型的线程池,定义了三个接口:Executor、 ExecutorService 、ScheduledExecutorService接口,他们都位于java.util.concurrent包下。 Executor:能够执行Runnable的简单接口,只含有execute一个方法 ExecutorService :继承自Executor,添加了shutdown、submit、invokeAll等方法,以支持异步执行 ScheduledExecutorService:继承自ExecutorService,支持周期性地执行任务 Java线程池目前有三个实现,分别是ThreadPoolExecutor、ScheduledThreadPoolExecutor、ForkJoinPool。ThreadPoolExecutor可以根据构造方法实现不同类型的线程池(或者使用Executors类),但是不支持定时任务;ScheduledExecutorService支持定时执行;ForkJoinPool利用Fork-join框架,实现了work-stealing,对于执行时间差异很大的任务使用该类型线程池能够实现负载均衡。图1展示了他们直接的继承/实现关系。 三、线程池参数与使用实例 下面我们分别介绍这三个线程池的构造方法,这样我们才能够知道如何创建线程池。因为每种线程池都有多个构造方法,我们只介绍参数最复杂的那一个。 1. ThreadPoolExecutor 构造方法 corePoolSize: 当线程池中线程数量小于corePoolSize, 即使这些线程是空闲的,也不会被销毁。但如果调用方法allowCoreThreadTimeOut(true),表示核心线程池的线程在没有任务到达的时候,keepAliveTime时间后销毁。 maximumPoolSize:限定线程池最大数量。当线程池中线程数达到corePoolSize时,且任务队列workQueue以及满了,就会创建新线程直到数量达到maxiumPoolSize。注意,如果workQueue是一个无界队列(unbounded)时,该参数是无效的,因为你无论添加多少任务workQueue都不会满。 keepAliveTime:当线程数大于corePoolSize时,多余线程的存活时间。 unit:keepAliveTime参数的时间单位 workQueue:用于存放尚未执行任务的队列,元素必须是Runnable。workQueue必须是一个阻塞队列,例如LinkedBlockingQueue、ArrayBlockingQueue。 threadFactory:创建线程时所使用的线程工厂,默认为Executors.defaultThreadFactor。如果你想让创建的线程带有自定义name或者优先级时,可以传入自己实现的线程工厂。 handler:在某种情况下(下面会提到),无法提交任务所执行的处理策略。目前有如下内置的handler实现。 AbortPolicy 直接拒绝新任务,并抛出RejectedExecutionException异常 CallerRunsPolicy 用当前线程的execute方法执行被拒绝的任务,如果执行器已经关闭则丢弃任务 DiscardPolicy 默默地丢弃新到的任务 DiscardOldestPolicy 丢弃最老的一个未执行的任务并执行当前任务 线程池逻辑 图2描述了线程创建与入队的逻辑。如果从线程创建和入队的角度分别观察,能够整理出如下规则。 线程创建规则 当线程池中线程数量小于corePoolSize时,将会创建新线程(即使之前创建当线程处于空闲) 如果线程数量大于等于corePoolSize且小于maximumPoolSize时,只有队列已满才会创建新线程 入队规则 如果线程数量小于corePoolSize,优先创建线程而不入队…

Read more

312. 戳气球

题目描述 有 n 个气球,编号为0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。 现在要求你戳破所有的气球。每当你戳破一个气球 i 时,你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后,气球 left 和气球 right 就变成了相邻的气球。 求所能获得硬币的最大数量。 说明: 你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的所以并不能被戳破。 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100 示例: 输入: [3,1,5,8] 输出: 167 解释: nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []   coins = 315 + 358…

Read more