分享我的Lintcode题解，目前进度244/248

从6月26号开始刷Lintcode，到今天已经二十多天。目前还剩4题，实在刷累了，打算停下来歇会儿。
回顾下每道题目的思路。每道ac的题我都尽量找最优解，不过有的题目还无法做到最优。

有一点很重要。Lintcode和Leetcode一样，你就算写暴力解通常都能ac，但一定不能满足于此，因为面试官不会满意的。在自己的能力范围内，要力求优化。
相比之下，大多数面向ACM的OJ都会卡复杂度，甚至卡常系数优化（各种程序调优），不做到最优就无法AC。

下面每层楼给出一道题的AC代码和思路简述，附带复杂度分析。因为题目很多，每题就不打算写得很详细了。
要一口气写完也不容易，所以我打算不定期更新，争取每次来逛尽量多写几题。

欢迎各种挑错和建议(^_^)

Github repo在此https://github.com/zhuli19901106/lintcode

加上题目目录
10楼 A + B Problem
11楼 Trailing Zeros
12楼 Digit Counts
13楼 Ugly Number
14楼 Kth Largest Element
15楼 Merge Sorted Array II
16楼 Binary Tree Serialization
17楼 Rotate String
18楼 Fizz Buzz
19楼 Search Range in Binary Search Tree
20楼 Min Stack
21楼 strStr
22楼 Binary Search
23楼 Permutations
24楼 Permutations II


补充内容 (2015-7-18 21:34):
25楼 Subsets

补充内容 (2015-7-18 21:53):
26楼 Subsets II

补充内容 (2015-7-18 22:10):
28楼 Search a 2D Matrix

补充内容 (2015-7-18 23:01):
37楼 Interleaving String

补充内容 (2015-7-18 23:11):
39楼 Insert Interval

补充内容 (2015-7-18 23:17):
41楼 Partition Array

补充内容 (2015-7-18 23:40):
46楼 Minimum Window Substring

补充内容 (2015-7-19 15:30):
56楼 N-Queens II

补充内容 (2015-7-19 15:32):
57楼 Reverse Linked List

补充内容 (2015-7-19 15:37):
58楼 Reverse Linked List II

补充内容 (2015-7-19 15:47):
59楼 Search a 2D Matrix II

补充内容 (2015-7-19 16:31):
60楼 Recover Rotated Sorted Array

补充内容 (2015-7-19 16:40):
61楼 Implement Queue by Two Stacks

补充内容 (2015-7-19 16:45):
62楼 Maximum Subarray

补充内容 (2015-7-19 16:53):
63楼 Maximum Subarray II

补充内容 (2015-7-19 17:01):
64楼 Maximum Subarray III

补充内容 (2015-7-19 17:36):
67楼 Majority Number

补充内容 (2015-7-19 17:40):
69楼 Majority Number II

补充内容 (2015-7-19 17:42):
65楼 Minimum Subarray

补充内容 (2015-7-19 17:42):
66楼 Maximum Subarray Difference

补充内容 (2015-7-19 17:46):
70楼 Majority Number III

补充内容 (2015-7-19 19:23):
71楼 Product of Array Exclude Itself

补充内容 (2015-7-19 19:25):
72楼 Previous Permuation

补充内容 (2015-7-19 19:37):
73楼 Next Permutation

补充内容 (2015-7-19 20:02):
74楼 Reverse Words in a String

补充内容 (2015-7-19 20:07):
75楼 String to Integer(atoi)

补充内容 (2015-7-19 21:55):
76楼 Compare Strings

补充内容 (2015-7-19 22:24):
77楼 2 Sum

补充内容 (2015-7-19 22:51):
78楼 3 Sum

补充内容 (2015-7-19 23:14):
79楼 4 Sum

补充内容 (2015-7-19 23:23):
80楼 3 Sum Closest

补充内容 (2015-7-19 23:28):
81楼 Search Insert Position

补充内容 (2015-7-19 23:31):
82楼 Search for a Range

补充内容 (2015-7-20 00:16):
83楼 Search in Rotated Sorted Array

补充内容 (2015-7-20 00:47):
84楼 Search in Rotated Sorted Array II

补充内容 (2015-7-20 03:59):
56楼 N-Queens

