1 #include <iostream>
2 #include<vector>
3 #include <stack>
4 #include<map>
5 #include<list>
6 #include <sstream>
7 #include <algorithm>//里边有好多现成的函数
8 #include <queue>
9
10 using namespace std;
11
12 struct TreeNode {
13 int val;
14 struct TreeNode *left;
15 struct TreeNode *right;
16 TreeNode(int x) :
17 val(x), left(NULL), right(NULL) {
18 }
19 };
20 struct ListNode {
21 int val;
22 struct ListNode *next;
23 ListNode(int x) :
24 val(x), next(NULL) {
25 }
26 };
27 struct RandomListNode {
28 int label;
29 struct RandomListNode *next, *random;
30 RandomListNode(int x) :
31 label(x), next(NULL), random(NULL) {
32 }
33 };
34 struct TreeLinkNode {
35 int val;
36 struct TreeLinkNode *left;
37 struct TreeLinkNode *right;
38 struct TreeLinkNode *next;
39 TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
40 }
41 };
42 class Solution {
43 public:
44 /*请实现两个函数，分别用来序列化和反序列化二叉树*/
45 TreeNode* decode(char *&str) {
46 if (*str == '#'){
47 str++;
48 return NULL;
49 }
50 int num = 0;
51 while (*str != ',')
52 num = num * 10 + (*(str++) - '0');
53 str++;
54 TreeNode *root = new TreeNode(num);
55 root->left = decode(str);
56 root->right = decode(str);
57 return root;
58 }
59 char* Serialize2(TreeNode *root) {
60 if (!root) return "#";
61 string r = to_string(root->val);
62 r.push_back(',');
63 char *left = Serialize(root->left);
64 char *right = Serialize(root->right);
65 char *ret = new char[strlen(left) + strlen(right) + r.size()];
66 strcpy_s(ret, sizeof(r.c_str()),r.c_str());
67 strcat(ret, left);
68 strcat(ret, right);
69 return ret;
70 }
71 TreeNode* Deserialize2(char *str) {
72 return decode(str);
73 }
74
75 char* Serialize(TreeNode *root)
76 {
77 //先序遍历 中序遍历 保存结果
78 if (root == NULL) return NULL;
79 vector<TreeNode*>preOrder, inOrder;
80 PreOrder(root, preOrder);
81 InOrderTraverse(root, inOrder);
82
83 char * combine = new char[preOrder.size()+inOrder.size()+1];
84 for (int i = 0; i < preOrder.size();i++)
85 {
86 combine[i] = preOrder[i]->val;
87 }
88 for (int i = preOrder.size(); i < preOrder.size() + inOrder.size(); i++)
89 {
90 combine[i] = inOrder[i - preOrder.size()]->val;
91 }
92 combine[preOrder.size() + inOrder.size()] = '\0';
93 return combine;
94 }
95 TreeNode* Deserialize(char *str)
96 {
97 int len = strlen(str);
98 vector<int>preOrder, inOrder;
99 for (int i = 0; i < len / 2;i++)
100 {
101 preOrder.push_back((int)str[i]);
102 }
103 for (int i = len/2; i < len; i++)
104 {
105 inOrder.push_back((int)str[i]);
106 }
107
108 return reConstructBinaryTree(preOrder, inOrder);
109 }
110 /*请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。
111 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，
112 但是与"aa.a"和"ab*a"均不匹配http://www.voidcn.com/blog/huzhigenlaohu/article/p-6087740.html*/
113 bool matchCore(char* str, int strIndex, char* pattern, int patternIndex)
114 {
115 //str到尾，pattern到尾，匹配成功
116 if (strIndex == strlen(str) && patternIndex == strlen(pattern))return true;
117 //str未到尾，pattern到尾，匹配失败
118 if (strIndex != strlen(str) && patternIndex == strlen(pattern)) return false;
119
120 //str到尾，pattern未到尾(不一定匹配失败，因为a*可以匹配0个字符)
121 if (strIndex == strlen(str) && patternIndex != strlen(pattern)) {
122 //只有pattern剩下的部分类似a*b*c*的形式，才匹配成功
123 if (patternIndex + 1 < strlen(pattern) && pattern[patternIndex + 1] == '*') {
124 return matchCore(str, strIndex, pattern, patternIndex + 2);
125 }
126 return false;
127 }
128
129 //str未到尾，pattern未到尾
130 if (patternIndex + 1 < strlen(pattern) && pattern[patternIndex + 1] == '*')
131 {
132 if (pattern[patternIndex] == str[strIndex] || (pattern[patternIndex] == '.' && strIndex != strlen(str)))
133 {
134 return matchCore(str, strIndex, pattern, patternIndex + 2)//*匹配0个，跳过
135 || matchCore(str, strIndex + 1, pattern, patternIndex + 2)//*匹配1个，跳过
136 || matchCore(str, strIndex + 1, pattern, patternIndex);//*匹配1个，再匹配str中的下一个
137 }
138 else
139 {
140 //直接跳过*（*匹配到0个）
141 return matchCore(str, strIndex, pattern, patternIndex + 2);
142 }
143 }
144 }
145 bool match(char* str, char* pattern)
146 {
147 if (strlen(str) == 0 || strlen(pattern) == 0)
148 {
149 return false;
150 }
151 int strIndex = 0;
152 int patternIndex = 0;
153 return matchCore(str, strIndex, pattern, patternIndex);
154 }
155 /*地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，
156 但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），
157 因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？*/
158 int sumOfDigits(int n)
159 {
160 int sum = 0;
161 while (n>0)
162 {
163 sum += n % 10;
164 n /= 10;
165 }
166 return sum;
167 }
168 int count(int threshold, int rows, int cols, int *flag,int i,int j)
169 {
170 if (i < 0 || i >= rows || j < 0 || j >= cols || sumOfDigits(i) + sumOfDigits(j) > threshold || flag[i*cols + j] == 1)
171 return 0;
172 flag[i*cols + j] = 1;
173
174 return 1 + count(threshold, rows, cols, flag, i + 1, j) +
175 count(threshold, rows, cols, flag, i - 1, j) +
176 count(threshold, rows, cols, flag, i, j + 1) +
177 count(threshold, rows, cols, flag, i, j - 1);
178
179 }
180 int movingCount(int threshold, int rows, int cols)
181 {
182 int* flag = new int[rows*cols];
183 for (int i = 0; i < rows*cols;i++)
184 {
185 flag[i] = 0;
186 }
187 return count(threshold,rows,cols,flag,0,0);
188 }
189 /*请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，
190 每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
191 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bccced"的路径，
192 但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。*/
193 /*这是一个可以用回朔法解决的典型题。http://www.voidcn.com/blog/huzhigenlaohu/article/p-6090898.html
194 首先，在矩阵中任选一个格子作为路径的起点。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的第i个位置。
195 如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。除在矩阵边界上的格子之外，其他格子都有4个相邻的格子。
196 重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。
197 由于回朔法的递归特性，路径可以被开成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，
198 在与第n个字符对应的格子的周围都没有找到第n+1个字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。
199 由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。
200 当矩阵中坐标为（row,col）的格子和路径字符串中相应的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)
201 以及(row+1,col)中去定位路径字符串中下一个字符如果4个相邻的格子都没有匹配字符串中下一个的字符，
202 表明当前路径字符串中字符在矩阵中的定位不正确，我们需要回到前一个，然后重新定位。
203 一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置*/
204 bool isHasPath(char* matrix,int rows,int cols,int i,int j,char* str,int k,bool* flag)
205 {
206 int index = i*cols + j;
207 if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] || flag[index]) return false;
208
209 if (k == strlen(str) - 1) return true;
210
211 flag[index] = true;
212
213 if (isHasPath(matrix, rows, cols, i, j + 1, str, k + 1, flag) ||
214 isHasPath(matrix, rows, cols, i, j - 1, str, k + 1, flag) ||
215 isHasPath(matrix, rows, cols, i + 1, j, str, k + 1, flag) ||
216 isHasPath(matrix, rows, cols, i - 1, j, str, k + 1, flag) )
217 {
218 return true;
219 }
220 flag[index] = false;
221 return false;
222 }
223 bool hasPath(char* matrix, int rows, int cols, char* str)
224 {
225 if (strlen(matrix)<rows*cols || strlen(str)>strlen(matrix)) return false;
226
227 bool* flag = new bool[rows*cols];//标记该位置是否有效
228 for (int i = 0; i < rows*cols; i++)flag[i] = false;
229 for (int i = 0; i < rows;i++)
230 {
231 for (int j = 0; j < cols;j++)
232 {
233 if (isHasPath(matrix, rows, cols, i, j, str,0, flag))
234 return true;
235 }
236 }
237
238 delete[] flag;
239 return false;
240 }
241 /*输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
242 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
243 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。*/
244 TreeNode* ConstructTree(vector<int>&pre, vector<int>&vin,int preLeft,int preRight,int vinLeft,int vinRight)
245 {
246 if (preLeft > preRight || vinLeft> vinRight)return NULL;
247
248 TreeNode* root = new TreeNode(0);
249 root->val = pre[preLeft];
250
251 int index = vinLeft;
252 while (vin[index] != pre[preLeft])index++;//在中序遍历中找到根节点位置
253 int length = index - vinLeft;//左子树节点个数
254 //int length2 = vinRight - index;//右子树节点个数
255
256 TreeNode* leftTree = ConstructTree(pre, vin, preLeft + 1, preLeft+length,index-length,index -1);//注意下标
257 TreeNode* rightTree = ConstructTree(pre, vin, preLeft+length + 1,preRight,index+1,vinRight );
258
259 root->left = leftTree;
260 root->right = rightTree;
261 return root;
262 }
263 TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin)
264 {
265 if (pre.size() == 0||pre.size()!=vin.size()) return NULL;
266
267 TreeNode* root = new TreeNode(0);
268 root->val = pre[0];
269 root = ConstructTree(pre, vin, 0, pre.size() - 1, 0, vin.size() - 1);
270 return root;
271 }
272 /*输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
273 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。*/
274 bool isOK(vector<int>&a,int left,int right)
275 {//抄的 马克（Mark）
276 if (left >= right) return true;
277 int i = right;
278 while (i > left && a[i - 1] > a[right])i--;//a[right]为根 找到中间左右子树界限
279 for (int j = i - 1; j >= left;j--)
280 {
281 if (a[j] > a[right])return false;//如果左子树有大于根的 返回FALSE
282 }
283 return isOK(a, left, i - 1) && isOK(a, i, right - 1);
284 }
285 bool VerifySquenceOfBST(vector<int> sequence)
286 {//BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，
287 //那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。完美的递归定义 : ) 。
288 if (sequence.size() == 0)return false;
289 return isOK(sequence,0,sequence.size()-1);
290
291 }
292 /*输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
293 要求不能创建任何新的结点，只能调整树中结点指针的指向。*/
294 void InOrderNonRecursiveTraverse(TreeNode*pRoot, vector<TreeNode*>& result)//非递归中序遍历
295 {
296 if (pRoot == NULL)return;
297 stack<TreeNode*>st;
298 while (pRoot!=NULL||!st.empty())
299 {
300 while (pRoot != NULL)
301 {
302 st.push(pRoot);
303 pRoot = pRoot->left;//最左端
304 }
305 if (!st.empty())
306 {
307 pRoot = st.top();//出栈
308 st.pop();
309 result.push_back(pRoot);
310 pRoot = pRoot->right;//向右边遍历
311 }
312 }
313 }
314 TreeNode* Convert(TreeNode* pRootOfTree)
315 {//首先中序遍历，存储在一个vector里 然后遍历vector建立链表 别人貌似不是这么做的。。么有用vector存储一遍的
316 if (pRootOfTree == NULL)return pRootOfTree;
317 vector<TreeNode*> result;
318 InOrderTraverse(pRootOfTree, result);
319
320 for (int i = 0; i < result.size()-1; i++)
321 {
322 result[i]->right = result[i + 1];
323 result[i + 1]->left = result[i];
324 }
325
326 return result[0];
327 }
328
329 /*给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
330 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。*/
331 TreeLinkNode* GetNext(TreeLinkNode* pNode)
332 {
333 if (pNode == NULL) return NULL;
334 if (pNode->right!=NULL)//有右子树
335 {
336 pNode = pNode->right;
337 while (pNode->left!=NULL)
338 {
339 pNode = pNode->left;
340 }
341 return pNode;
342 }
343
344 TreeLinkNode* parent = pNode->next;
345 while (parent!=NULL )//父亲的父亲的。。。父亲为空停止循环 或者找到 作为父亲的左孩子为止&& parent->next->left != parent
346 {
347 if (parent->left == pNode)//if (parent->next->left ==parent)//原来是这么写的 不对！！！
348 {
349 return parent;//return parent->next;
350 }
351 pNode = parent;
352 parent = parent->next;
353
354 }
355
356 return NULL;
357
358 }
359 /*给定一颗二叉搜索树，请找出其中的第k大的结点。
360 例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。*/
361 void InOrderTraverse(TreeNode*pRoot, vector<TreeNode*>& result)
362 {
363 if (pRoot!=NULL)
364 {
365 InOrderTraverse(pRoot->left, result);
366 result.push_back(pRoot);
367 InOrderTraverse(pRoot->right, result);
368 }
369 }
370 TreeNode* KthNode(TreeNode* pRoot, int k)
371 {//首先中序遍历 然后返回kth值。。。效率太低了吧。。但是暂时没有高效率方法
372 if (pRoot == NULL || k <= 0) return NULL;
373 vector<TreeNode*> result;
374 InOrderTraverse(pRoot,result);
375
376 if (k > result.size()) return NULL;
377 return result[k - 1];
378 }
379 /*输入一棵二叉树，判断该二叉树是否是平衡二叉树。*/
380 //网上有复杂度为O（n）方法
381 int getTreeDepth(TreeNode* pRoot)
382 {
383 if (pRoot == NULL) return 0;
384 return 1+max(getTreeDepth(pRoot->left),getTreeDepth(pRoot->right));
385 }
386 bool IsBalanced_Solution(TreeNode* pRoot)
387 {
388 if (pRoot == NULL) return true;
389 if (!IsBalanced_Solution(pRoot->left))return false;
390 if (!IsBalanced_Solution(pRoot->right))return false;
391
392 int leftDepth = getTreeDepth(pRoot->left);
393 int rightDepth = getTreeDepth(pRoot->right);
394
395 if (abs(leftDepth - rightDepth) > 1) return false;
396 return true;
397 }
398 /*输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），
399 返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）*/
400 RandomListNode* Clone(RandomListNode* pHead)
401 {
402 if (pHead == NULL)
403 return NULL;
404
405 //开辟一个新节点
406 RandomListNode* pClonedHead = new RandomListNode(pHead->label);
407 pClonedHead->next = pHead->next;
408 pClonedHead->random = pHead->random;
409
410 //递归其他节点
411 pClonedHead->next = Clone(pHead->next);
412
413 return pClonedHead;
414 /*if (pHead == NULL)return pHead;
415 RandomListNode* tempPre = new RandomListNode(0);
416 tempPre->label = pHead->label;
417 pHead = pHead->next;
418 while (pHead != NULL)
419 {
420 RandomListNode* tempCur = new RandomListNode(0);
421 RandomListNode* tempRandom = new RandomListNode(0);
422 tempPre->next = tempCur;
423 tempPre->random = tempRandom;
424
425 tempCur->label = pHead->label;
426
427 temp->label = pHead->label;
428 temp->next = pHead->next;
429 temp->random = pHead->random;
430 pHead = pHead->next;
431 }*/
432 }
433 /*如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
434 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
435 */
436 ///别人貌似都不是这么做的。。不知道为啥他们都用堆结构等等。。。不是舍近求远么
437 vector<int> data;
438 void Insert(int num)
439 {
440 data.push_back(num);
441 }
442 double GetMedian()
443 {
444 sort(data.begin(),data.end());
445 if (data.size() % 2 == 1)
446 {
447 return data[data.size() / 2];
448 }
449 else
450 return (data[data.size() / 2] + data[data.size() / 2 - 1]) / 2.0;
451 }
452 /*一个链表中包含环，请找出该链表的环的入口结点。*/
453 ListNode* EntryNodeOfLoop(ListNode* pHead)
454 {
455 if (pHead == NULL)return NULL;
456 map<ListNode*, int> table;//用来记录访问次数
457 ListNode* entry= NULL;
458 while (pHead!=NULL)
459 {
460 table[pHead]++;
461 if (table[pHead]==2)
462 {
463 return pHead;
464 }
465 pHead = pHead->next;
466 }
467 return entry;
468 }
469 /*输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）*/
470 /*class Solution {//别人 de
471 bool isSubtree(TreeNode* pRootA, TreeNode* pRootB) {
472 if (pRootB == NULL) return true;
473 if (pRootA == NULL) return false;
474 if (pRootB->val == pRootA->val) {
475 return isSubtree(pRootA->left, pRootB->left)
476 && isSubtree(pRootA->right, pRootB->right);
477 }
478 else return false;
479 }
480 public:
481 bool HasSubtree(TreeNode* pRootA, TreeNode* pRootB)
482 {
483 if (pRootA == NULL || pRootB == NULL) return false;
484 return isSubtree(pRootA, pRootB) ||
485 HasSubtree(pRootA->left, pRootB) ||
486 HasSubtree(pRootA->right, pRootB);
487 }
488 };*/
489 void PreOrder(TreeNode* pRoot, vector<TreeNode*>& result)
490 {
491 if (pRoot != NULL)
492 {
493 result.push_back(pRoot);
494 PreOrder(pRoot->left, result);
495 PreOrder(pRoot->right, result);
496 }
497 }
498 bool isContain2(vector<TreeNode*>order1, vector<TreeNode*>order2)
499 {//子串是否包含函数
500 int N = order1.size();
501 int M = order2.size();
502 for (int i = 0; i <= N - M; i++)//判断连续子串 只需到N-M
503 {
504 int j;
505 for (j = 0; j < M; j++)
506 {
507 if (order1[i + j]->val != order2[j]->val)//是order1[i + j]->val相等 不是order1[i + j]相等
508 break;
509 }
510 if (j == M)
511 {
512 return true;
513 }
514 }
515 return false;
516 }
517 /*测试用例:{8,8,7,9,2,#,#,#,#,4,7},{8,9,2} true*/
518 bool isContain(vector<TreeNode*>order1, vector<TreeNode*>order2)
519 {
520 int N = order1.size();
521 int M = order2.size();
522 int j = 0;
523 for (int i = 0; i < N; i++)//边界条件！此题不需要连续子串
524 {
525
526 if (j<M && order1[i]->val==order2[j]->val)
527 {
528 j++;
529 }
530 if (j == M)
531 {
532 return true;
533 }
534 }
535 return false;
536 }
537 bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
538 {//中序遍历和前序遍历 生成字符串 同理判断是否存在包含关系
539 if (pRoot1 == NULL || pRoot2 == NULL) return false;
540 vector<TreeNode*>inOrder1, inOrder2,preOrder1,preOrder2;
541 PreOrder(pRoot1, preOrder1);
542 PreOrder(pRoot2, preOrder2);
543
544 InOrderTraverse(pRoot1, inOrder1);
545 InOrderTraverse(pRoot2, inOrder2);
546
547 //判断是否是子串关系
548 if (isContain(preOrder1, preOrder2) && isContain(inOrder1, inOrder2))
549 return true;
550
551 return false;
552
553 }
554 /*请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，
555 第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。*/
556 vector<vector<int> > Print2(TreeNode* pRoot)
557 {
558 vector<vector<int> > result;
559 if (pRoot==NULL)return result;
560 //首先层次遍历 最后将偶数层 翻转。。。。效率貌似不高。。。 高效率就是 访问偶数层的时候 反着插入
561 queue<TreeNode*>myqueue;
562 myqueue.push(pRoot);
563 int flag = 1;//flag 表示奇数还是偶数层
564 while (!myqueue.empty())
565 {
566 int index = 0, levelSize = myqueue.size();
567 vector<int> level;
568 TreeNode* temp;
569
570 while (index++ < levelSize)
571 {
572 temp = myqueue.front();
573 myqueue.pop();
574 vector<int>::iterator it;
575
576 if (flag==1)//第奇数层
577 {
578 level.push_back(temp->val);
579 }
580 else//第偶数层
581 {
582 it = level.begin();
583 level.insert(it, temp->val);
584 }
585 if (temp->left) myqueue.push(temp->left);
586 if (temp->right)myqueue.push(temp->right);
587 }
588 result.push_back(level);
589 level.clear();
590 if (flag == 1)flag = 0;
591 else if (flag == 0)flag = 1;
592 }
593 return result;
594
595 }
596 /*从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。*/
597 vector<vector<int> > Print(TreeNode* pRoot)
598 {
599 /* vector<vector<int>> ret;
600 if (pRoot == NULL) return ret;
601
602 queue<TreeNode*> q;
603 q.push(pRoot);
604
605 while (!q.empty())
606 {
607 int low = 0, high = q.size();
608 vector<int> level;
609 TreeNode *tmp;
610
611 while (low++ < high) //按层次来!!!
612 {
613 tmp = q.front();
614 q.pop();
615 level.push_back(tmp->val);
616 if (tmp->left)
617 q.push(tmp->left);
618 if (tmp->right)
619 q.push(tmp->right);
620 }
621 ret.push_back(level);
622 level.clear();
623 }
624 return ret;*/
625
626 vector<vector<int>> result;
627 if (pRoot == NULL)return result;
628 queue<TreeNode*> myqueue;
629 myqueue.push(pRoot);
630 int i = 0, levelLen = 1,nextLevelLen = 0;//当前索引 当前层的长度 下一层长度 貌似看别人的方法不用求 利用queue.size 统计队内元素个数
631 while (!myqueue.empty())
632 {
633 vector<int> temp;
634 while (i < levelLen)
635 {
636 temp.push_back(myqueue.front()->val);
637 if (myqueue.front()->left!=NULL)
638 {
639 myqueue.push(myqueue.front()->left);
640 nextLevelLen++;
641 }
642 if (myqueue.front()->right != NULL)
643 {
644 myqueue.push(myqueue.front()->right);
645 nextLevelLen++;
646 }
647 myqueue.pop();
648 if (i == levelLen-1)//本层最后一个元素 将本层遍历过的元素保存
649 {
650 result.push_back(temp);
651 }
652 i++;
653 }
654 levelLen = nextLevelLen; //本层遍历结束 进入下一层
655 nextLevelLen = 0;
656 i = 0;//每层从头开始
657 }
658 return result;
659 }
660 /*从上往下打印出二叉树的每个节点，同层节点从左至右打印。*/
661 vector<int> PrintFromTopToBottom(TreeNode* root)
662 { //层序遍历
663 vector<int> result;
664 queue<TreeNode*> myqueue;
665 if (root == NULL) return result;
666
667 myqueue.push(root);
668 while (!myqueue.empty())
669 {
670 result.push_back(myqueue.front()->val);
671 if (myqueue.front()->left != NULL)
672 {
673 myqueue.push(myqueue.front()->left);
674 }
675 if (myqueue.front()->right != NULL)
676 {
677 myqueue.push(myqueue.front()->right);
678 }
679 myqueue.pop();
680 }
681
682 return result;
683
684 }
685 /*请实现一个函数，用来判断一颗二叉树是不是对称的。
686 注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的*/
687 bool Symmetrical(TreeNode* pLeft, TreeNode* pRight)
688 {
689 if (pLeft == NULL && pRight == NULL)return true;
690 if ((pLeft == NULL&&pRight != NULL) || (pLeft != NULL&&pRight == NULL))return false;
691 if (pLeft->val != pRight->val)return false;
692
693 return Symmetrical(pLeft->left, pRight->right) && Symmetrical(pLeft->right, pRight->left);
694 }
695 bool isSymmetrical(TreeNode* pRoot)
696 {
697 if (pRoot == NULL)return true;
698 return Symmetrical(pRoot, pRoot);
699 }
700 /*输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
701 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。*/
702 vector<vector<int>> result;
703 vector<int> temp;
704 void Traverse(TreeNode* root, int expectNumber)
705 {
706 temp.push_back(root->val);
707 if (expectNumber == root->val && root->left==NULL && root->right ==NULL)//正好找到为叶结点
708 {
709 result.push_back(temp);
710 }
711 else
712 {
713 if(root->left)Traverse(root->left, expectNumber - root->val);
714 if(root->right)Traverse(root->right, expectNumber - root->val);
715 }
716 temp.pop_back(); //深度遍历 要回退一个结点
717 }
718 vector<vector<int> > FindPath(TreeNode* root, int expectNumber)
719 {
720 if (root == NULL ) return result;
721
722 Traverse(root,expectNumber);
723 return result;
724 }
725 /*操作给定的二叉树，将其变换为源二叉树的镜像。 */
726 void Mirror(TreeNode *pRoot)
727 {//递归 类似先序遍历
728 if (pRoot == NULL)return;
729 TreeNode* temp = pRoot->left;
730 pRoot->left = pRoot->right;
731 pRoot->right = temp;
732 Mirror(pRoot->left);
733 Mirror(pRoot->right);
734
735 }
736 /*求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,
737 但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。*/
738 int PowerBase10(unsigned int n)
739 { // 10^n
740 int result = 1;
741 for (unsigned int i = 0; i < n; ++i)
742 result *= 10;
743 return result;
744 }
745 int b10(unsigned int n)
746 {
747 return PowerBase10(n);
748 }
749 int NumberBitCount(unsigned int n)
750 {
751 int N = 0;
752 while (n)
753 {
754 n = n / 10;
755 N++;
756 }
757 return N;
758 }
759 int NumberOf1Between1AndN_Solution(int n)
760 {//看不懂 抄的http://www.cnblogs.com/hellogiser/p/3738812.html
761 // T(n) = o(N) = o(lgn)
762 if (n<=0)
763 {
764 return 0;
765 }
766 int N = NumberBitCount(n);
767 int si, sum = 0;
768 int A, B, bi, ri;
769 for (int i = 1; i <= N; i++)
770 {
771 A = n / b10(i) * b10(i - 1);
772 bi = n / b10(i - 1) % 10;
773 ri = n % b10(i - 1);
774 if (bi == 0)
775 {
776 B = 0;
777 }
778 else if (bi == 1)
779 {
780 B = ri + 1;
781 }
782 else if (bi > 1)
783 {
784 B = b10(i - 1);
785 }
786 si = A + B;
787 sum += si;
788 }
789 return sum;
790 }
791 /*输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
792 假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，
793 序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
794 （注意：这两个序列的长度是相等的）*/
795 bool IsPopOrder(vector<int> pushV, vector<int> popV)
796 {//设置一个辅助栈，将pushV中的数字依次压入栈中，一直检查栈顶元素是否与popV中的第一个数字相等，
797 //如果相等则弹出栈，不相等就接着将pushV中数字push进栈，直到将所有数字都入栈，如果最后栈不空，则不是弹出序列
798 /* if(pushV.size() == 0) return false;//别人的简洁
799 vector<int> stack;
800 for(int i = 0,j = 0 ;i < pushV.size();){
801 stack.push_back(pushV[i++]);
802 while(j < popV.size() && stack.back() == popV[j]){
803 stack.pop_back();
804 j++;
805 }
806 }
807 return stack.empty();*/
808 if (pushV.size() != popV.size() || pushV.size()<1 || popV.size()<1)return false;
809
810 stack<int>temp;
811 int i=1,j = 0;
812 temp.push(pushV[0]);
813 while (1)
814 {
815 while (temp.top() != popV[j] && i < pushV.size())
816 {
817 temp.push(pushV[i++]);
818 }
819 if (temp.top() == popV[j])
820 {
821 temp.pop();
822 j++;
823 }
824 else //将pushV里的数字都入栈了也没有找到
825 {
826 return false;
827 }
828 if (temp.size() == 0) //栈最后为空 或者popV为空 说明都匹配完毕
829 {
830 return true;
831 }
832 }
833 return false;//yong 不上
834 }
835 /*把只包含因子2、3和5的数称作丑数（Ugly Number）。
836 例如6、8都是丑数，但14不是，因为它包含因子7。
837 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。*/
838 int GetUglyNumber_Solution(int index)
839 {//参考作者博客http://zhedahht.blog.163.com/blog/static/2541117420094245366965/
840 if (index < 1)return index;
841 vector<int>ugly;
842 ugly.push_back(1);
843 int index2 = 0, index3 = 0, index5 = 0;
844 int i = 1;
845 while (i<index)
846 {
847 ugly.push_back(std::min(ugly[index2] * 2, std::min(ugly[index3] * 3, ugly[index5] * 5)));
848 while (ugly[index2] * 2 <= ugly[i])
849 index2++;
850 while (ugly[index3] * 3 <= ugly[i])
851 index3++;
852 while (ugly[index5] * 5 <= ugly[i])
853 index5++;
854 i++;
855 }
856 return ugly[index - 1];
857 }
858 /*请实现一个函数用来找出字符流中第一个只出现一次的字符。*/
859 //Insert one char from stringstream
860 //用map来统计出现次数
861 map<char, int>table;
862 vector<char>charStream;
863 void Insert(char ch)
864 {
865 charStream.push_back(ch);
866 table[ch]++;
867 }
868 //return the first appearence once char in current stringstream
869 char FirstAppearingOnce()
870 {
871 vector<char>::iterator it;
872 for (it = charStream.begin(); it != charStream.end();it++)
873 {
874 if (table[*it]==1)
875 {
876 return *it;
877 }
878 }
879 return '#';
880 }
881 /*输入两个链表，找出它们的第一个公共结点。*/
882 int getListLength(ListNode* pHead)
883 {
884 int length = 0;
885 if (pHead == NULL)return length;
886 while (pHead)
887 {
888 pHead = pHead->next;
889 length++;
890 }
891 return length;
892 }
893 ListNode *move(ListNode* list,int length)
894 {
895 while (length)
896 {
897 list = list->next;
898 length--;
899 }
900 return list;
901 }
902 ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)
903 {//首先求两个链表长度，做差 同时向后移动
904 int length1 = 0, length2 = 0;
905 length1 = getListLength(pHead1);
906 length2 = getListLength(pHead2);
907 if (length1 == 0)return NULL;
908 if (length2 == 0)return NULL;
909 ListNode* temp1 = pHead1;
910 ListNode* temp2 = pHead2;
911 if (length1>length2)
912 {
913 temp1 = move(pHead1, length1 - length2);
914 }
915 else if (length1<length2)
916 {
917 temp2 = move(pHead2, length2 - length1);
918 }
919 while (temp1&&temp2)
920 {
921 if (temp1==temp2)
922 {
923 return temp1;
924 }
925 else
926 {
927 temp1 = temp1->next;
928 temp2 = temp2->next;
929 }
930 }
931
932 return NULL;
933 }
934 /*扑克牌顺子 大王用0表示 可以表示任何数字*/
935 bool IsContinuous(vector<int> numbers)
936 {
937 if (numbers.size() != 5)return false;
938 sort(numbers.begin(),numbers.end());
939 int zreos = 0, gap = 0;//记录0的个数 和记录差距
940 for (int i = 0; i < numbers.size();i++)
941 {
942 if (numbers[i] == 0)zreos++;
943 else if (i + 1 < numbers.size())
944 {
945 if (numbers[i] == numbers[i + 1])return false;
946 gap += numbers[i + 1] - numbers[i] - 1;
947 }
948 }
949 if (gap>zreos) //差距大于0的个数
950 return false;
951 return true;
952
953 }
954 /*输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序*/
955 vector<vector<int> > FindContinuousSequence(int sum)
956 {
957 vector<vector<int>> result;
958 if (sum <= 2)return result;
959
960 for (int a = 1; a <= sum / 2;a++)
961 {
962 float b;
963 b = (-1 + sqrt(1 + 4 * a*a - 4 * a + 8 * sum)) / 2;
964 if ((b-(int)b)==0)//如果b是整数 则存在序列
965 {
966 vector<int> temp;
967 for (int i = a; i <= b;i++)
968 {
969 temp.push_back(i);
970 }
971 result.push_back(temp);
972 }
973 }
974 return result;
975 }
976 /*输入一个递增排序的数组和一个数字S，在数组中查找两个数，
977 是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。 */
978 vector<int> FindNumbersWithSum(vector<int> array, int sum)
979 {//别人写的o（n）的复杂度
980 /* vector<int> result;
981 int length = array.size();
982 int start = 0;
983 int end = length - 1;
984 while (start < end)
985 {
986 if (array[start] + array[end] == sum)
987 {
988 result.push_back(array[start]);
989 result.push_back(array[end]);
990 break;
991 }
992 else if (array[start] + array[end] < sum)
993 start++;
994 else
995 end--;
996 }*/
997 vector<int>result;
998 if (array.size() <= 1)return result;
999 for (int i = 0; i < array.size() - 1;i++)
1000 {
1001 for (int j = array.size() - 1; j>i;j--)
1002 {
1003 if (array[i]+array[j]==sum)
1004 {
1005 result.push_back(array[i]);
1006 result.push_back(array[j]);
1007 //break; 退出循环
1008 i = array.size();
1009 }
1010 }
1011 }
1012 return result;
1013
1014 }
1015 /*定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。*/
1016 stack<int>s1, min1;
1017 void push1(int value)
1018 {
1019 s1.push(value);
1020 if (min1.empty())min1.push(value);
1021 if (min1.top()>=value)
1022 {
1023 min1.push(value);
1024 }
1025
1026 }
1027 void pop1()
1028 {
1029 s1.pop();
1030 if (s1.top() == min1.top())min1.pop();
1031 }
1032 int top()
1033 {
1034 return s1.top();
1035 }
1036 int min()
1037 {
1038 return min1.top();
1039 }
1040
1041 /*输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。*/
1042 ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
1043 {//别人写的
1044 //ListNode* result = NULL;
1045 //ListNode* current = NULL;
1046
1047 //if (pHead1 == NULL)return pHead2;
1048 //if (pHead2 == NULL)return pHead1;
1049 ///*if (pHead1->val <= pHead2->val)//递归版本
1050 //{
1051 // result = pHead1;
1052 // result->next = Merge(pHead1->next, pHead2);
1053 //}
1054 //else
1055 //{
1056 // result = pHead2;
1057 // result->next = Merge(pHead1, pHead2->next);
1058 //}*/
1059 //
1060 //while (pHead1 != NULL && pHead2 != NULL){
1061 // if (pHead1->val <= pHead2->val){
1062 // if (result == NULL){
1063 // current = result = pHead1;
1064 // }
1065 // else {
1066 // current->next = pHead1;
1067 // current = current->next;
1068 // }
1069 // pHead1 = pHead1->next;
1070 // }
1071 // else {
1072 // if (result == NULL){
1073 // current = result = pHead2;
1074 // }
1075 // else {
1076 // current->next = pHead2;
1077 // current = current->next;
1078 // }
1079 // pHead2 = pHead2->next;
1080 // }
1081 //}
1082
1083 //if (pHead1 == NULL) current->next = pHead2;
1084 //if (pHead2 == NULL) current->next = pHead1;
1085 //return result;
1086
1087 if (pHead1 == NULL)return pHead2;
1088 if (pHead2 == NULL)return pHead1;
1089
1090 ListNode* head = pHead2;
1091 ListNode* tempNode = pHead1->next;
1092 ListNode* tempNode2= pHead2;
1093 while (pHead1) //将list1中结点挨个插入到list2中的合适位置
1094 {
1095 bool isHead = true;//用来标记是否将list1的结点插入到list2的头部
1096 while (pHead2 && pHead1->val > pHead2->val)//找到合适位置 大于当前
1097 {
1098 tempNode2 = pHead2;//tempNode2用来保存phead2前边结点
1099 pHead2 = pHead2->next;
1100 isHead = false;
1101 }
1102 if (isHead)//插入头部
1103 {
1104 tempNode = pHead1->next;//保存list1中下一个结点
1105 pHead1->next = pHead2;
1106 //tempNode2->next = pHead1;
1107 head = pHead1;
1108 }
1109 else//非头部
1110 {
1111 if (pHead2)//插入结点 此时list2中存在结点
1112 {
1113 tempNode = pHead1->next;//保存list1中下一个结点
1114 pHead1->next = pHead2;
1115 tempNode2->next = pHead1;
1116 }
1117 else//插到list2最后
1118 {
1119 tempNode = pHead1->next;
1120 tempNode2->next = pHead1;
1121 pHead1->next = pHead2;//此时pHead2==NULL
1122 }
1123 }
1124 pHead1 = tempNode;//开始list1中的下一结点
1125 if (tempNode)
1126 {tempNode = tempNode->next;
1127 }
1128
1129 pHead2 = head; //从list2 的头开始遍历
1130 }
1131
1132 return head;
1133 }
1134 /*数组中的逆序对：在数组中的两个数字，如果前面一个数字大于后面的数字，
1135 则这两个数字组成一个逆序对。输入一个数组,
1136 求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。
1137 即输出P%1000000007
1138 题目保证输入的数组中没有的相同的数字
1139 输入例子: 1,2,3,4,5,6,7,0
1140 输出例子: 7 */
1141 //：出处http://blog.csdn.net/ns_code/article/details/27520535
1142 long long MergePairsBetweenArray(int *arr, int *brr, int start, int mid, int end)
1143 {
1144 int i = mid;
1145 int j = end;
1146 int k = end; //辅助数组的最后一位
1147 long long count = 0;
1148
1149 //设置两个指针i,j分别从右往左依次比较，
1150 //将较大的依次放入辅助数组的右边
1151 while (i >= start && j >= mid + 1)
1152 {
1153 if (arr[i] > arr[j])
1154 {
1155 count += j - mid;
1156 brr[k--] = arr[i--];
1157 }
1158 else
1159 brr[k--] = arr[j--];
1160 }
1161
1162 //将其中一个数组中还剩下的元素拷贝到辅助数组中，
1163 //两个循环只会执行其中的一个
1164 while (i >= start)
1165 brr[k--] = arr[i--];
1166 while (j >= mid + 1)
1167 brr[k--] = arr[j--];
1168
1169 //从辅助数组中将元素拷贝到原数组中，使其有序排列
1170 for (i = end; i > k; i--)
1171 arr[i] = brr[i];
1172
1173 return count;
1174 }
1175 long long CountMergePairs(int *arr, int *brr, int start, int end)
1176 {
1177 long long PairsNum = 0;
1178 if (start < end)
1179 {
1180 int mid = (start + end) >> 1;
1181 PairsNum += CountMergePairs(arr, brr, start, mid); //统计左边子数组的逆序对
1182 PairsNum += CountMergePairs(arr, brr, mid + 1, end); //统计右边子数组的逆序对
1183 PairsNum += MergePairsBetweenArray(arr, brr, start, mid, end); //统计左右子数组间的逆序对
1184 }
1185 return PairsNum;
1186 }
1187 int InversePairs(vector<int> data)
1188 {
1189 if (data.size() == 0)return 0;
1190 long long count = 0;
1191 //for (int i = 0; i < data.size() - 1;i++)//时间复杂度太大 不通过
1192 //for (int j = i + 1; j < data.size(); j++)
1193 //if (data[i]>data[j])count++;
1194
1195 //vector<int> temp(data.size());//初始化向量的大小
1196
1197 int *brr = new int[data.size()];
1198 for (int i = 0; i < data.size();i++)
1199 {
1200 brr[i] = data[i];
1201 }
1202 int *temp = new int[data.size()];
1203
1204 count = CountMergePairs(brr, temp, 0, data.size() - 1);
1205
1206
1207 return count % 1000000007;
1208 }
1209 /*在一个字符串(1<=字符串长度<=10000，全部由大写字母组成)
1210 中找到第一个只出现一次的字符,并返回它的位置*/
1211 int FirstNotRepeatingChar(string str)
1212 {
1213 if (str.size() == 0)return -1;
1214 //构造一个hash表 统计出现次数
1215 map<char, int> table;
1216 for (char i = 'A'; i <= 'Z';i++) table[i] = 0;
1217 char *p = new char[str.size()+1];
1218 str.copy(p, str.size(), 0);
1219
1220 for (int i = 0; i < str.size();i++) table[str[i]]++;
1221 map<char, int>::iterator it;
1222 int pos = str.size();
1223 for (it = table.begin(); it != table.end();it++)
1224 {
1225 if (it->second == 1 && pos>str.find_first_of(it->first))//只出现一次
1226 {
1227 pos = str.find_first_of(it->first);
1228 }
1229 }
1230 if (pos == str.size())
1231 {
1232 return -1;
1233 }
1234 else
1235 return pos;
1236
1237 }
1238 /*{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止(子向量的长度至少是1)*/
1239 int FindGreatestSumOfSubArray(vector<int> array)
1240 {
1241 if (array.size() < 1) return 0;
1242 int max = array[0],sum = 0;
1243 //int result = array[0];//作为记录单次遍历最大和
1244
1245 //如果左边总和为负数 那么从下一个值开始 O(n)复杂度 效率高
1246 for (int i = 0; i < array.size();i++)
1247 {
1248 if (sum < 0)
1249 {
1250 sum = array[i];
1251 }
1252 else
1253 {
1254 sum += array[i];
1255 }
1256 if (max < sum)max = sum;
1257
1258 }
1259
1260 //for (int i = 0; i < array.size();i++) //效率低
1261 //{
1262 // result = array[i];
1263 // sum = 0;
1264 // for (int j = i; j < array.size(); j++)
1265 // {
1266 // sum += array[j];
1267 // if (result < sum)
1268 // {
1269 // result = sum;
1270 // }
1271 // }
1272 // if (max<result)
1273 // {
1274 // max = result;
1275 // }
1276
1277 //}
1278
1279 return max;
1280 }
1281 /*约瑟夫环 让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列,
1282 下一个继续0...m-1报,问最后剩下谁*/
1283 int LastRemaining_Solution(int n, int m)
1284 {
1285 if (n == 0)
1286 return -1;
1287 if (n == 1)
1288 return 0;
1289 else
1290 return (LastRemaining_Solution(n - 1, m) + m) % n;//参考的别人的
1291
1292 if (m <= 0||n<1)return -1;
1293 list<int>* table = new list<int>();
1294 for (int i = 1; i <= n;i++) table->push_back(i);
1295
1296 int count = 1;
1297 for (list<int>::iterator it = table->begin(); table->size() != 1;)
1298 {
1299 if (count == m)
1300 {
1301 cout << " " <<*it;
1302 it = table->erase(it);
1303 count = 0;
1304 }
1305 else
1306 {
1307 it++;
1308 }
1309 if (it == table->end())
1310 {
1311 it = table->begin();
1312 }
1313 count++;
1314 }
1315 //cout << endl<<"The last one is:";
1316 cout << *table->begin() << endl;
1317
1318 return *table->begin();
1319 return 0;
1320
1321 }
1322 //堆排序，root为根节点下标
1323 void heapSort(vector<int> &input, int root, int end)
1324 {
1325 for (int j = end - 1; j >= root; j--)
1326 {
1327 int parent = (j + root - 1) / 2;
1328 if (input[parent] > input[j])
1329 {
1330 int temp = input[j];
1331 input[j] = input[parent];
1332 input[parent] = temp;
1333 }
1334 }
1335 }
1336 /*输入n个整数，找出其中最小的K个数。
1337 例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,*/
1338 vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
1339 {
1340 vector<int> result;
1341 if (input.size() < k||k<=0)return result;
1342 sort(input.begin(), input.end());
1343 for (int i = 0; i < k;i++)
1344 {
1345 result.push_back(input[i]);
1346 }
1347 return result;
1348 }
1349 /*输入一个字符串,按字典序打印出该字符串中字符的所有排列。
1350 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串
1351 abc,acb,bac,bca,cab和cba。输入一个字符串,长度不超过9(可能有字符重复),
1352 字符只包括大小写字母。*/
1353 void digui(char *sortStr, int begin, int end, vector<string>& result)
1354 {
1355 if (begin == end)
1356 {
1357 string str;
1358 //for (int i = 0; i < end; i++) str += sortStr[i];
1359 str = sortStr;
1360 result.push_back(str);
1361 //result.push_back(sortStr);//其实可以直接这样
1362 return;
1363 }
1364 else
1365 {
1366 for (int i = begin; i < end;i++)
1367 {
1368 swap(sortStr[begin],sortStr[i]);
1369 digui(sortStr, begin+1, end, result);
1370 swap(sortStr[begin], sortStr[i]);
1371 }
1372 }
1373
1374 }
1375 vector<string> Permutation(string str)
1376 {
1377 vector<string> result;
1378 if (str.size() == 0) return result;
1379 // const char* tempStr = new char[str.size() + 1];tempStr = str.c_str();
1380 char* sortStr = new char[str.size() + 1];//有了这个就可以啦
1381 //for (int i = 0; i < str.size(); i++) sortStr[i] = tempStr[i];
1382 str.copy(sortStr, str.size(),0);
1383 sortStr[str.size()] = '\0';
1384 cout << sortStr << endl;
1385 //递归
1386 digui(sortStr, 0, str.size(), result);
1387 sort(result.begin(), result.end());
1388 //for (int i = 0; i < str.size()-1;i++)//排序
1389 // for (int j = 0; j<str.size()-i-1;j++)
1390 // if (sortStr[j]>sortStr[j + 1]){ char temp = sortStr[j]; sortStr[j] = sortStr[j+1]; sortStr[j+1] = temp; }
1391
1392 //去除重复项
1393 for (auto it = result.begin() + 1; it != result.end();)
1394 {
1395 if (*it == *(it - 1))
1396 it = result.erase(it);
1397 else
1398 it++;
1399 }
1400
1401 return result;
1402
1403 }
1404 vector<string> Permutation2(string str) {//网上看别人写的 LuL
1405 vector<string> out;
1406 int len = str.length();
1407 if (len == 0)
1408 return out;
1409 char* p = (char *)malloc((len + 1)*sizeof(char));
1410 str.copy(p, len, 0);
1411
1412 //全排列，迭代
1413 myPermutation(p, 0, len, out);
1414 //字典序排序
1415 sort(out.begin(), out.end());
1416 //去除重复项
1417 for (auto it = out.begin() + 1; it != out.end();){
1418 if (*it == *(it - 1))
1419 it = out.erase(it);
1420 else
1421 it++;
1422 }
1423 return out;
1424 }
1425
1426 void myPermutation(char* p, int k, int m, vector<string>& out){
1427 if (k == m){
1428 //将结果存入out中
1429 string s;
1430 for (int i = 0; i < m; ++i)
1431 s += p[i];
1432 out.push_back(s);
1433 return;
1434 }
1435 for (int i = k; i < m; ++i){
1436 swap(p[k], p[i]);
1437 myPermutation(p, k + 1, m, out);
1438 swap(p[k], p[i]);
1439 }
1440 }
1441 /*汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。
1442 对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。
1443 例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。*/
1444 string LeftRotateString(string str, int n)
1445 {
1446 if (str.size()==0 || n<0) return "";
1447 if (n>str.size()) n %= str.size();
1448 const char* sequence = str.c_str();
1449 char* roateStr = new char[str.size() + 1];
1450 char* doubleSeq = new char[2 * str.size()+1]; //建立一个双倍的字符串类似 abcXYZdefabcXYZdef可直接返回结果
1451 for (int i = 0; i < str.size();i++)
1452 {
1453 doubleSeq[i] = sequence[i];
1454 doubleSeq[i+str.size()] = sequence[i];
1455 }
1456 doubleSeq[2 * str.size()] = '\0';
1457 for (int i = 0; i < str.size(); i++)///这种情况不需要开辟一个双倍空间了 复杂度为O（n）
1458 {
1459 //roateStr[i] = doubleSeq[i+n];
1460 if ((i+n)<str.size())
1461 {
1462 roateStr[i] = sequence[i + n];
1463 }
1464 else
1465 {
1466 roateStr[i] = sequence[i+n-str.size()];
1467 }
1468
1469 }
1470 roateStr[str.size() + 1] = '\0';
1471 //cout << doubleSeq << endl;
1472 //cout << roateStr << endl;
1473 return roateStr;
1474 }
1475 /*数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
1476 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
1477 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。*/
1478 int MoreThanHalfNum_Solution(vector<int> numbers)
1479 {//用map hash存储关键字 统计出现次数 看到别人用 map.count() 作为查找 good~
1480 if (numbers.size() == 0)
1481 {
1482 return 0;
1483 }
1484 map<int, int> mapValue;
1485 map<int, int>::iterator iter;
1486 for (int i = 0; i < numbers.size(); i++)
1487 {
1488 mapValue[numbers[i]] = 0;//初始化
1489 }
1490 for (int i = 0; i < numbers.size(); i++)//统计出现次数
1491 {
1492 mapValue[numbers[i]]++;
1493 }
1494 for (iter = mapValue.begin(); iter != mapValue.end(); iter++)
1495 {
1496 if (iter->second*2 > numbers.size())
1497 {
1498 return iter->first;
1499 }
1500 }
1501 return 0;
1502
1503 }
1504 /*牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，
1505 写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，
1506 但却读不懂它的意思。例如，“student. a am I”。
1507 后来才意识到，这家伙原来把句子单词的顺序翻转了，
1508 正确的句子应该是“I am a student.”。
1509 Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？*/
1510 string ReverseSentence(string str)
1511 {//下面6行是马克(Mark)的方法。。。够简洁。。学习了
1512 /*string res = "", tmp = "";
1513 for (unsigned int i = 0; i < str.size(); ++i){
1514 if (str[i] == ' ') res = " " + tmp + res, tmp = "";
1515 else tmp += str[i];
1516 }
1517 if (tmp.size()) res = tmp + res;
1518 return res;*/
1519 if (str.size() == 0) return str;///这块儿不能返回NULL 返回""就行
1520
1521 //首先分出单词 然后统计单词个数
1522 string reverse = "";
1523 const char *temp = str.c_str();
1524 cout << temp << endl;
1525
1526 //split word
1527 int i = 0,wordStart = 0,wordEnd = 0;
1528 vector<string> strVec;//保存所有单词
1529 while (temp[i] != '\0')
1530 {
1531 if (temp[i] ==' ')//先假设单词间都是1个空格 结尾没有空格
1532 {
1533 wordEnd = i - 1;
1534 char word[128];
1535 int k = 0;
1536 for (int j = wordStart; j <= wordEnd;j++)//
1537 {
1538 word[k] = temp[j];
1539 k++;
1540 }
1541 word[k] = '\0';
1542 strVec.push_back(word);
1543 wordStart = i + 1;
1544 }
1545 i++;
1546 }
1547 wordEnd = i - 1;
1548 char word[128];
1549 int k = 0;
1550 for (int j = wordStart; j <= wordEnd; j++)//
1551 {
1552 word[k] = temp[j];
1553 k++;
1554 }
1555 word[k] = '\0';
1556 strVec.push_back(word);
1557
1558 for (int i = 0; i < strVec.size()/2;i++)
1559 {
1560 string temp = strVec[i];
1561 strVec[i] = strVec[strVec.size() - 1 - i];
1562 strVec[strVec.size() - 1 - i] = temp;
1563 }
1564
1565 for (int i = 0; i < strVec.size();i++)
1566 {
1567 //cout << strVec[i].c_str() << " ";
1568 if (i != strVec.size()-1) reverse = reverse + strVec[i].c_str() + " ";
1569 else reverse = reverse + strVec[i].c_str();
1570 }
1571
1572 return reverse;
1573 }
1574 /*请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
1575 例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。
1576 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。*/
1577 bool isNumeric(char* string)
1578 {
1579 int i = 0;
1580 if (string[i] == '+' || string[i] == '-'||isdigit(string[i]))//判断第一位
1581 {
1582 while (string[++i] != '\0'&&isdigit(string[i]));//检测到第一个非数字符号
1583
1584 if (string[i]=='.')
1585 {
1586 if (isdigit(string[++i]))//小数点后下一位是否是数字
1587 {
1588 while (string[++i] != '\0'&&isdigit(string[i]));//检测到第一个非数字符号
1589
1590 if (string[i] == 'e' || string[i] == 'E')
1591 {
1592 i++;
1593 if (string[i] == '+' || string[i] == '-' || isdigit(string[i]))
1594 {
1595 while (string[++i] != '\0' && isdigit(string[i]));
1596 if (string[i] == '\0') return true;
1597 else return false;
1598 }
1599 else return false;
1600 }
1601 else if (string[i] == '\0')
1602 {
1603 return true;
1604 }
1605 else return false;
1606 }
1607 else
1608 return false;
1609 }
1610 else if (string[i] == 'e' || string[i] == 'E')
1611 {
1612 i++;
1613 if (string[i] == '+' || string[i] == '-' || isdigit(string[i]))
1614 {
1615 while (string[++i] != '\0' && isdigit(string[i]));
1616 if (string[i] == '\0') return true;
1617 else return false;
1618 }
1619 else return false;
1620 }
1621 else if (string[i] == '\0')
1622 {
1623 return true;
1624 }
1625 else
1626 return false;//其他情况 非数字
1627 }
1628 else
1629 {
1630 return false;
1631 }
1632 }
1633 /*///网上说用双端队列~~~~~~~....待优化
1634 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
1635 例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，
1636 他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个：
1637 {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}，
1638 {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
1639 */
1640 vector<int> maxInWindows(const vector<int>& num, unsigned int size)
1641 {
1642 vector<int> maxInWindow;
1643 if (size > num.size()|| size == 0) return maxInWindow;
1644
1645 for (int i = 0; i < num.size() + 1 - size;i++)
1646 {
1647 //在下标范围为[i i+1 ...i+size-1]找最大值
1648 int max = num[i];
1649
1650 for (int j = 0; j < size;j++)
1651 {
1652 if (max < num[i+j])
1653 {
1654 max = num[i+j];
1655 }
1656 }
1657 maxInWindow.push_back(max);
1658 }
1659
1660 return maxInWindow;
1661 }
1662 /*在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，
1663 重复的结点不保留，返回链表头指针。
1664 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5*/
1665 ListNode* deleteDuplication(ListNode* pHead)
1666 {//参考别人的思路改写的。。牛客网id ：Charles_Lee
1667
1668 if (pHead == NULL) return NULL;
1669
1670 //定义一个临时头结点，防止头结点被删除
1671 ListNode* pTempHead = new ListNode(0);
1672 pTempHead->next = pHead;
1673
1674
1675 ListNode* pCur = pHead, *pLast = pTempHead;//ptemp
1676 int toDeleteVal = 0;
1677 while (pCur && pCur->next)
1678 {
1679 if (pCur->val == pCur->next->val)//当前值和下一个相等 往后移动 知道不相等或空
1680 {
1681 toDeleteVal = pCur->val;
1682 while (pCur && pCur->val == toDeleteVal)
1683 {
1684 pCur = pCur->next;
1685 }
1686 pLast->next = pCur;
1687 }
1688 else//当前和下一个不相等，则当前肯定不被删除 判断下一个
1689 {
1690 pLast = pCur;
1691 pCur = pCur->next;
1692 }
1693
1694 }
1695
1696 return pTempHead->next;
1697
1698
1699 }
1700 /*统计一个数字在排序数组中出现的次数。网上好多二分查找 递归什么的。。。待优化*/
1701 int GetNumberOfK(vector<int> data, int k)
1702 {
1703 int count = 0;
1704 for (int i = 0; i < data.size(); i++)
1705 {
1706 if (data[i] == k)
1707 {
1708 count++;
1709 }
1710 }
1711 return count;
1712
1713 }
1714 /*将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。
1715 数值为0或者字符串不是一个合法的数值则返回0
1716 输入描述: 输入一个字符串,包括数字字母符号,可以为空
1717 输出描述: 如果是合法的数值表达则返回该数字，否则返回0
1718 输入例子: +2147483647 1a33
1719 输出例子: 2147483647 0
1720 */
1721 int StrToInt(string str)
1722 {
1723 if (str.size() == 0)
1724 {
1725 return 0;
1726 }
1727 int value = 0;
1728
1729 //char* temp;
1730 /*temp = new char[str.size() + 1];
1731 strcpy_s(temp,strlen(temp), str.c_str());*//////牛客网上编译不通过 因为strcpy_s()没有
1732 const char * temp;
1733 temp = str.c_str();
1734
1735 cout << temp << endl;
1736
1737 if (temp[0] == '+' || temp[0] == '-')
1738 {
1739 for (int i = 1; temp[i] != '\0'; i++)
1740 {
1741 if (temp[i] >= '0' && temp[i] <= '9')
1742 {
1743 value = value * 10 + temp[i] - '0';
1744 }
1745 else
1746 {
1747 return 0;
1748 }
1749 }
1750 if (temp[0] == '+')
1751 {
1752 return value;
1753 }
1754 else
1755 {
1756 return -value;
1757 }
1758
1759 }
1760 else if (temp[0] >= '0'&&temp[0] <= '9')
1761 {
1762 for (int i = 0; temp[i] != '\0'; i++)
1763 {
1764 if (temp[i] >= '0' && temp[i] <= '9')
1765 {
1766 value = value * 10 + temp[i] - '0';
1767 }
1768 else
1769 {
1770 return 0;
1771 }
1772 }
1773 return value;
1774 }
1775 return 0;////这儿在牛客网上必须写 否则编译不通过。
1776
1777 }
1778 /*用两个栈来实现一个队列，完成队列的Push和Pop操作。
1779 队列中的元素为int类型。*/
1780 void push(int node)
1781 {
1782 stack1.push(node);
1783 }
1784
1785 int pop()
1786 {
1787 int result, temp;
1788 while (!stack1.empty())//将所有元素放到stack2里
1789 {
1790 temp = stack1.top();
1791 stack1.pop();
1792 stack2.push(temp);
1793 }
1794 result = stack2.top();//保存一下要弹出队列的第一个元素
1795 stack2.pop();
1796 while (!stack2.empty())
1797 {
1798 temp = stack2.top();
1799 stack2.pop();
1800 stack1.push(temp);
1801 }
1802 return result;
1803
1804 }
1805
1806 /*在一个长度为n的数组里的所有数字都在0到n-1的范围内。
1807 数组中某些数字是重复的，但不知道有几个数字是重复的。
1808 也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
1809 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，
1810 那么对应的输出是重复的数字2或者3。*/
1811 // Parameters:
1812 // numbers: an array of integers
1813 // length: the length of array numbers
1814 // duplication: (Output) the duplicated number in the array number
1815 // Return value: true if the input is valid, and there are some duplications in the array number
1816 // otherwise false
1817 bool duplicate(int numbers[], int length, int* duplication)
1818 {
1819
1820 int *flags = new int[length];//标记数组
1821 for (int i = 0; i < length; i++)
1822 {
1823 flags[i] = 0;//初始化为0
1824 }
1825 for (int i = 0; i < length; i++)
1826 {
1827 flags[numbers[i]]++;
1828 }
1829 for (int i = 0; i < length; i++)
1830 {
1831 if (flags[i] >= 2)
1832 {
1833 *duplication = i;
1834 }
1835
1836 }
1837 if (*duplication >= 0 && *duplication<length)
1838 {
1839 return true;
1840 }
1841 return false;
1842
1843 }
1844 /*一个整型数组里除了两个数字之外，其他的数字都出现了两次。
1845 请写程序找出这两个只出现一次的数字。
1846 网上说用异或的方法。。。没太明白好处在哪*/
1847 void FindNumsAppearOnce(vector<int> data, int* num1, int *num2)
1848 {
1849 if (data.size() < 2)
1850 {
1851 return;
1852 }
1853 bool flag = false;
1854 vector<int> result;
1855 for (int i = 0; i < data.size(); i++)
1856 {
1857 flag = false;
1858 for (int j = 0; j < data.size(); j++)
1859 {
1860 if (!flag && i != j && data[i] == data[j])
1861 {
1862 flag = true;
1863 }
1864 }
1865 if (!flag)
1866 {
1867 result.push_back(data[i]);
1868 }
1869 }
1870 *num1 = result[0];
1871 *num2 = result[1];////////////////这样写num1 = &result[0]; 结果不对
1872
1873
1874 }
1875 /*求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case
1876 等关键字及条件判断语句（A?B:C）。*/
1877 int Sum_Solution(int n)
1878 {
1879 //参考别人的方法，利用&&操作 666
1880 int sum = n;
1881 (n>0) && (sum += Sum_Solution(n - 1));
1882
1883 return sum;
1884 }
1885
1886 /*给定一个数组A[0,1,...,n-1],
1887 请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。
1888 不能使用除法。*/
1889 //待优化
1890 vector<int> multiply(const vector<int>& A)
1891 {
1892 int b = 1;
1893 vector<int> B;
1894 for (int i = 0; i < A.size(); i++)
1895 {
1896 b = 1;
1897 for (int j = 0; j < A.size(); j++)
1898 {
1899 if (j != i)
1900 {
1901 b *= A[j];
1902 }
1903
1904 }
1905 B.push_back(b);
1906 }
1907 return B;
1908 }
1909
1910 /*写一个函数，求两个整数之和，
1911 要求在函数体内不得使用+、-、*、/四则运算符号。*/
1912 int Add(int num1, int num2)
1913 {
1914 /*1.异或为不带进位的加法
1915 2.进位的求法可以通过 两数相与： 1 1才会得1，然后左移1位
1916 3.将步骤2和步骤1的值相加*/
1917 //if (num2 == 0)
1918 // return num1;
1919 //int temp = num1^num2;
1920 //int carry = (num1&num2) << 1;
1921 //return Add(temp, carry);
1922
1923 //非递归版本
1924 while (num2 != 0)
1925 {
1926 int temp = num1^num2;
1927 num2 = (num1&num2) << 1;
1928 num1 = temp;
1929 }
1930 return num1;
1931
1932 }
1933 /*输入一个正整数数组，把数组里所有数字拼接起来排成一个数，
1934 打印能拼接出的所有数字中最小的一个。
1935 例如输入数组{ 3，32，321 }，
1936 则打印出这三个数字能排成的最小数字为321323。*/
1937 static bool compare(string str1,string str2)///需要加上static 修饰符
1938 {
1939 string s1 = str1 + str2;
1940 string s2 = str2 + str1;
1941 return s1 < s2;
1942 }
1943 string PrintMinNumber(vector<int> numbers)
1944 {
1945 string result;
1946 if (numbers.size() == 0)return result;
1947
1948 vector<string> allResult;
1949 for (int i = 0; i < numbers.size();i++)
1950 {
1951 stringstream ss;
1952 ss<<numbers[i];//将不同类型的值转换成string类型的好方法
1953 allResult.push_back(ss.str());
1954 }
1955 sort(allResult.begin(),allResult.end(),compare);
1956 for (int i = 0; i < numbers.size();i++)
1957 {
1958 result.append(allResult[i]);//值得学习的方法
1959 }
1960 return result;
1961 }
1962 /*把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
1963 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
1964 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
1965 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
1966 //网上说是2分查找最好*/
1967 int minNumberInRotateArray(vector<int> rotateArray)
1968 {
1969 int size = rotateArray.size();
1970 if (size == 0)
1971 {
1972 return 0;
1973 }
1974 int min = rotateArray[0];
1975 for (int i = 0; i < size; i++)
1976 {
1977
1978 if ((i + 1 < size) && (rotateArray[i]> rotateArray[i + 1]))
1979 {
1980 min = rotateArray[i + 1];
1981 }
1982 }
1983 return min;
1984
1985 }
1986 /*输入一个链表，输出该链表中倒数第k个结点。*/
1987 ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
1988 {
1989 if (pListHead == NULL || k <= 0)
1990 {
1991 return NULL;
1992 }
1993
1994 //首先从头结点开始 算上头结点在内访问k 个结点 然后从头结点和此节点一起向前推进
1995 //直到前边那个结点到最后一个结点 此时前边那个结点即为所求
1996 ListNode *resultNode = pListHead;
1997 ListNode *currentNode = pListHead;
1998 for (int i = 0; i < k - 1; i++)
1999 {
2000 if (currentNode->next == NULL)
2001 {
2002 return NULL;
2003 }
2004 currentNode = currentNode->next;
2005 }
2006
2007 while (currentNode->next != NULL)
2008 {
2009 resultNode = resultNode->next;
2010 currentNode = currentNode->next;
2011 }
2012
2013 return resultNode;
2014
2015 }
2016 /*输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，
2017 所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。*/
2018 void reOrderArray(vector<int> &array)
2019 {
2020 //扫描一趟，分别记录奇数 和偶数
2021 vector<int> odd, even;
2022
2023 for (int i = 0; i < array.size(); i++)
2024 {
2025 if (array[i] % 2 == 1)
2026 {
2027 odd.push_back(array[i]);
2028 }
2029 else
2030 {
2031 even.push_back(array[i]);
2032 }
2033 }
2034 int oddSize = odd.size();
2035 int evenSize = even.size();
2036
2037 for (int i = 0; i < oddSize; i++)
2038 {
2039 array[i] = odd[i];
2040 }
2041 for (int j = oddSize; j < oddSize + evenSize; j++)
2042 {
2043 array[j] = even[j - oddSize];
2044 }
2045
2046 }
2047 /*我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。
2048 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？*/
2049 int rectCover(int number)
2050 {
2051 if (number == 1 || number == 2)
2052 {
2053 return number;
2054 }
2055 else
2056 {
2057 return rectCover(number - 1) + rectCover(number - 2);
2058 }
2059 }
2060 /*给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。*/
2061 double Power(double base, int exponent)
2062 {
2063 double result = 1.0;
2064
2065 if (exponent == 0)
2066 {
2067 return 1.0;
2068 }
2069 else if (exponent > 0)
2070 {
2071 for (int i = 0; i < exponent; i++)
2072 {
2073 result *= base;
2074 }
2075 return result;
2076 }
2077 else
2078 {
2079 exponent = -exponent;
2080 for (int i = 0; i < exponent; i++)
2081 {
2082 result *= base;
2083 }
2084 return 1 / result;
2085 }
2086
2087
2088 }
2089 /*输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示*/
2090 int NumberOf1(int n) {
2091 //每一位均需判断
2092 int count = 0;
2093 int flag = 1;
2094 while (flag != 0) {
2095 if ((n & flag) != 0) {
2096 count++;
2097 }
2098
2099 flag = flag << 1;
2100 }
2101 return count;
2102 }
2103 /*大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。*/
2104 int Fibonacci(int n)
2105 {
2106 if (n <= 0) return 0;
2107 if (n == 1 || n == 2)
2108 return 1;
2109 else
2110 return Fibonacci(n - 1) + Fibonacci(n - 2);
2111 }
2112 /*一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。*/
2113 int jumpFloorII(int number)
2114 {
2115 if (number <= 0) return -1;
2116 if (number == 1) return 1;
2117 else return 2 * jumpFloorII(number - 1);
2118
2119 }
2120 /*一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。*/
2121 int jumpFloor(int number)
2122 {
2123 if (number == 1)return 1;
2124 else if (number == 2)return 2;
2125 return jumpFloor(number - 1) + jumpFloor(number - 2);
2126 }
2127 /*输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，
2128 例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.*/
2129 vector<int> printMatrix(vector<vector<int> > matrix)
2130 {
2131 int row = matrix.size();
2132 int col = matrix[0].size();
2133 vector<int> a;
2134 //参考的别人的代码。。。 上地https://www.nowcoder.com/profile/709885
2135 if (row == 0 || col == 0) return a;
2136 // 定义四个关键变量，表示左上和右下的打印范围
2137 int left = 0, top = 0, right = col - 1, bottom = row - 1;
2138 while (left <= right && top <= bottom)
2139 {
2140 // left to right
2141 for (int i = left; i <= right; ++i) a.push_back(matrix[top][i]);
2142 // top to bottom
2143 for (int i = top + 1; i <= bottom; ++i) a.push_back(matrix[i][right]);
2144 // right to left
2145 if (top != bottom)
2146 for (int i = right - 1; i >= left; --i) a.push_back(matrix[bottom][i]);
2147 // bottom to top
2148 if (left != right)
2149 for (int i = bottom - 1; i > top; --i) a.push_back(matrix[i][left]);
2150 left++, top++, right--, bottom--;
2151 }
2152 return a;
2153 }
2154 /*输入一个链表，反转链表后，输出链表的所有元素。*/
2155 ListNode* ReverseList(ListNode* pHead)
2156 {
2157 if (pHead == NULL)
2158 return pHead;
2159 ListNode *curNode = pHead;
2160 ListNode *nextNode = curNode->next;
2161 ListNode *temp;
2162 if (curNode->next != NULL)
2163 {
2164 pHead = curNode->next;
2165 }
2166 curNode->next = NULL;
2167 //保存当前结点指针 下一个结点指针 还有下一个的下一个结点指针
2168 while (nextNode)
2169 {
2170 pHead = nextNode;
2171 temp = nextNode->next;
2172 nextNode->next = curNode;
2173
2174 curNode = nextNode;
2175 nextNode = temp;
2176 }
2177 return pHead;
2178 }
2179 /*输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。*/
2180 int TreeDepth(TreeNode* pRoot)
2181 {
2182 if (pRoot == NULL)
2183 {
2184 return 0;
2185 }
2186 int a = TreeDepth(pRoot->left);
2187 int b = TreeDepth(pRoot->right);
2188 return 1 + (a > b ? a : b);
2189 }
2190 /*输入一个链表，从尾到头打印链表每个节点的值。*/
2191 vector<int> printListFromTailToHead(ListNode* head)
2192 {
2193 vector<int> a;
2194 if (head != NULL)
2195 {
2196 a.insert(a.begin(), head->val);
2197 while (head->next != NULL)
2198 {
2199 head = head->next;
2200 a.insert(a.begin(), head->val);
2201 }
2202 }
2203 return a;
2204 }
2205 /*实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。*/
2206 void replaceSpace(char *str, int length)
2207 {
2208 if (str == NULL || length <= 0) return;
2209 int i = 0;
2210 int oldLength = 0;
2211 int space = 0;
2212 while (str[i] != '\0')
2213 {
2214 oldLength++;
2215 if (str[i] == ' ') space++;
2216 i++;
2217 }
2218 int newLength = oldLength + space * 2;//新的字符串长度
2219 if (newLength > length) return;
2220 while (oldLength >= 0)
2221 {
2222 if (str[oldLength] == ' ')
2223 {
2224 str[newLength--] = '0';
2225 str[newLength--] = '2';
2226 str[newLength--] = '%';
2227 }
2228 else
2229 {
2230 str[newLength--] = str[oldLength];
2231 }
2232
2233 oldLength--;
2234 }
2235 }
2236 /*在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
2237 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。*/
2238 bool Find(int target, vector<vector<int> > array)
2239 {
2240 int colNum;
2241 int rowNum;
2242 rowNum = array.size();
2243 colNum = array[0].size();
2244 bool flag = false;
2245 int j = 0;
2246 int i = rowNum - 1;
2247 while (!flag)
2248 {
2249 if (0 <= i && j <= colNum - 1)
2250 {
2251 if (array[i][j] < target) j++;
2252 else if (array[i][j] > target) i--;
2253 else if (array[i][j] == target) flag = true;
2254 }
2255 else break;
2256 }
2257 return flag;
2258 }
2259
2260 private:
2261 stack<int> stack1;
2262 stack<int> stack2;
2263 };
2264
2265 int main()
2266 {
2267 ListNode node1(1), node2(2), node3(3), node4(4), node5(9),node6(5);
2268 ListNode* resultNode= NULL;
2269 node1.next = &node3;
2270 node2.next = &node4;
2271 node3.next = &node5;
2272 node4.next = &node6;
2273 node5.next = &node4;
2274 vector<int> test,popV;
2275
2276 test.push_back(1);
2277 test.push_back(2);
2278 test.push_back(4);
2279 test.push_back(7);
2280 test.push_back(3);
2281 test.push_back(5);
2282 test.push_back(6);
2283 test.push_back(8);
2284
2285 popV.push_back(4);
2286 popV.push_back(7);
2287 popV.push_back(2);
2288 popV.push_back(1);
2289 popV.push_back(5);
2290 popV.push_back(3);
2291 popV.push_back(8);
2292 popV.push_back(6);
2293
2294
2295 Solution sl;
2296 vector<vector<int>> result;
2297 vector<TreeNode*> tree;
2298
2299 TreeNode * root;
2300
2301 root = sl.reConstructBinaryTree(test, popV);
2302
2303 // cout << sl.Serialize(root);
2304 for (int i = 0; i < strlen(sl.Serialize(root));i++)
2305 {
2306 cout <<(int)sl.Serialize(root)[i] << " ";
2307 }
2308
2309 cout << endl;
2310
2311 TreeNode * root2;
2312 root2 = sl.Deserialize(sl.Serialize(root));
2313 for (int i = 0; i < strlen(sl.Serialize(root2)); i++)
2314 {
2315 cout << (int)sl.Serialize(root2)[i] << " ";
2316 }
2317
2318 for (int i = 0; i < tree.size();i++)
2319 {
2320 cout << tree[i]->val << " ";
2321 }
2322
2323 getchar();
2324 return 0;
2325 }
已经上传到 github上，请朋友们多多指教。