0
0

LeetCode算法题目解答汇总

四火 发表于 2015年01月19日 22:12 | Hits: 24857
Tag: Algorithm & Data Structure | Recommended | LeetCode

LeetCode算法题目解答汇总

只要不是特别忙或者特别不方便,最近一直保持着每天做几道算法题的规律,到后来随着难度的增加,每天做的题目越来越少。我的初衷就是练习,因为一方面我本身算法基础并不好,再一方面是因为工作以后传统意义上所谓算法的东西接触还是太少。为了题目查找方便起见,我把之前几篇陆陆续续贴出来的我对LeetCode上面算法题的解答汇总在下面,CTRL+F就可以比较方便地找到。一共154道题,这个数量大概是两个月前的数量,现在其实题目的数目已经超过这个数了(【2015-02-06】注:做了一次更新,新补充的题目解答在本文后半部分)。下面表格里面的Acceptance和Difficulty的Easy/Medium/Hard的分类都是来自LeetCode上面的数据,而Difficulty括号里面的数值和Frequency则来自这个文档。另外,LeetCode数据库的那十道题(截止到目前)我记录在这里

总体来说,做LeetCode的题目收获还是很大的。而这种可以很快获得代码正确性和性能即使的反馈的方式,对算法提高也是很有帮助的。有的题目困难,主要包括两方面的原因,有的是思路比较怪异,用常规思路去解题往往时间复杂度或者空间复杂度过高,还有的则是需要考虑的情况比较复杂,case众多,很容易遗漏。