补充内容 (2015-7-20 18:29):
91楼 Merge Sorted Array

补充内容 (2015-7-20 18:43):
92楼 Median of two Sorted Arrays

补充内容 (2015-7-20 20:21):
93楼 Binary Tree Preorder Traversal

补充内容 (2015-7-20 20:38):
94楼 Binary Tree Inorder Traversal

补充内容 (2015-7-20 21:32):
95楼 Binary Tree Postorder Traversal

补充内容 (2015-7-20 21:38):
96楼 Binary Tree Level Order Traversal

补充内容 (2015-7-20 21:44):
97楼 Binary Tree Level Order Traversal II

补充内容 (2015-7-20 21:55):
98楼 Binary Tree Zigzag Level Order Traversal

补充内容 (2015-7-20 22:10):
99楼 Construct Binary Tree from Inorder and Postorder Traversal

补充内容 (2015-7-20 22:40):
100楼 Construct Binary Tree from Preorder and Inorder Traversal

补充内容 (2015-7-20 22:45):
101楼 First Bad Version

补充内容 (2015-7-20 23:22):
102楼 Find Peak Element

补充内容 (2015-7-20 23:43):
103楼 Longest Increasing Subsequence

补充内容 (2015-7-20 23:47):
103楼 Longest Common Subsequence（上面那个打错了）

补充内容 (2015-7-20 23:55):
104楼 Longest Increasing Subsequence

补充内容 (2015-7-21 00:09):
105楼 Longest Common Prefix

补充内容 (2015-7-21 00:22):
106楼 Longest Common Substring

补充内容 (2015-7-21 00:43):
107楼 Median

补充内容 (2015-7-21 00:47):
108楼 Data Stream Median

补充内容 (2015-7-21 00:50):
109楼 Single Number

补充内容 (2015-7-21 00:56):
110楼 Single Number II

补充内容 (2015-7-21 01:24):
112楼 Single Number III

补充内容 (2015-7-21 01:41):
114楼 Binary Search Tree Iterator

补充内容 (2015-7-21 19:30):
116楼 Remove Node in Binary Search Tree

补充内容 (2015-7-21 19:40):
117楼 Lowest Common Ancestor

补充内容 (2015-7-21 20:02):
118楼 k Sum

补充内容 (2015-7-21 20:21):
119楼 k Sum II

补充内容 (2015-7-21 20:35):
121楼 Minimum Adjustment Cost

补充内容 (2015-7-21 20:38):
122楼 Backpack

补充内容 (2015-7-21 20:45):
123楼 Balanced Binary Tree

补充内容 (2015-7-21 20:56):
124楼 Binary Tree Maximum Path Sum

补充内容 (2015-7-21 21:01):
125楼 Validate Binary Search Tree

补充内容 (2015-7-21 22:16):
126楼 Partition List

补充内容 (2015-7-21 22:19):
127楼 Maximum Depth of Binary Tree

补充内容 (2015-7-21 22:28):
128楼 Sort List

补充内容 (2015-7-21 22:35):
129楼 Reorder List

补充内容 (2015-7-22 00:42):
132楼 Unique Paths

补充内容 (2015-7-22 00:47):
133楼 Unique Paths IIUnique Paths II

补充内容 (2015-7-22 00:48):
133楼 Unique Paths II

补充内容 (2015-7-22 00:55):
134楼 Jump Game

补充内容 (2015-7-22 00:58):
135楼 Jump Game II

补充内容 (2015-7-22 01:38):
136楼 Distinct Subsequences

补充内容 (2015-7-22 01:46):
137楼 Edit Distance

补充内容 (2015-7-22 02:34):
140楼 Word Ladder II

补充内容 (2015-7-22 02:46):
142楼 Largest Rectangle in Histogram

补充内容 (2015-7-22 03:03):
143楼 Word Search

补充内容 (2015-7-22 03:12):
144楼 Longest Consecutive Sequence

补充内容 (2015-7-22 03:15):
145楼 Backpack II

补充内容 (2015-7-22 03:30):
146楼 Max Tree

补充内容 (2015-7-22 04:40):
148楼 Hash Function

补充内容 (2015-7-22 04:49):
150楼 Heapify

补充内容 (2015-7-22 04:56):
151楼 Word Search II

