C++笔试真题

可变分区管理方案

• 最佳适应：空闲区按容量递增
• 最坏适应：空闲区按容量递减
• 首先适应：空闲区按地址递增

C++的结构体中有构造函数。

Linux新建用户或组

• useradd：命令用于建立用户账号
• usermod：修改用户账号
• groupadd：创建一个新的工作组
• userdel：删除用户账号

#include可以出现在程序文件的中间。

函数声明可以省略形参名，定义时不可以。

线性表

一个非空的数据结构如果满足以下两个条件：

1. 有且只有一个根节点
2. 每一个结点最多有一个前节点，也最多有一个后节点

称为线性结构，在数据结构中称为线性表。
双向链表结点具有两个指针域，属于线性结构。
循环链表所有结点的指针都非空，也属于线性结构。

查找哈希表

构造哈希表的方法包括：直接地址法、除留余数法。

解决冲突的方法包括：

• 链地址法：将哈希值相同的元素用链表进行相连。
• 线性探测再散列法：冲突后依次向下循环查找空位置进行放置

数字范围按位与

给两个整数left和right，表示区间[left, right]，返回此区间内所有数字按位与的结果。

对于一系列的位，只要有一个零值的位，那么这一系列的按位与运算结果都为零。

在上面的例子中，我们可以发现，对所有数字执行按位与运算的结果是所有对应二进制字符串的公共前缀再用零补上后面的剩余位。

只出现一次的数字（二）

给一个整数数组nums，除某个元素仅出现一次外，其余每个元素都出现三次，找到并返回只出现了一次的元素。

设计线性时间复杂度的算法，并且使用常数级空间解决此问题。

依次确定每个二进制位
由于数组中的元素在int范围内，可以依次计算答案的每一个二进制位是0还是1。

具体地，考虑答案的第i个二进制位（i从0开始编号），它可能为0或1。

答案的第i个位就是数组中所有元素的第i个二进制位之和除以3的余数。

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(int i=0; i<32; i++){int sum = 0;for(int num : nums){sum += ((num >> i) & 1);}ret += ((sum%3) << i);}return ret;}
};

Pow(x, n)

快速幂+递归
快速幂算法的本质是分治算法。
从x开始，每次直接把上一次的结果平方。计算5次就可以得到x64次方。

class Solution {
public:double quickMul(double x, long long N){if(N == 0){return 1.0;}double y = quickMul(x, N/2);return N%2 == 0 ? y * y : y * y * x;}double myPow(double x, int n) {long long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N); }
};

阶乘后的零

给一个整数n，返回n!结果中尾随零的数量。

n!尾零的数量，就是求因子10的个数，而10=2x5，因此转换成求n!中质因子2的个数和质因子5的个数的较小值。

由于质因子5的个数不会大于质因子2的个数，仅考虑质因子5的个数。

而n!中质因子5的个数等于每个数的质因子5的个数之和。

class Solution {
public:int trailingZeroes(int n) {int res = 0;for(int i=5; i<=n; i += 5){for(int j=i; j%5 == 0; j/=5){res++;}}return res;}
};

环形链表

快慢指针

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {if(head == nullptr || head->next == nullptr){return false;}ListNode* slow = head->next;ListNode* fast = head->next->next;while(fast != nullptr){if(slow == fast){return true;}if(fast->next == nullptr){return false;}slow = slow->next;fast = fast->next->next;}return false;}
};

合并两个有序链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1 == nullptr){return list2;}if(list2 == nullptr){return list1;}ListNode* newHead;if(list1->val <= list2->val){newHead = list1;list1 = list1->next;}else{newHead = list2;list2 = list2->next;}ListNode* p = newHead;while(list1 && list2){if(list1->val <= list2->val){p->next = list1;p = p->next;list1 = list1->next;}else{p->next = list2;p = p->next;list2 = list2->next;}}while(list1){p->next = list1;p = p->next;list1 = list1->next;}while(list2){p->next = list2;p = p->next;list2 = list2->next;}return newHead;}
};

对称二叉树

如果一个树的左子树和右子树镜像对称，那么这个树是对称的。

• 它们的两个根节点具有相同的值
• 每个树的右子树与另一个树的左子树镜像对称

二叉树的层平均值

广度优先遍历
从根节点开始搜索，每一轮遍历同一层的全部节点，计算该层的节点数以及该层的节点数之和，然后计算该层的平均值。