Title Acceptance Difficulty Frequency
Palindrome Number 28.8% Easy (2) 2
ZigZag Conversion 23.4% Easy (3) 1
Valid Sudoku 27.6% Easy (2) 2
Add Binary 25.5% Easy (2) 4
Valid Parentheses 28.2% Easy (2) 5
Valid Palindrome 22.2% Easy (2) 5
Balanced Binary Tree 32.5% Easy (1) 2
Valid Number 11.0% Easy (2) 5
Symmetric Tree 31.6% Easy (1) 2
String to Integer (atoi) 14.2% Easy (2) 5
Same Tree 41.8% Easy (1) 1
Binary Tree Level Order Traversal 30.6% Easy (3) 4
Binary Tree Level Order Traversal II 31.0% Easy (3) 1
Roman to Integer 33.9% Easy (2) 4
Reverse Integer 39.8% Easy (2) 3
Remove Nth Node From End of List 29.3% Easy (2) 3
Remove Element 33.0% Easy (1) 4
Remove Duplicates from Sorted List 34.7% Easy (1) 3
Climbing Stairs 34.0% Easy (2) 5
Remove Duplicates from Sorted Array 32.2% Easy (1) 3
Plus One 31.4% Easy (1) 2
Path Sum 30.4% Easy (1) 3
Pascal's Triangle II 30.1% Easy (2) 1
Pascal's Triangle 31.1% Easy (2) 1
Minimum Depth of Binary Tree 29.4% Easy (1) 1
Merge Two Sorted Lists 33.2% Easy (2) 5
Merge Sorted Array 31.8% Easy (2) 5
Maximum Depth of Binary Tree 43.8% Easy (1) 1
Longest Common Prefix 27.0% Easy (2) 1
Count and Say 26.7% Easy (2) 2
Length of Last Word 29.0% Easy (1) 1
Implement strStr() 21.9% Easy (4) 5
Divide Two Integers 16.6% Medium (4) 3
3Sum 16.7% Medium (3) 5
Evaluate Reverse Polish Notation 19.9% Medium  
Find Minimum in Rotated Sorted Array 31.7% Medium  
Word Search 19.8% Medium (3) 4
Word Ladder 18.4% Medium (3) 5
Flatten Binary Tree to Linked List 28.2% Medium (3) 3
Gas Station 25.9% Medium  
Generate Parentheses 31.4% Medium (3) 4
Gray Code 32.1% Medium (4) 2
Word Break 21.3% Medium  
Validate Binary Search Tree 25.9% Medium (3) 5
Insertion Sort List 25.3% Medium  
Integer to Roman 33.8% Medium (3) 4
4Sum 21.4% Medium (3) 2
Jump Game 27.2% Medium (3) 2
Add Two Numbers 22.9% Medium (3) 4
Anagrams 23.9% Medium (3) 4
Decode Ways 16.2% Medium (3) 4
Letter Combinations of a Phone Number 26.4% Medium (3) 3
Linked List Cycle 35.7% Medium  
Linked List Cycle II 30.8% Medium  
Best Time to Buy and Sell Stock 31.2% Medium (2) 1
Unique Paths II 27.9% Medium (3) 3
Longest Palindromic Substring 20.6% Medium (4) 2
Longest Substring Without Repeating Characters 22.2% Medium (3) 2
Unique Paths 31.7% Medium (2) 3
Unique Binary Search Trees II 27.3% Medium (4) 1
Unique Binary Search Trees 36.5% Medium (3) 1
Two Sum 18.4% Medium (2) 5
Convert Sorted List to Binary Search Tree 27.3% Medium (4) 3
Maximum Product Subarray 15.9% Medium  
Maximum Subarray 34.0% Medium (3) 3
Triangle 26.6% Medium (3) 1
Best Time to Buy and Sell Stock II 36.6% Medium (3) 1
Swap Nodes in Pairs 32.4% Medium (2) 4
Convert Sorted Array to Binary Search Tree 32.9% Medium (2) 3
Container With Most Water 31.3% Medium (3) 2
Minimum Path Sum 31.0% Medium (3) 3
Surrounded Regions 14.2% Medium (4) 3
Multiply Strings 20.5% Medium (4) 3
Sum Root to Leaf Numbers 29.7% Medium (2) 4
Subsets II 27.0% Medium (4) 2
Next Permutation 25.4% Medium (5) 2
3Sum Closest 27.0% Medium (3) 1
Palindrome Partitioning 25.9% Medium (3) 4
Subsets 27.9% Medium (3) 4
Partition List 27.0% Medium (3) 3
Construct Binary Tree from Inorder and Postorder Traversal 26.6% Medium  
Construct Binary Tree from Preorder and Inorder Traversal 26.5% Medium  
Combinations 30.0% Medium (3) 4
Combination Sum II 24.7% Medium (4) 2
Path Sum II 26.9% Medium (2) 2
Permutation Sequence 22.3% Medium (5) 1
Permutations 31.2% Medium (3) 4
Sqrt(x) 22.3% Medium (4) 4
Combination Sum 26.8% Medium (3) 3
Populating Next Right Pointers in Each Node 35.3% Medium (3) 3
Spiral Matrix II 30.8% Medium (3) 2
Pow(x, n) 25.9% Medium (3) 5
Spiral Matrix 20.6% Medium (4) 2
Sort List 20.6% Medium  
Clone Graph 23.0% Medium  
Remove Duplicates from Sorted Array II 30.6% Medium (2) 2
Sort Colors 32.1% Medium (4) 2
Remove Duplicates from Sorted List II 24.8% Medium (3) 3
Binary Tree Zigzag Level Order Traversal 26.5% Medium (4) 3
Binary Tree Preorder Traversal 35.5% Medium  
Reorder List 20.4% Medium  
Restore IP Addresses 20.5% Medium (3) 3
Single Number II 33.8% Medium  
Reverse Linked List II 26.1% Medium (3) 2
Single Number 45.6% Medium  
Reverse Words in a String 14.0% Medium  
Simplify Path 19.9% Medium (3) 1
Rotate Image 31.2% Medium (4) 2
Rotate List 22.0% Medium (3) 2
Binary Tree Inorder Traversal 35.5% Medium (4) 3
Set Matrix Zeroes 30.8% Medium (3) 5
Search a 2D Matrix 31.2% Medium (3) 3
Search for a Range 27.4% Medium (4) 3
Search Insert Position 34.9% Medium (2) 2
Search in Rotated Sorted Array II 30.9% Medium (5) 3
Text Justification 14.0% Hard (4) 2
Search in Rotated Sorted Array 28.6% Hard (4) 3
Binary Tree Maximum Path Sum 20.2% Hard (4) 2
Reverse Nodes in k-Group 24.9% Hard (4) 2
Binary Tree Postorder Traversal 31.0% Hard  
Candy 19.3% Hard  
Edit Distance 25.5% Hard (4) 3
Recover Binary Search Tree 23.7% Hard (4) 2
Populating Next Right Pointers in Each Node II 30.7% Hard (4) 2
Permutations II 25.0% Hard (4) 2
Best Time to Buy and Sell Stock III 22.4% Hard (4) 1
Palindrome Partitioning II 18.3% Hard (4) 3
N-Queens II 33.9% Hard (4) 3
Substring with Concatenation of All Words 18.1% Hard (3) 1
Sudoku Solver 20.9% Hard (4) 2
N-Queens 25.9% Hard (4) 3
Minimum Window Substring 18.1% Hard (4) 2
Merge k Sorted Lists 21.2% Hard (3) 4
Merge Intervals 20.9% Hard (4) 5
Scramble String 22.8% Hard (5) 2
Trapping Rain Water 28.9% Hard (4) 2
Median of Two Sorted Arrays 17.6% Hard (5) 3
Maximal Rectangle 21.5% Hard (5) 1
Max Points on a Line 11.2% Hard  
LRU Cache 14.1% Hard  
Longest Valid Parentheses 19.7% Hard (4) 1
Longest Consecutive Sequence 28.2% Hard (4) 3
Copy List with Random Pointer 23.5% Hard  
Largest Rectangle in Histogram 21.5% Hard (5) 2
Jump Game II 24.7% Hard (4) 2
Interleaving String 19.5% Hard (5) 2
Insert Interval 20.7% Hard (4) 5
Wildcard Matching 14.3% Hard (5) 3
Distinct Subsequences 25.0% Hard (4) 2
Word Break II 16.6% Hard  
First Missing Positive 22.6% Hard (5) 2
Word Ladder II 11.5% Hard (1) 1
Find Minimum in Rotated Sorted Array II 27.9% Hard  
Regular Expression Matching 20.2% Hard (5) 3

