欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

小试牛刀-算法题

程序员文章站 2024-02-23 14:11:10
...
<?php
/**
 *题目1:
给定一组数字,一组有9个数字,将这9个数字填写到3*3的九宫格内; 使得横,竖,斜对角条线一上的三个数字之和相等; 如果无解则打印无解;

算法解释:
根据口诀:如下将9宫格视为一个二维数组,按照“一居上行正*,依次斜填切莫忘;上出框时向下放,右出框时向左放;排重便在下格填,右上排重一个样。”先将9个数字依次填入格中,然后查看是否满足横、竖、斜一条线之和相等。满足就输出,不满足则误解。
$res[0][0] $res[0][1] $res[0][2]
$res[1][0] $res[1][1] $res[1][2]
$res[2][0] $res[2][1] $res[2][2]
 */
//例
$a=array(1,2,3,9,4,5,6,7,9);
var_dump(sudoku($a));
//九宫格数独函数
function sudoku($num){
    if(!is_array($num)){
        return '请传入正确参数';
    }
    sort($num);//先把数组按从小到大排序
    $x=0;$y=1;//把九宫格视为一个数组
    $res[$x][$y]=$num[0];//一居上行正*
    for ($i=1;$i<9;$i++){
        $newx=$x-1;
        $newy=$y+1;//依次斜填切莫忘
        if($newx<0){//上出框时向下放
            $newx=2;
        }
        if($newy>2){//右出框时向左放
            $newy=0;
        }
        // echo $x.'-'.$y;echo '<br>';
        if(!empty($res[$newx][$newy])){//排重便在下格填,右上排重一个样
            $newx=$x+1;
            $newy=$y;
        }
        $res[$newx][$newy]=$num[$i];
        $x=$newx;
        $y=$newy;
        // echo '<pre>';var_dump($res);

    }
    // echo '<pre>';var_dump($res);exit;
    //计算九宫格中每一行,列,斜对角线上的值
    $row1=$res[0][0]+$res[0][1]+$res[0][2];
    $row2=$res[1][0]+$res[1][1]+$res[1][2];
    $row3=$res[2][0]+$res[2][1]+$res[2][2];
    $col1=$res[0][0]+$res[1][0]+$res[2][0];
    $col2=$res[0][1]+$res[1][1]+$res[2][1];
    $col3=$res[0][2]+$res[1][2]+$res[2][2];
    $dig1=$res[0][0]+$res[1][1]+$res[2][2];
    $dig2=$res[2][0]+$res[1][1]+$res[0][2];
    //比较横竖斜方向上的的值是否相等
    if($row1==$row2 && $row1==$row3&& $row1==$col1&&$row1==$col2&&$row1==$col3&&$row1==$dig1&&$row1==$dig2){
        return $res;
    }else{
        return '无解';
    }

}

/*题目2:
给定形如下面的矩阵,
111111
110001
100010
110111
010100
111111
上面矩阵的中的1代表海岸线,0代表小岛。求第二大小岛的面积(即被1中包围的0的
个数,如果只有一个小岛,输出最大小岛的面积)
注意
1.仅求这样的0,该0所在行中被两个1包围,该0所在列中被两个1包围;
2.输入矩阵中包含的小岛K >= 1;
样例输入:
111111
110001
100010
110111
010100
111111
样例输出:
8
解题思路:
根据定义对于矩阵中的 0 是否属于内陆,取决于该 0 所处的行和列上,
如果 0 满足,如下条件则 O 为内陆,否则不是。
 0 所在的行,0 的左边和右边必须有 1
 0 所在的列,0 的上面和下面必须有 1
所以遍历所有的行和列,记录改行或列,最左面和最右面(或者最上面和
最下面)1 的坐标,然后当遇到 0,判断是否处于记录的值的中间,是,则是内陆,递归将相邻的0标记,
最后计算每个被标记的小岛面积,输入第二大岛,若无则输出最大。
*/
//例:
    $matrix=array(
        array(1,1,1,1,1,1),
        array(1,1,0,0,0,1),
        array(1,0,1,0,1,0),
        array(1,1,0,1,1,1),
        array(0,1,0,1,0,0),
        array(1,1,1,1,1,1)
    );
    echo index($matrix);
