一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 17261|回复: 354
收起左侧

[算法题] 分享我的Lintcode题解,目前进度244/248

  [复制链接] |试试Instant~ |关注本帖
zhuli19901106 发表于 2015-7-18 06:04:50 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 zhuli19901106 于 2015-7-18 17:51 编辑

从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里好了,待我重新写好一份目录以后,会在此给出链接的。

评分

14

查看全部评分

EroicaCMCS 发表于 2015-7-19 03:42:23 | 显示全部楼层
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
复制代码
回复 支持 2 反对 0

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-19 17:00:46 | 显示全部楼层
Maximum Subarray III
题意:hard难度。给定一个数组,从其中选取不重叠的K个子数组,使得和最大。
解法:这题我开始想了俩钟头都没思路,就是因为对前面两题的DP没有仔细想。这题的关键在于理解“局部最优”和“全局最优”。比如从前i个元素选出j个子数组,那么什么是全局和局部?区别就在于是否包含了第i个元素。不包含,那就是全局的,包含了就是局部的。局部和全局相互依赖于彼此,而且交替更新,才有了O(K * N)的DP。
我的代码直接用空间优化了,所以空间是O(N)的。
代码:
  1. // O(k * n) DP with O(n) space, yes!
  2. #include <algorithm>
  3. #include <climits>
  4. using namespace std;

  5. class Solution {
  6. public:
  7.     /**
  8.      * @param nums: A list of integers
  9.      * @param k: An integer denote to find k non-overlapping subarrays
  10.      * @return: An integer denote the sum of max k non-overlapping subarrays
  11.      */
  12.     int maxSubArray(vector<int> nums, int k) {
  13.         vector<int> &a = nums;
  14.         int n = a.size();
  15.         if (k <= 0 || k > n) {
  16.             return 0;
  17.         }
  18.         vector<vector<int> > dp(2, vector<int>(n, 0));
  19.         vector<int> mx(n, 0);
  20.         int i, j;
  21.         int f, nf;
  22.         
  23.         mx[0] = dp[0][0] = a[0];
  24.         for (i = 1; i < n; ++i) {
  25.             dp[0][i] = max(dp[0][i - 1], 0) + a[i];
  26.         }
  27.         mx[0] = dp[0][0];
  28.         for (i = 1; i < n; ++i) {
  29.             mx[i] = max(mx[i - 1], dp[0][i]);
  30.         }
  31.         
  32.         f = 1;
  33.         nf = !f;
  34.         for (i = 1; i < k; ++i) {
  35.             dp[f][i] = dp[nf][i - 1] + a[i];
  36.             for (j = i + 1; j < n; ++j) {
  37.                 dp[f][j] = max(dp[f][j - 1], mx[j - 1]) + a[j];
  38.             }
  39.             mx[i] = dp[f][i];
  40.             for (j = i + 1; j < n; ++j) {
  41.                 mx[j] = max(mx[j - 1], dp[f][j]);
  42.             }
  43.             f = !f;
  44.             nf = !f;
  45.         }
  46.         return mx[n - 1];
  47.     }
  48. };
复制代码
复杂度:时间O(K * N),空间O(N)

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

love1point 发表于 2015-8-6 00:52:46 | 显示全部楼层
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
回复 支持 1 反对 0

使用道具 举报

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

楼主加油,支持你!
回复 支持 1 反对 0

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-23 21:29:17 | 显示全部楼层
stellari 发表于 2015-7-23 21:27
我想,有可能是你在“短时间内发了大量相似的帖子”。我在的那个论坛中以前都无需审核,结果经常有人用脚 ...

好吧,如果是程序计算文本相似度来过滤垃圾信息的话,那也没办法了。。
我也不能每题换种语言去写@_@
回复 支持 1 反对 0

使用道具 举报

stellari 发表于 2015-7-23 21:14:55 | 显示全部楼层
zhuli19901106 发表于 2015-7-23 18:46
Merge Two Sorted Lists
题意:给定两个有序链表,归并成一条。
解法:基础题。既可以用一个额外的dummy  ...

我记得在哪里看过,dummy不要定义成动态的,比如:

ListNode dummy(0);
dummy.next = &head;
...
return dummy.next;