【2015-2-6】从上次贴出来我的解答以后,最新更新的题目,除了一些需要买书只能在电子书上面看解答的没法验证以外,凡是题目能够在线解答和验证答案的,我把我的全部和分析放在了下面。欢迎指正。

155 Min Stack 15.8% Easy
160 Intersection of Two Linked Lists 27.5% Easy
162 Find Peak Element 32.3% Medium
164 Maximum Gap 24.2% Hard
165 Compare Version Numbers 14.8% Easy
166 Fraction to Recurring Decimal 12.1% Medium
168 Excel Sheet Column Title 17.6% Easy
169 Majority Element 34.4% Easy
171 Excel Sheet Column Number 37.7% Easy
172 Factorial Trailing Zeroes 28.0% Easy
173 Binary Search Tree Iterator 28.9% Medium
174 Dungeon Game 16.5% Hard
179 Largest Number 14.9% Medium

Min Stack

【题目】Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) — Push element x onto stack.
  • pop() — Removes the element on top of the stack.
  • top() — Get the top element.
  • getMin() — Retrieve the minimum element in the stack.

【解答】需要注意时间复杂度是常数阶的,前三个方法很容易做到常数阶,因此只需要额外考虑getMin方法就可以了。

class MinStack {
    static class Item {
        int min;
        int val;
        Item prev;
    }
    
    private Item tail = null;
    
    public void push(int x) {
        Item item = new Item();
        item.val = x;
        
        if (tail==null)
            item.min = x;
        else
            item.min = Math.min(tail.min, x);
        
        item.prev = tail;
        tail = item;
    }

    public void pop() {
        if (tail==null)
            throw new RuntimeException("no data");
            
        tail = tail.prev;
    }

    public int top() {
        if (tail==null)
            throw new RuntimeException("no data");
        
        return tail.val;
    }

    public int getMin() {
        if (tail==null)
            throw new RuntimeException("no data");
            
        return tail.min;
    }
}

Intersection of Two Linked Lists

【题目】Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

