时间戳

首页 > 技术文章 > 剑指offer

剑指offer

dxy1993 2017-08-17 16:59 原文

网址：https://www.nowcoder.com/ta/coding-interviews?page=1

1.二维数组中的查找

 1 class Solution {
 2 public:
 3     bool Find(int target, vector<vector<int> > array) {
 4         if (array.empty())
 5             return false;
 6         
 7         int row = array.size();
 8         int column = array[0].size();
 9         int n = 0;
10         int m = column - 1;
11         while (n < row && m >= 0)
12         {
13             if (array[n][m] == target)
14                 return true;
15             else if (array[n][m] < target)
16                 n++;
17             else
18                 m--;
19         }
20         return false;
21     }
22 };
View Code

2.替换空格

 1 class Solution {
 2 public:
 3     void replaceSpace(char *str,int length) {
 4         int len = strlen(str);
 5         int cnt = 0;
 6         
 7         for (int i = 0; i < len; i++)
 8         {
 9             if (str[i] == ' ')
10                 cnt++;
11         }
12         
13         cnt = cnt * 2 + len;
14         if (cnt > length)
15             return ;
16         
17         for (int i = len; i >= 0; i--)
18         {
19             if (str[i] == ' ')
20             {
21                 str[cnt--] = '0';
22                 str[cnt--] = '2';
23                 str[cnt--] = '%';
24             }
25             else
26                 str[cnt--] = str[i];
27         }
28     }
29 };
View Code

 3.从尾到头打印链表

 1 /**
 2 *  struct ListNode {
 3 *        int val;
 4 *        struct ListNode *next;
 5 *        ListNode(int x) :
 6 *              val(x), next(NULL) {
 7 *        }
 8 *  };
 9 */
10 class Solution {
11 public:
12     vector<int> res;
13     void dfs(ListNode* head)
14     {
15         if (head)
16         {
17             dfs(head->next);
18             res.push_back(head->val);
19         }
20     }
21     vector<int> printListFromTailToHead(ListNode* head) {
22         dfs(head);
23         return res;
24     }
25 };
View Code
 1 /**
 2 *  struct ListNode {
 3 *        int val;
 4 *        struct ListNode *next;
 5 *        ListNode(int x) :
 6 *              val(x), next(NULL) {
 7 *        }
 8 *  };
 9 */
10 class Solution {
11 public:
12     vector<int> res;
13     void dfs(ListNode* head)
14     {
15         if (head)
16         {
17             if (head->next)
18                 dfs(head->next);
19             res.push_back(head->val);
20         }
21     }
22     vector<int> printListFromTailToHead(ListNode* head) {
23         dfs(head);
24         return res;
25     }
26 };
View Code
 1 /**
 2 *  struct ListNode {
 3 *        int val;
 4 *        struct ListNode *next;
 5 *        ListNode(int x) :
 6 *              val(x), next(NULL) {
 7 *        }
 8 *  };
 9 */
10 class Solution {
11 public:
12     vector<int> printListFromTailToHead(ListNode* head) {
13         vector<int> res;
14         stack<int> s;
15         
16         while (head)
17         {
18             s.push(head->val);
19             head = head->next;
20         }
21         
22         while (!s.empty())
23         {
24             res.push_back(s.top());
25             s.pop();
26         }
27         
28         return res;
29     }
30 };
View Code

4.重建二叉树

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     TreeNode* construct(vector<int>& pre, int preStart, int preEnd, vector<int>& vin, int vinStart, int vinEnd)
13     {
14         if (preStart > preEnd || vinStart > vinEnd)
15             return NULL;
16         
17         int pos;
18         for (pos = vinStart; pos <= vinEnd; pos++)
19         {
20             if (vin[pos] == pre[preStart])
21                 break;
22         }
23         
24         TreeNode* node = new TreeNode(vin[pos]);
25         node->left = construct(pre, preStart + 1, preStart + pos - vinStart, vin, vinStart, pos - 1);
26         node->right = construct(pre, preStart + pos - vinStart + 1, preEnd, vin, pos + 1, vinEnd);
27         
28         return node;
29     }
30     TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) 
31     {
32         return construct(pre, 0, pre.size() - 1, vin, 0, vin.size() - 1);
33     }
34 };
View Code