这样完全不需要考虑内存动态分配回收的问题。

还有就是可以把dummy定义成static的。无论调用多少次函数,都不需要重新创建dummy.
回复 支持 1 反对 0

使用道具 举报

stellari 发表于 2015-7-18 22:53:38 | 显示全部楼层
zhuli19901106 发表于 2015-7-18 15:50
A + B Problem
题意:求32位整数之和A + B
解法1:直接相加就不提了。此处可以考虑用全加器的原理,纯位 ...

这题其实还有更简单的解法。原理是:先完全不带Carry Flag每位加一遍,得到一个临时的sum;再单独把每位的Carry Flag都找出来(还要左移一位)。然后再把sum和carry相加。然后又得到新的sum和carry……不停把sum和carry相加,直到carry全为0为止。最差时间复杂度同样是O(logN),不过,如果这两个数字相加的进位很少的话,实际的循环次数也会很少:

  1. int aplusb(int a, int b) {
  2.         while (b) {
  3.             int sum = a ^ b;    // Adding without carry flag
  4.             int carry = (a & b) << 1; // Get only the carry flag
  5.             a = sum;            // Then in the next step, add
  6.             b = carry;          // sum(without CF) and CF only
  7.         }                       // Until one of them (usualy CF) becomes 0.
  8.         return a;      // Now at least one of a and b must be 0
  9.     }
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-18 06:07:19 | 显示全部楼层
又天亮了,待我先补个觉去~
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-7-18 07:54:11 | 显示全部楼层
zhuli19901106 发表于 2015-7-18 06:07
又天亮了,待我先补个觉去~

要是有Java版本就好了。
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-18 08:04:30 | 显示全部楼层
水逼一枚 发表于 2015-7-18 07:54
要是有Java版本就好了。

我下次重刷leetcode或者lintcode,就打算换java了。目前java还不熟,主要用的C++和python。
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-7-18 08:48:24 | 显示全部楼层
偶java刷的差不多了。 想用c++
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-7-18 11:40:38 | 显示全部楼层
请问lintCode和leetCode重复率大概多高呢?
回复 支持 反对

使用道具 举报

julia1006 发表于 2015-7-18 12:43:16 | 显示全部楼层
求lz传了python的解法吧~~
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-18 15:31:06 | 显示全部楼层
handsomecool 发表于 2015-7-18 11:40
请问lintCode和leetCode重复率大概多高呢?

几乎leetcode所有题目lintcode都有,也有两者互不包含的题目。总体来说lintcode比leetcode要略难一些。
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-18 15:50:07 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-18 22:35 编辑

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一样

回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-18 16:01:21 | 显示全部楼层
Trailing Zeros
题意:给定N,求N的阶乘末尾有多少个0
解法:0的个数等于N!可以分解出多少个10,也就是多少个5,所以不断除以5并求和即可。
代码:
  1. class Solution {
  2. public:
  3.     // param n : description of n
  4.     // return: description of return
  5.     long long trailingZeros(long long n) {
  6.         long long int sum = 0;
  7.         while (n > 0) {
  8.             sum += n / 5;
  9.             n /= 5;
  10.         }
  11.         return sum;
  12.     }
  13. };
复制代码
复杂度:时间O(log N),空间O(1)。
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-18 16:11:37 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-18 22:36 编辑