补充内容 (2015-7-22 05:10):
152楼 LRU Cache

补充内容 (2015-7-22 05:22):
153楼 Combination Sum

补充内容 (2015-7-22 05:29):
154楼 Palindrome Partitioning

补充内容 (2015-7-22 05:48):
155楼 Clone Graph

补充内容 (2015-7-22 05:51):
156楼 Subarray Sum

补充内容 (2015-7-22 17:48):
157楼 Subarray Sum Closest

补充内容 (2015-7-22 17:54):
158楼 Fast Power

补充内容 (2015-7-22 20:19):
160楼 O(1) Check Power of 2

补充内容 (2015-7-22 20:24):
161楼 Sort Colors II

补充内容 (2015-7-22 20:33):
162楼 Interleaving Positive and Negative Numbers

补充内容 (2015-7-22 20:44):
163楼 Sort Colors

补充内容 (2015-7-22 20:49):
164楼 Best Time to Buy and Sell Stock

补充内容 (2015-7-22 21:14):
165楼 Best Time to Buy and Sell Stock II

补充内容 (2015-7-22 21:31):
166楼 Best Time to Buy and Sell Stock III

补充内容 (2015-7-22 21:47):
167楼 Combinations

补充内容 (2015-7-22 21:55):
168楼 Combination Sum II

补充内容 (2015-7-22 22:16):
169楼 Regular Expression Matching

补充内容 (2015-7-22 22:22):
170楼 Minimum Depth of Binary Tree

补充内容 (2015-7-22 22:26):
171楼 Unique Characters

补充内容 (2015-7-22 22:47):
172楼 Two Strings Are Anagrams

补充内容 (2015-7-22 23:33):
173楼 Find Minimum in Rotated Sorted Array

补充内容 (2015-7-23 00:01):
174楼 Find Minimum in Rotated Sorted Array II

补充内容 (2015-7-23 00:03):
175楼 Rotate Image

补充内容 (2015-7-23 00:08):
176楼 Set Matrix Zeroes

补充内容 (2015-7-23 18:26):
187楼 Unique Binary Search Trees II

补充内容 (2015-7-23 18:47):
188楼 Merge Two Sorted Lists

补充内容 (2015-7-23 20:19):
189楼 Nth to Last Node in List

补充内容 (2015-7-23 20:22):
190楼 Add Two Numbers

补充内容 (2015-7-23 20:31):
191楼 Rotate List

补充内容 (2015-7-23 21:10):
192楼 Anagrams

补充内容 (2015-7-23 21:14):
193楼 Remove Element

补充内容 (2015-7-23 21:19):
196楼 Remove Nth Node From End of List

补充内容 (2015-7-23 21:24):
197楼 Route Between Two Nodes in Graph

补充内容 (2015-7-23 21:35):
201楼 Update Bits

补充内容 (2015-7-23 21:47):
202楼 Binary Representation

补充内容 (2015-7-23 21:51):
203楼 Flip Bits

补充内容 (2015-7-23 21:57):
204楼 Delete Digits

补充内容 (2015-7-23 22:02):
205楼 Wood Cut

补充内容 (2015-7-23 22:21):
206楼 Largest Number

补充内容 (2015-7-23 22:24):
207楼 Matrix Zigzag Traversal

补充内容 (2015-7-23 23:13):
209楼 Gas Station

补充内容 (2015-7-23 23:35):
210楼 Maximum Product Subarray

补充内容 (2015-7-23 23:39):
212楼 Wildcard Matching

补充内容 (2015-7-24 03:25):
214楼 Segment Tree Build

补充内容 (2015-7-24 03:38):
216楼 Segment Tree Query

补充内容 (2015-7-24 03:42):
217楼 Segment Tree Modify

补充内容 (2015-7-24 04:04):
218楼 Singleton

补充内容 (2015-7-24 04:31):
219楼 Interval Minimum Number

补充内容 (2015-7-24 08:12):
223楼 Interval Sum

补充内容 (2015-7-24 08:16):
224楼 Interval Sum II

补充内容 (2015-7-24 08:20):
225楼 Segment Tree Query II

补充内容 (2015-7-24 17:54):
226楼 First Missing Positive

补充内容 (2015-7-25 00:02):
229楼 Sliding Window Maximum