【解答】注意要求时间复杂度O(n)和空间复杂度O(1)。在草稿纸上画一下A和B的图示,可以发现在交汇以后,右侧的部分可以认为A和B是等长的,因此A和B长度的不同就只在左侧。比如A长于B,那么长就长在左侧未交汇的部分,那我让A的指针先走A.length()-B.length(),这样就可以保证之后A和B一齐前进的时候,一定能在交汇点处相遇。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null || headB==null)
            return null;
        
        int lenA = length(headA);
        int lenB = length(headB);
        
        if (lenA>lenB) {
            int steps = lenA-lenB;
            while (steps>0) {
                headA = headA.next;
                steps--;
            }
        } else if (lenB>lenA) {
            int steps = lenB-lenA;
            while (steps>0) {
                headB = headB.next;
                steps--;
            }
        }
        
        ListNode nodeA = headA;
        ListNode nodeB = headB;
        
        while (nodeA!=null) {
            if (nodeA==nodeB)
                return nodeA;
            
            nodeA = nodeA.next;
            nodeB = nodeB.next;
        }
        
        return null;
    }
    
    private int length(ListNode head) {
        int len = 1;
        ListNode node = head;
        while (node.next!=null) {
            node = node.next;
            len++;
        }
        
        return len;
    }
}

Find Peak Element

【题目】A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

【解答】唯一要小心的地方在于Integer.MIN_VALUE上面,我转成了long型,就避开了越界的问题。

public class Solution {
    public int findPeakElement(int[] num) {
        for (int i=0; i<num.length; i++) {
            long prev;
            if (i==0)
                prev = Integer.MIN_VALUE-1l;
            else
                prev = num[i-1];
            
            long next;
            if (i==num.length-1)
                next = Integer.MIN_VALUE-1l;
            else
                next = num[i+1];
            
            if (num[i]>prev && num[i]>next)
                return i;
        }
        
        return -1;
    }
}

Maximum Gap

【题目】Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

【解答】注意题目要求solve in linear time/space,因此普通的排序不能考虑,因为普通的排序复杂度都是n(log n)的,考虑到这些数都是32-bit signed integer,因此说白了就是0~2^31,我最先考虑搞一个boolean数组存放这些可能的数,下标表示实际数值-1(这里“-1”是因为考虑到数组最大只能表示2^31-1,而0用额外的另一个boolean变量表示):

public class Solution {
    public int maximumGap(int[] num) {
        boolean arr[] = new boolean[Integer.MAX_VALUE]; // 0 ~ 2147483647-1
        boolean zero = false;
        
        for (int n : num) {
            if (n==0)
                zero = true;
            else
                arr[n-1] = true;
        }
        
        int gap = 0;
        Integer last = null;
        if (zero)
            last = 0;
        
        for (int i=0; i<arr.length; i++) {
            if (arr[i]) {
                if (last==null) {
                    last = i+1;
                } else {
                    if (i+1-last>gap)
                        gap = i+1-last;
                }
            }
        }
        
        return gap;
    }
}

不过申请那么大一个数组,不出意外地出现了java.lang.OutOfMemoryError: Java heap space。因此要调整一下思路,我原来的方法相当于先做了一个“计数排序”,这种特殊的排序方法使得线性时间复杂度成为可能,还有一些排序方法也具备接近线性时间复杂度的,比如基数排序,比如桶排序,这些思路从实质上说起来有很多类似的地方。我下面采用类似基数排序的思路,由于所有数值都不会超过十位数,因此构建一棵树,每个非叶子节点都有10个子节点(十叉树),从根节点开始,每深一层(深度从0开始算起),从根到叶子路径上位于第i层的节点就是从最高位开始数第i位数值的表示。比如123可表示为0000000123,进而表示为这样的从根到叶子节点的路径:

root – nexts[0] - nexts[0] - nexts[0] - nexts[0] - nexts[0] - nexts[0] - nexts[0] - nexts[1] - nexts[2] – value: 123

在这种方式下,空间复杂度和入参数组的长度是线性相关的,时间复杂度也是(因为树的深度只有10)。注意代码中Item节点里面的nextIndex的作用,这个指的是在求max gap的过程中,我实际做的是深度优先遍历,因此需要一个stack保存前一层节点访问的状态,而这个nextIndex表示的是该节点再出栈时应该访问第几个孩子节点了。

class Item {
    Item[] nexts = new Item[10];
    Integer val = null;
    int nextIndex = 0;
}
public class Solution {
	public int maximumGap(int[] num) {

		Item head = new Item();

		// build tree
		for (int i = 0; i < num.length; i++) {
			// 0~2147483647
			Item node = head;
			int n = num[i];

			for (int j = 1000000000; j >= 1; j = j / 10) {
				int digit = n / j;
				n = n % j;

				if (node.nexts[digit] == null)
					node.nexts[digit] = new Item();

				node = node.nexts[digit];

				if (j == 1)
					node.val = num[i];
			}
		}

		Stack<Item> stack = new Stack<Item>();
		stack.push(head);
		Integer last = null;
		int maxGap = 0;
		Item node = null;

		// calculate gaps, DFS
		while (!stack.isEmpty()) {
			if (node == null)
				node = stack.pop();

			if (node.val != null) {
				if (last != null)
					maxGap = Math.max(maxGap, node.val - last);

				last = node.val;
				node = null;
			} else {
				int index = node.nextIndex;
				if (index != 9) {
					node.nextIndex++;
					stack.push(node);
				}
				node = node.nexts[index];
			}
		}

		return maxGap;
	}
}

Compare Version Numbers

【题目】Compare two version numbers version1 and version1.

If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

【解答】没什么可说的,注意有大于一个的点号。

public class Solution {
    public int compareVersion(String version1, String version2) {
        String[] tokens1 = version1.split("\\.");
        String[] tokens2 = version2.split("\\.");
        
        return compareVersion(tokens1, tokens2, 0);
    }
    
    private int compareVersion(String[] tokens1, String[] tokens2, int pos) {
        if (tokens1.length<=pos && tokens2.length<=pos)
            return 0;
        
        int v1 = 0;
        if (tokens1.length>pos)
            v1 = Integer.parseInt(tokens1[pos]);
        
        int v2 = 0;
        if (tokens2.length>pos)
            v2 = Integer.parseInt(tokens2[pos]);
        
        if (v1>v2)
            return 1;
        else if (v1<v2)
            return -1;
        
        return compareVersion(tokens1, tokens2, pos+1);
    }
}

Fraction to Recurring Decimal

【题目】Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

  • Given numerator = 1, denominator = 2, return “0.5″.
  • Given numerator = 2, denominator = 1, return “2″.
  • Given numerator = 2, denominator = 3, return “0.(6)”.

【解答】首先,要知道这样一件事情,在不断做除法往后求小数位数的时候,如果遇到某一位的计算,商和余数都在前面某一位上出现过,这就意味着循环节已经寻找完毕。知道这一点以后,就有思路并且可以写代码了。大致思路是,用一个map来存放之前小数计算过程中遇到过数值,key是商和余数组成的对象,值是当时出现这个情况的小数位数(从0开始)。但是这道题陷阱我还是踩了,就是整型溢出的问题,尤其是求绝对值的代码如果写成Math.abs(numerator)的话,要知道Math.abs(Integer.MIN_VALUE)会导致溢出的,无法得到正确的正数,因此需要Math.abs((long)(numerator))。因此谁都知道要当心整数溢出,可实际使用中还是会遇上。同事说简单的题目要写bug free的代码如何如何,可真要写bug free的代码真是太难了,即便是很简单的题目。

class Item {
    long quotient;
    long remainder;

    public Item(long quotient, long remainder) {
        this.quotient = quotient;
        this.remainder = remainder;
    }

    @Override
    public boolean equals(Object p) {
        Item another = (Item) p;
        return another.quotient == this.quotient
                && another.remainder == this.remainder;
    }

    @Override
    public int hashCode() {
        return (int) (new Long(this.quotient).hashCode() ^ new Long(
                this.remainder));
    }
}

public class Solution {
    public static void main(String[] args) {
        System.out.println(new Solution().fractionToDecimal(1, 6));
    }

    public String fractionToDecimal(int numerator, int denominator) {
        String negative = "";
        if ((numerator < 0 && denominator > 0)
                || (numerator > 0 && denominator < 0))
            negative = "-";

        long numeratorL = Math.abs((long)(numerator));
        long denominatorL = Math.abs((long)(denominator));

        long inte = numeratorL / denominatorL;
        long remainder = numeratorL % denominatorL;
        String fraction = "";

        Map<Item, Integer> map = new HashMap<Item, Integer>();
        int pos = 0;
        while (remainder != 0) {
            remainder *= 10;
            long quotient = remainder / denominatorL;
            remainder = remainder % denominator;

            Item item = new Item(quotient, remainder);
            if (map.containsKey(item)) {
                int startPos = map.get(item);
                fraction = fraction.substring(0, startPos) + '('
                        + fraction.substring(startPos) + ')';
                break;
            } else {
                fraction += quotient;
                map.put(item, pos);
                pos++;
            }
        }

        if ("".equals(fraction))
            return negative + inte;
        else
            return negative + inte + "." + fraction;
    }
}

Excel Sheet Column Title

【题目】Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

【解答】看着挺简单,但是还是没能一遍做对。看起来就是一个从十进制转成二十六进制的题目,但是它的起始数值是1,而不是0,这就意味着,循环中每一轮,拿到一个数的时候,都要先把它减一,才能继续按照自己习惯的二十六进制的思路来进行。

public class Solution {
    public String convertToTitle(int n) {
        String s = "";
        while (true) {
            n = n-1;
        
            int remainder = n%26;
            n = n/26;
            
            s = (char)(remainder+'A') + s;
            
            if (n==0)
                break;
        }
        
        return s;
    }
}

Majority Element

【题目】Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

【解答】没啥说的。

public class Solution {
    public int majorityElement(int[] num) {
        Map<Integer, Integer> map = new HashMap<>();
        int cap = num.length/2;
        for (int n : num) {
            if (!map.containsKey(n))
                map.put(n, 1);
            else
                map.put(n, map.get(n)+1);
        }
        
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue()>cap) {
                return entry.getKey();
            }
        }
        
        return 0; // unreachable
    }
}

Excel Sheet Column Number

【题目】Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 

【解答】没什么说的。

public class Solution {
    public int titleToNumber(String s) {
        if (null==s || s.equals("")) {
            return 0;
        }
        
        int total = 0;
        for (int i=s.length()-1; i>=0; i--) {
            int n = s.charAt(i) - 'A' + 1;
            total += Math.pow(26, s.length()-i-1)*n;
        }
        
        return total;
    }
}

Factorial Trailing Zeroes

【题目】Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

【解答】要找末尾0的个数,0只可能由2乘以5造出来,如果你说10也可能啊,但是10也是2乘以5。因此,我只需要统计2和5的个数,选择这两个个数中较小的一个即可。于是我对每个数统计2和5的个数,并累加:

public class Solution {
    public int trailingZeroes(int n) {
        int twos = 0;
        int fives = 0;
        for (int i=1; i<=n; i++) {
            int num = i;
            
            while (num%2==0) {
                twos++;
                num = num/2;
            }
            
            while (num%5==0) {
                fives++;
                num = num/5;
            }
        }
        
        return Math.min(twos, fives);
    }
}

结果,Time Limit Exceeded。我只能继续想法子改进:

以求5的个数为例,2的个数求法也是类似的。给定一个数,比如6,那么6的阶乘中,5的个数是6/5,为1,因为只有这个数是5或者5的倍数的时候才会出现因子5,这里不整除没有关系,只需要找整数部分即可。但是如果这个数是26呢,26/5,结果为5,但是26的阶乘里面却有6个5,因为26/5的结果5本身也是5的倍数,因此可见这里有一个递归求5的个数的过程在里面:

public class Solution {
    public int trailingZeroes(int n) {
        if (n==0)
            return 0;
            
        int fives = n/5;
        fives += trailingZeroes(fives);
        
        int twos = n/2;
        twos += trailingZeroes(twos);
        
        return Math.min(fives, twos);
    }
}

Binary Search Tree Iterator

【题目】Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

【解答】注意root为空的情况。用一个stack放置parent节点,构造方法里面,循环往左孩子节点顺下去,一顺到底;对每个节点访问以后,都尝试寻找右孩子节点,如果找到,就从右孩子节点开始,循环往它的做孩子节点顺下去,一顺到底,如果没有右孩子节点,就尝试出栈。

public class BSTIterator {

    private Stack<TreeNode> stack = new Stack<>();
    private TreeNode node;
    
    public BSTIterator(TreeNode root) {
        node = root;
        while (node!=null && node.left!=null) {
            stack.push(node);
            node = node.left;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return node!=null;
    }

    /** @return the next smallest number */
    public int next() {
        int ret = node.val;
        if (node.right!=null) {
            node = node.right;
            
            while (node.left!=null) {
                stack.push(node);
                node = node.left;
            }
        } else if (!stack.isEmpty()) {
            node = stack.pop();
        } else {
            node = null;
        }
        
        return ret;
    }
}

Dungeon Game

【题目】The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0′s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K) -3 3
-5 -10 1
10 30 -5 (P)

Notes:

  • The knight’s health has no upper bound.
  • Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

【解答】这让我想起了龙与地下城的游戏啊。一看就想到是DP,但是DP的构造递推关系是关键,我一开始没有想对,导致走上了一条又复杂又做不对的路上:我想“把起点固定在(0, 0),用arr[i][j]表示终点在(i,j)时,起点所需最小的HP”,但是问题在于,在这种情况下如果我知道arr[i-1][j]和arr[i][j-1],我其实是很难得到arr[i][j]的。举个例子:

1, -3, 3,
0, -2, 0,
-3,-3,-3

看这样一个矩阵,要求arr[2][2],但是arr[2][1]为2,arr[1][2]为2,考虑到dungeon[2][2]=-3,求得arr[2][2]=5。这是错的,正确答案应该是arr[2][2]=3。错误的原因就是在于递推关系的考察上面,arr[i-1][j]以及arr[i][j-1],这两者其实并无法推出arr[i][j]。

后来把思路倒过来,“把终点固定在(dungeon.length-1, dungeon[0].length-1),而arr[i][j]表示起点为(i, j)所需的最小HP”,这时问题就豁然开朗了:arr[i][j] = min(arr[i-1][j], arr[i][j-1]) – dungeon[i][j]。当然需要注意生命值在任何时候都不能小于1。

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        Integer[][] arr = new Integer[dungeon.length][dungeon[0].length];

        return calculate(dungeon, 0, 0, arr);
    }

    // return the min HP from (i, j) to the end (dungeon.length-1, dungeon[0].length-1)
    private int calculate(int[][] dungeon, int i, int j, Integer[][] arr) {
        if (arr[i][j] != null)
            return arr[i][j];

        if (dungeon.length-1==i && dungeon[0].length-1==j) {
            arr[i][j] = Math.max(1, -dungeon[i][j]+1);
            return arr[i][j];
        }

        int fromRow = Integer.MAX_VALUE;
        if (i<dungeon.length-1) {
            int past = calculate(dungeon, i+1, j, arr);
            fromRow = Math.max(1, past-dungeon[i][j]);
        }
        
        int fromCol = Integer.MAX_VALUE;
        if (j<dungeon[0].length-1) {
            int past = calculate(dungeon, i, j+1, arr);
            fromCol = Math.max(1, past-dungeon[i][j]);
        }

        arr[i][j] = Math.min(fromRow, fromCol);
        return arr[i][j];
    }
}

虽然看起来不新鲜,但其实这道题收获还是挺大的。

Largest Number

【题目】Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

【解答】我开始的做法是,转化成字符串比较,但是遇到 12 和 123 这样一个串是另一个串的前缀怎么办?我就做法就是把长串靠前面的共同短串截取,之后的那个字符和它本来前面那个字符比较,如果更大,这个长串要往前放;反之往后放。比如 12 和 123 中,3要大于2,因此123往前放,因此最后结果是12312;再比如 32 和 321 ,1要小于2,因此321要往后放,因此最后结果是32321。

public class Solution {
    public String largestNumber(int[] num) {
        Integer[] numbers = new Integer[num.length];
        for (int i=0; i<num.length; i++) {
            numbers[i] = num[i];
        }
        
        Arrays.sort(numbers, new Comparator<Integer>(){
            @Override
            public int compare(Integer left, Integer right) {
                String ls = left + "";
                String rs = right + "";
                
                // return -ls.compareTo(rs);
                int ll = ls.length();
                int rl = rs.length();
                
                for (int i=0; i<Math.min(ll, rl); i++) {
                    if (ls.charAt(i)>rs.charAt(i))
                        return -1;
                    else if (ls.charAt(i)<rs.charAt(i))
                        return 1;
                }
                
                if (ll>rl) {
                    char base = ls.charAt(rl-1);
                    int i=rl;
                    while (i<ll) {
                        char ch = ls.charAt(i);
                        if (ch>base)
                            return -1;
                        else if(ch<base)
                            return 1;
                        
                        i++;
                    }
                } else if (ll<rl) {
                    char base = rs.charAt(ll-1);
                    int i=ll;
                    while (i<rl) {
                        char ch = rs.charAt(i);
                        if (ch>base)
                            return 1;
                        else if (ch<base)
                            return -1;
                        
                        i++;
                    }
                }
                
                return 0;
            }
        });
        
        StringBuilder sb = new StringBuilder();
        boolean headingZero = true;
        for (int n : numbers) {
            if (headingZero) {
                if (n==0)
                    continue;
                else
                    headingZero = false;
            }
            
            sb.append(n);
        }
        
        String ret = sb.toString();
        if ("".equals(ret))
            return "0";
        
        return ret;
    }
}