Digit Counts
题意:给定一个数字k,以及一个整数n,求0~n的所有整数中,数字k出现了多少次。k可以是0~9。
解法:典型的数位动归题目,这种题直接从0数到N肯定会被面试官鄙视的。这题头疼的是0的处理,我的代码中1~9可以用同一套解法,0单独处理。数组sum{i}表示i位数中总共出现了多少个1~9,sum0{i}表示数组中总共出现了多少个0。至于它们为什么不能归为同类,可以这么理解。最高位数字可以是1~9,而不能是0。所以0要单独处理,思路也不一样。这题我的实现很复杂,自己都觉得晕,请问有效率不差,而且更简洁易懂的思路吗?
代码:
  1. typedef long long int LL;

  2. class Solution {
  3. public:
  4.     Solution() {
  5.         int i, j;
  6.         LL b10;
  7.         
  8.         sum[0] = 0;
  9.         sum[1] = 1;
  10.         b10 = 1;
  11.         for (i = 2; i < M; ++i) {
  12.             b10 *= 10;
  13.             sum[i] = 10 * sum[i - 1] + b10;
  14.         }
  15.         
  16.         LL ss;

  17.         sum0[0] = 0;
  18.         sum0[1] = 0;
  19.         b10 = 1;
  20.         for (i = 2; i < M; ++i) {
  21.             b10 *= 10;
  22.             ss = 0;
  23.             for (j = 1; j < i; ++j) {
  24.                 ss += sum0[j];
  25.             }
  26.             sum0[i] = 9 * (leadingZero(b10 - 1, i - 1) + ss);
  27.         }
  28.     }
  29.     /*
  30.      * param k : As description.
  31.      * param n : As description.
  32.      * return: How many k's between 0 and n.
  33.      */
  34.     int digitCounts(int k, int n) {
  35.         if (k == 0) {
  36.             return countZero(n) + 1;
  37.         }
  38.         return countDigit(n, k);
  39.     }
  40. private:
  41.     static const int M = 19;
  42.     LL sum[M];
  43.     LL sum0[M];
  44.    
  45.     LL countDigit(LL x, int d) {
  46.         LL b10;
  47.         int idx;

  48.         if (x < d) {
  49.             return 0;
  50.         } else if (x < 10) {
  51.             return 1;
  52.         }

  53.         b10 = 1;
  54.         idx = 0;
  55.         while (b10 * 10 <= x) {
  56.             b10 *= 10;
  57.             ++idx;
  58.         }
  59.         if (x / b10 > d) {
  60.             return (x / b10) * sum[idx] + b10 + countDigit(x % b10, d);
  61.         } else if (x / b10 == d) {
  62.             return (x / b10) * sum[idx] + (x % b10 + 1) + countDigit(x % b10, d);
  63.         } else {
  64.             return (x / b10) * sum[idx] + countDigit(x % b10, d);
  65.         }
  66.     }
  67.    
  68.     LL leadingZero(LL x, int idx) {
  69.         LL b10 = 1;
  70.         LL sum = idx;
  71.         int bi = 1;
  72.         while (b10 * 10 <= x) {
  73.             sum += 9 * b10 * (idx - bi);
  74.             b10 *= 10;
  75.             ++bi;
  76.         }
  77.         sum += (x - b10 + 1) * (idx - bi);
  78.         return sum;
  79.     }
  80.    
  81.     LL countZero(LL x) {
  82.         LL b10;
  83.         int idx;
  84.         
  85.         if (x < 10) {
  86.             return 0;
  87.         }

  88.         b10 = 1;
  89.         idx = 0;
  90.         while (b10 * 10 <= x) {
  91.             b10 *= 10;
  92.             ++idx;
  93.         }

  94.         LL ans = 0;
  95.         LL ss = 0;
  96.         int i;

  97.         for (i = 1; i <= idx; ++i) {
  98.             ans += sum0[i];
  99.             ss += sum0[i];
  100.         }
  101.         ans += (x / b10 - 1) * (ss + leadingZero(b10 - 1, idx));
  102.         ans += leadingZero(x % b10, idx) + countZero(x % b10);

  103.         return ans;
  104.     }
  105. };
复制代码
复杂度:时间上对DP数组的预处理O(log N),函数调用过程也是O(log N)。空间也是O(log N)。
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-18 16:21:02 | 显示全部楼层
Ugly Number
题意:这题和Humble Number一样,数论里名字有好几个,下面这个应该是一般化的定义。就是求所有质因数只有3, 5, 7的数里,从小到大排第k的那个。
https://en.wikipedia.org/wiki/Smooth_number
解法:3个指针逐步向前移,每次选取最小值。
代码:
  1. #include <algorithm>
  2. using namespace std;

  3. typedef long long int LL;

  4. class Solution {
  5. public:
  6.     /*
  7.      * @param k: The number k.
  8.      * @return: The kth prime number as description.
  9.      */
  10.     LL kthPrimeNumber(int k) {
  11.         vector<LL> v;
  12.         int p1, p2, p3;
  13.         LL a1, a2, a3;
  14.         LL val;
  15.         
  16.         p1 = p2 = p3 = 0;
  17.         v.push_back(1);
  18.         while (v.size() <= k) {
  19.             a1 = v[p1] * 3;
  20.             a2 = v[p2] * 5;
  21.             a3 = v[p3] * 7;
  22.             val = min(a1, min(a2, a3));
  23.             if (val == a1) {
  24.                 ++p1;
  25.             }
  26.             if (val == a2) {
  27.                 ++p2;
  28.             }
  29.             if (val == a3) {
  30.                 ++p3;
  31.             }
  32.             v.push_back(val);
  33.         }
  34.         return v[k];
  35.     }
  36. };