5.用两个栈实现队列

 1 class Solution
 2 {
 3 public:
 4     void push(int node) {
 5         stack1.push(node);
 6     }
 7 
 8     int pop() {
 9         int num;
10         if (stack2.empty())
11         {
12             while (!stack1.empty())
13             {
14                 stack2.push(stack1.top());
15                 stack1.pop();
16             }
17         }
18         
19         num = stack2.top();
20         stack2.pop();
21         return num;
22     }
23 
24 private:
25     stack<int> stack1;
26     stack<int> stack2;
27 };
View Code

6.旋转数组的最小数字

 1 class Solution {
 2 public:
 3     int minNumberInRotateArray(vector<int> rotateArray) {
 4         if (rotateArray.empty())
 5             return 0;
 6         
 7         int len = rotateArray.size();
 8         int l = 0;
 9         int r = len - 1;
10         int mid;
11         while (l < r)
12         {
13             mid = l + (r - l) / 2;
14             if (rotateArray[mid] > rotateArray[r])
15                 l = mid + 1;
16             else
17                 r = mid;
18         }
19         return rotateArray[l];
20     }
21 };
View Code

 7.斐波那契数列

 1 class Solution {
 2 public:
 3     int Fibonacci(int n) {
 4         if (n == 0)
 5             return 0;
 6         
 7         if (n == 1)
 8             return 1;
 9         
10         int a = 0;
11         int b = 1;
12         int res;
13         for (int i = 2; i <= n; i++)
14         {
15             res = a + b;
16             a = b;
17             b = res;
18         }
19         return res;
20     }
21 };
View Code
 1 class Solution {
 2 public:
 3     int Fibonacci(int n) {
 4         vector<int> res(2, 0);
 5         res[1] = 1;
 6         
 7         for (int i = 2; i <= n; i++)
 8             res[i % 2] = res[0] + res[1];
 9         
10         return res[n % 2];
11     }
12 };
View Code

8.跳台阶

 1 class Solution {
 2 public:
 3     int jumpFloor(int number) {
 4         if (number == 1)
 5             return 1;
 6         if (number == 2)
 7             return 2;
 8         
 9         int a = 1;
10         int b = 2;
11         int res;
12         for (int i = 3; i <= number; i++)
13         {
14             res  = a + b;
15             a = b;
16             b = res;
17         }
18         return res;
19     }
20 };
View Code
 1 class Solution {
 2 public:
 3     int jumpFloor(int number) {
 4         vector<int> res(2, 0);
 5         res[0] = 1;
 6         res[1] = 2;
 7         
 8         for (int i = 2; i < number; i++)
 9             res[i % 2] = res[0] + res[1];
10         
11         return res[(number - 1) % 2];
12     }
13 };
View Code

9.变态跳台阶

1 class Solution {
2 public:
3     int jumpFloorII(int number) {
4         int res = (int)pow(2, number - 1);
5         return res;
6     }
7 };
View Code
1 class Solution {
2 public:
3     int jumpFloorII(int number) {
4         int res = 1;
5         for (int i = 2; i <= number; i++)
6             res *= 2;
7         return res;
8     }
9 };
View Code

10.矩形覆盖

 1 class Solution {
 2 public:
 3     int rectCover(int number) {
 4         vector<int> res(2, 0);
 5         res[0] = 1;
 6         res[1] = 2;
 7         
 8         for (int i = 2; i < number; i++)
 9             res[i % 2] = res[0] + res[1];
10         
11         return res[(number - 1) % 2];
12     }
13 };
View Code

11.二进制中1的个数

 1 class Solution {
 2 public:
 3      int  NumberOf1(int n) {
 4          int cnt = 0;
 5          while (n)
 6          {
 7              cnt++;
 8              n &= (n - 1);
 9          }
10          return cnt;
11      }
12 };
View Code

