有效的括号序列

题目 给定一个字符串所表示的括号序列,包含以下字符: '(', ')', '{', '}', '[' and ']', 判定是否是有效的括号序列。 样例 括号必须依照 "()" 顺序表示, "()[]{}" 是有效的括号,但 "([)]"则是无效的括号。 分析 很简单的一道题目,用栈进行匹配即可。 代码 public class Solution { /** * @param s: A string * @return: whether the string is a valid parentheses */ public boolean…

422. 最后一个单词的长度

题目 给定一个字符串, 包含大小写字母、空格' ',请返回其最后一个单词的长度。 如果不存在最后一个单词,请返回 0 。 分析 先不考虑特殊值,从后往前找,首先跳过尾部所有的空格字符,找到字符串中最后一位字母,记下坐标last,接着从last往前找空格,只要找到了空格i,那么last - i就是最后一个单词的长度。 也可能找不到空格,说明这个单词是从头到last都是字母,那么单词的长度就应该是last + 1。 然后再考虑蛋疼的null,以及单词数小于1的情况。 代码 public class Solution { /** * @param s: A string * @return: the length of last word */ public int lengthOfLastWord(String s) { // write your code here if…

415. 有效回文串

题目 给定一个字符串,判断其是否为一个回文串。只考虑字母和数字,忽略大小写。 样例 "A man, a plan, a canal: Panama" 是一个回文。 "race a car" 不是一个回文。 分析 先除去字母和数字以外的字符, 然后将大小写统一, 此时,只需要首尾互相匹配,若均一致,则是回文 代码 public class Solution { /** * @param s: A string * @return: Whether the string is a valid palindrome */ public boolean isPalindrome(String s)…

413. 反转整数

题目 将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 (标记为 32 位整数)。 样例 给定 x = 123,返回 321 给定 x = -123,返回 -321 分析 每次模10,就能得到末尾,然后除10,就能逐位取到x的数字;将取得的数字乘以10,不断累加,就能得到逆序的数字。 负数可以记下符号位,然后当成正数处理,最后还原符号位 如果颠倒后溢出,直接返回0,如何判断溢出?只要累计的值超过Integer.MAX_VALUE,就溢出了,可以用long类型存储计算结果 代码 public class Solution { /** * @param n: the integer to be reversed * @return:…

408. 二进制求和

题目 给定两个二进制字符串,返回他们的和(用二进制表示)。 http://www.lintcode.com/zh-cn/problem/add-binary/ 分析 二进制加法,主要考虑一下两个字符串长度不等的处理,以及进位。 代码 public class Solution { int toInt(char c) { return c == '1' ? 1 : 0; } char toChar(int i) { return i == 0 ? '0':'1'; } /** * @param a: a number * @param b: a number * @return: the result */ public String…

397. Longest Continuous Increasing Subsequence

题目 给定一个整数数组(下标从 0 到 n-1, n 表示整个数组的规模),请找出该数组中的最长上升连续子序列。(最长上升连续子序列可以定义为从右到左或从左到右的序列。) http://www.lintcode.com/zh-cn/problem/longest-continuous-increasing-subsequence/ 分析 虽然叫上升序列,但其实升、降都可以,具体的差值不用关心,只要描述出增长的趋势就可以了。 因此,可以先将原始数组做一遍处理,计算出相邻两个元素的差值,产生一个新数组,由于不必关心实际数值,新数组中,可以使用1或-1来表示相邻的大小关系,至于相等的元素,都应当忽略。 这样一来,我们就会得到一个完全由1或-1组成的序列,计算连续的相同数字个数,取最大值,就是我们要求的连续增长子序列的大小。 代码 public class Solution { List merge(List A){ List result = new ArrayList<>(); int…

389. 判断数独是否合法

题目 请判定一个数独是否有效。 该数独可能只填充了部分数字,其中缺少的数字用 . 表示。 http://www.lintcode.com/zh-cn/problem/valid-sudoku/ 分析 判断数独填充是否有效,主要看3方面: 每一行内,填充的数字不重复 每一列中,填充的数字不重复 每一个小的九宫格中,填充的数字不重复 暴力枚举即可,逐个考察九宫格中的每一个元素,如果该元素为'.',则合法,继续下一个。 如果格子里是数字,就要进行三方面的判断,分别用三个独立的函数判断即可。 代码 public class Solution { boolean isValidRow(char[][] board, int row, int col) { for(int i=0; i…

376. 二叉树的路径和

最近忙着做React分享研究,好久没刷算法题了。 题目 给定一个二叉树,找出所有路径中各节点相加总和等于给定 目标值 的路径。 一个有效的路径,指的是从根节点到叶节点的路径。 http://www.lintcode.com/zh-cn/problem/binary-tree-path-sum/ 分析 几个重点: 限定了是从根节点到叶子节点的和 节点的值有可能是负数,因此如果到某个节点累计和超过目标值时,仍需继续探索 思路还是很清晰的,遍历这棵树,如果节点是叶子节点,则查看求和是否满足目标值要求,若满足,就找到一组解。若非叶子节点,则将当前节点的值保存到一个队列中,继续探索其子节点。 代码 /** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.…

373. 奇偶分割数组

题目 分割一个整数数组,使得奇数在前偶数在后。http://www.lintcode.com/zh-cn/problem/partition-array-by-odd-and-even/ 分析 很简单的一道题目,从后往前找奇数,从前往后找偶数,如果奇数的下标大于偶数的下标,则两者交换,继续重复该动作;否则表明无需再处理。 快速判断奇数、偶数,只需要考察 number & 0x01 == 0x01 是否成立 代码 public class Solution { boolean isOdd(int val) { return (val & 0x1) == 0x01; } int findNext(int[] array, int start, int end, int step, boolean isOdd)…

372. 在O(1)时间复杂度删除链表节点

题目 给定一个单链表中的一个等待被删除的节点(非表头或表尾)。请在在O(1)时间复杂度删除该链表节点。 Linked list is 1->2->3->4, and given node 3, delete the node in place 1->2->4 分析 题目中还给了一个例子,在1->2->3->4的单链表中,如果给了节点3的情况下,如何将链表原地更新成1->2->4 一般的单链表节点删除,我们都会从前一个节点开始更新,比如更新1->2-&…