devbox
程序代码艺术家
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

剑指Offer题目汇总(C++版)_剑指offer c++版

作者：程序代码艺术家 | 2024-01-29 17:14:23

赞

踩

剑指offer c++版

最近，鉴于目前网上关于《剑指Offer》C++版的汇总资料特别少或者不规范，特整理了一版书中重要的考题，以备学习使用。

目录

一、位运算

1. 二进制中1的个数

2. 二进制中0的个数

3. 二进制高位连续0的个数

二、二叉树

1. 二叉搜索树第k个结点

2. 从上往下打印二叉树

3. 二叉树打印成多行

4. 数据流中位数

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

6. 重建二叉树

7. 树的子结构

8. 二叉树的镜像

9. 二叉树的下一个节点

三、字符串

1. 正则表达式的匹配

2. 表示数值的字符串

3. 第一个只出现一次的字符

4. 左旋转字符串

四、数组

1. 构建乘积数组

2. 二维数组的查找

3. 连续子数组的最大和

一、位运算

1. 二进制中1的个数

题目：输入一个整数，输出该数二进制表示中1的个数，负数用补码表示。

思路：&运算通常用于二进制的取位操作，n&(n-1) 操作相当于把二进制表示中最右边的1变成0。

  1. int NumberOf1(int n)
  2. {
  3.     int count = 0;
  4.     while (n != 0)
  5.     {
  6.         n = n & (n-1);
  7.         ++count;
  8.     }
  9.     return count;
  10. }

2. 二进制中0的个数

题目：输入一个整数，输出该二进制表示中0的个数，负数用补码表示。

思路：n&1操作相当于判断二进制最后一位数是否位1，左移相当乘2，右移除2，左移补0，有符号右移，正数补0，负数补1，无符号右移，均补0。每次无符号右移一位，同1做&运算，可以判断最后一位是否为1。

  1. int NumberOf0(int n)
  2. {
  3.     int count = 0;
  4.     while (n != 0)
  5.     {
  6.         if ((n&1) != 1)
  7.             count++;
  8.         n>>=1;
  9.     }
  10.     return count;
  11. }

3. 二进制高位连续0的个数

题目：输入一个整数，输出该二进制中高位连续0的个数。

思路：0x80000000的二进制是1000 0000 0000 0000 0000 0000 0000 0000，仅最高位为1，每次左移一位，与最高位为1的二进制进行&操作，可以判断高位连续为0的个数。

  1. int numberOfLeading0(int n)
  2. {
  3.     if (n == 0)
  4.         return 32;
  5.     int count = 0;
  6.     int mask = 0x80000000;
  7.     int m = n & mask;
  8.     while (m == 0)
  9.     {
  10.         ++count;
  11.         n <<= 1;
  12.         m = n & mask;
  13.     }
  14.     return count;
  15. }

二、二叉树

1. 二叉搜索树第k个结点

题目：输入一颗二叉搜索树，输出第k个节点。

思路：二叉搜索树是满足根节点值大于左节点，小于右节点的。中序遍历二叉搜索树可得到有序的，判断当前是否为k即可。

  1. struct treeNode {
  2.      int val;
  3.      treeNode * left;
  4.      treeNode * right;
  5.      treeNode(int x) : val(x), left(NULL), right(NULL) {}
  6.  };
  7.  
  8.  treeNode *inorder(treeNode *root, int &k)
  9.  {
  10.     if (root == NULL) return NULL;
  11.     treeNode * node = NULL;
  12.  
  13.     node = inorder(root->left,k);
  14.  
  15.     if (k-- == 1)
  16.         node = root;
  17.     if (k > 0)
  18.         node = inorder(root->right, k);
  19.      return node;
  20.  }
  21.  
  22.  treeNode *KthNode(treeNode * pRoot, int k)
  23.  {
  24.      return inorder(pRoot, k);
  25.  }

2. 从上往下打印二叉树

题目：输入一颗二叉树，输出从上到下，从左到右节点的值。

思路：可借助队列先进先出的特性，先层次遍历二叉树，依次存入队列中，最后再逐个弹出。

  1. struct treeNode {
  2.      int val;
  3.      treeNode * left;
  4.      treeNode * right;
  5.      treeNode(int x) : val(x), left(NULL), right(NULL) {}
  6.  };
  7.  
  8. vector<int> PrintFromTopToBottom(treeNode *root)
  9. {
  10.     vector<int> vec;
  11.     queue<treeNode*> queue;
  12.  
  13.     if (root == NULL) return vec;
  14.     queue.push(root);
  15.  
  16.     while(!queue.empty())
  17.     {
  18.         vec.push_back(queue.front()->val);
  19.         if (queue.front()->left != NULL)
  20.             queue.push(queue.front()->left);
  21.         if (queue.front()->right != NULL)
  22.             queue.push(queue.front()->right);
  23.         queue.pop();
  24.     }
  25. }

3. 二叉树打印成多行

题目：输入一颗二叉树，输出从上到下，从左到右节点的值，且每一层输出在一行。

思路：可借助队列先进先出的特性，先层次遍历二叉树，依次存入队列中，最后再逐个弹出。

  1. vector<vector<int>> Print(treeNode *root)
  2. {
  3.     vector<vector<int>> vec;
  4.     queue<treeNode*> queue;
  5.  
  6.     if (root == NULL) return vec;
  7.     queue.push(root);
  8.  
  9.     while(!queue.empty())
  10.     {
  11.         int n = queue.size(); //n用于保存每一次队列的元素个数，即二叉树每一层节点的个数。
  12.         vector<int> v;
  13.         while(v.size() < n)
  14.         {
  15.             v.push_back(queue.front()->val);
  16.             if(queue.front()->left)
  17.                 queue.push(queue.front()->left);
  18.             if(queue.front()->right)
  19.                 queue.push(queue.front()->right);
  20.             queue.pop();
  21.         }
  22.         vec.push_back(v);
  23.     }
  24. }

4. 数据流中位数

题目：输入一个数据流，输出数据流中的中位数。

思路：最容易的办法是如果排序取中间值，显然这种不是面试官希望的答案。简单的办法是采取优先队列priority_queue，优先队列具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的。把列表分成两半，分别用两个优先级队列来保存，左侧为数字越大优先级越高，右侧为数字越小优先级越高。那么取出两个优先级的top值即可。 

  1. priority_queue<int, vector<int>, greater<int>> Rqueue;  //最小堆
  2. priority_queue<int, vector<int>, less<int>> Lqueue;     //最大堆
  3.  
  4. void addNum(int num)
  5. {
  6.     Lqueue.push(num);
  7.     if ((Lqueue.size() - Rqueue.size())>1)
  8.     {
  9.         Rqueue.push(Lqueue.top());
  10.         Lqueue.pop();
  11.     }
  12.     if(Rqueue.size() > 0 && Lqueue.top() > Rqueue.top())
  13.     {
  14.         int tmp = Lqueue.top();
  15.         Lqueue.pop();
  16.         Lqueue.push(Rqueue.top());
  17.         Rqueue.top();
  18.         Rqueue.push(tmp);
  19.     }
  20. }
  21.  
  22. double findMedian()
  23. {
  24.     if (Lqueue.size() == Rqueue.size()) return  1.0*(Lqueue.top()+Rqueue.top())/2;
  25.     else return Lqueue.top();
  26. }

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

题目：输入一颗二叉树的跟节点和一个整数，输出二叉树中结点值的和为输入整数的所有路径，返回的数组长度大的靠前。

思路：使用前序遍历的方式访问节点，使用二维向量vec存储全部路径，使用一维向量tmp存储当前路径。遍历二叉树的过程：按前序遍历顺序访问每一个节点。访问每个结点时，将结点添加到路径向量tmp中。如果当前结点是叶子结点，则判断当前路径是否是符合条件的路径，符合条件的路径存入到二维向量vec；如果当前结点不是叶子结点，则递归当前节点的左右子节点。

  1. struct treeNode {
  2.  int val;
  3.  treeNode * left;
  4.  treeNode * right;
  5.  treeNode(int x) : val(x), left(NULL), right(NULL) {}
  6. };
  7.  
  8. vector<vector<int>> vec;
  9. vector<int> tmp;
  10.  
  11. void search(treeNode* root, int target)
  12. {
  13.     tmp.push_back(root->val);
  14.  
  15.     if (root->left == NULL && root->right == NULL) {
  16.         if (root->val == target) {
  17.             vec.push_back(tmp);
  18.         }
  19.     }
  20.  
  21.     if (root->left != NULL)
  22.         search(root->left, target-root->val);
  23.  
  24.     if (root->right != NULL)
  25.         search(root->right,target-root->val);
  26.  
  27.     if (!tmp.empty())
  28.          tmp.pop_back();
  29.  
  30. }
  31.  
  32. void findTarget(treeNode* root, int target)
  33. {
  34.     if (root == NULL) return;
  35.  
  36.     search(root,target);
  37. }

6. 重建二叉树

题目：输入某二叉树的前序遍历和中序遍历的结果，且前序遍历和中序遍历的结果中都不含重复的数字，输出重建二叉树。

思路：根据前序遍历找到根节点，再根据中序遍历找到左右子树，最后根据前序遍历得到左右子树的前序遍历和中序遍历，进行递归求解。

  1. struct treeNode {
  2.  int val;
  3.  treeNode * left;
  4.  treeNode * right;
  5.  treeNode(int x) : val(x), left(NULL), right(NULL) {}
  6. };
  7.  
  8. treeNode* ReConstructTree(vector<int>& pre, vector<int>& mid)
  9. {
  10.     if (pre.empty() || mid.empty())
  11.         return NULL;
  12.  
  13.     treeNode *head = new treeNode(pre[0]);
  14.  
  15.     vector<int> leftpre, leftmid;
  16.     vector<int> rightpre, rightmid;
  17.  
  18.     size_t root = 0;
  19.  
  20.     // 寻找根节点
  21.     for (size_t i = 0;i < mid.size();++i)
  22.     {
  23.         if (mid[i] == pre[0])
  24.         {
  25.             root = i;
  26.             break;
  27.         }
  28.     }
  29.  
  30.     // 左子树
  31.     for (size_t i = 0;i < root;++i)
  32.     {
  33.         leftpre.push_back(pre[i+1]);
  34.         leftmid.push_back(mid[i]);
  35.     }
  36.  
  37.     // 右子树
  38.     for (size_t i = root+1;i < mid.size();++i)
  39.     {
  40.         rightpre.push_back(pre[i]);
  41.         rightmid.push_back(mid[i]);
  42.     }
  43.  
  44.     head->left  = ReConstructTree(leftpre,leftmid);
  45.     head->right = ReConstructTree(rightpre,rightmid);
  46.  
  47.     return head;
  48. }

7. 树的子结构

题目：输入两棵二叉树A，B，判断B是不是A的子结构。

思路：从树A的根节点开始寻找与B根节点相同的节点，如果相同，则继续比较其他节点，不相同，则继续。

  1. struct treeNode {
  2.  int val;
  3.  treeNode * left;
  4.  treeNode * right;
  5.  treeNode(int x) : val(x), left(NULL), right(NULL) {}
  6. };
  7.  
  8. bool IsEqualTree(treeNode* pRoot1, treeNode* pRoot2)
  9. {
  10.     if (pRoot2 == NULL)
  11.         return true;
  12.     if (pRoot1 == NULL)
  13.         return false;
  14.     if (pRoot1->val != pRoot2->val)
  15.         return false;
  16.  
  17.     return IsEqualTree(pRoot1->left,pRoot2->left) && IsEqualTree(pRoot1->right,pRoot2->right);
  18. }
  19.  
  20. bool HasSubTree(treeNode* pRoot1, treeNode* pRoot2)
  21. {
  22.     bool result = false;
  23.     if (pRoot2 != NULL && pRoot1 != NULL)
  24.     {
  25.         if (pRoot1->val == pRoot2->val)  //头结点相同
  26.         {
  27.             result = IsEqualTree(pRoot1,pRoot2); //比较子节点
  28.         }
  29.         if (!result)
  30.         {
  31.             result = HasSubTree(pRoot1->left, pRoot2); //继续找头结点相同的节点
  32.         }
  33.         if (!result)
  34.         {
  35.             result = HasSubTree(pRoot1->right, pRoot2);
  36.         }
  37.     }
  38.     return result;
  39. }

8. 二叉树的镜像

题目：输入一颗二叉树，输出源二叉树的镜像。

思路：递归转换二叉树即可。

  1. struct treeNode {
  2.  int val;
  3.  treeNode * left;
  4.  treeNode * right;
  5.  treeNode(int x) : val(x), left(NULL), right(NULL) {}
  6. };
  7.  
  8. treeNode* imageTree(treeNode* pRoot)
  9. {
  10.     if (!pRoot) return NULL;
  11.  
  12.     treeNode* iRoot = new treeNode(pRoot->val);
  13.  
  14.     iRoot->left  = imageTree(pRoot->right);
  15.     iRoot->right = imageTree(pRoot->left);
  16.  
  17.     return iRoot;
  18. }

9. 二叉树的下一个节点