12.数值的整数次方

 1 class Solution {
 2 public:
 3     double Power(double base, int exponent) {
 4         if (exponent == 0)
 5             return 1.0;
 6         else if (exponent == 1)
 7             return base;
 8         
 9         double res = Power(base, exponent >> 1);
10         res *= res;
11         
12         if (exponent & 0x01 == 1)
13             res *= base;
14         
15         return res;
16     }
17 };
View Code
 1 class Solution {
 2 public:
 3     double Power(double base, int exponent) {
 4         if (exponent == 0)
 5             return 1.0;
 6         else if (exponent == 1)
 7             return base;
 8         
 9         return (exponent & 0x01 == 1) ? Power(base * base, exponent >> 1) : base * Power(base * base, exponent >> 1);
10     }
11 };
View Code
 1 class Solution {
 2 public:
 3     double Power(double base, int exponent) {
 4         if (exponent == 0)
 5             return 1.0;
 6         else if (exponent == 1)
 7             return base;
 8         else if (exponent < 0)
 9         {
10             exponent = -exponent;
11             base = 1 / base;
12         }
13         
14         double res = 1.0;
15         while (exponent)
16         {
17             if (exponent & 0x01 == 1)
18                 res *= base;
19             base *= base;
20             exponent >>= 1;
21         }
22         
23         return res;
24     }
25 };
View Code

 13.调整数组顺序使奇数位于偶数前面

 1 class Solution {
 2 public:
 3     void reOrderArray(vector<int> &array) {
 4         if (array.empty())
 5             return ;
 6         
 7         vector<int> ji;
 8         vector<int> ou;
 9         int len = array.size();
10         for (int i = 0; i < len; i++)
11         {
12             if (array[i] & 0x01)
13                 ji.push_back(array[i]);
14             else
15                 ou.push_back(array[i]);
16         }
17         
18         int i = 0;
19         for (auto num: ji)
20             array[i++] = num;
21         for (auto num: ou)
22             array[i++] = num;
23     }
24 };
View Code
 1 class Solution {
 2 public:
 3     void reOrderArray(vector<int> &array) {    //未考虑相对位置的顺序
 4         int len = array.size();
 5         int cnt = 0;
 6         
 7         int l = 0;
 8         int r = len - 1;
 9         while (l < r)
10         {
11             while (l < r && (array[l] & 0x01) == 1)
12                 l++;
13             
14             while (l < r && (array[r] & 0x01) == 0)
15                 r--;
16             
17             if (l < r)
18                 swap(array[l], array[r]);
19         }
20     }
21 };
View Code

14.链表中倒数第k个结点

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
12         int i = 1;
13         ListNode* slow = pListHead;
14         ListNode* fast = pListHead;
15         
16         while (i <= k && fast)
17         {
18             i++;
19             fast = fast->next;
20         }
21         
22         if (i <= k)
23             return NULL;
24         else
25         {
26             while (fast)
27             {
28                 fast = fast->next;
29                 slow = slow->next;
30             }
31             return slow;
32         }
33     }
34 };
View Code

15.反转链表

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* ReverseList(ListNode* pHead) {
12         ListNode* head = NULL;
13         while (pHead)
14         {
15             ListNode* next = pHead->next;
16             pHead->next = head;
17             head = pHead;
18             pHead = next;
19         }
20         return head;
21     }
22 };
View Code

16.合并两个排序的链表

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
12     {
13         ListNode* head = new ListNode(0);
14         ListNode* p = head;
15         while (pHead1 && pHead2)
16         {
17             if (pHead1->val <= pHead2->val)
18             {
19                 p->next = pHead1;
20                 pHead1 = pHead1->next;
21             }
22             else
23             {
24                 p->next = pHead2;
25                 pHead2 = pHead2->next;
26             }
27             p = p->next;
28         }
29         
30         p->next = (pHead1 == NULL) ? pHead2 : pHead1;
31         
32         return head->next;
33     }
34 };
View Code

