數(shù)據(jù)結(jié)構(gòu)是算法的基石，如果沒(méi)有扎實(shí)的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，要想把算法學(xué)好甚至融會(huì)貫通是非常困難的，而優(yōu)秀的算法又往往取決于你采用哪種數(shù)據(jù)結(jié)構(gòu)
數(shù)組、字符串(Array & String)
字符串轉(zhuǎn)化
數(shù)組和字符串是最基本的數(shù)據(jù)結(jié)構(gòu)，在很多編程語(yǔ)言中都有著非常相似的性質(zhì)，圍繞著這兩者的算法面試題是最多的
很多時(shí)候，在分析字符串相關(guān)面試題的過(guò)程中，我們往往要針對(duì)字符串中的每一個(gè)字符進(jìn)行分析和處理，甚至有時(shí)候我們得先把給定的字符串轉(zhuǎn)換成字符數(shù)組后再進(jìn)行分析和處理
舉例：翻轉(zhuǎn)字符串 "algorithm"
注意：字符串中的字符是不允許被修改的，我們只能將原字符串轉(zhuǎn)換成字符數(shù)組針對(duì)每一個(gè)字符進(jìn)行分析和處理
解法：
<?php
/**
* 在這里我們不使用 php built in function 處理，在 php 中有一個(gè)built in function strRev 一行代碼即可實(shí)現(xiàn)翻轉(zhuǎn)字符串，
* 但是在面試的時(shí)候這肯定是面試官不愿意看到結(jié)果，面試在一定程度上考察的是我們處理問(wèn)題的思維邏輯。如果要是在實(shí)際開(kāi)發(fā)中我們可以使用 php built in function
*
* 另外需要注意的是，要想實(shí)現(xiàn)字符串翻轉(zhuǎn)我們?cè)谶@里需要將給定的字符串轉(zhuǎn)換成字符數(shù)組，然后再分析處理。在 php 中的字符串可以直接作為數(shù)組處理，比如代碼：
* echo $str[4]; 輸出結(jié)果為 r，則代表的是該字符串的第四個(gè)字符為 r
*/
// 待測(cè)試字符串
$str = 'algorithm';
function str_rev($str) {
// 結(jié)合 for 循環(huán)，將第二個(gè)條件置為 true，模擬死循環(huán)，計(jì)算字符串的長(zhǎng)度
for($i = 0;true;$i++) {
if(!isset($str[$i])) {
break;
}
}
// 通過(guò)上面 for 循環(huán)計(jì)算出字符串長(zhǎng)度，下面我們根據(jù)使用下標(biāo)獲取字符數(shù)組元素，將字符串從末尾開(kāi)始循環(huán)進(jìn)行字符串拼接
$newStr = '';
for($j = $i - 1;$j >= 0;$j--) {
$newStr .= $str[$j];
}
return $newStr;
}
// 輸出
var_dump(str_rev($str));
數(shù)組的優(yōu)缺點(diǎn)
掌握一種數(shù)據(jù)結(jié)構(gòu)，就必須要了解這種數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn)，這樣我們才能根據(jù)其特性選擇適合我們算法的數(shù)據(jù)結(jié)構(gòu)，數(shù)組的優(yōu)點(diǎn)：
- 數(shù)組支持隨機(jī)訪問(wèn)，可根據(jù)數(shù)組下標(biāo)在時(shí)間復(fù)雜度為 O(1) 的情況下訪問(wèn)數(shù)組元素
而數(shù)組的缺點(diǎn)在于：
- 數(shù)組在分配內(nèi)存空間前需要預(yù)估下要存儲(chǔ)數(shù)據(jù)元素的大小，如果分配內(nèi)存空間不夠需要手動(dòng)擴(kuò)容，這在一定程度上會(huì)耗費(fèi)資源，使得性能受到一定影響
- 數(shù)組的插入和刪除操作，均需要移動(dòng)元素，這使得其插入和刪除操作的時(shí)間復(fù)雜度為 O(n)
所以我們?cè)谑欠襁x擇數(shù)組作為我們算法的數(shù)據(jù)結(jié)構(gòu)時(shí)，需要考慮到數(shù)組的優(yōu)缺點(diǎn)，比如算法中查詢、插入和刪除哪種操作比較多，根據(jù)數(shù)據(jù)確定知道數(shù)組明顯不擅長(zhǎng)元素插入和刪除
例題分析
給定兩個(gè)字符串 s 和 t，編寫(xiě)一個(gè)函數(shù)來(lái)判斷 t 是否是 s 的字母異位詞
示例 1：
輸入：s = "anagram",t = "nagaram"
輸出：true
示例 2：
輸入：s = "rat",t = "car"
輸出：false
說(shuō)明：你可以假設(shè)字符串只包含小寫(xiě)字母
字母異位詞，也就是兩個(gè)字符串中相同字符的數(shù)量要對(duì)應(yīng)相等。例如，s 等于 "anagram"，t 等于 "nagaram", s 和 t 就互為字母異位詞。因?yàn)樗麄兌及齻€(gè)字符 a,一個(gè)字符 g,一個(gè)字符 m，一個(gè)字符 n ，以及一個(gè)字符 r。而當(dāng) s 為 "rat" ，t 為 "cat" 的時(shí)候，s 和 t 不互為字母異位詞
具體代碼實(shí)現(xiàn)如下：
class Solution {
/**
* @param String $s
* @param String $t
* @return Boolean
*/
function isAnagram($s, $t) {
// 首先互為字母異位詞的兩個(gè)字符串長(zhǎng)度一定相等
// 使用 for 循環(huán)分別計(jì)算兩個(gè)字符串的長(zhǎng)度
// 計(jì)算字符串 s 的長(zhǎng)度
for($i = 0;true;$i ++) {
if(!isset($s[$i])) {
break;
}
}
// 計(jì)算字符串 t 的長(zhǎng)度
for($j = 0;true;$j ++) {
if(!isset($t[$j])) {
break;
}
}
// 判斷兩個(gè)字符串長(zhǎng)度是否相等，如果不相等，這兩個(gè)字符串一定不互為字母異位詞
if($i != $j) {
return false;
}
// 判斷當(dāng)兩個(gè)字符串同時(shí)輸入的都是空字符串時(shí)，則兩個(gè)字符串也互為字母異位詞
if($i == 0 && $j == 0) {
return true;
}
// 定義一個(gè)字符數(shù)組，使用 26 個(gè)小寫(xiě)字母作為數(shù)組的 key,將 每個(gè) key 對(duì)應(yīng)的 value 統(tǒng)一置為 0
$letterArr = array('a'=>0,'b'=>0,'c'=>0,'d'=>0,'e'=>0,'f'=>0,'g'=>0,'h'=>0,'i'=>0,'j'=>0,'k'=>0,'l'=>0,'m'=>0,'n'=>0,'o'=>0,'p'=>0,'q'=>0,'r'=>0,'s'=>0,'t'=>0,'u'=>0,'v'=>0,'w'=>0,'x'=>0,'y'=>0,'z'=>0);
// 計(jì)算字符串 s 中的字符 在字符數(shù)組 letterArr 中出現(xiàn)的個(gè)數(shù)
for($m = 0;$m < $i;$m++){
if(isset($letterArr[$s[$m]])) {
$letterArr[$s[$m]]++;
}else{
$letterArr[$s[$m]] = 1;
}
}
// 計(jì)算字符串 t 中的字符 在字符數(shù)組中 letterArr 出現(xiàn)的個(gè)數(shù)，并將其減 1
for($n = 0;$n < $j;$n++) {
if(!isset($letterArr[$t[$n]]) || $letterArr[$t[$n]] == 0) {
return false;
}
if(isset($letterArr[$t[$n]])) {
$letterArr[$t[$n]]--;
}
}
return true;
}
}
$solution = new Solution();
$s = 'aacc';
$t = 'ccac';
$solution = $solution->isAnagram($s,$t);
echo $solution;
上面代碼是我在 leetcode 提交的具體實(shí)現(xiàn)邏輯，在上述代碼中我未使用 php 內(nèi)置函數(shù)，在計(jì)算字符串長(zhǎng)度時(shí)，使用 for 循環(huán)模擬死循環(huán)，解題思路：
一個(gè)重要前提是假設(shè)輸入的兩個(gè)字符串中的字符都是小寫(xiě)字母，小寫(xiě)字母我們知道一共有 26 個(gè)，因此：
- 創(chuàng)建一個(gè)包含 26 個(gè)小寫(xiě)字母的字符數(shù)組，并將每個(gè)小寫(xiě)字母作為數(shù)組的 key,每個(gè) key 對(duì)應(yīng)的 value 初始化為 0，將出現(xiàn)在字符串 s 中的字符加 1，而將出現(xiàn)在字符串 t 中的字符減 1，最后判斷每個(gè)小寫(xiě)字母對(duì)應(yīng)的值 value 是否都為 0，如果都為 0，則說(shuō)明輸入的兩個(gè)字符串互為字母異位詞
例題分析
翻轉(zhuǎn)字符串：編寫(xiě)一個(gè)函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過(guò)來(lái)。輸入字符串以字符數(shù)組 char[] 的形式給出。
不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組、使用 O(1) 的額外空間解決這一問(wèn)題。
你可以假設(shè)數(shù)組中的所有字符都是 ASCII 碼表中的可打印字符。
示例 1：
輸入：["h","e","l","l","o"]
輸出：["o","l","l","e","h"]
示例 2：
輸入：["H","a","n","n","a","h"]
輸出：["h","a","n","n","a","H"]
具體代碼實(shí)現(xiàn)如下：
class Solution {
/**
* @param String[] $s
* @return NULL
*/
function reverseString(&$s) {
for($i = 0;true;$i++) {
if(!isset($s[$i])) {
break;
}
}
for($n = 0;$n < $i;$n++) {
$temp = $s[$n];
$s[$n] = $s[$i - 1];
$s[$i - 1] = $temp;
$i--;
}
return $s;
}
}
$str = ["h","e","l","l","o"];
$solution = new Solution();
$result = $solution->reverseString($str);
var_dump($result);
解題思路
使用兩個(gè)指針，一個(gè)指針指向字符數(shù)組的第一個(gè)字符，一個(gè)指向字符數(shù)組的最后一個(gè)字符，然后相互交換。交換之后，兩個(gè)指針向中央一步步地靠攏，直到兩個(gè)指針相遇。這是一種比較快速和直觀的方法
例題分析
替換空格：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，把字符串 s 中的空格替換成 "%20"
示例 1：
輸入：s = "We are happy."
輸出："We%20are%20happy."
這道題目是劍指offer上面的一道原題，在力扣上這道題目的難度等級(jí)是簡(jiǎn)單，我們來(lái)分析下這道題目，如果面試中拿到面試官給我們的題目，我們首先不要著急答題，先和面試官溝通清楚題目的要求，有的面試官可能不會(huì)說(shuō)，讓我們自己主動(dòng)思考，比如上面這道題目。
看到上面這道題目我們應(yīng)該想到有兩種情況存在，一個(gè)是在原有字符串的基礎(chǔ)上直接替換;一個(gè)是創(chuàng)建新字符串，在新字符串上替換。如果是在原始字符串上替換的話，那么需要保證字符串后面有足夠多的空閑內(nèi)存，因?yàn)樽址械目崭癖惶鎿Q后字符串的長(zhǎng)度變長(zhǎng)了，之前處于空格后面的字符需要向后移動(dòng)，如果字符串后面沒(méi)有足夠多的內(nèi)存空間，那么有可能會(huì)出現(xiàn)內(nèi)存覆蓋的問(wèn)題，這些需要向面試官確認(rèn)，我們來(lái)看下這兩情況分別對(duì)應(yīng)的具體實(shí)現(xiàn)：
創(chuàng)建新字符串，在新字符串上替換
class Solution {
/**
* @param String $s
* @return String
*/
function replaceSpace($s) {
// 計(jì)算字符串的長(zhǎng)度
for ($sLength = 0;true;$sLength++) {
if(!isset($s[$sLength])) {
break;
}
}
$S = "";
for ($i = 0;$i < $sLength;$i++) {
if($s[$i] == " ") {
$S .= '%20';
}else{
$S .= $s[$i];
}
}
return $S;
}
}
$str = 'We are happy.';
$solution = new Solution();
$result = $solution->replaceSpace($str);
var_dump($result);