复制代码
复杂度:时间空间都是O(K)
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-18 16:26:09 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-18 22:29 编辑

Kth Largest Element
题意:求一个数组中,第K大的数。允许交换数组中的元素。
解法1:根据快排改造得到快速选择算法。注意题目要求的是第K大,不是第K小。
代码1:
  1. #include <algorithm>
  2. using namespace std;

  3. class Solution {
  4. public:
  5.     /*
  6.      * param k : description of k
  7.      * param nums : description of array and index 0 ~ n-1
  8.      * return: description of return
  9.      */
  10.     int kthLargestElement(int k, vector<int> nums) {
  11.         int n = nums.size();
  12.         return quickSelect(nums, 0, n - 1, n - k);
  13.     }
  14. private:
  15.     int quickSelect(vector<int> &a, int ll, int rr, int k) {
  16.         if (ll == rr) {
  17.             return a[k];
  18.         }
  19.         int i = ll + 1;
  20.         int j = rr;
  21.         int piv = a[ll];
  22.         while (true) {
  23.             while (i <= j && a[i] < piv) {
  24.                 ++i;
  25.             }
  26.             while (i <= j && a[j] > piv) {
  27.                 --j;
  28.             }
  29.             if (i > j) {
  30.                 break;
  31.             }
  32.             swap(a[i++], a[j--]);
  33.         }
  34.         swap(a[ll], a[j]);
  35.         if (k < j) {
  36.             return quickSelect(a, ll, j - 1, k);
  37.         } else if (k > j) {
  38.             return quickSelect(a, j + 1, rr, k);
  39.         } else {
  40.             return a[k];
  41.         }
  42.     }
  43. };
复制代码
复杂度1:时间可以做到O(N),但由于是递归,理论上空间复杂度介于O(log N)和O(N)之间。不知道O(1)空间的算法应该怎么做?

解法2:感谢stellari的提醒,递归经过简单的改造就变成了迭代。我居然没看出自己写的是尾递归(-_-)||
代码2:
  1. // The iterative version
  2. #include <algorithm>
  3. using namespace std;

  4. class Solution {
  5. public:
  6.     /*
  7.      * param k : description of k
  8.      * param nums : description of array and index 0 ~ n-1
  9.      * return: description of return
  10.      */
  11.     int kthLargestElement(int k, vector<int> nums) {
  12.         int n = nums.size();
  13.         return quickSelect(nums, 0, n - 1, n - k);
  14.     }
  15. private:
  16.     int quickSelect(vector<int> &a, int ll, int rr, int k) {
  17.         int i;
  18.         int j;
  19.         int piv;
  20.         
  21.         while (true) {
  22.             if (ll == rr) {
  23.                 return a[k];
  24.             }
  25.             i = ll + 1;
  26.             j = rr;
  27.             piv = a[ll];
  28.             while (true) {
  29.                 while (i <= j && a[i] < piv) {
  30.                     ++i;
  31.                 }
  32.                 while (i <= j && a[j] > piv) {
  33.                     --j;
  34.                 }
  35.                 if (i > j) {
  36.                     break;
  37.                 }
  38.                 swap(a[i++], a[j--]);
  39.             }
  40.             swap(a[ll], a[j]);
  41.             if (k < j) {
  42.                 rr = j - 1;
  43.             } else if (k > j) {
  44.                 ll = j + 1;
  45.             } else {
  46.                 return a[k];
  47.             }
  48.         }
  49.     }
  50. };
复制代码
复杂度2:由于是迭代,所以空间变成O(1)了,时间是O(N)。

