国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

劍指offer中的算法題(PHP版)

big_cat / 1145人閱讀

摘要：二維數(shù)組中的查找在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。解法有兩種，一種是遞歸法，一種是迭代法但是遞歸法計(jì)算的時(shí)間復(fù)雜度是以的指數(shù)的方式遞增的，如果面試中千萬不要用遞歸法，一定要用迭代法。

二維數(shù)組中的查找 
在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
function search($target, $array)
{
    $i = count($array[0]) - 1;
    $j = 0;

    if ($array[count($array) - 1][$i] < $target || $array[0][0] > $target) {
        return false;
    }

    for ($i; $i >= 0; $i--) {
        if ($array[$j][$i] <= $target) {
            for ($j; $j < count($array); $j++) {
                if ($array[$j][$i] == $target) {
                    return true;
                } else if ($array[$j][$i] > $target) {
                    break;
                }
            }
        }
    }

    return false;
}


$s = [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]];
var_dump(search(1, $s));
替換空格 
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。
function replace($str) {
    $len = strlen($str);
    if ($len <= 0 ) {
        return false;
    }
    $blank = 0;
    for ($i = 0; $i < $len; $i++) {
        if ($str[$i] == " ") {
            $blank++;
        }
    }
    if ($blank == 0) {
        return false;
    }

    $new_length = ($len + $blank * 2) - 1;

    for ($i = $len-1; $i >=0; $i--) {
        if ($str[$i] == " ") {
            $str[$new_length--] = "0";
            $str[$new_length--] = "2";
            $str[$new_length--] = "%";
        } else {
            $str[$new_length--] = $str[$i];
        }
    }

    return $str;
}


var_dump(replace("We Are Happy"));
斐波那契數(shù)列 
大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)。解法有兩種，一種是遞歸法，一種是迭代法,但是遞歸法計(jì)算的時(shí)間復(fù)雜度是以n的指數(shù)的方式遞增的，如果面試中千萬不要用遞歸法，一定要用迭代法。

遞歸法

function a($n) {
    if ($n == 0) {
        return 0;
    } else if ($n == 1) {
        return 1;
    }

    return a($n-1) + a($n - 2);
}


echo a(10);

迭代法

function a($n) {

    $ret = array();

    for ($i=0; $i <= $n; $i++) {
        if ($i == 0) {
            $ret[$i] = 0;
            continue;
        }else if ($i == 1) {
            $ret[$i] = 1;
            continue;
        }

        $ret[$i] = $ret[$i-1] + $ret[$i-2];
    }

    return $ret[$n];
}

echo a(10);
調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面 
輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于位于數(shù)組的后半部分
function test($array) {

    if (count($array) < 2) {
        return false;
    }

    $start = 0;
    $end = count($array) - 1;

    while ($start < $end) {
        while ($array[$end] % 2 == 0 && $start < $end) {
            $end--;
        }

        while ($array[$start] % 2 == 1 && $start < $end) {
            $start++;
        }

        if ($array[$start] % 2 == 0 && $array[$end] % 2 == 1) {
            $temp = $array[$end];
            $array[$end] = $array[$start];
            $array[$start] = $temp;
        }
    }

    return $array;
}
順時(shí)針打印矩陣 
輸入一個(gè)矩陣，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字

這個(gè)是書上的方法

function printMatrixMain($data) {
    $start = 0;
    $columns = count($data);
    $rows = count($data[0]);

    while ($columns > $start * 2 && $rows > $start * 2) {
        printMatrix($data, $columns, $rows, $start);
        ++$start;
    }
}


function printMatrix($data, $columns, $rows, $start)
{
    $endx     = $columns - 1 - $start;
    $endy     = $rows - 1 - $start;

    for ($i = $start; $i <= $endx; $i++) {
        echo $data[$start][$i], "/";
    }

    for ($i = $start + 1; $i <= $endy; $i++) {
        echo $data[$i][$endx], "/";
    }

    for ($i = $endx - 1; $i >= $start; $i--) {
        echo $data[$endy][$i], "/";
    }

    for ($i = $endy - 1; $i > $start; $i--) {
        echo $data[$i][$start], "/";
    }
}


$s = array(
    array(1, 2, 3, 4, 5),
    array(5, 6, 7, 8, 9),
    array(9, 10, 11, 12, 13),
    array(13, 14, 15, 16, 17),
    array(1, 2, 3, 4, 5),
);

printMatrixMain($s);

這個(gè)是我自己寫的方法

function printMatrix($data)
{
    $start    = 0;
    $num      = 0;
    $can_loop = true;
    $endx     = count($data[0]) - 1;
    $endy     = count($data) - 1;

    while ($can_loop) {
        if (($endx - $num - $start < 2) || ($endy - $num - $start) < 2) {
            $can_loop = false;
        }

        for ($i = $start; $i <= $endx - $num; $i++) {
            echo $data[$start][$i], "/";
        }

        for ($i = $start + 1; $i <= $endy - $num; $i++) {
            echo $data[$i][$endx - $num], "/";
        }

        for ($i = $endx - $num - 1; $i >= $start; $i--) {
            echo $data[$endy - $num][$i], "/";
        }

        for ($i = $endy - $num - 1; $i > $start; $i--) {
            echo $data[$i][$start], "/";
        }

        $start++;
        $num++;
    }
}


