PHP Interview Questions (4)

面试时间:2018 年 9 月 10 日,周一,上午十点。


1. 求一个矩阵中最大的二维矩阵(元素和最大).如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求: (1)写出代码; (2)分析时间复杂度

$matrix = [
[1, 2, 0, 3, 4],
[2, 3, 4, 5, 1],
[1, 1, 5, 3, 0]
];
$row = 3;
$col = 5;
$maxMatrix = [];
$maxSum = 0;

for ($i = 0; $i < $row - 1; $i++) {
    for ($j = 0; $j < $col - 1; $j++) {
        $sum = $matrix[$i][$j] + $matrix[$i][$j + 1] + $matrix[$i + 1][$j] + $matrix[$i + 1][$j + 1];
        if ($sum > $maxSum) {
            $maxSum = $sum;
            $maxMatrix = [
                [$matrix[$i][$j], $matrix[$i][$j + 1]],
                [$matrix[$i + 1][$j], $matrix[$i + 1][$j + 1]]
            ];
        }
    }
}

O(row*col)

2. 输入 n 个整数,输出其中最大的 k 个。例如输入 1,2,3,4,5,6,7,8 这 8 个数字,则其中最大的 3 个数字为 8,7,6。

$n = 8;
$k = 3;
$arr = [1, 2, 3, 4, 5, 6, 7, 8];

O(N*log2N)
rsort($arr);
for ($i = 0; $i < $k; $i++) {
    echo $arr[$i], "\n";
}

O(N*K)
$maxKeys = [];
for ($i = 0; $i < $k; $i++) {
    $max = 0;
    foreach ($arr as $key => $value) {
        if (!in_array($key, $maxKeys) && $value > $max) {
            $max = $value;
            $maxKey = $key;
        }
    }
    echo $max, "\n";
    $maxKeys[] = $maxKey;
}

3. 输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

<?php
$str = 'abc';
$arr = str_split($str);
$len = strlen($str);

function exchange(&$a, &$b) {
    $temp = $a;
    $a = $b;
    $b = $temp;
}

function permutation($arr, $i, $len) {
    if ($i == $len) {
        return;
    }
    if ($i == $len - 1) {
        echo join('', $arr), "\n";
    }
    for ($j = $i; $j < $len; $j++) {
        exchange($arr[$i], $arr[$j]);
        permutation($arr, $i + 1, $len);
    }
}

permutation($arr, 0, $len);

 448 total views,  1 views today

Leave a Reply

Your email address will not be published. Required fields are marked *