可是遇到这个case的时候傻眼了:

Input:   [824,938,1399,5607,6973,5703,9609,4398,8247]
Output:  "9609938824782469735703560743981399"
Expected:"9609938824824769735703560743981399"

这个case其实可以简化成 824 和 8247 这两个数,就能重现问题。原来我原有的判定逻辑就不正确。

我觉得正确的做法应该把较小的那个串作为循环节,较大串去掉较小串以后,相当于较小串指针移到头部继续比较,比如 1212123 和 12 进行比较时,1212123 把 12 重复了三遍,之后那个数是3,要比1大,因此结果应是121212312。

public class Solution {
	public String largestNumber(int[] num) {
		Integer[] numbers = new Integer[num.length];
		for (int i = 0; i < num.length; i++) {
			numbers[i] = num[i];
		}

		Arrays.sort(numbers, new Comparator<Integer>() {
			@Override
			public int compare(Integer left, Integer right) {
				String ls = left + "";
				String rs = right + "";

				// return -ls.compareTo(rs);
				int ll = ls.length();
				int rl = rs.length();

				for (int i = 0; i < Math.min(ll, rl); i++) {
					if (ls.charAt(i) > rs.charAt(i))
						return -1;
					else if (ls.charAt(i) < rs.charAt(i))
						return 1;
				}

				if (ll > rl) {
					int li = rl;
					int ri = 0;

					while (li < ll) {
						if (ri == rl)
							ri = 0;

						if (ls.charAt(li) < rs.charAt(ri))
							return 1;
						else if (ls.charAt(li) > rs.charAt(ri))
							return -1;

						ri++;
						li++;
					}
				} else if (ll < rl) {
					int ri = ll;
					int li = 0;

					while (ri < rl) {
						if (li == ll)
							li = 0;

						if (ls.charAt(li) < rs.charAt(ri))
							return 1;
						else if (ls.charAt(li) > rs.charAt(ri))
							return -1;

						ri++;
						li++;
					}
				}

				return 0;
			}
		});

		StringBuilder sb = new StringBuilder();
		boolean headingZero = true;
		for (int n : numbers) {
			if (headingZero) {
				if (n == 0)
					continue;
				else
					headingZero = false;
			}

			sb.append(n);
		}

		String ret = sb.toString();
		if ("".equals(ret))
			return "0";

		return ret;
	}
}

可是结果依然是错误的:

Input:   [121,12]
Output:	 "12112"
Expected:"12121"

原因在于,当较长串扣除若干个较短串了以后,剩下的部分,如果依然是循环节的一部分,这种情况会比较复杂。虽然也能继续下去,但是显然这已经不是一个好的解决办法了。

一个比较好的思路是,我根本不要去比较两个数个体之间的前后关系,那样太困难,因为二者长度不同,不变检查;但是我去比较这两个数不同前后排列组合后形成的数的前后关系,比如 12 和 123,我不比较他们谁在前面,而是比较不同的前后排列组合,即 12312 和 12123 谁更大,这带来的好处就是,两个数长度相等,比较显而易见,于是代码变得非常简洁:

public class Solution {
	public String largestNumber(int[] num) {
		Integer[] numbers = new Integer[num.length];
		for (int i = 0; i < num.length; i++) {
			numbers[i] = num[i];
		}

		Arrays.sort(numbers, new Comparator<Integer>() {
			@Override
			public int compare(Integer left, Integer right) {
				String s1 = "" + left + right;
                String s2 = "" + right + left;

                return s2.compareTo(s1);
			}
		});

		StringBuilder sb = new StringBuilder();
		boolean headingZero = true;
		for (int n : numbers) {
			if (headingZero) {
				if (n == 0)
					continue;
				else
					headingZero = false;
			}

			sb.append(n);
		}

		String ret = sb.toString();
		if ("".equals(ret))
			return "0";

		return ret;
	}
}

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

分享到:

原文链接: http://www.raychase.net/2763

0     0

评价列表(0)