LeetCode题目解答——Easy部分

LeetCode题目解答——Easy部分 LeetCode最近很火,我以前不太知道有这么一个很方便练习算法的网站,直到大概数周前同事和我说起,正好我老婆要找工作,而根据同事的理论,LeetCode的题目是必须攻破的第一道关卡。我虽说又不找工作,但是纯粹拿来练手和学习,觉得很多题目都挺有趣的。现在已经做了三分之一,我会把我的解答分几次放上来。这里是第一部分,难度为easy的题目。

我觉得做这样的题目很有帮助,但也要有正确的目的。有些题是锻炼思维的,我比较喜欢;有的题目是考察问题分析得仔细不仔细,各种corner case,我觉得没太大意思;还有一些题目则是要求具备一些算法数据结构之外的知识,比如罗马数字什么的,这样的题目就更不好了。

(点击表格中题目的名称进入解答详情)

Palindrome Number 28.8% Easy
ZigZag Conversion 23.4% Easy
Valid Sudoku 27.6% Easy
Add Binary 25.5% Easy
Valid Parentheses 28.2% Easy
Valid Palindrome 22.2% Easy
Balanced Binary Tree 32.5% Easy
Valid Number 11.0% Easy
Symmetric Tree 31.6% Easy
String to Integer (atoi) 14.2% Easy
Same Tree 41.8% Easy
Binary Tree Level Order Traversal 30.6% Easy
Binary Tree Level Order Traversal II 31.0% Easy
Roman to Integer 33.9% Easy
Reverse Integer 39.8% Easy
Remove Nth Node From End of List 29.3% Easy
Remove Element 33.0% Easy
Remove Duplicates from Sorted List 34.7% Easy
Climbing Stairs 34.0% Easy
Remove Duplicates from Sorted Array 32.2% Easy
Plus One 31.4% Easy
Path Sum 30.4% Easy
Pascal's Triangle II 30.1% Easy
Pascal's Triangle 31.1% Easy
Minimum Depth of Binary Tree 29.4% Easy
Merge Two Sorted Lists 33.2% Easy
Merge Sorted Array 31.8% Easy
Maximum Depth of Binary Tree 43.8% Easy
Longest Common Prefix 27.0% Easy
Count and Say 26.7% Easy
Length of Last Word 29.0% Easy
Implement strStr() 21.9% Easy

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 '.'.

LeetCode题目解答——Easy部分

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.

LeetCode题目解答——Easy部分

Each column must have the numbers 1-9 occuring just once.

LeetCode题目解答——Easy部分

And the numbers 1-9 must occur just once in each of the 9 sub-boxes of the grid.

LeetCode题目解答——Easy部分

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的关系式,也可以寻找任一行对于它上一行的递推式。还不清楚的,可以去看看杨辉三角的维基百科,特别是这个:

LeetCode题目解答——Easy部分

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;
    }
}

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

9 comments

  1. 李硕 说道:

    开始学习

  2. tao 说道:

    PlusOne 程序有问题

    System.arraycopy(,,,,digits.length-1)改为System.arraycopy(,,,,digits.length)

  3. ctliu3 说道:

    其实我觉得这些题目的cornor case都算合理,这些平时写算法就是要特别注意的。
    罗马数字这种题目放面试中,只要面试官给出罗马到数学的转移规则,也是合理的,可以考察一个人掌握新知识的能力。
    LZ代码不少部分太冗长了….

    • 四火 说道:

      说的是,所以我才需要更多练习。哪些太冗长了,指出来我也学习一下。。。

      • ctliu3 说道:

        既然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

        • 四火 说道:
          多谢。
          #Palindrome Number,说得对
          #Add Binary,是的,文中我也说了
          #Valid Number,对,用DFA是最清楚的做法
          #Symmetric Tree, 这个没啥大的区别吧,我觉得左右分支分开存放更清楚
          #Remove Nth Node From End of List,我想了一下,确实可以用O(n),做法就是用两个指针,一个快指针fast,一个慢指针slow,让fast先走距离n,然后fast和slow再每次一步各自往前走,之间距离始终保持n,等到快指针走到底的时候,慢指针的位置就是要动刀的位置
          #Length of Last Word, 确实,实际上的trim+split本身复杂度要大于手动循环,我是图省事了

           

发表评论

电子邮件地址不会被公开。

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Preview on Feedage: