ShockUCCU | Web Design

 Search Insert Position 給一個排序且沒有重複的整數陣列，尋找目標值在陣列哪個位置，如果沒有結果則回傳該整數應該在的位置。 Example 1 Input: nums = [1,3,5,6], target = 5 Output: 2 Example 2 Input: nums = [1,3,5,6], target = 2 Output: 1 Example 3 Input: nums = [1,3,5,6], target = 7 Output: 4 解法 class Solution { /** * @param Integer[] $nums * @param Integer $target * @return Integer */ function searchInsert($nums, $target) { $count = count($nums); $data = 0; for ($i = 0; $i < $count; $i++) { if ($target == $nums[$i]) { $data = $i; break; } if ($target > $nums[$i]) { $data = $i + 1; } } return $data; } }

Remove Duplicates from Sorted Array 把有一排序過的整數陣列，移除重複元素後，計算該陣列有多少唯一值。這題運用的概念是 In-place algorithm 原地演算法或是就地演算法，利用本身的資料結構進行變換的演算法。 Example 1 Input: nums = [1,1,2] Output: 2, nums = [1,2,_] Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the returned k (hence they are underscores). Example 2 Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4,_,_,_,_,_] Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively. It does not matter what you leave beyond the returned k (hence they are underscores). 解法 用 PHP 內建函數 array_unique() 移除陣列中的重複的值。 class Solution { /** * @param Integer[] $nums * @return Integer */ function removeDuplicates(&$nums) { $nums = array_unique($nums); return count($nums); } } 用原地演算法，判斷是否與上個元素是否相同，如果相同則移除該元素。 class Solution { /** ...

 Remove Element 設定一個只有整數的陣列，並移除指定的整數，最後返回該陣列剩幾個元素。 Example 1 Input: nums = [3,2,2,3], val = 3 Output: 2, nums = [2,2,_,_] Example 2 Input: nums = [0,1,2,2,3,0,4,2], val = 2 Output: 5, nums = [0,1,4,0,3,_,_,_] 解法 class Solution { /** * @param Integer[] $nums * @param Integer $val * @return Integer */ function removeElement(&$nums, $val) { $count = count($nums); for ($i = 0; $i < $count; $i++) { if ($nums[$i] === $val) unset($nums[$i]); } return count($nums); } }