• 初始时，将根节点入队列。
• 每一轮遍历时，将队列中的节点全部取出，计算这些节点的数量以及和，然后计算平均值，然后将节点的全部为空子节点加入队列。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {vector<double> average;queue<TreeNode *> que;que.push(root);while(!que.empty()){double sum = 0;int size = que.size();for(int i=0; i<size; i++){TreeNode* node = que.front();que.pop();sum += node->val;TreeNode* left = node->left;TreeNode* right = node->right;if(left){que.push(left);}if(right){que.push(right);}}average.push_back(sum / size);}return average;}
};

二叉树层序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;queue<TreeNode* > que;if(!root){return res;}que.push(root);while(!que.empty()){vector<int> temp;int size = que.size();for(int i=0; i<size; i++){TreeNode* node = que.front();que.pop();temp.push_back(node->val);TreeNode* left = node->left;TreeNode* right = node->right;if(left){que.push(left);}if(right){que.push(right);}}res.push_back(temp);}return res;}
};

删除有序数组中的重复项

一个有序数组nums，原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次，返回删除后数组的新长度。

必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。

class Solution {
public:int removeDuplicates(vector<int>& nums) {int left = 0;int right = 0;int n = nums.size();int count = 0;int sum = 0;while (right < n) {if (nums[left] == nums[right]) {count++;right++;} else {if (count > 1) {nums[++left] = nums[left];sum += 2;} else {sum += 1;}nums[++left] = nums[right++];count = 1;}}if (count > 1) {nums[++left] = nums[left];sum += 2;} else {sum += 1;}return sum;}
};

轮转数组

给定一个整数数组nums，将数组中的元素向右轮转k个位置。

class Solution {
public:void rotate(vector<int>& nums, int k) {int n = nums.size();k = k % n;reverse(nums.begin(), nums.end());reverse(nums.begin(), nums.begin()+k);reverse(nums.begin()+k, nums.end());}
};

买卖股票的最佳时机

class Solution {
public:int maxProfit(vector<int>& prices) {int result = 0;int price = prices[0];for(int i=1; i<prices.size(); i++){if(prices[i] > price){result = max(result, prices[i] - price);}else{price = prices[i];}}return result;}
};

买股票的最佳时机二

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n,vector<int>(2)); //dp[i][0]第i天没有股票dp[0][0] = 0;dp[0][1] = -prices[0];for(int i=1; i<n; i++){dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]);}return dp[n-1][0];}
};

跳跃游戏

给一个非负整数组nums，最初位于数组第一个下标，数组中每个元素代表可以跳跃的最大长度。
判断是否能跳到最后一个下标。

贪心
对于数组中任意一个位置y，只要存在一个位置x，它本身可以到达，并且x + nums[x] ≥ y，那么y也可以到达。

对于每一个可到达的位置x，它使得x+1，x+2，…，x+nums[x]这些连续的位置可以到达。

class Solution {
public:bool canJump(vector<int>& nums) {int n = nums.size();int rightmost = 0;for(int i=0; i<n; i++){if(i <= rightmost){rightmost = max(rightmost, i+nums[i]);if(rightmost >= n-1){return true;}}}return false;}
};

Z字形变换

给定一个字符串s，根据给定的行数numRows，以上往下，从左到右进行z字形排列。

利用二维矩阵模拟
设n为字符串s的长度，r = numRows，对于r=1（只有一行），或者r >= n（只有一列的情况），答案与s相同，可以直接返回。

其余情况，考虑创建一个二维矩阵，然后在矩阵上按Z字形填写字符串s，最后逐行扫描矩阵中的非空字符，组成答案。

根据题意，当我们在矩阵上填写字符时，会向下填写r个字符，然后向右上填写r-2个字符，最后回到第一行，因此Z字形变换周期t = r + r - 2 = 2r - 2。 每个周期会占用矩阵上的1+r-2 = r-1列。

共有n/t个周期乘上列数，等于矩阵的列数。

创建一个r行c列的矩阵，然后遍历字符串并按Z字形填写。

class Solution {
public:string convert(string s, int numRows) {int n = s.length(), r = numRows;if(r == 1 || r >= n){return s;}//变换周期int t = 2*r - 2;int c = (n + t -1) / t * (r - 1);//创建二维字符串vector<string> mat(r, string(c, 0));for(int i = 0, x = 0, y =0; i<n; i++){mat[x][y] = s[i];if(i % t < r - 1){++x; //向下移动}else{--x;++y; //向右上移动}}string ans;for(auto &row : mat){for(char ch : row){if(ch){ans += ch;}}}return ans;}
};

反转字符串中的单词

class Solution {
public:vector<string> splitString(string s){istringstream iss(s);vector<string> res;string word;while(iss >> word){res.push_back(word);}return res;}string reverseWords(string s) {vector<string> words = splitString(s);string res;for(int i=words.size()-1; i>=0; i--){res += words[i] + " ";}res.pop_back();return res;}
};