回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-18 16:32:37 | 显示全部楼层
Merge Sorted Array II
题意:归并两个有序数组,存在新数组里。
解法:略
代码:
  1. class Solution {
  2. public:
  3.     /**
  4.      * @param A and B: sorted integer array A and B.
  5.      * @return: A new sorted integer array
  6.      */
  7.     vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
  8.         vector<int> C;
  9.         int i, j;
  10.         int na, nb;
  11.         
  12.         na = A.size();
  13.         nb = B.size();
  14.         i = j = 0;
  15.         while (i < na && j < nb) {
  16.             if (A[i] < B[j]) {
  17.                 C.push_back(A[i++]);
  18.             } else {
  19.                 C.push_back(B[j++]);
  20.             }
  21.         }
  22.         while (i < na) {
  23.             C.push_back(A[i++]);
  24.         }
  25.         while (j < nb) {
  26.             C.push_back(B[j++]);
  27.         }
  28.         return C;
  29.     }
  30. };
复制代码
复杂度:时间O(N + M),空间O(1)。
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-18 16:37:23 | 显示全部楼层
Binary Tree Serialization
题意:序列化和反序列化一棵二叉树。
解法:这题其实考察的是对二叉树遍历的理解,不论前序、后序、中序、层次遍历都可以。我倾向于选前序或者层次遍历。序列化的表示方法则可以自有选择。
代码:
  1. #include <vector>
  2. using namespace std;
  3. /**
  4. * Definition of TreeNode:
  5. * class TreeNode {
  6. * public:
  7. *     int val;
  8. *     TreeNode *left, *right;
  9. *     TreeNode(int val) {
  10. *         this->val = val;
  11. *         this->left = this->right = NULL;
  12. *     }
  13. * }
  14. */
  15. class Solution {
  16. public:
  17.     string serialize(TreeNode *root) {
  18.         serializePreorder(root);
  19.         
  20.         string ans = "";
  21.         int n = v.size();
  22.         int i;
  23.         for (i = 0; i < n; ++i) {
  24.             ans += v[i];
  25.             ans.push_back(' ');
  26.         }
  27.         ans.pop_back();
  28.         v.clear();
  29.         
  30.         return ans;
  31.     }

  32.     TreeNode *deserialize(string data) {
  33.         int n = data.length();
  34.         int i, j;
  35.         string s;
  36.         
  37.         while (i < n) {
  38.             s = "";
  39.             j = i;
  40.             while (j < n && data[j] != ' ') {
  41.                 s.push_back(data[j++]);
  42.             }
  43.             v.push_back(s);
  44.             ++j;
  45.             i = j;
  46.         }
  47.         
  48.         idx = 0;
  49.         TreeNode *root;
  50.         deserializePreorder(root);
  51.         v.clear();
  52.         
  53.         return root;
  54.     }
  55. private:
  56.     vector<string> v;
  57.     int idx;
  58.    
  59.     void serializePreorder(TreeNode *root) {
  60.         if (root == NULL) {
  61.             v.push_back("#");
  62.             return;
  63.         }
  64.         v.push_back(to_string(root->val));
  65.         serializePreorder(root->left);
  66.         serializePreorder(root->right);
  67.     }
  68.    
  69.     void deserializePreorder(TreeNode *&root) {
  70.         if (v[idx] == "#") {
  71.             root = NULL;
  72.             ++idx;
  73.         } else {
  74.             root = new TreeNode(atoi(v[idx].data()));
  75.             ++idx;
  76.             deserializePreorder(root->left);
  77.             deserializePreorder(root->right);
  78.         }
  79.     }
  80. };
复制代码
复杂度:时间O(N),空间O(N)。
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-18 16:41:41 | 显示全部楼层
Rotate String
题意:给定一个字符串,把它循环右移K位。
解法:使用神奇的reverse函数,注意处理边界情况。
代码:
  1. #include <algorithm>
  2. using namespace std;

  3. class Solution {
  4. public:
  5.   /**
  6.      * param A: A string
  7.      * param offset: Rotate string with offset.
  8.      * return: Rotated string.
  9.      */
  10.     string rotateString(string A, int offset) {
  11.         if (A == "") {
  12.             return A;
  13.         }
  14.         offset %= A.length();
  15.         if (offset == 0) {
  16.             return A;
  17.         }
  18.         reverse(A.begin(), A.begin() + A.length() - offset);
  19.         reverse(A.begin() + A.length() - offset, A.end());
  20.         reverse(A.begin(), A.end());
  21.         return A;
  22.     }
  23. };