Merge Two Sorted Lists 合併兩個已排序的鍊表 Example 1 Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4] Example 2 Input: list1 = [], list2 = [] Output: [] Example 3 Input: list1 = [], list2 = [0] Output: [0] 解法 一開始的想法是取出兩個表的值進行排序，最後再重新產出新的鏈表。 /** * Definition for a singly-linked list. * class ListNode { * public $val = 0; * public $next = null; * function __construct($val = 0, $next = null) { * $this->val = $val; * $this->next = $next; * } * } */ class Solution { /** * @param ListNode $list1 * @param ListNode $list2 * @return ListNode */ function mergeTwoLists($list1, $list2) { $arr_dic = array(); while (true) { # 取出兩陣列的值 if (isset($list1->val)) $arr_dic[] = $list1->val; if (isset($list2->val)) $arr_dic[] = $list2->val; $list1 = $list1->next; $list2 = $list2->next; ...

Valid Parentheses 檢查字串當中，是否包含有效的括號 ()、[]、{}。其有效定義為 括號的頭尾必須是相同類型的括號 括號的頭尾的順序必須正確 Example 1 Input: s = "()" Output: true Example 2 Input: s = "()[]{}" Output: true Example 3 Input: s = "(]" Output: false 解法 可用正規式進行比對，並把匹配的括號移除，反覆執行直到再也找不到對應的括號。但執行效率大多落在60-70ms，明顯不是最佳解。 class Solution { /** * @param String $s * @return Boolean */ function isValid($s) { if ( preg_match('/\(\)/', $s, $matches) || preg_match('/\[\]/', $s, $matches) || preg_match('/\{\}/', $s, $matches) ) { if (preg_match('/\(\)/', $s, $matches)) $s = str_replace('()', '', $s); if (preg_match('/\[\]/', $s, $matches)) $s = str_replace('[]', '', $s); if (preg_match('/\{\}/', $s, $matches)) $s = str_replace('{}', '', $s); if ...

Longest Common Prefix 在一陣列中，找出所有字串共同的字首且長度最長的字首，如果沒有匹配的結果回傳空值。 Example 1 Input: strs = ["flower","flow","flight"] Output: "fl" Example 2 Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings. 解法 先找出陣列中最短的字串，並利用該字串一一去比對，只要符合是共同字首且長度最長的字首變停止比對，反之回傳空值。 class Solution { /** * @param String[] $strs * @return String */ function longestCommonPrefix($strs) { // 找出陣列中長度最小的字串 $min_len = strlen($strs[0]); $now_len = strlen($strs[0]); $min_len_str = $strs[0]; foreach ($strs as $i => $str) { $now_len = strlen($str); if ($min_len > $now_len) { $min_len = $now_len; $min_len_str = $str; } } // 一一比對陣列中的字串 for ($i = $min_len; $i > 0; $i--) { $count = 0; foreach ($strs as $...

Roman to Integer 羅馬數字(Roman Numbers)共有7個 I, V, X, L, C, D, M。 Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 舉例來說羅馬數字的 II 表示 2、12 -> XII、27 -> XXVII。但往右加的數字不會超過三位，因此產生右加左減的計算方式： 在較大的羅馬數字的右邊記上較小的羅馬數字，表示大數字加小數字 在較大的羅馬數字的左邊記上較小的羅馬數字，表示大數字減小數字 IV -> 4 IX -> 9 XL -> 40 XC -> 90 CD -> 400 CM -> 900 Example 1 Input: s = "III" Output: 3 Explanation: III = 3. Example 2 Input: s = "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3. Example 3 Input: s = "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4. 解法 class Solution { /** * @param String $s * @return Integer */ function romanToInt($s) { $arr_list = array( 'I' => 1, 'V' => 5, 'X' => 10, 'L' => 50, 'C' => 100,...

Palindrome Number 給一整數 x ，如果反轉該數字一樣的話，則回傳 true。 Example 1 Input: x = 121 Output: true Explanation: 121 reads as 121 from left to right and from right to left. Example 2 Input: x = -121 Output: false Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome. Example 3 Input: x = 10 Output: false Explanation: Reads 01 from right to left. Therefore it is not a palindrome. 解法 Palindrome 回文，也就是正讀反讀都能讀通，比如 12321 從前面看或後面看都是一樣的數字，但 -123321 的回文是 12321- ，所以負整數無法符合回文的條件。 將原始整數利用除以 10 取出餘數，加總該餘數及位數，直到原始整數不能再除為止。 class Solution { /** * @param Integer $x * @return Boolean */ function isPalindrome($x) { $temp_x = $x; $new_x = 0; while ($temp_x != null) { $d = $temp_x % 10; $new_x = $new_x * 10 + $d; $temp_x = intval($temp_x / 10); } if ($new_x == $x && $new_x >= 0) return true; else return ...

Add Two Numbers 相加兩個非負整數的鏈表，計算加總後的數字。 Example 1 Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807. Example 2 Input: l1 = [0], l2 = [0] Output: [0] Example 3 Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1] 解法 PHP /** * Definition for a singly-linked list. * class ListNode { * public $val = 0; * public $next = null; * function __construct($val = 0, $next = null) { * $this->val = $val; * $this->next = $next; * } * } */ class Solution { /** * @param ListNode $l1 * @param ListNode $l2 * @return ListNode */ function addTwoNumbers($l1, $l2) { $sum = 0; $carry = 0; $arr_sum = []; while ($l1 != '' || $l2 != '') { $sum = $l1->val + $l2->val + $carry; if ($sum >= 10) { $carry = intval($sum / 10); $sum = $sum % 10; } else { $...

Two Sum  給一串整數陣列為 nums 和一個整數 target ，需要回傳兩個加總起來等於 target 的兩個索引值。 輸入的陣列一定只會有一個解，且索引值不能重複使用。 Example 1 Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]. Example 2 Input: nums = [3,2,4], target = 6 Output: [1,2] Example 3 Input: nums = [3,3], target = 6 Output: [0,1] 解法 暴力解法 利用兩層for迴圈進行計算，以 [2, 7, 11, 15] 為例，(2, 7)、(2, 11)、(2, 15)、(7, 11)...以此類推，當加總等於目標值即回傳結果。 function twoSum($nums, $target) { for ($i = 0; $i < count($nums); $i++) { for ($j = $i + 1; $j < count($nums); $j++) { if ($nums[$i] + $nums[$j] == $target) return [$i, $j]; } } } 雜湊解法 將目標值與當前數值相減後比對雜湊表，並把當前的 value-key 存放到雜湊表， 重複此操作直到找到結果。 nums = (11, 7, 2, 15) target = 9 current_key: 0, current_num: 11, remaining: -2 map: {11:0}, return: null current_key: 1, current_num: 7, remaining: 2 map: {11:0, 7:1}, return: null current_key: 2, current_num: 2, remaining: 7 map: {11:0, 7:1}, return: [2, 1] PHP f...