15. 三数之和

题目描述 给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。 注意:答案中不可以包含重复的三元组。 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ] https://leetcode-cn.com/problems/3sum/ 解法1 首先对原数组nums进行排序, 用指针i指向nums的每个元素, 然后另指针j=i+1, k=|nums|-1. 指针j与k相向而行, 直到nums[i]+nums[j]+nums[k] == 0我们就找到了一个解, 此时需要继续相向而行直到k>=j. 将数组排序可以把算法的时间复杂度降低到O(n^2). 若不对数组排序, 为了寻找j, k使得nums[i]+nums[j]+nums[k] == 0, 需要使用双重循环遍历nums, 这样会使复杂度达到O(n^3). 因为题目要求“不可以包含重复的三元组”, 这就需要我们一旦找到符合条件的i, j, k. 就需要跳过nums中相同的元素(代码中被标记的部分), 以避免寻找重复的解. 例如…

Read more

Hive源码阅读-3-hive启动

当我们在终端中输入hive时,会执行位于$HIVE_HOME/bin/hive的一个脚本,这个脚本又会执行bin下面的ext目录中的每个sh脚本。在ext目录下面包含了很多脚本,用于启动各种Hive所依赖的服务。 这些脚本中cli.sh是我们关注的入口,中cli.sh中会调用hadoop jar命令,启动”org.apache.hadoop.hive.cli.CliDriver”。 CliDriver的第620行是main函数,在这里实例化CliDriver并调用run方法。 在CliDriver的构造函数中,会获得SessionState实例。SessionState封装了与会话相关的公共数据。SessionState同样为线程静态会话对象提供支持,这样就可以在代码的任何地方访问Session,并且能够获得配置信息。 每个线程都与SessionStates相关联,SessionStates包含SessionState与HiveConf实例。 SessionStates实例化后,state与conf变量都为空。当CliDriver调用ss.get方法获取一个与线程关联的SessionStates,会得到空的state变量。CliDriver发现state为空,会创建Configuration实例。 当CliDriver实例化完成后,会执行run方法。在run方法中实例化OptionsProcessor、初始化Log4j、创建CliSessionState。其中CliSessionState继承自SessionState,CliSessionState添加了database、execString、filename等属性。 在创建CliSessionState时,需要传递HiveConf实例。HiveConf继承自hadoop的Configuration类。HiveConf的构造函数需要SessionState.class来获取hiveJar路径(“apache-hive-1.2.1-bin/lib/hive-exec-1.2.1.jar”)。 当CliSessionState实例化完成后,将该实例传递给SessionState.start来启动session。Session启动时,首先将CliSessionState关联到该线程当SessionStates当state变量上. 然后调用getMSC获取SessionHiveMetaStoreClient实例。IMetaStoreClient接口包含获取数据库名、表名、分区信息等获取元数据等方法. 当Session启动后,CliDriver的executeDriver方法会被调用. 在这个方法中,还会初始化另一个CliDriver实例,接下来获取用户输入的SQL语句,将SQL语句传递给CliDriver的processLine处理. processLine方法将会把用户输入的SQL按照分号”;”拆分,每个SQL称为oneCmd. oneCmd可能是被‘\’修饰的换行SQL中其中的一行,所以需要拼接. 拼接的完整SQL存入command变量中,交给processCmd方法处理. 在processCmd方法中,获取CliSessionState实例,将即将被执行的command存入Session的lastCommand变量, 以保存上一条执行的SQL. command不光是SQL,也可能是exit、quit等命令, 还可能是一条由!开头的shell命令, 在这里我们只关注SQL. SQL将会继续交给processLocalCmd方法处理, processLocalCmd需要待执行的SQL-cmd、CommandProcessor – proc与CliSessionState – ss. 如果proc是Driver的实例, 那么就会把待执行的SQL交给org.apache.hadoop.hive.ql.Driver的run方法执行. 下图显示出了从CliDriver.main开始到Driver.run的调用栈. 本文分析了从键入hive命令开始,到接受待执行到SQL语句的过程. SQL语句的实际执行交由Driver的run方法负责, 下一章我们从分析Driver类开始.

