[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于 tricky 的方法。我没有为了这个再更新，就让它们去吧。
LeetCode 最近很火，我以前不太知道有这么一个很方便练习算法的网站，直到大概数周前同事和我说起，正好我老婆要找工作，而根据同事的理论，LeetCode 的题目是必须攻破的第一道关卡。我虽说又不找工作，但是纯粹拿来练手和学习，觉得很多题目都挺有趣的。现在已经做了三分之一，我会把我的解答分几次放上来。这里是第一部分，难度为 easy 的题目。
我觉得做这样的题目很有帮助，但也要有正确的目的。有些题是锻炼思维的，我比较喜欢；有的题目是考察问题分析得仔细不仔细，各种 corner case，我觉得没太大意思；还有一些题目则是要求具备一些算法数据结构之外的知识，比如罗马数字什么的，这样的题目就更不好了。
（点击表格中题目的名称进入解答详情）
Palindrome Number
【题目】Determine whether an integer is a palindrome. Do this without extra space.
【解答】Palindrome 指的是回文，而这里需要找的是回文数，指的是 1、121、34543 这样从左往右看和从右往左看都相等的数。先找到数字总共有几位，然后判断高位和低位是否相等，相等是回文数。getDigit 方法是用来取数 x 的第 i 位的数字的，i 从低到高记位，最低位为 1。
public class Solution {
public boolean isPalindrome(int x) {
if(x<0)
return false;
int quotient = x;
int digits = 0;
while (quotient!=0) {
quotient /= 10;
digits++;
}
for (int i=1; i<=digits; i++) {
int high = digits - i + 1;
int low = i;
if (getDigit(x, high) != getDigit(x, low))
return false;
}
return true;
}
private int getDigit(int x, int i){
if (i==1)
return x%10;
return (x / (int)Math.pow(10, i-1)) % 10;
}
}
ZigZag Conversion
【题目】The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N A P L S I I G Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
【解答】光看到这个题目我觉得没法理解这个题意啊，再多给几个 nRows 就好了。没办法去网上搜了一下，终于明白 ZigZag 是这样一种形式，比如在 nRows=4 的时候，它是：
P I N A LS IG YA HR P I
就是说，它从左往右是由一个个可重复的矩形单元构成的，每个矩形高是 nRows，宽是 nRows-2，字母在每个矩形中构成的规则是，先从上到下排最左边一列（比如上面的 PAYP），然后再从左下到右上排斜对角线（比如上面的 PALI）。
掌握了这样的信息以后，就好办了，建立一个二维数组 map 用来模拟存放这个东西，最后按行输出，跳过空字符即可（这里的逻辑还是有点绕的。当然，如果你能找到每一行关于字符在字符串中序号的通式，会简单得多）：
public class Solution {
public String convert(String s, int nRows) {
if (nRows == 1)
return s;
// each unit
int amountInUnit = nRows + nRows - 2;
int totalUnits = s.length() / amountInUnit;
if (s.length() % amountInUnit != 0)
totalUnits++;
// each unit is a rectangle
int rows = nRows;
int cols = totalUnits * (nRows - 1);
char[][] map = new char[rows][cols];
int i = 0;
while (i < s.length()) {
char ch = s.charAt(i);
// which unit, starts from 0
int unitNumber = i / amountInUnit;
// which postion in the unit, starts from 0
int posInUnit = i % (amountInUnit);
// if it's in the first column of the unit
int x, y;
if (posInUnit < nRows) {
x = posInUnit;
y = unitNumber * (nRows - 1);
} else {
x = nRows - 1 - (posInUnit + 1 - nRows);
y = nRows - x - 1 + unitNumber * (nRows - 1);
}
map[x][y] = ch;
i++;
} // while
// iterate and output
StringBuilder sb = new StringBuilder();
for (i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (map[i][j] != 0)
sb.append(map[i][j]);
}
}
return sb.toString();
}
}
Valid Sudoku
【题目】Determine if a Sudoku is valid, according to: Sudoku Puzzles – The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
A partially filled sudoku which is valid.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
【解答】我把 Sudoku 的规则贴在这里：
Each row must have the numbers 1-9 occuring just once.
Each column must have the numbers 1-9 occuring just once.
And the numbers 1-9 must occur just once in each of the 9 sub-boxes of the grid.
Click here for Help playing Online.
算法的具体做法是：先检查行规则，再检查列规则，最后检查每个 sub-box 规则。利用 Set 的 add 方法，根据返回值判定是否在 Set 里面已经存在这个字符了，这样就不需要省掉了调用 contains 方法。
另外，其实可以写得更简洁，用一个嵌套的双重循环就可以搞定，拿空间换时间，需要用三个二维数组分别表示行规则、列规则和 sub-box 规则的检查结果，而不是一个 Set 了，做法就是对每一个字符的坐标 (i,j)，分别算出在这三个数组中的位置并检进行重复性检查。
public class Solution {
public boolean isValidSudoku(char[][] board) {
HashSet<Character> set = new HashSet<Character>();
// check rows
for (int i = 0; i < board.length; i++) {
set.clear();
for (int j = 0; j < board.length; j++) {
if (board[i][j] != '.' && !set.add(board[i][j]))
return false;
}
}
// check columns
for (int j = 0; j < board.length; j++) {
set.clear();
for (int i = 0; i < board.length; i++) {
if (board[i][j] != '.' && !set.add(board[i][j]))
return false;
}
}
// check each sub box, there're p*q sub-boxes
int totalBoxes = board.length / 3;
for (int p = 0; p < totalBoxes; p++) {
for (int q = 0; q < totalBoxes; q++) {
set.clear();
for (int i = p * 3; i < p * 3 + 3; i++) {
for (int j = q * 3; j < q * 3 + 3; j++) {
if (board[i][j] != '.' && !set.add(board[i][j]))
return false;
}
}
}
}
return true;
}
}
Add Binary
【题目】Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
【解答】我是先循环 a 和 b 共同的子串，再单独处理余下的，但是写得看起来有点复杂了，其实可以用一个循环搞定（循环内部注意判断 a 或者 b 是否已经循环完成），循环次数等 a 和 b 中比较长那个的字符个数（还有一种思路是给短的那个字符串高位补零，补到两个字符串长度相等）。注意处理进位，特别是循环完成以后，如果还有进位要处理，需要在高位补 1：
public class Solution {
public String addBinary(String a, String b) {
int carry = 0;
String s = "";
int i, j;
for (i = a.length() - 1, j = b.length() - 1; i >= 0 && j >= 0; i--, j--) {
int sum = carry + a.charAt(i) - '0' + b.charAt(j) - '0';
if (sum == 0) {
s = '0' + s;
carry = 0;
} else if (sum == 1) {
s = '1' + s;
carry = 0;
} else if (sum == 2) {
s = '0' + s;
carry = 1;
} else {
s = '1' + s;
carry = 1;
}
}
if (i >= 0)
return prepend(s, a, i, carry);
else if (j >= 0)
return prepend(s, b, j, carry);
if (carry == 1)
return "1" + s;
return s;
}
private String prepend(String s, String a, int i, int carry) {
if (carry == 0)
return a.substring(0, i + 1) + s;
for (; i >= 0; i--) {
if (carry == 1) {
if (a.charAt(i) == '1') {
s = '0' + s;
carry = 1;
} else {
s = '1' + s;
carry = 0;
}
} else {
if (a.charAt(i) == '1') {
s = '1' + s;
carry = 0;
} else {
s = '0' + s;
carry = 0;
}
}
}
if (carry == 1) {
s = '1' + s;
}
return s;
}
}
Valid Parentheses
【题目】Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
【解答】
用栈来记录前半个括号的情况，注意不同情况下如果栈为空的处理：
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i=0; i<s.length(); i++) {
char ch = s.charAt(i);
if (ch=='(' || ch=='[' || ch=='{')
stack.push(ch);
if (ch==')' && (stack.empty() || stack.pop()!='('))
return false;
if (ch==']' && (stack.empty() || stack.pop()!='['))
return false;
if (ch=='}' && (stack.empty() || stack.pop()!='{'))
return false;
} // for
if (!stack.empty())
return false;
return true;
}
}
Valid Palindrome
【题目】Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
【解答】注意大小写，注意数字和字母都要算有效字符。
public class Solution {
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length()-1;
while (left<right) {
char l = s.charAt(left);
char r = s.charAt(right);
if ( !isValidChar(l) ) {
left++;
continue;
}
if ( !isValidChar(r) ) {
right--;
continue;
}
if (toLowerCase(l)!=toLowerCase(r))
return false;
left++;
right--;
}
return true;
}
private boolean isValidChar(char ch) {
return (ch<='z' && ch>='a') || (ch<='Z' && ch>='A') || (ch>='0' && ch<='9');
}
private char toLowerCase(char ch) {
if (ch>='a' && ch<='z')
return ch;
else
return (char) ( ch + ('z'-'Z') );
}
}
Balanced Binary Tree
【题目】Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
【解答】checkBalanced 方法用来递归检查是否平衡的，返回树高度，偷了个巧，如果发现不平衡抛出 TreeUnbalancedException 异常：
class TreeUnbalancedException extends RuntimeException {
public TreeUnbalancedException(String msg) {
super(msg);
}
}
public class Solution {
public boolean isBalanced(TreeNode root) {
try {
checkBalanced(root);
} catch (TreeUnbalancedException e) {
return false;
}
return true;
}
private int checkBalanced(TreeNode root){
if (root==null)
return 0;
int left = checkBalanced(root.left);
int right = checkBalanced(root.right);
if(left-right<-1 || left-right>1)
throw new TreeUnbalancedException( "" + (left-right) );
if (left>=right)
return left+1;
else
return right+1;
}
}
Valid Number
【题目】Validate if a given string is numeric.
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.
【解答】就是要考虑各种 case，题意上看我以为存在任意空格都没关系，但是实际上它要求只有字符串前后端空格是可以被容忍的，另外，解答判定检测的时候没有考虑到 16 进制。我偷了个懒，用正则表达式，不过表达式写得也不足够优雅：
public class Solution {
public boolean isNumber(String s) {
if(null==s)
return false;
return s.matches("^\\s*[\\+|\\-]{0,1}[0-9]*(([\\.]{0,1}[0-9]+)|([0-9]+[\\.]{0,1}))([e|E][\\+|\\-]{0,1}[0-9]+){0,1}\\s*$");
}
}
Symmetric Tree
【题目】Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1 / \ 2 2 / \ / \ 3 4 4 3
But the following is not:
1 / \ 2 2 \ \ 3 3
【解答】从上至下一层一层遍历，注意处理某一层全部为空的情况，全部为空意味着循环出口。
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null)
return true;
List<TreeNode> list = new ArrayList<TreeNode>();
list.add(root.left);
list.add(root.right);
boolean containsData = true;
while (containsData) { // BFS
containsData = false;
int left = list.size() / 2 - 1;
int right = left + 1;
List<TreeNode> leftList = new ArrayList<TreeNode>();
List<TreeNode> rightList = new ArrayList<TreeNode>();
while (left >= 0) {
TreeNode leftNode = list.get(left);
TreeNode rightNode = list.get(right);
if (leftNode == null && rightNode == null) {
left--;
right++;
continue;
}
containsData = true;
if (leftNode == null || rightNode == null
|| leftNode.val != rightNode.val)
return false;
left--;
right++;
leftList.add(0, leftNode.right);
leftList.add(0, leftNode.left);
rightList.add(rightNode.left);
rightList.add(rightNode.right);
}
list.clear();
list.addAll(leftList);
list.addAll(rightList);
}
return true;
}
}
String to Integer (atoi)
【题目】Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
spoilers alert… click to show requirements for atoi.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
【解答】各种 case，包括正负号、溢出、非法字符、空格等等（说实话这种 corner case 题我实在是不喜欢……）：
public class Solution {
public int atoi(String str) {
int digit = 0;
double number = 0;
str = str.trim();
boolean signed = false;
for (int i=str.length()-1; i>=0; i--) {
char ch = str.charAt(i);
if (ch>='0' && ch<='9') { // number
number += (ch-'0') * (int)Math.pow(10, digit);
digit++;
} else if(ch=='-' || ch=='+') {
if(signed)
return 0;
signed = true;
if (ch=='-')
number = -number;
} else {
number = 0;
digit = 0;
signed = false;
}
}
if (number>Integer.MAX_VALUE)
return Integer.MAX_VALUE;
if (number<=Integer.MIN_VALUE)
return Integer.MIN_VALUE;
return (int)number;
}
}
Same Tree
【题目】Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
【解答】没什么好说的，处理好空的情况：
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// only one node is null
if (p==null && q!=null)
return false;
if (p!=null && q==null)
return false;
// two nodes are both null
if (p==null && q==null)
return true;
// val
if (p.val!=q.val)
return false;
// neither node is null
if (isSameTree(p.left, q.left) && isSameTree(p.right, q.right))
return true;
return false; //p!=q
}
}
Binary Tree Level Order Traversal
【题目】Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
【解答】层序遍历：
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if (root==null)
return list;
List<TreeNode> level = new ArrayList<>();
level.add(root);
while (true) {
List<TreeNode> newLevel = new ArrayList<>();
List<Integer> item = new ArrayList<>();
for (TreeNode node : level) {
item.add(node.val);
if (node.left!=null)
newLevel.add(node.left);
if (node.right!=null)
newLevel.add(node.right);
}
list.add(item);
if (newLevel.isEmpty())
break;
level = newLevel;
} // while
return list;
}
}
Binary Tree Level Order Traversal II
【题目】Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[ [15,7], [9,20], [3] ]
【解答】和上面那道题很类似，把循环换成了递归，利用递归工作栈，让先遍历到的列表后插入：
public class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if (null==root)
return list;
List<TreeNode> nodes = new ArrayList<>();
nodes.add(root);
traverseLevel(list, nodes);
return list;
}
private void traverseLevel(List<List<Integer>> list, List<TreeNode> nodes) {
List<Integer> item = new ArrayList<>();
List<TreeNode> nextLevel = new ArrayList<>();
for (TreeNode node : nodes) {
item.add(node.val);
if (node.left!=null)
nextLevel.add(node.left);
if (node.right!=null)
nextLevel.add(node.right);
}
if (!nextLevel.isEmpty())
traverseLevel(list, nextLevel);
list.add(item);
}
}
Roman to Integer
【题目】Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
【解答】这道题我非常不喜欢，因为它考察本身有一个前提，就是你必须对罗马数字非常熟悉啊，罗马数字中字母的含义可以参考这个表，但是有一些规则却是必须要知道的，我知道大数的左侧表示减去，右侧表示加上，比如 IV 表示 5-1=4，VII 表示 5+2=7，但是，MCMXCVI 表示什么？C 表示 100，夹在两个 M（M 表示 1000）之间，那么这个 C 应该被减去还是被加上？这一点没搞清楚以前，题目是没法做的。
搞清楚其中的规律以后就好办了，罗马数字都有个特点，字母贡献值是正还是负，取决于它后面那个字母。即任意相邻两个字母，如果后面那个代表的数比前一个大，那么前一个表示的数最终贡献是要被减去的；反之，如果后面那个数比前一个小，那么前一个数是要被加到最终结果去的，因此 MCMXCVI 中的第一个 C 表示的含义是负 100：
public class Solution {
public int romanToInt(String s) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);
int result = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (i == 0) {
result += map.get(ch);
} else {
char prev = s.charAt(i - 1);
if (map.get(ch) > map.get(prev)) {
result += map.get(ch);
result -= map.get(prev) * 2;
} else {
result += map.get(ch);
}
}
}
return result;
}
}
Reverse Integer
【题目】Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
【解答】注意符号的处理：
public class Solution {
public int reverse(int x) {
int sign = 1;
if(x<0){
sign = -1;
x = -x;
}
int reversed = 0;
for (; x>0; x /= 10){
reversed = reversed*10 + x%10;
}
return reversed*sign;
}
}
Remove Nth Node From End of List
【题目】Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
【解答】用一个栈来解决问题，注意特殊情况，即要删掉的节点是 head：
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
Stack<ListNode> stack = new Stack<>();
ListNode node = head;
while (node!=null) {
stack.push(node);
node = node.next;
}
ListNode n1 = null;
ListNode n2 = null;
while (n>0) {
n2 = n1;
n1 = stack.pop();
n--;
}
if (stack.empty())
head = n2;
else
stack.peek().next = n2;
return head;
}
}
Remove Element
【题目】Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
【解答】没啥可说的：
public class Solution {
public int removeElement(int[] A, int elem) {
int pos = 0;
for (int a : A) {
if(a!=elem){
A[pos]=a;
pos++;
}
}
return pos;
}
}
Remove Duplicates from Sorted List
【题目】Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
【解答】两个指针，一个 current 始终保持只遍历非重复的元素，另一个 moving 一直向前移动，注意处理链表末端的情况：
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(null==head)
return null;
ListNode current = head, moving = head.next;
while (null!=moving) {
if (moving.val==current.val) {
moving = moving.next;
if (moving==null)
current.next = null;
}
else {
if (current.next!=moving)
current.next = moving;
current = moving;
moving = moving.next;
}
}
return head;
}
}
Climbing Stairs
【题目】You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
【解答】有好几种方法可以求解，我以前写文章分析过这个问题，就不展开了：
public class Solution {
// k=1, f(k)=1
// k=2, f(k)=2 [1,1] or [2]
// k=3, f(k)=f(3)=f(2)+f(1)
// k=n, f(n)=f(n-1)+f(n-2)
// Fibonacci sequence
public int climbStairs(int n) {
if(n==0)
return 0;
if(n==1)
return 1;
if(n==2)
return 2;
int last = 2, beforeLast = 1;
for (int i=3; i<=n; i++) {
int newOne = last + beforeLast;
beforeLast = last;
last = newOne;
}
return last;
}
}
Remove Duplicates from Sorted Array
【题目】Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].
【解答】双指针：
public class Solution {
public int removeDuplicates(int[] A) {
if (A.length<=1)
return A.length;
int i=0;
int j=1;
while (j<A.length) {
if (A[j]==A[i]) {
j++;
}
else {
i++;
A[i] = A[j];
j++;
}
}
return i+1;
}
}
Plus One
【题目】Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.
【解答】在从低位到高位循环的时候，不需要单独设置一个布尔变量 carry 表示是否有进位，因为逢 9 就要进位，而非 9 的情况，这个方法直接可以返回了。同样，在循环结束以后也不需要判断数组最高位是否为 0，能走完循环的，数组最高位肯定为 0，数组需要扩张一位：
public class Solution {
public int[] plusOne(int[] digits) {
for (int i=digits.length-1; i>=0; i--) {
if (digits[i]==9) {
digits[i]=0;
continue;
} else {
digits[i] += 1;
return digits;
}
}
// digits[0]==0
int[] newDigits = new int[digits.length+1];
newDigits[0] = 1;
System.arraycopy(digits, 0, newDigits, 1, digits.length);
return newDigits;
}
}
Path Sum
【题目】Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
【解答】没什么可说的，见代码：
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (null==root)
return false;
List<Integer> list = calculate(root, sum);
return list.contains(sum);
}
private List<Integer> calculate(TreeNode root, int sum) {
List<Integer> list = new ArrayList<Integer>();
if (root.left!=null) {
for (int num : calculate(root.left, sum)){
num += root.val;
list.add(num);
}
}
if (root.right!=null) {
for (int num : calculate(root.right, sum)){
num += root.val;
list.add(num);
}
}
if (root.left==null&&root.right==null){
list.add(root.val);
}
return list;
}
}
Pascal’s Triangle II
【题目】Given an index k, return the kth row of the Pascal’s triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?
【解答】有了 Pascal’s Triangle，这道题就很好解了，但是注意题目给的 example，它是从第 0 行开始计数的，而不是第 1 行：
public class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> list = new ArrayList<>();
list.add(1);
if (rowIndex==0)
return list;
for (int i=1; i<=rowIndex; i++) {
List<Integer> newList = new ArrayList<>();
newList.add(1);
int prev=0;
for (int num : list) {
if (prev==0){
prev = num;
continue;
}
newList.add(prev+num);
prev = num;
}
newList.add(1);
list = newList;
}
return list;
}
}
Pascal’s Triangle
【题目】Given numRows, generate the first numRows of Pascal’s triangle.
For example, given numRows = 5,
Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
【解答】原来这个 Pascal 三角就是杨辉三角，如果发现其中的规律就很好解了。可以寻找每一行对于行号 n 的关系式，也可以寻找任一行对于它上一行的递推式。还不清楚的，可以去看看杨辉三角的维基百科，特别是这个：
public class Solution {
public List<List<Integer>> generate(int numRows) {
// 0
List<List<Integer>> list = new ArrayList<>();
if (numRows==0)
return list;
// 1
List<Integer> first = new ArrayList<>();
first.add(1);
list.add(first);
if (numRows==1)
return list;
// >1
for (int i=2; i<=numRows; i++) {
List<Integer> latest = list.get(list.size()-1);
List<Integer> item = new ArrayList<>();
item.add(1);
int prev = 0;
for (int num : latest) {
if (prev==0) {
prev = num;
continue;
}
item.add(prev + num);
prev = num;
}
item.add(1);
list.add(item);
}
return list;
}
}
Minimum Depth of Binary Tree
【题目】Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
【解答】广度优先遍历。注意的是题目对于根节点为空的情况认为深度为 0，根节点的情况深度为 1。这其实是不正确的定义——参见树的维基百科，空树的深度应该是-1，而根节点的深度为 0：
The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path). This is commonly needed in the manipulation of the various self-balancing trees, AVL Trees in particular. The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has depth and height -1.
public class Solution {
public int minDepth(TreeNode root) {
if (null==root)
return 0;
List<TreeNode> list = new ArrayList<>();
list.add(root);
int depth = 1;
while (true) {
List<TreeNode> newList = new ArrayList<>();
for (TreeNode node : list) {
if (node.left==null && node.right==null)
return depth;
if (null!=node.left)
newList.add(node.left);
if (null!=node.right)
newList.add(node.right);
}
list = newList;
depth++;
}
}
}
Merge Two Sorted Lists
【题目】Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
【解答】注意头和尾的处理：
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (null==l1)
return l2;
if (null==l2)
return l1;
ListNode head, tail;
if(l1.val<=l2.val) {
head = tail = l1;
l1 = l1.next;
}
else {
head = tail = l2;
l2 = l2.next;
}
while (l1!=null&&l2!=null) {
if(l1.val<=l2.val){
tail.next = l1;
tail = l1;
l1 = l1.next;
}
else{
tail.next = l2;
tail = l2;
l2 = l2.next;
}
}
if (l1!=null) {
tail.next = l1;
}
if (l2!=null){
tail.next = l2;
}
return head;
}
}
Merge Sorted Array
【题目】Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m andn respectively.
【解答】
这道题如果从前往后把 B 归并到 A 的话，每次插入操作都会导致 A 中插入的数后面的所有数后移，但是如果是从后往前归并的话，这个低效的行为就巧妙地避免了，而且，归并完毕后，如果 A 中还有剩余元素，它们天然地躺在最小端，什么额外的事情都不需要做：
public class Solution {
public void merge(int A[], int m, int B[], int n) {
// for write to A
int cur = m+n-1;
// for A
int i = m-1;
// for B
int j =n-1;
for(; i>=0 && j>=0; cur--)
{
if(A[i] >= B[j])
{
A[cur] = A[i];
i--;
}
else
{
A[cur] = B[j];
j--;
}
}
while(j >=0) // don't need to do anything if i>=0
{
A[cur] = B[j];
cur--;
j--;
}
}
}
Maximum Depth of Binary Tree
【题目】Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
【解答】还是和前面求最小深度的题目提到的一样，在这里根节点被认为深度为 1，空树被认为深度为 0：
public class Solution {
int max = 0;
public int maxDepth(TreeNode root) {
if (null==root)
return 0;
traverse(root, 1);
return max;
}
private void traverse(TreeNode root, int depth) {
if (depth >= max)
max = depth;
if (null != root.left)
traverse(root.left, depth+1);
if (null != root.right)
traverse(root.right, depth+1);
}
}
Longest Common Prefix
【题目】Write a function to find the longest common prefix string amongst an array of strings.
【解答】注意入参空数组：
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length==0)
return "";
int i=0;
StringBuilder sb = new StringBuilder();
while (true) {
char ch = 0;
for (String s : strs) {
if (i==s.length())
return sb.toString();
if (ch==0 || ch==s.charAt(i))
ch = s.charAt(i);
else
return sb.toString();
}
sb.append(ch);
i++;
}
}
}
Count and Say
【题目】The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.
【解答】唯一需要注意的就是对于特殊值 n=1 的处理：
public class Solution {
public String countAndSay(int n) {
String s = "1";
if (n == 1)
return s;
for (int i = 2; i <= n; i++) {
char lastChar = 0;
int lastAmount = 0;
StringBuilder sb = new StringBuilder();
for (int j = 0; j < s.length(); j++) {
char ch = s.charAt(j);
if (0 != lastAmount && ch == lastChar)
lastAmount++;
else {
if (0 != lastAmount)
sb.append(lastAmount).append(lastChar);
lastChar = ch;
lastAmount = 1;
}
}
sb.append(lastAmount).append(lastChar);
s = sb.toString();
}
return s;
}
}
Length of Last Word
【题目】Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = "Hello World",
return 5.
【解答】留意尾部有空格的情况：
public class Solution {
public int lengthOfLastWord(String s) {
if (null==s || "".equals(s.trim()))
return 0;
String[] tokens = s.trim().split(" ");
return tokens[tokens.length-1].length();
}
}
Implement strStr()
【题目】Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
【解答】其实最好的解法应该是 KMP 算法，我的实现只是挨个遍历：
public class Solution {
public int strStr(String haystack, String needle) {
if(needle.length() == 0)
return 0;
for(int i = 0; i <= haystack.length() - needle.length(); i++) {
int n = 0;
while(n < needle.length() && haystack.charAt(i+n) == needle.charAt(n))
n++;
if(n == needle.length())
return i;
}
return -1;
}
}
文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》
开始学习
PlusOne 程序有问题
System.arraycopy（，，，，digits.length-1）改为 System.arraycopy（，，，，digits.length）
谢谢。已修正。
其实我觉得这些题目的 cornor case 都算合理，这些平时写算法就是要特别注意的。
罗马数字这种题目放面试中，只要面试官给出罗马到数学的转移规则，也是合理的，可以考察一个人掌握新知识的能力。
LZ 代码不少部分太冗长了….
说的是，所以我才需要更多练习。哪些太冗长了，指出来我也学习一下。。。
既然 LZ 回了我，那我就一道道看了..
Palindrome Number
getDigit() 可以不用，得到 x 的长度后，直接`/`和`%`就能得到 x 的首末数字了。
多了 getDigit() 起码多了 log 的复杂度
Add Binary
i >= 0 && j >= 0 只要换成 i >= 0 || j >= 0，然后改下处理细节，后面的 append() 函数就可以不用了
Valid Number
哈，这个实在太投机了.. 分类讨论或是 DFA 可能更好些
Symmetric Tree
这题从头到尾只要一个 Queue 就能搞定了，只要注意下结点放进队列的顺序就行了。你用了 2 个 List 处理每一层的情况，实际上我没觉得更清晰..
Remove Nth Node From End of List
可以 O(n) 而不是 O(2n)..
Length of Last Word
trim(), split() 复杂度 > length() + for
其它比如 List 的题用个哨兵结点，往往会省掉一些不必要的 corner check
牛逼
start study
good