17.树的子结构

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     bool comp(TreeNode* pRoot1, TreeNode* pRoot2)
13     {
14         if (pRoot2 == NULL)
15             return true;
16         else if (pRoot1 == NULL || pRoot1->val != pRoot2->val)
17             return false;
18         
19         return comp(pRoot1->left, pRoot2->left) && comp(pRoot1->right, pRoot2->right);
20     }
21     bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
22         if (pRoot2 == NULL)
23             return false;
24         if (pRoot1 == NULL)
25             return false;
26         
27         return comp(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);
28     }
29 };
View Code

 18.二叉树的镜像

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     void Mirror(TreeNode *pRoot) {
13         if (pRoot == NULL)
14             return ;
15         
16         if (pRoot->left == NULL && pRoot->right == NULL)
17             return ;
18         
19         TreeNode* t = pRoot->left;
20         pRoot->left = pRoot->right;
21         pRoot->right = t;
22         
23         if (pRoot->left)
24             Mirror(pRoot->left);
25         if (pRoot->right)
26             Mirror(pRoot->right);
27     }
28 };
View Code

 19顺时针打印矩阵

 1 class Solution {
 2 public:
 3     vector<int> printMatrix(vector<vector<int> > matrix) {
 4         vector<int> res;
 5         if (matrix.empty())
 6             return res;
 7         
 8         int n = matrix.size();
 9         int m = matrix[0].size();
10         int rowStart = 0;
11         int rowEnd = n - 1;
12         int columnStart = 0;
13         int columnEnd = m - 1;
14         int num = 0;
15         
16         while (res.size() < n * m)
17         {
18             for (int i = columnStart; i <= columnEnd; i++)
19                 res.push_back(matrix[rowStart][i]);
20             rowStart++;
21             
22             for (int i = rowStart; i <= rowEnd; i++)
23                 res.push_back(matrix[i][columnEnd]);
24             columnEnd--;
25             
26             if (rowStart > rowEnd || columnStart > columnEnd)
27                 break;
28             
29             for (int i = columnEnd; i >= columnStart; i--)
30                 res.push_back(matrix[rowEnd][i]);
31             rowEnd--;
32             
33             for (int i = rowEnd; i >= rowStart; i--)
34                 res.push_back(matrix[i][columnStart]);
35             columnStart++;
36         }
37         return res;
38     }
39 };
View Code

20.包含min函数的栈

 1 class Solution {
 2 public:
 3     stack<int> s;
 4     void push(int value) {
 5         int num = value;
 6         if (!s.empty())
 7         {
 8             num = s.top();
 9             if (num > value)
10                 num = value;
11         }
12         s.push(num);
13         s.push(value);
14     }
15     void pop() {
16         s.pop();
17         s.pop();
18     }
19     int top() {
20         return s.top();
21     }
22     int min() {
23         int num = s.top();
24         s.pop();
25         int res = s.top();
26         s.push(num);
27         return res;
28     }
29 };
View Code

21.栈的压入、弹出序列

22.从上往下打印二叉树

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     vector<int> PrintFromTopToBottom(TreeNode* root) {
13         vector<int> res;
14         if (root == NULL)
15             return res;
16         
17         queue<TreeNode*> q;
18         TreeNode* p = NULL;
19         q.push(root);
20         while (!q.empty())
21         {
22             int len = q.size();
23             for (int i = 0; i < len; i++)
24             {
25                 p = q.front();
26                 q.pop();
27                 res.push_back(p->val);
28                 
29                 if (p->left)
30                     q.push(p->left);
31                 if (p->right)
32                     q.push(p->right);
33             }
34         }
35         return res;
36     }
37 };
View Code

23.二叉搜索树的后序遍历序列

24.二叉树中和为某一值的路径

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     vector<vector<int>> res;
13     vector<int> v;
14     void dfs(TreeNode* root, int sum, int t)
15     {
16         if (root == NULL)
17             return ;
18         
19         sum += root->val;
20         v.push_back(root->val);
21         if (sum == t && root->left == NULL && root->right == NULL)
22             res.push_back(v);
23             
24         if (root->left)
25             dfs(root->left, sum, t);
26         if (root->right)
27             dfs(root->right, sum, t);
28         
29         v.pop_back();
30     }
31     vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
32         if (root == NULL)
33             return res;
34         
35         dfs(root, 0, expectNumber);
36         return res;
37     }
38 };
View Code

 

推荐阅读