-
Notifications
You must be signed in to change notification settings - Fork 1
/
coding.php
374 lines (295 loc) · 7.32 KB
/
coding.php
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
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
<?php
/**
* 1反转函数的实现
* 反转数组
* @param array $arr
* @return array
*/
function reverse($arr)
{
$n = count($arr);
$left = 0;
$right = $n - 1;
while ($left < $right) {
$temp = $arr[$left];
$arr[$left++] = $arr[$right];
$arr[$right--] = $temp;
}
return $arr;
}
//2两个有序int集合是否有相同元素的最优算法
/**
* 寻找两个有序数组里相同的元素
* @param array $arr1
* @param array $arr2
* @return array
*/
function find_common($arr1, $arr2)
{
$common = array();
$i = $j = 0;
$count1 = count($arr1);
$count2 = count($arr2);
while ($i < $count1 && $j < $count2) {
if ($arr1[$i] < $arr2[$j]) {
$i++;
} elseif ($arr1[$i] > $arr2[$j]) {
$j++;
} else {
$common[] = $arr[$i];
$i++;
$j++;
}
}
return array_unique($common);
}
//3将一个数组中的元素随机(打乱)
/**
* 打乱数组
* @param array $arr
* @return array
*/
function custom_shuffle($arr)
{
$n = count($arr);
for ($i = 0; $i < $n; $i++) {
$rand_pos = mt_rand(0, $n);
if ($rand_pos != $i) {
$temp = $arr[$i];
$arr[$i] = $arr[$rand_pos];
$arr[$rand_pos] = $temp;
}
}
return $arr;
}
//4给一个有数字和字母的字符串,让连着的数字和字母对应
function number_alphabet($str)
{
$number = preg_split('/[a-z]+/', $str, -1, PREG_SPLIT_NO_EMPTY);
$alphabet = preg_split('/\d+/', $str, -1, PREG_SPLIT_NO_EMPTY);
$n = count($number);
for ($i = 0; $i < $count; $i++) {
echo $number[$i] . ':' . $alphabet[$i] . '</br>';
}
}
$str = '1a3bb44a2ac';
number_alphabet($str);
//5求n以内的质数(质数的定义:在大于1的自然数中,除了1和它本身意外,无法被其他自然数整除的数)
//思路:
// 1.(质数筛选定理)n不能够被不大于根号n的任何质数整除,则n是一个质数
// 2.除了2的偶数都不是质数
// 代码如下:
/**
* 求n内的质数
* @param int $n
* @return array
*/
function get_prime($n)
{
$prime = array(2);//2为质数
for ($i = 3; $i <= $n; $i += 2) {//偶数不是质数,步长可以加大
$sqrt = intval(sqrt($i));//求根号n
for ($j = 3; $j <= $sqrt; $j += 2) {//i是奇数,当然不能被偶数整除,步长也可以加大。
if ($i % $j == 0) {
break;
}
}
if ($j > $sqrt) {
array_push($prime, $i);
}
}
return $prime;
}
print_r(getPrime(1000));
// 6约瑟夫环问题
// 相关题目:一群猴子排成一圈,按1,2,…,n依次编号。然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数, 再数到第m只,在把它踢出去…,如此不停的进行下去, 直到最后只剩下一只猴子为止,那只猴子就叫做大王。要求编程模拟此过程,输入m、n, 输出最后那个大王的编号。
/**
* 获取大王
* @param int $n
* @param int $m
* @return int
*/
function get_king_mokey($n, $m)
{
$arr = range(1, $n);
$i = 0;
while (count($arr) > 1) {
$i++;
$survice = array_shift($arr);
if ($i % $m != 0) {
array_push($arr, $survice);
}
}
return $arr[0];
}
// 7如何快速寻找一个数组里最小的1000个数
// 思路:假设最前面的1000个数为最小的,算出这1000个数中最大的数,然后和第1001个数比较,如果这最大的数比这第1001个数小的话跳过,如果要比这第1001个数大则将两个数交换位置,并算出新的1000个数里面的最大数,再和下一个数比较,以此类推。
// 代码如下:
//寻找最小的k个数
//题目描述
//输入n个整数,输出其中最小的k个。
/**
* 获取最小的k个数
* @param array $arr
* @param int $k [description]
* @return array
*/
function get_min_array($arr, $k)
{
$n = count($arr);
$min_array = array();
for ($i = 0; $i < $n; $i++) {
if ($i < $k) {
$min_array[$i] = $arr[$i];
} else {
if ($i == $k) {
$max_pos = get_max_pos($min_array);
$max = $min_array[$max_pos];
}
if ($arr[$i] < $max) {
$min_array[$max_pos] = $arr[$i];
$max_pos = get_max_pos($min_array);
$max = $min_array[$max_pos];
}
}
}
return $min_array;
}
/**
* 获取最大的位置
* @param array $arr
* @return array
*/
function get_max_pos($arr)
{
$pos = 0;
for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] > $arr[$pos]) {
$pos = $i;
}
}
return $pos;
}
$array = [1, 100, 20, 22, 33, 44, 55, 66, 23, 79, 18, 20, 11, 9, 129, 399, 145, 2469, 58];
$min_array = get_min_array($array, 10);
print_r($min_array);
// 8.如何在有序的数组中找到一个数的位置(二分查找)
/**
* 二分查找
* @param array $array 数组
* @param int $n 数组数量
* @param int $value 要寻找的值
* @return int
*/
function binary_search($array, $n, $value)
{
$left = 0;
$right = $n - 1;
while ($left <= $right) {
$mid = intval(($left + $right) / 2);
if ($value > $mid) {
$right = $mid + 1;
} elseif ($value < $mid) {
$left = $mid - 1;
} else {
return $mid;
}
}
return -1;
}
// 9.给定一个有序整数序列,找出绝对值最小的元素
// 思路:二分查找
/**
* 获取绝对值最小的元素
* @param array $arr
* @return int
*/
function get_min_abs_value($arr)
{
//如果符号相同,直接返回
if (is_same_sign($arr[0], $arr[$n - 1])) {
return $arr[0] >= 0 ? $arr[0] : $arr[$n - 1];
}
//二分查找
$n = count($arr);
$left = 0;
$right = $n - 1;
while ($left <= $right) {
if ($left + 1 === $right) {
return abs($arr[$left]) < abs($arr[$right]) ? $arr[$left] : $arr[$right];
}
$mid = intval(($left + $right) / 2);
if ($arr[$mid] < 0) {
$left = $mid + 1;
} else {
$right = $mid - 1;
}
}
}
/**
* 判断符号是否相同
* @param int $a
* @param int $b
* @return boolean
*/
function is_same_sign($a, $b)
{
if ($a * $b > 0) {
return true;
} else {
return false;
}
}
// 10.找出有序数组中随机3个数和为0的所有情况
// 思路:动态规划
function three_sum($arr)
{
$n = count($arr);
$return = array();
for ($i=0; $i < $n; $i++) {
$left = $i + 1;
$right = $n - 1;
while ($left <= $right) {
$sum = $arr[$i] + $arr[$left] + $arr[$right];
if ($sum < 0) {
$left++;
} elseif ($sum > 0) {
$right--;
} else {
$numbers = $arr[$i] . ',' . $arr[$left] . ',' . $arr[$right];
if (!in_array($numbers, $return)) {
$return[] = $numbers;
}
$left++;
$right--;
}
}
}
return $return;
}
$arr = [-10, -9, -8, -4, -2, 0, 1, 2, 3, 4, 5, 6, 9];
var_dump(three_sum($arr));
// 11编写一个PHP函数,求任意n个正负整数里面最大的连续和,要求算法时间复杂度尽可能低。
// 思路:动态规划
/**
* 获取最大的连续和
* @param array $arr
* @return int
*/
function max_sum_array($arr)
{
$currSum = 0;
$maxSum = 0;//数组元素全为负的情况,返回最大数
$n = count($arr);
for ($i = 0; $i < $n; $i++) {
if ($currSum >= 0) {
$currSum += $arr[$i];
} else {
$currSum = $arr[$i];
}
}
if ($currSum > $maxSum) {
$maxSum = $currSum;
}
return $maxSum;
}