Read more

9. 回文数

题目描述 判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 示例 1: 输入: 121 输出: true 示例 2: 输入: -121 输出: false 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3: 输入: 10 输出: false 解释: 从右向左读, 为 01 。因此它不是一个回文数。进阶:你能不将整数转为字符串来解决这个问题吗? https://leetcode-cn.com/problems/palindrome-number/ 解法 我们按照进阶的要求,不将整数转化为字符串。代码模板中,变量x是int类型的。那么,将其反转结果使用long类型存放是不会溢出的。题目提到了一个case为“-121”,逆序读“121-”不是回文串。那么我们就可以推测,负数一定不是回文数。 我们按照“7.整数反转”这道题的技巧,判断反转后的数字与原数字是否一致来判定是否为回文数字即可。

Read more

7. 整数反转

题目描述 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例 1: 输入: 123 输出: 321  示例 2: 输入: -123 输出: -321 示例 3: 输入: 120 输出: 21 注意: 假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231,  231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。 https://leetcode-cn.com/problems/reverse-integer/ 解法 首先说明一点,如果直接转成StringBuffer,然后reverse以下再转成int就没意思了。我们尽可能不要使用这种straightforward的方法去做,才能够学到东西。 变量x存放了要被反转的数字,假设x=123.我们让x对10取余就能获得末尾数字,然后再另x=x/10,直到x为0. 例如:123%10==3,123->12; 12%10==2, 12->1; 1%10==1, 1->0循环结束。让我们对取过来对数字3、2、1记为n,分别带入公式result = result*10 + n,其中result初值为0。列如:分别带入3、2、1,0*10+3==3;3*10+2==32;32*10+1==321。 这样,我们通过一次循环就能逆序取出x的各位数字,然后带入result = result*10 + n就能得到逆序后的数字。还有一点是,题目要求发生溢出返回0。为了能够判定溢出,我们就要用比int范围更广的类型来存储逆序后的结果。每次循环,都要判定result变量是否小于Integer.MIN_VALUE或大于Integer.MAX_VALUE。

Read more

8. 字符串转换整数 (atoi)

请你来实现一个 atoi 函数,使其能将字符串转换成整数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。 当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。 该字符串除了有效的整数部分之后也可能会存在多余的字符,这些字符可以被忽略,它们对于函数不应该造成影响。 注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换。 在任何情况下,若函数不能进行有效的转换时,请返回 0。 说明: 假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围,请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。 示例 1: 输入: “42” 输出: 42 示例 2: 输入: ” -42″ 输出: -42 解释: 第一个非空白字符为 ‘-‘, 它是一个负号。   我们尽可能将负号与后面所有连续出现的数字组合起来,最后得到 -42 。 示例 3: 输入: “4193 with words” 输出: 4193 解释: 转换截止于数字 ‘3’ ,因为它的下一个字符不为数字。 示例 4: 输入: “words and 987” 输出:…

Read more

最长公共子串

在计算机科学中,最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的,而子串却必须是。 https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E4%B8%B2 解法1 – 动态规划 Wiki中提到要寻找最长公共子串,可以在两个字符串中所有的前缀组合中寻找最长的公共后缀。 例如:S1=”ABAB”, S2=”BABA”。那么S1与S2的所有前缀组合有(A, B) (A, BA) (A, BAB), (A, BABA), …, (ABAB, BABA)。我们可以使用一个矩阵来描述所有前缀的组合,表头代表两个字符串,表中的数值代表两个前缀的最长后缀。表头中的双引号代表空串,因为空串是任何字符串的前缀。 “” A B A B “” 0 0 0 0 0 B 0 0 1 0 1 A 0 1 0 2 0 B 0 0 2 0 3 A 0 1 0 3 0 我们很容易我们可以填好S1或S2只取一个字符后与另一个字符串的最长公共后缀,如果相同则填1,不同填0。那么如果S1或S2取两个字符与另一个字符串的最长公共后缀怎么求呢?我们可以看两个前缀最后一个字符,如果不相同那么该位置肯定是0,因为公共子串要求相同的字符连续。如果两个前缀最后一个字符相同,我们再对两个前缀各往回看一个字符,也就是该位置的斜上方。我们用斜上方的数值+1填入矩阵即可。 总结成公式也就是:…