补充内容 (2015-7-25 00:09):
230楼 Trapping Rain Water

补充内容 (2015-7-25 00:18):
231楼 Sliding Window Median

补充内容 (2015-7-25 00:27):
232楼 Trapping Rain Water II

补充内容 (2015-7-25 00:58):
233楼 Expression Evaluation

补充内容 (2015-7-25 01:01):
234楼 Permutation Sequence

补充内容 (2015-7-25 01:07):
235楼 Count of Smaller Number

补充内容 (2015-7-25 01:12):
236楼 Building Outline

补充内容 (2015-7-25 01:18):
237楼 Convert Expression to Polish Notation

补充内容 (2015-7-25 01:23):
238楼 Convert Expression to Reverse Polish Notation

补充内容 (2015-7-25 01:29):
239楼 Expression Tree Build

补充内容 (2015-7-25 01:34):
240楼 Valid Sudoku

补充内容 (2015-7-25 01:45):
241楼 Count of Smaller Number before itself

补充内容 (2015-7-25 02:58):
242楼 Longest Substring with At Most K Distinct Characters

补充内容 (2015-7-25 03:07):
243楼 The Smallest Difference

补充内容 (2015-7-25 03:11):
244楼 Number of Airplanes in the Sky

补充内容 (2015-7-25 03:14):
245楼 Longest Substring Without Repeating Characters

补充内容 (2015-7-25 15:42):
249楼 Container With Most Water

补充内容 (2015-7-25 15:58):
250楼 Print Numbers by Recursion

补充内容 (2015-7-25 16:16):
251楼 Assignment Operator Overloading (C++ Only)

补充内容 (2015-7-25 16:26):
252楼 Triangle Count

补充内容 (2015-7-25 16:39):
253楼 Add Binary

补充内容 (2015-7-25 17:34):
254楼 Convert Sorted Array to Binary Search Tree With Minimal Height

补充内容 (2015-7-25 17:37):
257楼 Plus One

补充内容 (2015-7-25 17:41):
258楼 Divide Two Integers

补充内容 (2015-7-25 17:49):
259楼 Gray Code

补充内容 (2015-7-25 17:56):
260楼 Reverse Integer

补充内容 (2015-7-25 18:03):
261楼 Candy

补充内容 (2015-7-25 18:08):
262楼 House Robber

补充内容 (2015-7-25 18:23):
263楼 Best Time to Buy and Sell Stock IV

补充内容 (2015-7-25 18:28):
264楼 Coins in a Line

补充内容 (2015-7-25 18:35):
265楼 Coins in a Line II

补充内容 (2015-7-25 18:56):
266楼 Subtree

补充内容 (2015-7-25 21:35):
267楼 Delete Node in the Middle of Singly Linked List

补充内容 (2015-7-25 22:06):
268楼 Fibonacci

补充内容 (2015-7-25 22:09):
259楼 Count 1 in Binary

补充内容 (2015-7-25 22:10):
269楼 Count 1 in Binary（上面那个打错了）

补充内容 (2015-7-25 22:16):
270楼 Merge Intervals

补充内容 (2015-7-25 22:36):
271楼 Next Permutation II

补充内容 (2015-7-25 22:47):
271楼 Next Permutation II

补充内容 (2015-7-25 22:59):
272楼 Longest Palindromic Substring

补充内容 (2015-7-25 23:06):
273楼 Partition Array by Odd and Even

补充内容 (2015-7-25 23:14):
274楼 Longest Increasing Continuous subsequence II

补充内容 (2015-7-25 23:18):
275楼 Longest Increasing Continuous subsequence

补充内容 (2015-7-25 23:44):
276楼 Minimum Size Subarray Sum

补充内容 (2015-7-25 23:48):
277楼  Valid Palindrome

补充内容 (2015-7-25 23:59):
278楼 Valid Number

补充内容 (2015-7-26 00:13):
279楼 Integer to Roman

补充内容 (2015-7-26 00:17):
280楼 Roman to Integer

补充内容 (2015-7-26 00:22):
281楼 Count and Say

补充内容 (2015-7-26 00:27):
282楼 Kth Smallest Number in Sorted Matrix

补充内容 (2015-7-26 00:54):
283楼 Maximum Gap

