Skip to content

四火的唠叨

一个纯正程序员的啰嗦

Menu
  • 所有文章
  • About Me
  • 关于四火
  • 旅行映像
  • 独立游戏
  • 资源链接
Menu

LeetCode 题目解答——Easy 部分

Posted on 11/03/201406/23/2019 by 四火

alg [Updated on 9/22/2017] 如今回头看来,里面很多做法都不是最佳的,有的从复杂度上根本就不是最优解,有的写的太啰嗦,有的则用了一些过于 tricky 的方法。我没有为了这个再更新,就让它们去吧。

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

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

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

Title
Acceptance
Difficulty
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 '.'.

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

PascalTriangleAnimated

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

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

×Scan to share with WeChat

你可能也喜欢看:

  1. LeetCode 题目解答—— 第 372 到 415 题
  2. LeetCode 题目解答—— 第 416 到 460 题
  3. LeetCode 题目解答——Medium 部分(下)
  4. LeetCode 题目解答——Medium 部分(上)
  5. LeetCode 题目解答——Hard 部分

10 thoughts on “LeetCode 题目解答——Easy 部分”

  1. 李硕 says:
    02/03/2017 at 1:33 PM

    开始学习

    Reply
  2. tao says:
    07/03/2016 at 8:16 PM

    PlusOne 程序有问题

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

    Reply
    1. 四火 says:
      07/04/2016 at 1:25 PM

      谢谢。已修正。

      Reply
  3. ctliu3 says:
    11/03/2014 at 1:11 PM

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

    Reply
    1. 四火 says:
      11/03/2014 at 1:32 PM

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

      Reply
      1. ctliu3 says:
        11/03/2014 at 3:01 PM

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

        Reply
        1. 四火 says:
          11/11/2014 at 1:55 AM
          多谢。
          #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 本身复杂度要大于手动循环,我是图省事了

           

          Reply
  4. datou says:
    11/03/2014 at 12:36 PM

    牛逼

    Reply
    1. 李硕 says:
      02/03/2017 at 1:33 PM

      start study

      Reply
      1. Anonymous says:
        04/17/2018 at 2:00 PM

        good

        Reply

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

订阅·联系

四火,啰嗦的程序员一枚,现居西雅图

Amazon Google Groovy Hadoop Haskell Java JavaScript LeetCode Oracle Spark 互联网 亚马逊 前端 华为 历史 同步 团队 图解笔记 基础设施 工作 工作流 工具 工程师 应用系统 异步 微博 思考 技术 数据库 曼联 测试 生活 眼界 程序员 管理 系统设计 缓存 编程范型 美股 英语 西雅图 设计 问题 面向对象 面试

分类

  • Algorithm and Data Structure (30)
  • Concurrency and Asynchronization (6)
  • System Architecture and Design (43)
  • Distributed System (18)
  • Tools Frameworks and Libs (13)
  • Storage and Data Access (8)
  • Front-end Development (33)
  • Programming Languages and Paradigms (55)
  • Testing and Quality Assurance (4)
  • Network and Communication (6)
  • Authentication and Authorization (6)
  • Automation and Operation Excellence (13)
  • Machine Learning and Artificial Intelligence (6)
  • Product Design (7)
  • Hiring and Interviews (14)
  • Project and Team Management (14)
  • Engineering Culture (17)
  • Critical Thinking (25)
  • Career Growth (57)
  • Life Experience and Thoughts (45)

推荐文章

  • 谈谈分布式锁
  • 常见分布式系统设计图解(汇总)
  • 系统设计中的快速估算技巧
  • 从链表存在环的问题说起
  • 技术面试中,什么样的问题才是好问题?
  • 从物理时钟到逻辑时钟
  • 近期面试观摩的一些思考
  • RSA 背后的算法
  • 谈谈 Ops(汇总 + 最终篇):工具和实践
  • 不要让业务牵着鼻子走
  • 倔强的程序员
  • 谈谈微信的信息流
  • 评审的艺术——谈谈现实中的代码评审
  • Blog 安全问题小记
  • 求第 K 个数的问题
  • 一些前端框架的比较(下)——Ember.js 和 React
  • 一些前端框架的比较(上)——GWT、AngularJS 和 Backbone.js
  • 工作流系统的设计
  • Spark 的性能调优
  • “残酷” 的事实
  • 七年工作,几个故事
  • 从 Java 和 JavaScript 来学习 Haskell 和 Groovy(汇总)
  • 一道随机数题目的求解
  • 层次
  • Dynamo 的实现技术和去中心化
  • 也谈谈全栈工程师
  • 多重继承的演变
  • 编程范型:工具的选择
  • GWT 初体验
  • java.util.concurrent 并发包诸类概览
  • 从 DCL 的对象安全发布谈起
  • 不同团队的困惑
  • 不适合 Hadoop 解决的问题
  • 留心那些潜在的系统设计问题
  • 再谈大楼扔鸡蛋的问题
  • 几种华丽无比的开发方式
  • 我眼中的工程师文化
  • 观点的碰撞
  • 谈谈盗版软件问题
  • 对几个软件开发传统观点的质疑和反驳
  • MVC 框架的映射和解耦
  • 编程的未来
  • DAO 的演进
  • 致那些自嘲码农的苦逼程序员
  • Java 多线程发展简史
  • 珍爱生命,远离微博
  • 网站性能优化的三重境界
  • OSCache 框架源码解析
  • “ 你不适合做程序员”
  • 画圆画方的故事

近期评论

  • panshenlian.com on 初涉 ML Workflow 系统:Kubeflow Pipelines、Flyte 和 Metaflow
  • panzhixiang on 关于近期求职的近况和思考
  • Anonymous on 闲聊投资:亲自体验和护城河
  • 四火 on 关于近期求职的近况和思考
  • YC on 关于近期求职的近况和思考
  • mafulong on 常见分布式基础设施系统设计图解(四):分布式工作流系统
  • 四火 on 常见分布式基础设施系统设计图解(八):分布式键值存储系统
  • Anonymous on 我裸辞了
  • https://umlcn.com on 资源链接
  • Anonymous on 我裸辞了
© 2025 四火的唠叨 | Powered by Minimalist Blog WordPress Theme