程序员面试经典题-菜木鸟

《程序员面试经典题-菜木鸟》由会员分享，可在线阅读，更多相关《程序员面试经典题-菜木鸟（78页珍藏版）》请在装配图网上搜索。

1、ContentsA.Permutation and Combination51.Permutations52.Combinations63.Combination sum74.Subsets7B.Two Pointers and Sliding Window91.Remove duplicates from sorted array92.Longest substring without repeating characters93.Container with most water104.3 Sum105.4 Sum116.Merge two sorted arrays without ad

2、ditional memory127.Merge k sorted lists128.strStr()149.Substring with concatenation of all words1510.Trapping rain water1511.Valid palindrome1612.Minimum window substring1713.Sort colors1714.Balance paranthesis1815.Minimum distance of three points18C.Binary Search201.Median of two sorted arrays202.D

3、ivide two integers203.Search in rotated sorted array214.Search for a range225.Find missing number236.Pow(x,n)237.Sqrt(x)248.Search a 2D matrix249.Find local minimum2510.Find kth smallest number in two sorted arrays25D.Linked List271.Remove nth node from end of list272.Remove duplicates273.Merge two

4、sorted lists284.Reverse nodes in k-group285.Rotate list296.Partition list307.Reverse list308.Detecting loop 319.Find the middle node3210.Reservoir sampling3211.Clone the complex linked list3212.Check if a singly linked list is palindrome3413.Get the intersection node of two linked lists3414.Union an

5、d intersection of two linked lists35E.Binary tree / Binary search tree371.Lowest common ancestor of a binary tree372.Lowest common ancestor of a binary tree II373.Two sum in a BST384.Minimum depth of binary tree395.Symmetric tree396.Find closest value of a BST397.Find k nearest neightbours in BST408

6、.Validate BST409.Recover BST4010.Convert sorted array to BST4111.Convert sorted linked list to BST4112.Binary tree inorder traversal4113.Binary tree level order traversal4214.Flatten binary tree to linked list4315.Construct Binary Tree from Inorder and Preorder/Postorder Traversal4416.Binary tree ma

7、ximum path sum4517.Serialization/Deserialization of a Binary Tree4618.Subtree4619.Path sum4620.Balanced binary tree4721.Build double linked list from BST47F.Greedy Strategy and Dynamic Programming491.Triangle492.Maximum subarray493.Unique path494.Unique path with obstacles505.Edit distance506.Best t

8、ime to buy and sell stock517.Unique binary search trees528.Decode ways539.Regular expression matching5310.Wildcard matching5511.Jump game5612.Minimum number of coins needed to represent an amount5613.Longest increasing sequence5714.Cut a batten5715.Segment string58G.Backtracking and Recursion591.Let

9、ter combinations of a phone number592.Generate parentheses593.Sudoku solver604.N-Queens615.Word search616.Restore IP Address627.Generate Gray code63H.Graph641.Check whether the graph is bigraph642.Topological sort643.Word ladder64I.Design Questions661.LRU cache design66J.Other Topics672.Valid parent

10、heses673.Valid number674.Set matrix zeroes685.Anagram696.Rotate image707.Spiral matrix708.Multiply strings719.Merge intervals7110.Insert interval7211.Text justification7312.Integer to Roman7313.Roman to integer7414.Reverse integer7415.Find the max and min elements of an unsorted integer7516.Rotate a

11、rray7517.Find k bigest elements7618.Word ladder7619.Longest consecutive sequence7720.Shuffle an array78A. Permutation and Combination排列组合题，包括子集生成，基本都是使用经典的回溯法求解。大多的follow up都是与是否有重复元素有关，比如permutations和subsets。处理重复元素的比较常见的方法是首先对原数组进行排序，然后在递归时判断当前处理元素是否与上一个元素相同，如果有必要还可以添置是否使用过的bool型变量进行判断。甚至是另外设置一个num

