---
tags: 提升程式設計師的面試力
---

# 陣列和字串 1.4~1.9

### 1.4 回文變位數: 你將得到一個字串，請寫一個函式來檢查他是否是一個回文的變位數。回文的意思是單詞或是短語無論向前讀或是向後讀都是一樣的，變位字就是字母的重新排列。回文不局限於字典單詞。

class PalindromePermutationChecker {
    public static function isPalindromePermutation($str) {
        $charCounts = [];
        for ($i=0, $length=strlen($str); $i<$length; $i++) {
            $char = $str[$i];
            // ignore spaces
            if ($char === ' ') {
                continue;
            }
            $char = strtolower($char);
            if (array_key_exists($char, $charCounts)) {
                $charCounts[$char]++;
            } else {
                $charCounts[$char] = 1;
            }
        }
        $oddCount = 0;
        foreach ($charCounts as $char => $count) {
            if ($count % 2 != 0 && ++$oddCount > 1) {
                return false;
            }
        }
        return true;
    }
}

### 一個編輯距離：可以對字串執行的編輯有三種，插入一個字元、刪除一個字元，或是替換一個字元。假設有兩個字串，請寫一個函式檢查他們是否為個或是０個的編輯距離。

class OneAwayChecker {
    public static function isOneOrZeroAway($str1, $str2) {
        $length1 = strlen($str1);
        $length2 = strlen($str2);
        if (abs($length2 - $length1) > 1) {
            return false;
        }
        if ($length1 == $length2) {
            $diffCount = 0;
            for ($i=0; $i<$length1; $i++) {
                if ($str1[$i] !== $str2[$i]) {
                    if (++$diffCount > 1) {
                        return false;
                    }
                }
            }
        } else {
            if ($length1 > $length2) {
                $longer = $str1;
                $shorter = $str2;
                $longerLength = $length1;
                $shorterLength = $length2;
            } else {
                $longer = $str2;
                $shorter = $str1;
                $longerLength = $length2;
                $shorterLength = $length1;
            }
            $diffCount = 0;
            for ($i=0, $j=0; $i<$longerLength && $j<$shorterLength; $i++, $j++) {
                $char1 = $longer[$i];
                $char2 = $shorter[$j];
                if ($char1 === $char2) {
                    continue;
                }
                if (++$diffCount > 1) {
                    return false;
                }
                $i++; // advance the cursor on the longer string an extra step because we found a diff
            }
        }
        return true;
    }
}

### 1.6 字元壓縮：藉由計算重複字元來實作一個執行基本字串的壓縮方法。例如：字串，aabbccccaaa將變成a2b1c5a3。如果『壓縮』字串不會變得比原來的字串更小，那個你的方法應該回傳原來的字串。可以假設字串只有大寫和小寫字母(a-z)。

class StringCompressor {
    public static function compress($original) {
        $originalLength = strlen($original);
        $compressedTokens = [];
        $compressedLength = 0;
        $lastChar = null;
        $sameCharCount = 0;
        for ($i=0; $i<$originalLength; $i++) {
            $char = $original[$i];
            if ($lastChar !== null && $char !== $lastChar) {
                $compressedToken = $lastChar . $sameCharCount;
                $compressedLength += strlen($compressedToken);
                if ($compressedLength >= $originalLength) {
                    return $original;
                }
                $compressedTokens[] = $compressedToken;
                $sameCharCount = 1;
            } else {
                $sameCharCount++;
            }
            $lastChar = $char;
        }
        // if the buffer isn't empty, flush it
        if ($sameCharCount > 0) {
            $compressedToken = $lastChar . $sameCharCount;
            $compressedLength += strlen($compressedToken);
            if ($compressedLength >= $originalLength) {
                return $original;
            }
            $compressedTokens[] = $compressedToken;
        }
        return implode($compressedTokens);
    }
}

### 1.7 旋轉矩陣：給定一個由NxN 矩陣 表示的圖像，其中圖像中的每個像素為四個位元組，請撰寫一個方法將圖像旋轉90度，您能在同一塊記憶體中就地完成嗎？

class MatrixRotator {
    public static function rotate(array &$matrix) {
        // process 1 layer of the matrix at a time
        // starting from the outside and moving inwards
        for ($layer=0, $layers=floor(count($matrix)/2), $begin=0, $end=count($matrix)-1; $layer<$layers; $layer++, $begin++, $end--) {
            for ($i=$begin, $j=$end; $i<$end; $i++, $j--) {
                // perform a 4-way swap of values in the current layer
                $tmp = $matrix[$begin][$i];
                $matrix[$begin][$i] = $matrix[$j][$begin];
                $matrix[$j][$begin] = $matrix[$end][$j];
                $matrix[$end][$j] = $matrix[$i][$end];
                $matrix[$i][$end] = $tmp;
            }
        }
    }
}

### 零矩陣：請撰寫這樣一個演算法，如果MxN矩陣中的一個元素為0Ｍ那麼將該元素所在的整個列和欄都設為０。

class ZeroMatrix {
    public static function zero(array &$matrix) {
        $leftColumnZero = false;
        $rowCount = count($matrix);
        for ($i=0; $i<$rowCount; $i++) {
            for ($j=0, $columnCount=count($matrix[$i]); $j<$columnCount; $j++) {
                if ($matrix[$i][$j] === 0) {
                    // use the topmost cell and the leftmost cells in the
                    // matrix to track whether the entire row/column should
                    // be zeroed, respectively.
                    $matrix[$i][0] = 0;
                    if ($j === 0) {
                        // since we are using cell (0,0) in the matrix
                        // to track whether the top row should be zeroed
                        // let's use a single boolean variable to track
                        // whether the left column should be zeroed.
                        $leftColumnZero = true;
                    } else {
                        $matrix[0][$j] = 0;
                    }
                    break;
                }
            }
        }
        // zero out rows based on zero in the first position
        for ($i=1; $i<$rowCount; $i++) {
            if ($matrix[$i][0] === 0) {
                for ($j=1, $columnCount=count($matrix[$i]); $j<$columnCount; $j++) {
                    $matrix[$i][$j] = 0;
                }
            }
        }
        // zero out columns based on zero in the first position
        for ($j=1, $columnCount=count($matrix[0]); $j<$columnCount; $j++) {
            if ($matrix[0][$j] === 0) {
                for ($i=1; $i<$rowCount; $i++) {
                    $matrix[$i][$j] = 0;
                }
            }
        }
        // zero out the top row if needed
        if ($matrix[0][0] === 0) {
            for ($j=1, $columnCount=count($matrix[0]); $j<$columnCount; $j++) {
                $matrix[0][$j] = 0;
            }
        }
        // zero out the left column if needed
        if ($leftColumnZero) {
            for ($i=0; $i<$rowCount; $i++) {
                $matrix[$i][0] = 0;
            }
        }
    }
}

### 字串旋轉：假設你有一個名為isSubString的方法，他可以檢查一個單詞是否是另外一個單詞的子字串。假設有兩個字串s1跟s2 ，限定只能使用一次的isSubString呼叫，撰寫程式碼以檢查s2是否是s1的旋轉。

class StringRotationChecker {
    public static function isRotation($s1, $s2) {
        if (strlen($s1) != strlen($s2)) {
            return false;
        }
        return self::isSubstring($s1 . $s1, $s2);
    }

    public static function isSubstring($haystack, $needle) {
        if (strpos($haystack, $needle) === false) {
            return false;
        }
        return true;
    }
}