$s = array(
    array(1, 2, 3, 4, 5),
    array(5, 6, 7, 8, 9),
    array(9, 10, 11, 12, 13),
    array(13, 14, 15, 16, 17),
    array(1, 2, 3, 4, 5),
);

printMatrix($s);
二叉搜索樹的后序遍歷序列 
輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出true,否則輸出false.
function VerifySquenceOfBST($data) {
    if(empty($data)){
        return false;
    }
    
    $length = count($data);
    $root   = $data[$length - 1];

    for($i = 0; $i<$length-1; $i++) {
        if($data[$i] > $root) {
            break;
        }
    }

    $j = $i;

    for($j; $j < $length -1; $j++) {
        if ($data[$j] < $root) {
            return false;
        }
    }

    $left = true;
    $right = true;

    if($i > 0) {
        $left = VerifySquenceOfBST(array_slice($data, 0, $i));
    }

    if($j < $length - 1) {
        $right = VerifySquenceOfBST(array_slice($data, $i, $length-1-$i));
    }

    return ($left&&$right);
}

var_dump(VerifySquenceOfBST([5,7,6,9,11,10,8]));
字符串的排列 
輸入一個(gè)字符串，打印出所有字符串的組合，例如：abc 會(huì)打印出abc,acb bac bca cab cba
function Permutation($str) {
    if ($str == NULL)
        return false;
    if (!is_string($str))
        return false;
    echo_child($str, 0);             /*書上用指針，這里我們用下標(biāo)*/
}

function echo_child($str, $index) {
    $len = strlen($str);
    if ($len == ($index + 1)) {
        echo $str . "    ";
        return false;
    } else {
        for ($i = $index; $i < $len; $i++) {
            $new_str         = $str;
            $tmp             = $new_str[$index];
            $new_str[$index] = $new_str[$i];
            $new_str[$i]     = $tmp;              /*以上是和第一個(gè)字符交換*/
            echo_child($new_str, $index + 1);  /*運(yùn)用遞歸不斷對(duì)余下的部分進(jìn)行交換*/
        }
    }
}

Permutation("abc");
數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字 
數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請(qǐng)找出這個(gè)數(shù)字。例如輸入一個(gè)長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半，因此輸出2。如果不存在則輸出0。
function MoreThanHalfNum_Solution($data)
{
   if (empty($data)) {
        return false;
    }

    $ret = array();

    foreach ($data as $key => $val) {
        if (empty($ret)) {
            $ret["value"] = $val;
            $ret["count"] = 1;
        } else {
            if ($val == $ret["value"]) {
                $ret["count"]++;
            } else {
                if (--$ret["count"] == 0) {
                    $ret["value"] = $val;
                    $ret["count"] = 1;
                }
            }
        }
    }

    if (checkMoreThanHalf($data, $ret["value"])) {
        return $ret["value"];
    } else {
        return 0;
    }
}

function checkMoreThanHalf($data, $number) {
    $time = 0;

    foreach ($data as $key => $val) {
        if ($val == $number) {
            $time++;
        }
    }

    if ($time * 2 > count($data)) {
        return true;
    } else {
        return false;
    }
}
連續(xù)子數(shù)組的最大和 
輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中一個(gè)或連續(xù)的多個(gè)整數(shù)組成一個(gè)子數(shù)組。求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)。
function FindGreatestSumOfSubArray($data)
{
    if (empty($data)) {
        return false;
    }

    $ret = 0;
    $max = $data[0];

    for ($i = 0; $i < count($data); $i++) {
        $ret = $ret + $data[$i];

        if ($ret > $max) {
            $max = $ret;
        }

        if ($ret < 0) {
            $ret = 0;
        }
    }

    return $max;
}
整數(shù)中1出現(xiàn)的次數(shù)（從1到n整數(shù)中1出現(xiàn)的次數(shù)） 
例如輸入12，從1到12這些整數(shù)中包含1的數(shù)字有1，10，11和12，1一共出現(xiàn)了5次
function NumberOf1Between1AndN_Solution($str)
{
    settype($str, "string");

    if ($str == 0 || strlen($str) == 0) {
        return 0;
    }

    $first = $str[0];

    if (strlen($str) == 1 && $first > 0) {
        return 1;
    }

    if ($first > 1) {
        $numFirstDigit = powerBase10(strlen($str) - 1);
    } else {
        $numFirstDigit = substr($str, 1) + 1;
    }

    $numOtherDigits = $first * (strlen($str)-1) * powerBase10(strlen($str)-2);
    $numRecursive = NumberOf1Between1AndN_Solution(substr($str, 1));

    return $numFirstDigit + $numOtherDigits + $numRecursive;
}