补充内容 (2015-7-26 01:05):
284楼 Simplify Path

补充内容 (2015-7-26 01:08):
285楼 Length of Last Word

补充内容 (2015-7-26 01:11):
286楼 Valid Parentheses

补充内容 (2015-7-26 01:12):
287楼 Evaluate Reverse Polish Notation

补充内容 (2015-7-26 01:15):
288楼 Continuous Subarray Sum

补充内容 (2015-7-26 02:16):
289楼 Continuous Subarray Sum II

补充内容 (2015-7-26 02:29):
290楼 Subarray Sum II

补充内容 (2015-7-26 16:25):
294楼 Maximal Square

补充内容 (2015-7-26 16:27):
295楼 Longest Words

补充内容 (2015-7-26 16:30):
296楼 Space Replacement

补充内容 (2015-7-26 16:39):
297楼 Max Points on a Line

补充内容 (2015-7-26 17:28):
299楼 Find the Missing Number

补充内容 (2015-7-26 17:32):
300楼 Number of Islands

补充内容 (2015-7-26 17:53):
301楼 Number of Islands II

补充内容 (2015-7-26 18:48):
302楼 Find the Connected Component in the Undirected Graph

补充内容 (2015-7-26 18:55):
303楼 Find the Weak Connected Component in the Directed Graph

补充内容 (2015-7-26 19:05):
304楼 Scramble String

补充内容 (2015-7-26 19:23):
305楼 Submatrix Sum

补充内容 (2015-7-26 19:52):
306楼 Word Break

补充内容 (2015-7-26 19:55):
307楼 Triangle

补充内容 (2015-7-26 19:58):
308楼 Remove Duplicates from Sorted Array

补充内容 (2015-7-26 20:00):
309楼 Remove Duplicates from Sorted Array II

补充内容 (2015-7-26 20:03):
310楼 Sort Letters by Case

补充内容 (2015-7-26 20:08):
311楼 Palindrome Partitioning II

补充内容 (2015-7-26 20:11):
312楼 Minimum Path Sum

补充内容 (2015-7-26 20:47):
314楼 Linked List Cycle

补充内容 (2015-7-26 20:54):
315楼 Linked List Cycle II

补充内容 (2015-7-26 21:07):
316楼 Convert Sorted List to Binary Search Tree

补充内容 (2015-7-26 21:09):
317楼 Climbing Stairs

补充内容 (2015-7-27 12:07):
由于被审核的帖子通过了，所以插楼导致之前的目录几乎都错位了(-_-)||
我还是把目录放在我的Github里好了，待我重新写好一份目录以后，会在此给出链接的。

zhuli19901106 发表于 2015-7-18 23:27
真是大道至简。。
同样一题我写完了自己都看不懂，你的版本20行就搞定。学习了~
有了stellari，天黑都 ...

其实是有公式的。。

LeetCode上一道类似的题目 #233-Number-of-Digit-One (https://leetcode.com/problems/number-of-digit-one/)
只用六行py代码就AC了:

1. class Solution:
   
2.     # @param {integer} n
   
3.     # @return {integer}
   
4.     def countDigitOne(self, n):
   
5.         counter, i = 0, 1
   
6.         while i <= n:
   
7.             a, b = n/i, n%i
   
8.             counter += (a+8)/10*i + int(a%10==1)*(b+1)
   
9.             i *= 10
   
10.         return counter
    

复制代码

zhuli19901106 发表于 2015-7-23 17:26
审核的人干嘛去了？在跟公务员比效率吗？审核五天之内不给通过的话，审核员全家都是孙子。有种删我贴啊~
...

This is the system problem, not one want to Shenhe your post. Just be calm. People are volunteer to manage  the bbs, not pay

zhuli19901106 发表于 2015-7-23 21:29
好吧，如果是程序计算文本相似度来过滤垃圾信息的话，那也没办法了。。
我也不能每题换种语言去写@_@

楼主加油，支持你！

又天亮了，待我先补个觉去~

zhuli19901106 发表于 2015-7-18 06:07
又天亮了，待我先补个觉去~

要是有Java版本就好了。

水逼一枚 发表于 2015-7-18 07:54
要是有Java版本就好了。