Read more

5. 最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1: 输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 2: 输入: “cbbd” 输出: “bb” https://leetcode-cn.com/problems/longest-palindromic-substring/ 解法1 暴力法很容易想到,我们使用双层循环固定字串的起止位置,然后对字串判断是否为回文串。双层循环的时间复杂度是O(n^2),再嵌套一个回文判断循环O(n),时间复杂度为O(n^3)。但是这里,我们不打算使用暴力法,因为很容易想到,码代码就好了。 我们在这里使用了一种方法,我称之为中心扩展法,那么我们先来定义中心。中心是由单个字符或连续多个相同的字符组成的子串。我们第一次扫描,找到字符串所有的中心。然后遍历每个中心的左右两边的字符,如果相同就继续扩展直到遇到边界或两边字符不同,这样我们就找到了一个回文串。题目要求最长回文串,我们就遍历每个中心,都做相同的扩展操作,选取找到的最长的回文串既是答案。需要特殊注意的是,中心本身也是回文串,也是潜在的答案。 代码中我们使用List<int[]>来存放找到的中心列表,int[0]与int[1]分别是中心的起止索引,都是闭区间。 解法2 方法分析 解法1是我自己想的,解法2、3都是源于LeetCode官方题解。解法2首先对字符串s逆序(reverse),记为s’。我们对字符串s与s’求最长公共子串。 例如,s=”acbcd”, s’=”dcbca”。求s与s’的最长公共子串为”cbc”,在这个例子中,这样的方法成功的求出了答案。我们再举一个例子,s=”abcdxydcba”, s’=”abcdyxdcba”。s与s’的最长公共子串是”abcd”,这显然不是回文子串。 问题出在哪呢?LeetCode题解说道“当s的其他部分中存在非回文子串的反向副本时,最长公共子串法就会失败”。我们来分析下,正是因为s中存在了非回文子串的反向副本,导致非回文子串出现在s’中。我们对s与s’求最长公共子串,也就把非回文子串取了出来。 举例分析:s=”[abcd]xy[dcba]”, s’=”[abcd]yx[dcba]”。s中第一个括号是[abcd],他的反向副本[dcba]同样在s中出现了。我们观察s中第二个中括号[dcba],在对s进行逆序操作后跑到了s’中第一个括号中。这样,我们对s与s’求最长公共子串就得到了错误的”abcd”。 那我们如何修正这样对情况,使得这个方法正确呢?我们只需要确保找到的最长公共子串的索引(indexOf)与最长公共子串的逆序的索引相同,就能保证找到的子串是反向的。(我认为这与判断找到的最长公共子串是否是回文串的条件是等价的,不对的话望指正) 作者疑问 还有一个问题,真的只需要寻找最长公共子串,并且确定最长公共子串的索引与其逆序的索引相同就够了吗? 例如 s=”abacdfgdcaba”, s’=”abacdgfdcaba”。s与s’的最长公共子串为abacd,但其在s中的索引与其反向索引不同,一个是0,一个是7,所以该子串不是最长回文子串。可是,方法二所说的求s与s’的最长公共子串可只有一个啊,接下来没法玩了啊!!!。 那该方法说的是不是不准确啊,应该找出s与s’所有的公共子串,然后所有公共子串的索引与其逆序的索引是否相同。这么做不就和暴力法差不多了吗?暴力法是找到s所有的子串判断是否为回文串。这个方法是找到s与s’所有的公共子串,判断索引与其逆序的索引是否相同。 代码 好吧,带着疑问写代码。我的做法是求出s与s’所有的公共子串,然后求其索引与反向索引是否相同。运行了几个case答案是正确的,但是粘贴到LeetCode提示超时。这个方法不太可取,创建了大量的临时变量,还包含递归函数。 解法3 解法三使用动态规划,这个方法源自LeetCode官方题解。 状态转移方程:P(i, j) = S[i] == S[j] and P(i + 1, j – 1)…

Read more