只出现一次的数字（2020-03-18）

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums) {
        $list = array_count_values($nums);
        return array_search(1,$list);
    }

    function singleNumber($nums) {
        $num = $nums[0];
        for ($i = 1, $count = count($nums); $i < $count; $i++) {
            $num ^= $nums[$i];
        }
        return $num;
    }
}

多数元素 （2020-03-18）

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于** ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function majorityElement($nums) {
        $count = array_flip(array_count_values($nums));
        krsort($count);
        foreach($count as $item){
            return $item;
        }
    }
}

搜索二维矩阵 II（2020-03-19）

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例:

现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

func searchMatrix(matrix [][]int, target int) bool {
    m := len(matrix)
    if m == 0 {
        return false
    }
    row,col  := 0 ,len(matrix[0]) - 1
    for  row < m &&  col >= 0 {
        if matrix[row][col] == target{
            return true
        }else if matrix[row][col] > target {
            col --
        }else{
            row ++
        }
    }
    return false
}

合并两个有序数组 （2020-03-19）

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 num1 成为一个有序数组。
说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

func merge(nums1 []int, m int, nums2 []int, n int)  {
   for i:=0;i<n;i++{
        nums1[m+i]=nums2[i]
    }
    sort.Ints(nums1)
}
func merge(nums1 []int, m int, nums2 []int, n int)  {
    tmp := make([]int, m+n)
    i, j, k := 0, 0, 0
    for i < m && j < n {
        if nums1[i] < nums2[j] {
            tmp[k] = nums1[i]
            k++
            i++
        } else {
            tmp[k] = nums2[j]
            k++
            j++
        }
    }
    for i < m {
        tmp[k] = nums1[i]
        k++
        i++
    }
    for j < n {
        tmp[k] = nums2[j]
        k++
        j++
    }
    for k := 0; k < m+n;k++ {
        nums1[k] = tmp[k]
    }
}

验证回文串 (2020-03-19)

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: “A man, a plan, a canal: Panama”
输出: true

示例 2:

输入: “race a car”
输出: false

 function isPalindrome($s) {
     $arr = preg_split('/(\W)/', $s);
     $str = strtolower(implode('', $arr));
     return $str === strrev($str) ? true : false;
}

//或者双指针 GO
func isPalindrome(s string) bool {
    i, j := 0, len(s) - 1
    for i < j {
        if !isValidAlphanumeric(s[i]) {
            i++
            continue
        } 
        if !isValidAlphanumeric(s[j]) {
            j--
            continue
        }
        if s[i] == s[j] || isUpperOrLower(s[i], s[j]) {
            i++
            j--
        }else {
            return false
        }
    }
    return true
}

func isValidAlphanumeric(s byte) bool {
    return (s >= '0' && s <= '9') || (s >= 'a' && s <= 'z') || (s >= 'A' && s <= 'Z')
}

func isUpperOrLower(a, b byte) bool {
    return a - b == 32 || b - a == 32 && !(a >= '0' && a <= '9') && !((b >= '0' && b <= '9'))
}

分割回文串（2020-03-20）

返回 s 所有可能的分割方案。

示例:
输入: “aab”
输出:
[
[“aa”,”b”],
[“a”,”a”,”b”]
]

class Solution {

    /** 
     * @param String $s
     * @return String[][]
     */
    function partition($s) {
        $arr =  $res  = [];
        $len = strlen($s);
        if($len != 0){
             $this->back($s, $arr, $res);
        }
        return $res;
    }


    private function back($str, &$array, &$res)
    {
        $len = strlen($str);
        if($len == 0 ){
            $res[] = $array; 
        }

        for($i = 0 ; $i < $len ; $i++){
            //判断一个子串是否是回文子串
             $tmp = substr($str,0,$i+1);
             if($this->checkPalindrome($tmp,$i)){
                  $array[] = $tmp;
                  $this->back(substr($str,$i+1), $array, $res);
                  array_pop($array);
             }
        }
    }


    private function checkPalindrome($str,$right){
        $left = 0;
        //字符串从左到右匹配
        while ($left < $right){
            if($str[$left] !== $str[$right]){
                return  false;
            } 
            $left ++ ;
            $right --;
        }
        return true;
    }
}

无重复字符的最长子串（2020-03-22）

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s)
    {
        $len = strlen($s);
        $left = $right = 0;
        $maxLen = 0 ;
        $dict = [];
        while($right < $len ){
            if(array_key_exists($s[$right],$dict)){
                $left =  max($left, $dict[$s[$right]]);
            }

            $maxLen = max($maxLen,$right-$left +1);
            $dict[$s[$right]] = $right + 1;
            $right ++ ; 
        }
        return $maxLen;
    }
}

最长公共前缀（2020-03-22)

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1:

输入: [“flower”,”flow”,”flight”]
输出: “fl”
示例 2:

输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。
说明:

所有输入只包含小写字母 a-z 。

function longestCommonPrefix($strs) {
        if (empty($strs)) {
            return "";
        }
        $len = strlen($strs[0]);
        $demo = $strs[0];
        for($i = 1; $i < count($strs); $i ++ ){
            $right = 0 ;
            for(;$right< $len && $right < strlen($strs[$i]) ; $right++){
                if(substr($demo,$right,1) != substr($strs[$i],$right,1)){
                    break;
                }
            }
            $demo = substr($demo,0,$right);
            if(empty($demo)){
                return "";
            }
        }
        return  $demo;
    }

字符串的排序（2020-03-23）

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).

示例2:

输入: s1= “ab” s2 = “eidboaoo”
输出: False

//个人理解：滑动窗口里面去判断字符串的个数值
function checkInclusion($s1, $s2) {
        $s1Len = strlen($s1);
        $s2Len = strlen($s2);
        if($s1Len > $s2Len){
            return false;
        }
        $a = count_chars($s1,1);
        $left = 0 ;
        $bool = false;
        while($left <= $s2Len - $s1Len){
            $sub_str = substr($s2, $left, $s1Len);//长字串中的子字串
            if(count_chars($sub_str,1) == $a){
                $bool = true;
                break; 
            } 
            $left++;
        }
        return $bool;
    }  

给定一个字符串，逐个翻转字符串中的每个单词。(2020-03-23)

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

输入: “the sky is blue”
输出: “blue is sky the”
示例 2：

输入: “ hello world! “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：

输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

    //php 真香
     function reverseWords($s) {
        $data =  array_reverse(array_filter(explode(" " ,$s)));
        return implode(" ",$data);
    }

简化路径 (2020-03-23)

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径

请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

function simplifyPath($path) {
        $arr =  explode("/",$path);
        $tmp = [];
        foreach($arr as $item){
            if($item == '.' || $item == ""){
                continue;
            }elseif($item == '..'){
                array_pop($tmp);
            }else{
                array_push($tmp,$item);
            }
        }
        return "/".implode("/",$tmp);
    }

本作品采用《CC 协议》，转载必须注明作者和本文链接