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