含负数进行绝对值排序
参考
给你一个整数数组 nums，请你将该数组升序排列
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256/* //插入排序，o(n2)，超时 //从第二个数开始，将每个数插入到前面已排好序的序列中（所有比当前数大的后移一格） class Solution { public: vector<int> sortArray(vector<int>& nums) { int n = nums.size(); for(int i = 1; i < n; i++) { int temp = nums[i]; int j = i-1; for( ; j >= 0; j--) { if(nums[j] > temp) nums[j+1] = nums[j]; else break; } nums[j+1] = temp; } return nums; } }; */ /* //希尔(shell)排序 //多轮插入排序，使序列逐步有序化 //可以通过所有测试例子 class Solution { public: vector<int> sortArray(vector<int>& nums) { int n = nums.size(); int d = n / 2; for(int d = n / 2; d >= 1; d /= 2 ) { for(int i = 0; i < d; i++) { for(int j = i + d; j < n; j += d) { int temp = nums[j]; int k = j - d; for(; k >= 0; k -= d) { if(nums[k] > temp) nums[k + d] = nums[k]; else break; } nums[k + d] = temp; } } } return nums; } }; */ /* //冒泡排序和快速排序都属于交换排序 //冒泡排序，o(n^2)，超时 //把小数不断地往数组前端换，或者把大数不断地往数组末端换 //如果某一轮没有发生任何交换，说明排好了 class Solution { public: void swap(int & x, int & y) { int temp = x; x = y; y = temp; } vector<int> sortArray(vector<int>& nums) { int n = nums.size(); for(int i = 0; i < n; i++) { bool flag = true; for(int j = n - 1; j > i; j--) { if(nums[j] < nums[j - 1]) { swap(nums[j], nums[j - 1]); flag = false; } } if(flag) break; } return nums; } }; */ /* //快速排序，o(nlogn) //每次随机选一个数，把比它大的数放右边，比它小的数放左边，然后对左右两边重复执行即可 class Solution { public: int partition(vector<int>& nums, int left, int right, int mid) { int temp = nums[mid]; nums[mid] = nums[left]; while(left < right) { while(left < right && nums[right] >= temp) right--; nums[left] = nums[right]; while(left < right && nums[left] <= temp) left++; nums[right] = nums[left]; } nums[right] = temp; return left; } void quick_sort(vector<int>& nums, int left, int right) { if(left < right) { int mid = left + rand() % (right - left + 1); mid = partition(nums, left, right, mid); quick_sort(nums, left, mid - 1); quick_sort(nums, mid + 1, right); } } vector<int> sortArray(vector<int>& nums) { int n = nums.size(); quick_sort(nums, 0, n-1); return nums; } }; */ /* //简单选择排序，每次从未排序部分选出一个最小的，放在数组左端；或每次从未排序部分选出一个最大的，放在数组右端 //简单选择排序不存在最好，或者最坏情况，时间复杂度总是o(n^2) class Solution { public: void swap(int & x, int & y) { int temp = x; x = y; y = temp; } vector<int> sortArray(vector<int>& nums) { for(int i = 0; i < nums.size(); i++) { int min = i; for(int j = i + 1; j < nums.size(); j++) if(nums[j] < nums[min]) min = j; if(min > i) swap(nums[i], nums[min]); } return nums; } }; */ /* //堆排序，o(nlogn) //先建大根堆，然后把根和尾部元素互换，然后重建堆 class Solution { public: void build_heap(vector<int>& nums) { int n = nums.size(); for(int i = n / 2 - 1; i >= 0; i-- ) { adjust_heap(nums, i, n - 1); } } void adjust_heap(vector<int>& nums, int k, int pos) //将k为根的子树调整为大根堆，pos是最后一个 { int temp = nums[k]; for(int i = k * 2 + 1; i <= pos; i = i * 2 + 1) { if(i + 1 <= pos && nums[i] < nums[i+1]) i++; //这里特别注意，是temp >= nums[i]，而不是nums[k] >= nums[i] //目的是找到第一个节点，其子女均不小于temp if(temp >= nums[i]) break; nums[k] = nums[i]; k = i; } nums[k] = temp; } vector<int> sortArray(vector<int>& nums) { int n = nums.size(); build_heap(nums); for(int i = n - 1; i > 0; i--) { swap(nums[i], nums[0]); adjust_heap(nums, 0, i-1); } return nums; } }; */ //归并排序，先将所有的数两两分组，再不断地执行合并两个升序数组的操作即可 //时间复杂度o(nlogn)，空间需要一个额外的与nums等长的数组 class Solution { public: void merge(vector<int>& nums, vector<int>& temp, int left, int right, int mid) //把两个已经排好序的合并，mid是左序列的尾 { for(int i = left; i <= right; i++) temp[i] = nums[i]; int i = left; int j = mid + 1; int k = left; while(i <= mid && j <= right) { if(temp[i] <= temp[j]) nums[k] = temp[i++]; else nums[k] = temp[j++]; k++; } while(i <= mid) nums[k++] = temp[i++]; while(j <= right) nums[k++] = temp[j++]; } void merge_sort(vector<int>& nums, vector<int> & temp, int left, int right) { if(right > left) { int mid = (left + right) / 2; merge_sort(nums, temp, left, mid); merge_sort(nums, temp, mid + 1, right); merge(nums, temp, left, right, mid); } } //二路归并 vector<int> sortArray(vector<int>& nums) { int n = nums.size(); vector<int> temp(n, 0); merge_sort(nums, temp, 0, n-1); return nums; } };
字符串按顺序包含
参考
把字符串 s 看作是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串，所以 s 看起来是这样的："…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…".
现在我们有了另一个字符串 p 。你需要的是找出 s 中有多少个唯一的 p 的非空子串，尤其是当你的输入是字符串 p ，你需要输出字符串 s 中 p 的不同的非空子串的数目。
注意: p 仅由小写的英文字母组成，p 的大小可能超过 10000。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution { public: bool isContinous(char prev, char curr) { if (prev == 'z') return curr == 'a'; return prev + 1 == curr; } int findSubstringInWraproundString(string p) { vector<int> dp(26, 0); int N = p.size(); int k = 0; for (int i = 0; i < N; ++i) { if (i > 0 && isContinous(p[i - 1], p[i])) { ++k; } else { k = 1; } dp[p[i] - 'a'] = max(dp[p[i] - 'a'], k); } return accumulate(dp.begin(), dp.end(), 0); } };
给定四坐标点，进行矩形相交面积求取
参考
给你 二维 平面上两个 由直线构成的 矩形，请你计算并返回两个矩形覆盖的总面积。
每个矩形由其 左下 顶点和 右上 顶点坐标表示：
第一个矩形由其左下顶点 (ax1, ay1) 和右上顶点 (ax2, ay2) 定义。
第二个矩形由其左下顶点 (bx1, by1) 和右上顶点 (bx2, by2) 定义。
示例1
输入：ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
输出：45
示例2
输入：ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
输出：16
提示
-104 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 104
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34class Solution { public: int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) { //计算第一个长方形的面积 int area1=(ax2-ax1)*(ay2-ay1); //计算第二个长方形的面积 int area2=(bx2-bx1)*(by2-by1); //计算总的长方形的面积 int allarea=area1+area2; //计算相交的部分形成的长方形的高度width int widthy1=max(ay1,by1); int widthy2=min(ay2,by2); //不相交 if(widthy1>=widthy2){ return allarea; } //计算相交部分的长方形的宽度length int lenthg1=max(ax1,bx1); int lenthg2=min(ax2,bx2); //不相交 if(lenthg1>=lenthg2){ return allarea; } int width=widthy2-widthy1; int length=lenthg2-lenthg1; //计算相交部分的面积 int subarea=width*length; //减去相交部分的面积即为答案 int realarea=allarea-subarea; return realarea; } };
n被k整除直到为0所得过程的最优求取
参考
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29/** * 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: void DFS(TreeNode *node, int deep, int &max_deep) { if (node == nullptr) { return; } max_deep = max(deep, max_deep); DFS(node->left, deep + 1, max_deep); DFS(node->right, deep + 1, max_deep); } int maxDepth(TreeNode* root) { //DFS int deep = 1, max_deep = 0; DFS(root, deep, max_deep); return max_deep; } };
最后
以上就是动人玫瑰最近收集整理的关于计算机转专业笔试题目的全部内容，更多相关计算机转专业笔试题目内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复