复制代码
复杂度:O(N)
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-18 16:44:57 | 显示全部楼层
Fizz Buzz
题意:纯水题,在面试里能碰见也算是人品爆发了。
解法:水过
代码:
  1. class Solution {
  2. public:
  3.     /**
  4.      * param n: As description.
  5.      * return: A list of strings.
  6.      */
  7.     vector<string> fizzBuzz(int n) {
  8.         vector<string> results;
  9.         for (int i = 1; i <= n; i++) {
  10.             if (i % 15 == 0) {
  11.                 results.push_back("fizz buzz");
  12.             } else if (i % 5 == 0) {
  13.                 results.push_back("buzz");
  14.             } else if (i % 3 == 0) {
  15.                 results.push_back("fizz");
  16.             } else {
  17.                 results.push_back(to_string(i));
  18.             }
  19.         }
  20.         return results;
  21.     }
  22. };
复制代码
复杂度:时间O(N),空间O(1)
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-18 16:50:26 | 显示全部楼层
Search Range in Binary Search Tree
题意:在一个BST中,给定K1个K2两个值,输出BST中所有介于两者之间的值,要求升序输出。
解法:对中序遍历进行修改,超出K1~K2的范围就不用继续递归了,可以理解为剪枝。
代码:
  1. /**
  2. * Definition of TreeNode:
  3. * class TreeNode {
  4. * public:
  5. *     int val;
  6. *     TreeNode *left, *right;
  7. *     TreeNode(int val) {
  8. *         this->val = val;
  9. *         this->left = this->right = NULL;
  10. *     }
  11. * }
  12. */
  13. class Solution {
  14. public:
  15.     /**
  16.      * @param root: The root of the binary search tree.
  17.      * @param k1 and k2: range k1 to k2.
  18.      * @return: Return all keys that k1<=key<=k2 in ascending order.
  19.      */
  20.     vector<int> searchRange(TreeNode* root, int k1, int k2) {
  21.         ans.clear();
  22.         ll = k1;
  23.         rr = k2;
  24.         
  25.         inorder(root);
  26.         return ans;
  27.     }
  28. private:
  29.     vector<int> ans;
  30.     int ll;
  31.     int rr;
  32.    
  33.     void inorder(TreeNode *root) {
  34.         if (root == NULL) {
  35.             return;
  36.         }
  37.         if (root->val > ll) {
  38.             inorder(root->left);
  39.         }
  40.         if (root->val >= ll && root->val <= rr) {
  41.             ans.push_back(root->val);
  42.         }
  43.         if (root->val < rr) {
  44.             inorder(root->right);
  45.         }
  46.     }
  47. };
复制代码
复杂度:时间基本还是O(N),对递归进行剪枝并不降低理论复杂度。空间也是O(N)。
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-18 16:55:08 | 显示全部楼层
Min Stack
题意:实现一个栈,除了普通栈的功能外,还能随时返回栈中的最小值。
解法:经典题目,用一个额外的栈维护最小值。每当遇到小于等于当前最小值的,就压入栈中。这个最小栈始终是单调的。
代码:
  1. #include <stack>
  2. using namespace std;

  3. class MinStack {
  4. public:
  5.     MinStack() {}

  6.     void push(int number) {
  7.         if (st.empty() || number <= mst.top()) {
  8.             mst.push(number);
  9.         }
  10.         st.push(number);
  11.     }

  12.     int pop() {
  13.         int val = st.top();
  14.         if (mst.top() == st.top()) {
  15.             mst.pop();
  16.         }
  17.         st.pop();
  18.         return val;
  19.     }

  20.     int min() {
  21.         return mst.top();
  22.     }
  23. private:
  24.     stack<int> st, mst;
  25. };
复制代码
复杂度:每个基本操作都是O(1)时间,维护一个最小栈需要额外O(N)空间。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 02:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表