function index($matrix=array())
{
    if(!is_array($matrix)){
        return '参数错误';
    }
    $rowNum=count($matrix);
    $colNum=count($matrix[0]);
    foreach ($matrix as $rk => $rv) {
        //每行最左边1row[$rk][0]
        $row[$rk][0]=array_search(1,$rv);
        krsort($rv);
        //每行最右边1row[$rk][1]
        $row[$rk][1]=array_search(1,$rv);
        foreach ($rv as $ck => $cv) {
            //每列最下边1col[i][1]
            if($cv==1){
               $col[$ck][1]=$rk;
            }
            //每列最上边1col[i][0]
            if($cv==1 && !isset($col[$ck][0])){
                $col[$ck][0]=$rk;
            }
            ksort($col[$ck]);
        }
        ksort($col);
    }
    // echo '<pre>';var_dump($row);exit;
    // echo '<pre>';var_dump($col);exit;
    //寻找小岛
    $flag=2;
    // $area=1;
    for ($i=0; $i <$rowNum ; $i++) {
        for ($j=0; $j <$colNum ; $j++) {
            if($matrix[$i][$j]==0){
                //如果该点左边,右边,上边,下边有1,则判断该点为岛
                if($j>$row[$i][0] && $j<$row[$i][1] && $i>$col[$j][0] && $i<$col[$j][1]){
                    $matrix=tuse($matrix,$i,$j,$flag);//进入该点,递归,将该点的连通区域都标记为$flag
                    $flag++;
                }
            }
        }
    }
    // echo $area;
    // echo '<pre>';var_dump($matrix);exit;
    foreach ($matrix as $rk => $rv) {
        foreach ($rv as $ck => $cv) {
           $numMatrix[$rk.$ck]=$cv;
        }
    }
    $result=array_count_values($numMatrix);
    unset($result['0']);
    unset($result['1']);
    rsort($result);
    //如果有第二大小岛,则输出area2的面积否则,输出最大小岛的面积area1
    if(count($result)>=2){
        return $result[1];
    }else{
        return $result[0];
    }
}
//采用递归将数组连通区域的标号k
function tuse(&$matrix,$rk,$ck,$area)
{
    //判断为小岛的点赋值为2,并进入该点上下左右的点,递归的进行扩展,将连通在一起的点,都赋值为k
    $matrix[$rk][$ck]=$area;
    //左边
    if($matrix[$rk][$ck-1]==0){
        tuse($matrix,$rk,$ck-1,$area);
    }
    //右边
    if($matrix[$rk][$ck+1]==0){
        tuse($matrix,$rk,$ck+1,$area);
    }
    //上面
    if($matrix[$rk-1][$ck]==0){
        tuse($matrix,$rk-1,$ck,$area);
    }
    //下面
    if($matrix[$rk+1][$ck]==0){
        tuse($matrix,$rk+1,$ck,$area);
    }
    // echo '<pre>';var_dump($matrix);
    return $matrix;
}



/*题目3:
设计- 一个股票模拟交易系统。假设我们有一一个很牛叉的AI系统,已经预测到未来一段时间内给定股票的价格,以数组来表示,它的第i个元素是一支给定的股票在第i天的价格。
假设:
1.如果你最多只允许完成两次交易(一次交易是指: 买入和卖出);
2.你有本金K单位(K>=1),一单位本金可以购买1股票; 这意味着你寻找的是K单位本金条件下最大利润。

提示: K=1的时候最简单,可以先考虑。
设计一个算法来找出最大利润。

解体思路:
对数组进行遍历,求出某点之前的最大利益和某点之后的最大利益,当二者和最大时即为利润最大。
 */
//例:
 $test=array(1,2,3,5,6,1,7,0);
 echo maxProfit($test);
function maxProfit($prices=array())
{
    $len=count($prices);
    if($len==0){
        return 0;
    }
    $pre=array();
    $post=array();
    $minPrice=$prices[0];
    //计算第i点之前的最大利润pre
    for ($i=1;$i<$len;$i++){
        $minPrice=min($minPrice,$prices[$i]);
        $pre[$i]=max($pre[$i-1],$prices[$i]-$minPrice);
    }
    //计算第i点之后的最大利润post
    $maxPrice=$prices[$len-1];
    for ($i=$len-2;$i>=0;$i--){
        $maxPrice=max($maxPrice,$prices[$i]);
        $post[$i]=max($post[$i+1],$maxPrice-$prices[$i]);
    }
    $maxProfit=0;
    //计算第i点的,pre[i]与post[i]之和的最大值,赋值给maxProfit
    for ($i=0;$i<$len;$i++){
        $maxProfit=max($maxProfit,$pre[$i]+$post[$i]);
    }
    return $maxProfit;
}

?>

相关标签: 算法 php面试