我下次重刷leetcode或者lintcode，就打算换java了。目前java还不熟，主要用的C++和python。

牛牛啊

偶java刷的差不多了。 想用c++

请问lintCode和leetCode重复率大概多高呢？

求lz传了python的解法吧~~

handsomecool 发表于 2015-7-18 11:40
请问lintCode和leetCode重复率大概多高呢？

几乎leetcode所有题目lintcode都有，也有两者互不包含的题目。总体来说lintcode比leetcode要略难一些。

A + B Problem
题意：求32位整数之和A + B
解法1：直接相加就不提了。此处可以考虑用全加器的原理，纯位操作来搞。
代码1：

1. class Solution {
   
2. public:
   
3.     /*
   
4.      * @param a: The first integer
   
5.      * @param b: The second integer
   
6.      * @return: The sum of a and b
   
7.      */
   
8.     int aplusb(int a, int b) {
   
9.         int s = 0;
   
10.         int c = 0;
    
11.         addBit(a, b, s, 0, c);
    
12.         addBit(a, b, s, 1, c);
    
13.         addBit(a, b, s, 2, c);
    
14.         addBit(a, b, s, 3, c);
    
15.         addBit(a, b, s, 4, c);
    
16.         addBit(a, b, s, 5, c);
    
17.         addBit(a, b, s, 6, c);
    
18.         addBit(a, b, s, 7, c);
    
19.         addBit(a, b, s, 8, c);
    
20.         addBit(a, b, s, 9, c);
    
21.         addBit(a, b, s, 10, c);
    
22.         addBit(a, b, s, 11, c);
    
23.         addBit(a, b, s, 12, c);
    
24.         addBit(a, b, s, 13, c);
    
25.         addBit(a, b, s, 14, c);
    
26.         addBit(a, b, s, 15, c);
    
27.         addBit(a, b, s, 16, c);
    
28.         addBit(a, b, s, 17, c);
    
29.         addBit(a, b, s, 18, c);
    
30.         addBit(a, b, s, 19, c);
    
31.         addBit(a, b, s, 20, c);
    
32.         addBit(a, b, s, 21, c);
    
33.         addBit(a, b, s, 22, c);
    
34.         addBit(a, b, s, 23, c);
    
35.         addBit(a, b, s, 24, c);
    
36.         addBit(a, b, s, 25, c);
    
37.         addBit(a, b, s, 26, c);
    
38.         addBit(a, b, s, 27, c);
    
39.         addBit(a, b, s, 28, c);
    
40.         addBit(a, b, s, 29, c);
    
41.         addBit(a, b, s, 30, c);
    
42.         addBit(a, b, s, 31, c);
    
43.         return s;
    
44.     }
    
45. private:
    
46.     void addBit(int &a, int &b, int &s, int i, int &c) {
    
47.         s |= (a ^ b ^ c) & (1 << i);
    
48.         c = (a & b & (1 << i)) | (b & c & (1 << i)) | (c & a & (1 << i));
    
49.         c <<= 1;
    
50.     }
    
51. };
    

复制代码

复杂度1：时间可以认为是O(logN)，毕竟数据的位数与数据本身是对数关系。空间也一样。

解法2：和前面一样，但是把我那白痴的32个函数调用改成移位循环。感谢stellari提醒。面试时要是纸上coding，那手写32个估计累死。233~
代码2：

1. // Use your smart, not your brute force...
   
2. class Solution {
   
3. public:
   
4.     /*
   
5.      * @param a: The first integer
   
6.      * @param b: The second integer
   
7.      * @return: The sum of a and b
   
8.      */
   
9.     int aplusb(int a, int b) {
   
10.         int s = 0;
    
11.         int c = 0;
    
12.         int mask;
    
13.         for (mask = 1; mask; mask <<= 1) {
    
14.             addBit(a, b, s, mask, c);
    
15.         }
    
16.         return s;
    
17.     }
    
18. private:
    
19.     void addBit(int &a, int &b, int &s, int mask, int &c) {
    
20.         s |= (a ^ b ^ c) & mask;
    
21.         c = (a & b & mask) | (b & c & mask) | (c & a & mask);
    
22.         c <<= 1;
    
23.     }
    
24. };

复制代码

复杂度2：和解法1一样