function powerBase10($number) {
    return pow(10, $number);
}
數(shù)組中只出現(xiàn)一次的數(shù)字 
一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。
function FindNumsAppearOnce($array) {
    if (empty($array)) {
        return false;
    }

    $xor = 0;
    foreach ($array as $key => $val) {
        $xor ^= $val;
    }

    $indexOf1 = findFirstBit1($xor);

    $result = array(0,0);
    foreach ($array as $key => $value) {
        if (isBit1($value, $indexOf1)) {
            $result[0] ^= $value;
        } else {
            $result[1] ^= $value;
        }
    }

    return $result;
}


function findFirstBit1($num) {
    $index = 0;

    while (($num & 1) == 0) {
        $num >>= 1;
        $index++;
    }

    return $index;
}

function isBit1($num, $indexBit) {
    $num >>= $indexBit;

    return (($num & 1) === 1);
}

$ret = FindNumsAppearOnce(array(2, 4, 3, 6, 3, 2,5,5));
echo $ret[0],$ret[1];
和為S的兩個(gè)數(shù)字 
輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字S，在數(shù)組中查找兩個(gè)數(shù)，使得他們的和正好是S，如果有多對(duì)數(shù)字的和等于S，輸出任意一對(duì)即可。
function FindNumbersWithSum($array, $sum) {
    if (empty($array)) {
        return false;
    }

    $start = 0;
    $end   = count($array) - 1;

    while ($start < $end) {
        if ($array[$start] + $array[$end] < $sum) {
            ++$start;
        } else if ($array[$start] + $array[$end] > $sum) {
            --$end;
        } else {
            return $array[$start]."/".$array[$end];
        }
    }

    return false;
}
圓圈中最后剩下的數(shù)字 
0,1,...,n-1這n個(gè)數(shù)字排成一個(gè)圓圈，從數(shù)字0開始每次從這個(gè)圓圈里刪除第m個(gè)數(shù)字，求出這個(gè)圓圈里剩下的最后一個(gè)數(shù)字。
//通過總結(jié)出的公式提供的算法，公式證明過程不展開。
function LastRemaining_Solution($n, $m) {
    if ($n < 1 || $m < 1) {
        return -1;
    }

    $last = 0;

    for($i = 2; $i <= $n; $i++) {
        $last = ($last + $m) % $i;
    }

    return $last;
}



//模擬環(huán)形鏈表，這個(gè)效率和性能都不如前一個(gè)，但是思路簡單
function LastRemaining_Solution2($n, $m) {
    if ($n < 1 || $m < 1) {
        return -1;
    }

    $data = array();
    for ($i=0; $i< $n; $i++) {
        $data[] = $i;
    }

    $p = 0;
    while (count($data) >1 ) {
        for ($i=1; $i<$m; $i++) {
            ++$p;
            $p = isset($data[$p]) ? $p : 0;
        }
        unset($data[$p]);
        $data = array_values($data);
        $p = isset($data[$p]) ? $p : 0;
    }

    return reset($data);
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/22512.html

相關(guān)文章

  • 劍指offer系列——劍指 Offer 06. 從尾到頭打印鏈表（C語言）

    摘要：導(dǎo)航小助手劍指從尾到頭打印鏈表題目詳情解題思路源代碼總結(jié)劍指從尾到頭打印鏈表題目詳情輸入一個(gè)鏈表的頭節(jié)點(diǎn)，從尾到頭反過來返回每個(gè)節(jié)點(diǎn)的值用數(shù)組返回。時(shí)間復(fù)雜度方法先反轉(zhuǎn)鏈表并求長度，在將反轉(zhuǎn)后的鏈表數(shù)據(jù)拷貝至數(shù)組中。 ...

    DevTTL 評(píng)論0 收藏0

  • 劍指offer系列——劍指 Offer 24. 反轉(zhuǎn)鏈表（C語言）

    摘要：假設(shè)反轉(zhuǎn)對(duì)象節(jié)點(diǎn)為，反轉(zhuǎn)指向的結(jié)點(diǎn)為，反轉(zhuǎn)后指向的結(jié)點(diǎn)為首結(jié)點(diǎn)。當(dāng)然也可以根據(jù)棧先進(jìn)后出的特點(diǎn)，使用棧反轉(zhuǎn)鏈表。 ??前面的話?? 大家好！博主開辟了一個(gè)新的專欄—...

    weakish 評(píng)論0 收藏0

  • PHPer也刷《劍指Offer》之鏈表

    摘要：劍指中鏈表相關(guān)題目俗話說光說不練假把式，既然學(xué)習(xí)了鏈表的基礎(chǔ)概念和基本操作那我們一定要找些題目鞏固下，下面來看劍指中的相關(guān)題目。題目分析合并兩個(gè)排序的鏈表，需要分別比較兩個(gè)鏈表的每個(gè)值，然后改變指針。 溫故知新 鏈表由一個(gè)一個(gè)的作為節(jié)點(diǎn)的對(duì)象構(gòu)成的，每一個(gè)節(jié)點(diǎn)都有指向下一個(gè)節(jié)點(diǎn)的指針，最后一個(gè)節(jié)點(diǎn)的指針域指向空。每個(gè)節(jié)點(diǎn)可以存儲(chǔ)任何數(shù)據(jù)類型。 根據(jù)類型可以分為單鏈表、雙鏈表、環(huán)形鏈表、...

    daydream 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<