题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路：1.如果存在右子节点，则右子节点的最左节点为下一个节点; 2.如果不存在右子节点，且该节点是父节点的左子节点，则父节点为下一个节点; 3.如果不存在右子节点，且该节点是父节点的右子节点，则向上找到一个节点是该其父节点的左孩子，则该其父节点为下一个节点。

  1. struct treeNode {
  2.     int val;
  3.     treeNode * left;
  4.     treeNode * right;
  5.     treeNode * next;
  6.     treeNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
  7. };
  8.  
  9. treeNode* GetNext(treeNode *pNode)
  10. {
  11.     if (pNode == NULL)
  12.         return NULL;
  13.     // 1.如果存在右子节点，则右子节点的最左节点为下一个节点
  14.     if (pNode->right)
  15.     {
  16.         pNode = pNode->right;
  17.         while(pNode->left)
  18.         {
  19.             pNode = pNode->left;
  20.         }
  21.         return pNode;
  22.     }
  23.     // 2.如果不存在右子节点，且该节点是父节点的左子节点，则父节点为下一个节点
  24.     if (!pNode->right)
  25.     {
  26.         if(pNode->next && pNode->next->left == pNode)
  27.         {
  28.             return pNode->next;
  29.         }
  30.     }
  31.     // 3.如果不存在右子节点，且该节点是父节点的右子节点，则向上找到一个节点是该其父节点的左孩子，则该其父节点为下一个节点
  32.     if (!pNode->right)
  33.     {
  34.         if(pNode->next && pNode->next->right == pNode)
  35.         {
  36.             pNode = pNode->next;
  37.             while (pNode->next)
  38.             {
  39.                 if (pNode->next->left == pNode)
  40.                     return pNode->next;
  41.                 pNode = pNode->next;
  42.             }
  43.         }
  44.     }
  45.     return NULL;
  46. }

三、字符串

1. 正则表达式的匹配

题目：输入一个字符串和其模式字符串，判断两者是否正则匹配。模式中的字符'.'表示任意一个字符，而'*'表示前一个字符重复出现任意次（包含0次）。

思路：按照pattern下个字符为'*'进行递归判断。

  1. bool match(const char* str, const char* pattern)
  2. {
  3.     if (str == NULL || pattern == NULL)
  4.         return false;
  5.     // 字符串都匹配结束，返回true
  6.     if (*str == '\0' && *pattern == '\0')
  7.         return true;
  8.     // pattern匹配结束，str还没匹配结束，返回false
  9.     if (*str != '\0' && *pattern == '\0')
  10.         return false;
  11.     // pattern下个字符为'*'
  12.     if (*(pattern+1) == '*')
  13.     {
  14.         // 1. 当前字符相等，则str后移一位或者pattern后移二位
  15.         if (*str == *pattern || (*str != '\0' && *pattern == '.'))
  16.         {
  17.             return match(str+1, pattern) || match(str, pattern+2);
  18.         }
  19.         // 2. 当前字符不相等，则pattern后移二位
  20.         else
  21.         {
  22.             return match(str, pattern+2);
  23.         }
  24.     }
  25.     // pattern下个字符不是'*'
  26.     else
  27.     {
  28.         // 当前字符相等，则str和pattern均后移一位，继续比较下一位
  29.         if (*str == *pattern || (*str != '\0' && *pattern == '.'))
  30.             return match(str+1, pattern+1);
  31.         else
  32.             return false;
  33.     }
  34. }

2. 表示数值的字符串

题目：输入一个字符串，判断该字符串是否表示数值（包括整数、小数、正负数、科学计数法等）

思路：按照当前字符为正负号、小数点、指数e进行循环判断。

  1. bool IsNumeric(char * str)
  2. {
  3.     if (str == NULL)
  4.         return false;
  5.     // 第一位为符号位
  6.     if (*str == '+' || *str == '-')
  7.         ++str;
  8.     // 第一位不为数字,且不为'.'
  9.     else if ((*str < '0' || *str > '9') && *str != '.')
  10.         return false;
  11.     bool flag = false; //是否出现过'.'或者'e'
  12.     while (*str != '\0')
  13.     {
  14.         // 当前字符为符号,且前一个字符不为'e'，不为最后一个数
  15.         if ((*str == '+' || *str == '-') && *(str-1) != 'e' && *(str-1) != 'E' && *(str+1) >= '0' && *(str+1) <= '9')
  16.             return false;
  17.         // 当前字符为'.'
  18.         if (*str == '.')
  19.         {
  20.             // 已经出现或者最后一位为'.'或者'e'或者'E'
  21.             if (flag || *(str+1) == '\0')
  22.                 return false;
  23.             else
  24.                 flag = true;
  25.         }
  26.         // 当前字符为'e'或者'E'
  27.         else if (*str == 'e' || *str == 'E')
  28.         {
  29.             // 已经出现或者最后一位为'.'或者'e'或者'E'
  30.             if (flag || *(str+1) == '\0')
  31.                 return false;
  32.             else {
  33.                 flag = true;
  34.             }
  35.         }
  36.         else if(*str < '0' || *str > '9')
  37.         {
  38.             return false;
  39.         }
  40.         ++str;
  41.     }
  42.     return true;
  43. }