12、bers和count数组来标记上去除重复以后的数字以及每一个数字的重复次数。下面给出的solution是相对比较简洁和易懂的。1. Permutations Leetcode 46,47Given a collection of numbers, return all possible permutations.For example,1,2,3have the following permutations:1,2,3,1,3,2,2,1,3,2,3,1,3,1,2, and3,2,1.void perm(vector &num, vectorvector &result, int nStar

13、t, int nEnd) if (nStart nEnd-1注意终止条件判断。) perm(num, result, nStart+1, nEnd); for (int i = nStart + 1; i nEnd; +i) swap(numnStart,numi);全排列的主要思路就是交换数组的元素，在递归后需要交换回来。注意循环前要首先递归一次。 perm(num, result, nStart+1, nEnd); swap(numnStart,numi); else result.push_back(num);Code 1 PermutationFollow up: the given

14、number might contain duplicates, return all possible unique permutations这类带有避免重复结果的递归题，往往用一个辅助的used数组来标记是否已经用过，类似的题还有带重复元素的数组求子集的。. vectorvector permuteUnique(vector &num) vector used(num.size(), false); vector path; vectorvector ret; sort(num.begin(), num.end(); dfs(num, used, path, ret); return re

15、t; void dfs(vector &num, vector &used, vector &path, vectorvector &ret) if (num.size() = path.size() ret.push_back(path); return; for (int i = 0; i num.size(); +i) if (usedi | (i != 0 & numi = numi - 1 & usedi - 1)如果去掉这个判断则结果就是普通的全排列。) continue; usedi = true; path.push_back(numi); dfs(num, used, pat

16、h, ret); usedi = false; path.pop_back(); Code 2 Permutation IIWe can also use STLs next_permutation method:vectorvector permuteUnique(vector &num) sort(num.begin(), num.end() ) ; vectorvector ret; do ret.push_back( num ); while(next_permutation(num.begin(), num.end()!=false); return ret; Code 3 Perm

17、utation II (using STL)2. Combinations Leetcode 77void com(int n, int k, int l, int pos,N代表给定的数字，k为组合数的个数，l是当前组合数的第几位，pos是原数字的第几个。本题可以很容易改成，给定一个数组（无重复数字）给定k大小求组合数。代码略做改动即可变成求子集。 vector vector &result, vector &rcd) if(l = k) result.push_back(rcd); return; for(int i = pos; i n; +i) rcdl = i + 1; com(n,

18、 k, l+1, i+1, result, rcd); vectorvector combine(int n, int k) vector vector result; vector rcd(k); com(n, k, 0, 0, result, rcd); return result;Code 4 Combination3. Combination sum本题也可以有follow up（leetcode的Combination II），比如给定数组中的数字只能用一次等等，只需要稍微改动代码即可。 Leetcode 39Given a set of candidate numbers (C)

19、and a target number (T), find all unique combinations inCwhere the candidate numbers sums toT.Thesamerepeated number may be chosen fromCunlimited number of times.Note: All numbers (including target) will be positive integers. Elements in a combination (a1,a2, a3,ak) must be in non-descending order.

20、(ie,a1=a2= a3 = = ak). The solution set must not contain duplicate combinations.For example, given candidate set2,3,6,7and target7,A solution set is:72, 2, 3void dfs(vectorvector & ret, vector path, vector& n, int p, int curSum, int target) if(curSum target注意这个一定要写，能够避免很多无意义的递归。) return; if(curSum =

21、 target) ret.push_back(path); return; for(int i = p; i n.size(); i+) curSum += ni; path.push_back(ni); dfs(ret, path, n, i这里传的是i，也就意味着原数组中的每一个数字可以用多次，如果题目要求一个数字只能用一次，这里就要传i+1。, curSum, target); curSum -= ni; path.pop_back(); vectorvector combinationSum( vector &candidates, int target) vectorvector r

22、et; vector path; sort(candidates.begin(), candidates.end(); dfs(ret, path, candidates,0,0,target); return ret; Code 5 Combination sum4. Subsets Leetcode 78,90Given a set of distinct integers,S, return all possible subsets. vectorvector subsets(vector &S) vector path; vectorvector result; sort(S.begi

23、n(), S.end(); sub(S, 0, path, result); return result; void sub(vector &s, int begin, vector &path, vectorvector &result) result.push_back(path); for (int i = begin; i s.size(); +i) /if (i != begin & si = si - 1) continue;这句代码可以保证，当S中有重复元素时，可避免重复结果。 path.push_back(si); sub(s, i + 1, path, result); pa

24、th.pop_back(); Code 6 SubsetsB. Two Pointers and Sliding Window多指针/滑动窗口法是面试题中最常见的题型之一，大多是利用多个指针对一个数组或链表 进行扫描，比如以不同 速度从头向尾扫描，或者分别从头和尾向中间扫描等等。使用多指针的目的是尽量减少循环pass的次数以提高效率。需要注意的是扫描终止条件的判断。1. Remove duplicates from sorted arrayint removeDuplicates(int A, int n) int i=0; int j; if (n=1) return n; for (j=1

25、;jn;j+) if (Aj != Ai) A+i=Aj; return i+1; 2. Longest substring without repeating characters Leetcode 3Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for abcabcbb is abc, which the length is 3. For bb

26、bbb the longest substring is b, with the length of 1. int lengthOfLongestSubstring(string s) int i = 0, j = 0; int n = s.size(); int maxlen = 0; bool map256 = false; while(j n) if(!mapsj) mapsj+ = true; else maxlen = max(j-i,maxlen); while(si != sj) mapsi = false; i+; i+; j+; return max(maxlen,j-i)循

27、环终止后依然要判断下最后一次不重复的子串。; Code 7 Longest substring without repeating3. Container with most water Leetcode 11Givennnon-negative integersa1,a2, .,an, where each represents a point at coordinate (i,ai).nvertical lines are drawn such that the two endpoints of lineiis at (i,ai) and (i, 0). Find two lines, w

28、hich together with x-axis forms a container, such that the container contains the most water.Note: You may not slant the container. int maxArea(vector &height) int i = 0; int j = height.size() - 1; int ret = 0; while(i j) int area = (j - i) * min(heighti, heightj); ret = max(ret, area); if (heighti

29、= heightj) i+; else j-;贪心策略，只有当前高度较小的线才会下移。即每一步只保留当前最优解。 return ret; Code 8 Container with most water4. 3 Sum Leetcode 15Given an arraySofnintegers, are there elementsa,b,cinSsuch thata+b+c= 0? Find all unique triplets in the array which gives the sum of zero. vectorvector threeSum(vector &num) vect

30、orvector result; sort(num.begin(), num.end(); for(int i = 0; i 0 & numi=numi-1) continue; int start = i+1; int end = num.size()-1; while(start i & numstart = numstart-1) start+; continue; if(end+1num.size()&numend = numend+1) end-; continue; int sum = numi + numstart + numend; if(sum = 0) vector r;

31、r.push_back(numi); r.push_back(numstart); r.push_back(numend); result.push_back(r); start+; else if(sum 0) end-; return result; Code 9 Three sum5. 4 Sum4Sum仅仅比3Sum多一重循环而已，方法一样。 Leetcode 18vectorvector fourSum(vector &num, int target) vectorvector ret;if(num.size() 4) return ret;sort(num.begin(), num

32、.end();for(int i = 0; i num.size(); +i)for(int j = i + 1; j num.size(); +j) int left = j + 1;int right = (int)num.size() - 1;int sum = 0;while(left right) sum=numi+numj+numleft+numright; if(target = sum)ret.push_back(vector(4);ret.back()0=numi;ret.back()1=numj);ret.back()2numleft; ret.back()3=numrig

33、ht;+left;-right; else if(sum target)-right; else+left;sort(ret.begin(), ret.end();ret.resize(unique上面3sum的重复判断是在循环里判断的，这里使用STL的范型算法。(ret.begin(),ret.end()-ret.begin();return ret;Code 10 Four sum6. Merge two sorted arrays without additional memoryint merge(vector& longArray, vector& shortArray, int l

34、ongUsed)int longTail = longUsed-1;int shortTail = shortArray.size()-1;while(longTail=0 & shortTail = 0)if(longArraylongTail shortArrayshortTail)longArraylongTail+shortTail+1 = longArraylongTail;longTail-;elselongArraylongTail+shortTail+1 = shortArraylongTail;shortTail-;while(shortTail=0)longArraysho

35、rtTail = shortArrayshortTail;shortTail-;return shortArray.size() + longUsed;Code 11 Merge sorted array in place7. Merge k sorted lists Leetcode 23Mergeksorted linked lists and return it as one sorted list. Analyze and describe its complexity. ListNode *merge(ListNode *node1, ListNode *node2) if (nod

36、e1 = NULL) return node2; if (node2 = NULL) return node1; ListNode *head = NULL; ListNode *curNode = NULL; ListNode *p = node1; ListNode *q = node2; while(p & q) ListNode *node; if (p-val val) node = p; p = p-next; else node = q; q = q-next; if (head = NULL) head = curNode = node; else curNode-next =

37、 node; node-next = NULL; curNode = node; if (p) curNode-next = p; else if (q) curNode-next = q; return head; ListNode *mergeKLists(vector &lists) if (lists.size() = 0) return NULL; ListNode *head = lists0; for(int i = 1; i lists.size(); i+) head = merge(head, listsi); return head; Code 12 Merge k li

38、sts如果允许使用STL，则可以使用multiset：ListNode *mergeKLists(vector &lists) multiset S; for (int i = 0; i next = node; if (node-next) S.insert(node-next); return head;struct comparator: public binary_function bool operator() (const ListNode* a, const ListNode* b) return a-val val; ;Code 13 Merge k lists (using

39、std:multiset) 也可以使用heap本题也算是常见题型，一般都是用heap做的比较多。：ListNode *mergeKLists(vector &lists) vector:iterator it = lists.begin(); while(it != lists.end() if(*it = NULL) lists.erase(it); else +it; if(lists.size() 0) if(head = NULL) head = cur = lists0; else cur = cur-next = lists0; pop_heap(lists.begin(), li

40、sts.end(), comp(); int last = lists.size() - 1; if(listslast-next != NULL) listslast = listslast-next; push_heap(lists.begin(), lists.end(), comp(); else lists.pop_back(); return head;class comp public: bool operator()(const ListNode* l,const ListNode* r)const return (l-val r-val); ;Code 14 Merge k

41、lists (using heap)8. strStr() Leetcode 28Implement strStr(). Returns a pointer to the first occurrence of needle in haystack, ornullif needle is not part of haystack. char* strStr(char *str, char *target) if (!target | !*target) return str; char *p1 = str, *p2 = target; char *p1Adv = str; while (*+p

42、2) p1Adv+;p1Adv相当于一个滑动窗口的作用，第一个while循环后可以p1Adv来控制滑动的次数。 while (*p1Adv) char *p1Begin = p1; p2 = target; while (*p1 & *p2 & *p1 = *p2) p1+; p2+; if (!*p2) return p1Begin; p1 = p1Begin + 1; p1Adv+; return NULL; Code 15 strStr()9. Substring with concatenation of all words Leetcode 30You are given a str

43、ing,S, and a list of words,L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters. vector findSubstring(string S, vector &L) map words; map curStr;对于Brutal force的解法来说，本题给出的soluti

44、on也是很大的优化空间的。比如实际上使用一个map就可以了。此外，此题有O(S.size()算法。for(int i = 0; i L.size(); +i)+wordsL.at(i);int N = L.size();vector ret;if(N = 0)return ret;int M = L.at(0).size();for(int i = 0; i = (int)S.size()-N*M; +i)curStr.clear();int j = 0;for(j = 0; j wordsw)break;if(j = N)ret.push_back(i);return ret; Code 1

45、6 Find Substring10. Trapping rain water Leetcode 42Givennnon-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.For example,Given0,1,0,2,1,0,1,3,2,1,2,1, return6. int trap(int A, int n) if (!A | !n) return 0; int

46、mid = 0, water = 0, h = 0; for (int i = 0; i Amid) mid = i先找到最大的bar，然后从两边往中间搜索。; for (int i = 0; i Ai) water += h - Ai; else h = Ai; h = 0; for (int i = n - 1; i mid; -i) if (h Ai) water += h - Ai; else h = Ai; return water; Code 17 Trapping rain water11. Valid palindrome Leetcode 125Given a string, de