3. 第一个只出现一次的字符

题目：在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）。

思路：利用map形成键值对，用于存储字符串中每个字符出现的次数，最后再遍历一遍字符串，找到第一个map值为1的索引即可。

  1. int FirstNotRepeatingChar(string str)
  2. {
  3.     std::map<char,int> map;
  4.     for (int i=0;i < str.size();++i)
  5.     {
  6.         map[str[i]]++;
  7.     }
  8.     for (int i=0;i < str.size();i++)
  9.     {
  10.         if (map[str[i]] == 1)
  11.             return i;
  12.     }
  13.     return -1;
  14. }

4. 左旋转字符串

题目：对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。

思路：拼接两次字符序列，然后从第n位开始取字符序列长度的字符串即可。例如，SS=”abcXYZdefabcXYZdef”，左移3位的话，从SS的第3个字符开始取，则翻转后的字符串为“XYZdefabc”。

  1. string reversal(string str, int k)
  2. {
  3.     string doubleS = str + str;
  4.     string reverS;
  5.     for (int i=k;i < str.size()+k;i++)
  6.     {
  7.         reverS += doubleS[i];
  8.     }
  9.     return reverS;
  10. }

四、数组

1. 构建乘积数组

题目：给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]，不能使用除法。

思路：用矩阵的方式，先计算左下三角，再计算右上三角，将B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]看成两部分来计算，即：A[0]*A[1]*...*A[i-1]和 *A[i+1]*...*A[n-1]两部分的乘积就是B[i]。

  1. vector<int> multiply(vector<int> A) {
  2.     int num = A.size();
  3.     vector<int> B1(num,1);
  4.     vector<int> B2(num,1);
  5.     vector<int> B(num,1);
  6.  
  7.     // 计算左下角B1
  8.     for (int i=1;i < num;++i)
  9.     {
  10.         B1[i] = B1[i-1]*A[i-1];
  11.     }
  12.     // 计算右上角B2
  13.     for (int i=num-2;i >= 0;--i)
  14.     {
  15.         B2[i] = B2[i+1]*A[i+1];
  16.     }
  17.     // 计算矩阵B
  18.     for (int i=0;i < num;i++)
  19.     {
  20.         B[i] = B1[i]*B2[i];
  21.     }
  22.     return B;
  23. }

2. 二维数组的查找

题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：从右上角开始，若小，向下走，删除一行，若大，向左走，删除一列。

  1. bool FindElement(vector<vector<int>> vecs, int target)
  2. {
  3.     if (vecs.empty())
  4.         return false;
  5.     int m = 0;
  6.     int n = vecs[0].size()-1;
  7.     while (m < vecs.size() && n >= 0)
  8.     {
  9.         if (vecs[m][n] == target)
  10.             return true;
  11.         else if (vecs[m][n] < target)
  12.             m++;
  13.         else
  14.             n--;
  15.     }
  16.     return false;
  17. }

3. 连续子数组的最大和

题目：给一个数组，返回它的最大连续子序列的和。

思路：利用动态规划解决，dp[i] = max(vec[i],dp[i-1]+vec[i])

  1. int MaxContinuesSubarraySum(vector<int> vec)
  2. {
  3.     vector<int> dp(vec.size(),0);
  4.     for (int i = 1;i < vec.size();i++)
  5.     {
  6.         dp[i] = vec[i] > (dp[i-1]+vec[i])?vec[i]:(dp[i-1]+vec[i]);
  7.     }
  8.     int max = 0;
  9.     for (int i = 0;i < dp.size();++i)
  10.     {
  11.         if (max < dp[i])
  12.             max = dp[i];
  13.     }
  14.     return max;
  15. }

参考文献

1. 《剑指offer Java版本》

 

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号