leetcode 刷题

9. 回文数

/*

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。


示例 1：

输入：x = 121
输出：true
示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。


提示：

-231 <= x <= 231 - 1

*/

思路

1.字符串翻转比较 strrev 函数或者自己写
2.字符串逐个前后比较
3.数字取模翻转比较
4.数字取模取一半，跟前半部分比较 ；分奇数偶数情况

代码

class Solution {

    /**
     * @param Integer $x
     * @return Boolean
     */
    function isPalindrome($x) {
        //方式1：翻转字符串 比较
        $x = (string) $x;
        $len = strlen($x);
        $str = '';
        for ($i=0; $i < $len; $i++) { 
            $str .= $x[$len-1-$i];
            # code...
        }

        if($str == $x){
            return true;
        }

        return false;
    }
    function isPalindrome4($x) {
        //全部翻转
        if($x<0){
            return false;
        }

        if($x<10){
            return true;
        } 

        $rev = '';
        $tmp = $x;
        while ($tmp>0) {
            # code...

            if($tmp<10){
                $rev .=$tmp;
                $tmp = 0;
            }else{
                $rev .= $tmp % 10;
                $tmp = (int) ($tmp/10);
            }

        }


        if($rev == $x){
            return true;
        }
        return false;

    }


    function isPalindrome3($x) {

        //对半翻转

        if($x<0){
            return false;
        }

        if($x<10){
            return true;
        } 
        //得到长度 
        $len =strlen((string)$x);

        if($len %2 !=0){
             //奇数情况
            $k = (int )($len/2);//左右各取的个数

            $left =   (int) ($x/pow(10,$k+1));
            $right = '';
            for ($i=0; $i < $k; $i++) { 
                # code...
                $right .= $x % 10;
                $x = (int) $x/10;
            }

            if($left == $right){
                return true;
            }
            return false;
            }else{
                //偶数情况
                $k = (int )($len/2);//左右各取的个数

                $left =   (int) ($x/pow(10,$k));
                $right = '';
                for ($i=0; $i < $k; $i++) { 
                    # code...
                    $right .= $x % 10;
                    $x = (int) $x/10;
                } 
                if($left == $right){
                    return true;
                }
                return false;
        }

    }
     //逐个字符比较

 function  isPalindrome4($x) {

     $x= (string)$x;

     $len = strlen($x);

     for($i=0;$i<$len;$i++){

     if($x[$i] !== $x[$len-1-$i]){  

     return  false;

            }

            }

     return  true;

    }
}

//TEST
$handle = new Solution();
$x = 1221; 

 $res = $handle->isPalindrome4($x) ;
 var_dump($res);

8. 字符串转换整数 (atoi)

/*
8. 字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。


示例 1：

输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。
示例 2：

输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -42"（读入 "42"）
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。
示例 3：

输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。

*/


/*
本题主要是考察如何对循环的精准控制
如何控制循环的跳出  循环中的执行步骤的控制
*/

代码

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function myAtoi($s) {

        $start  = 0; //刚开始
        $step1= ''; //符号位
        $step2= ''; //数字位

        $len = strlen($s);


        for ($i=0; $i < $len; $i++) { 

            $value = $s[$i];

            //1.读入字符串并丢弃无用的前导空格

            if($start == 0){
                if($value == ' '){
                    continue;
                }
                if($value == '+'|| $value == '-' ){
                    $start = 1;  // 符号位不再判断
                    $step1 = $value;
                    continue;
                }
                if(is_numeric($value)){
                    $start = 1;  //符号位不再判断
                    $step1 = '+';
                    $step2 .= $value;
                    continue;
                }

                //首位不是上述情况
                return  0;
            }

            //开始下一字符了
            if($start ==1){
                 //读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。
                 if(!is_numeric($value)){
                    $numStr = (int) ($step1.$step2);

                    return $this->ret($numStr);
                 }else{
                    $step2 .= $value;
                 }
            }
        }
        //或到达输入的结尾。
        $numStr = (int) ($step1.$step2);

        return $this->ret($numStr);
    }

    public  function ret($numStr){



        $max = pow(2,31)-1;
        $min = pow(-2,31);
        if($numStr>$max){
            return $max;
        }

        if( $numStr<$min){
            return $min;
        }
        return $numStr;
    }
}


//TEST
$handle = new Solution();
$x =  "words and 987";  ' -423';// "+-12";//  '-5-';// '-12';//

echo  $res = $handle->myAtoi($x) ;

7. 整数反转

/*
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。


示例 1：

输入：x = 123
输出：321
示例 2：

输入：x = -123
输出：-321
示例 3：

输入：x = 120
输出：21
示例 4：

输入：x = 0
输出：0

*/

代码

class Solution {

    /**
     * @param Integer $x
     * @return Integer
     */

    function reverse2($x) {
        $flag = $x>=0 ? '' : '-';
        $x = $x>=0 ? $x : -$x;
        while($x){
            $str .= $x%10;
            $x =  (int) ($x/10);
        }
        $x = $flag.(int)$str;
        if($x> pow(2,31)-1 || $x < pow(-2,31)){
            return 0;
        }
        return  $x;
    }

    function reverse($x) {
        if($x>=0){
            $flag = '';
        }else{
            $flag = '-';
            $x = -$x;
        }

        $str = '';
        while($x){
            if($x<10){
                $str .= $x;
                $x = 0;
            } else{
                $str .= $x%10;
                $x =  $x/10;
                $x = (int) $x;
            }

        }
        $x = $flag.(int)$str;
        if($x> pow(2,31)-1 || $x < pow(-2,31)){
            return 0;
        }
        return  $x;
    }
}

//TEST
$handle = new Solution();
$x =    1234; 

echo  $res = $handle->reverse($x) ;

6. N 字形变换

/*
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N

A P L S I I G

Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3

输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4

输出："PINALSIGYAHRPI"

解释：

P     I    N

A   L S  I G

Y A   H R

P     I

示例 3：

输入：s = "A", numRows = 1

输出："A"

*/
*/

想法

/* 
想法
将字符串按照N型排列存储在数组中，再依次横向读取得到结果
*/

代码

class Solution {

/**
 * @param String $s
 * @param Integer $numRows
 * @return String
 */
    function convert($s, $numRows) {
        $arrRes = [];  //存放结果

        $heng = 0;  //存放当前的横坐标
        $zong = 0;  //存放当前遍历的纵坐标

        $status = 0; //0 从上往下 1 从下往上 状态

        $strlen = strlen($s);
        for ($i=0; $i <$strlen ; ++$i) {
            $value =  $s[$i];

            if($status ==0){
                //从上往下时 
                if($zong< $numRows){
                    $arrRes[$zong][$heng] = $value;
                    $zong+=1;
                }else{
                    $status =1;
                    $zong-=1; //将超出的一次+1 回退回去
                }
            }

            if($status ==1){//var_dump($zong); exit;
                //从下往上时 ，一次只能放一个 ，除非zong-1 = 0

                $heng +=1;
                $zong -=1;

                $arrRes[$zong][$heng] = $value;

                if($zong == 0){
                   $status = 0;
                   $zong +=1; //将纵坐标的位置指向下一个 方便正向的插入
                }  
            }

        }
        return $arrRes;
    }
}

//TEST
$handle = new Solution();
$s =   "ABCD"; 

$res = $handle->convert($s,2) ;
 echo  bianli($res);



//二维数组的遍历

function bianli($arr)
{
    $str ='';
    foreach ($arr as $key => $value) {
        # code...
        foreach($value as $key2 => $value2){
            $str .= $value2;
        }
    }

    return $str;
}

5. 最长回文子串

/*
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb" 
*/

/*
方式1： 

方式2：马拉车算法
即便我们使用了中央扩展法很易筛选出字符串中间的回文，但是其复杂度还是太高，达到 O(n^2)。
 当我们遇到字符串为“laaaaaaaaa”，之前的算法就会发生各个回文相互重叠的情况，
 会产生重复计算，然后就产生了一个问题，能否改进？
 答案是能，1975年，一个叫Manacher的人发明了Manacher Algorithm算法，俗称马拉车算法， 
 其时间复杂达到惊人的 O(n)。

方式3：中央扩展法
*/

代码

class  Solution {

 /**

* @param  String $s

* @return  String

     */

     //马拉车算法

     function  longestPalindrome($s)

    {

 $s_len = strlen($s);

 if ($s_len < 1) {

 return  '';

} elseif ($s_len <= 2) {

 return  $s[0] == $s[1] ? $s : $s[0];

        }  

 $symbol = '#';

 $s_with_symbol = "\$"  .  $symbol;

 for ($i = 0; $i < $s_len; $i ++) {

 $sub_s = $s[$i] .  $symbol;

 $s_with_symbol  .=  $sub_s;

        }

 $p = [];

 $mx = 0;

 $id = 0;

 $resLen = 0;

 $resCenter = 0;

 $s_with_symbol_len = strlen($s_with_symbol);

 for ($i = 1; $i < $s_with_symbol_len; $i ++) {

 $p[$i] = $mx > $i ? min($p[2 * $id - $i], $mx - $i) : 1;

 while ($s_with_symbol[$i + $p[$i]] == $s_with_symbol[$i - $p[$i]]) {

++ $p[$i];

 if ($mx < $p[$i] + $i) {

 $mx = $p[$i] + $i;

 $id = $i;

                }

 if ($resLen < $p[$i]) {

 $resLen = $p[$i];

 $resCenter = $i;

                }

            }

        }

 return  substr($s, ($resCenter - $resLen)/2, $resLen - 1);

    }

     //这个方式时间复杂度太高了 超时时间限制

     //两层for循环，遍历区间起始位置和终止位置，然后判断这个区间是不是回文。

     //时间复杂度：O(n^3)

     function  longestPalindrome2($s) {

 //暴力破解

 //逐个遍历，都找出正反

 $maxlen = 0;

 $maxString = '';

 $strlen = strlen($s);

 for ($i=0; $i <$strlen ; ++$i) {

 $str = '';

 for ($j=0; $j < $strlen; $j++) {

 # code...

 if($i+$j+1 >$strlen){

 break;

                }

 $str  .=  $s[$i+$j];

 //  $map[$str] = '';

 // echo "当前字符串{$str}".PHP_EOL;

 $fanzhuan = $this->fanzhuan($str);

 // echo "反转后为{$fanzhuan}".PHP_EOL;

 if($fanzhuan == $str && strlen($fanzhuan) > $maxlen){

 $maxString = $str;

 $maxlen = strlen($str);

                }

            }

        }

 return  $maxString;

     }
}     
function  fanzhuan($s)

     {

 $strlen = strlen($s);

 $str = '';

 for ($i=0; $i <$strlen ; ++$i) {

 $str  .=  $s[$strlen-$i-1];

        }

 return  $str;

     }

//TEST

$handle = new  Solution();

$s = "babad";

$res = $handle->longestPalindrome2($s) ;

var_dump($res);

4. 寻找两个正序数组的中位数

题目要求

/*
4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
*/

想法

做这道题的时候思索过处理回文字符串在现实生活中具有什么意义？或者有哪些应用场景
不同于子串匹配，前缀匹配，回文匹配在工业界的确用得很少，几乎不会用到，因为确实没有可以对标的使用场景。有人说基因序列中自然的存在许多回文序列，所以权当练习题吧
/*
方式1：用php内置的 合并数组 排序数组
找到中位数并返回

方式二：本题考察的应该是数组的排序方法
可以依次比较注入一个新数组，因为其内部有序
*/

代码

class Solution {

function  findMedianSortedArrays2($nums1, $nums2) {

 $num1len = count($nums1);
 $nums2len =count($nums2);
 $letf = 0;
 $right = 0;
 $map = [];

 while($letf < $num1len || $right < $nums2len){
    if(isset($nums1[$letf]) && isset($nums2[$right])){
         if($nums1[$letf] < $nums2[$right]){
            echo  "左边小，录入左边".$nums1[$letf].PHP_EOL;
            $map[] = $nums1[$letf];
            $letf+=1;
          }else{
         echo  "右边小，录入右边".$nums2[$right].PHP_EOL;
        $map[] = $nums2[$right];
         $right+=1;
        }
     }elseif(isset($nums1[$letf]) ){
         echo  "只有左边，录入左边".$nums1[$letf].PHP_EOL;
         $map[] = $nums1[$letf]; $letf+=1;
     }elseif(isset($nums2[$right]) ){
         echo  "只有右边，录入右边".$nums1[$right].PHP_EOL;
         $map[] = $nums2[$right];$right+=1;
     }
    }

     $len = count($map);
     if($len %2 ==0){
     return ( $map[($len/2)-1] +  $map[($len/2)] ) /2;
     }else{  
     return $map[($len-1)/2];
     }
   }
  /**
   * @param Integer[] $nums1
   * @param Integer[] $nums2
   * @return Float
   */
  function findMedianSortedArrays($nums1, $nums2) {
    if(!$nums1 && !$nums2){
      return false;
    }

    $arr = array_merge($nums1, $nums2);

    $len = count($arr);
    if($len == 1){
      return $arr[0];
    }

    sort($arr);

    if($len %2 ==0){
       return ( $arr[($len/2)-1] +  $arr[($len/2)] ) /2;
    }else{  
      return  $arr[($len-1)/2];
    }

  }
}

//TEST
$handle = new Solution();
$nums1 = [1,2];
$nums2 = [3,4];
$res = $handle->findMedianSortedArrays($nums1, $nums2) ;
var_dump($res);

3. 无重复字符的最长子串

题目要求

/*
给定一个字符串 `s` ，请你找出其中不含有重复字符的 **最长子串 **的长度。
示例 1:

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

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

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

想法：

方式1：
创建一个哈希表
放置每次未重复前的 值 
遇到重复的 ，保存当前长度 ，删除数组中重复的以及之前的值
再次往后遍历录入
最后对比长度  （或是直接每次对比长度）

方式2：
-   利用滑动窗口的思想，动态维护窗口左右边界的准确性即可。

//方式2
/*
//双指针法 动态维护窗口左右边界的准确性
//左右指针都指向第一个 初始化
//右指针一直往前指
//如果遇到重复项
//比较窗口值的大小
//左指针指向重复项+1的位置即可
//注意 要防止左指针回退
*/
function  lengthOfLongestSubstring40($s) {
 $left = 0;
 $right = 0;
 $maxLen = 0;
 $map = [];
 $strlen = strlen($s);

 for ($i=0; $i <$strlen ; ++$i) {
         $value =$s[$i];
        if(isset($map[$value]) && $map[$value]>=$left){ //防止左指针回退 
        $map[$value]>=$left
        //计算此时窗口大小
        $len = $right - $left;
        //移动左指针之前，比较最大窗户
        $maxLen = $maxLen > $len ? $maxLen :$len;
        //遇到重复了 ，左指针移动到重复项之前的值里的下一位
        $left = $map[$value]  +1;
        }

        $right +=1;//右指针往前指  
        $len = $right - $left;
        //修正map 里重复值的位置下标
        $map[$value] =  $i;
    }
    $currentLen = $right - $left;
    return  $maxLen = $maxLen > $currentLen ? $maxLen : $currentLen;
}

//方式1
function lengthOfLongestSubstring($s) {
        $maxLen = 0;
        $map = [];  
        $strlen = strlen($s);
        for ($i=0; $i <$strlen ; ++$i) {
            $value =  $s[$i]; 
            if(!isset($map[$value])){
                $map[$value] = '' ;
            }else{
                $currentLen = count($map);
                $maxLen = $maxLen > $currentLen ? $maxLen : $currentLen;

                foreach ($map as $key =>$tmp) {
                        if( $key == $value){
                            unset($map[$key]);
                            break;
                        }else{
                            unset($map[$key]);
                        }
                }
                $map[$value] = '';  
            }
        }
        $currentLen = count($map);
        return $maxLen = $maxLen > $currentLen ? $maxLen : $currentLen;
     }

//TEST
$handle = new  Solution();
$s = "iqbtbscgdztpgfp";//"bbbbb";//"bpfbhmipx";//"tmmzuxt";//"asjrgapa";
$res = $handle->lengthOfLongestSubstring($s) ;
var_dump($res);

2.两数相加

题目要求

/*
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例1：
**输入：**
l1 = [2,4,3], 
l2 = [5,6,4]
**输出：**[7,0,8]
**解释：**342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[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 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) {

        $len1 = count($l1);
        $len2 = count($l2);
        $l3 = $len1 > $len2 ? $l1 :$l2; 
        $l4 = $len1 > $len2 ? $l2 :$l1;
        $a = 0;
        $map = [];
        foreach ($l3 as $key => $value) {

            if(isset($l4[$key])){
                // var_dump($value,$l4[$key],$a);
                  $res =  $value + $l4[$key] + $a;
                if($res > 9){
                    $map[] = $res-10;
                    $a = 1;
                }else{
                    $map[] = $res;
                    $a = 0;
                }
            }else{
                if($a == 1){
                    $map[] = 1;
                    $a = 0;
                }else{
                    $map[] = 0;
                }
            }
        }
        if($a = 1){
            $map[] = 1;
        }

        return $map;
    }

    //本题考察的是对于链表这种数据结构的应用
    //链表实现
    //这里面应该还涉及到一个浅拷贝 深拷贝的知识点  这里 $cur = $dummyHead; 应该是浅拷贝 ，没有开辟新的堆栈

    function addTwoNumbers2($l1, $l2) {
        $carry = 0; // 进位
        $dummyHead = new ListNode(0); // 添加虚拟头节点, 方便返回
        $cur = $dummyHead;

        while($l1!== null || $l2!=null || $carry){
            $sum = $carry;
            if($l1!=null){
                $sum += $l1->val;
                // echo $sum;
                $l1 = $l1->next;
            }
            if($l2!=null){
                $sum += $l2->val;
                $l2 = $l2->next;
            }
            if($sum > 9){
                $sum -=10;
                $carry = 1; 
            }else{
                $carry = 0;//复位
            }
            // echo $sum.'<br>';
            $cur->next = new ListNode($sum);  //这里返回的是一个新节点
            $cur  = $cur->next; //这里进行了节点的挂载
            // var_dump($dummyHead);
        }
        return $dummyHead->next;
    }
}

//TEST
// $handle = new Solution();
// // $l1 = [2,4,3];
// // $l2 = [5,6,4];
// // $l1 = [0];
// // $l2 = [0];
// $l1 =  [9,9,9,9,9,9,9];
// $l2 = [9,9,9,9];
// $res = $handle->addTwoNumbers($l1, $l2) ;
// var_dump($res);


//TEST List
$handle = new Solution();
$l1 = getList([9,9,9,9,9,9,9]) ;
$l2 = getList([9,9,9,9]) ;
$res = $handle->addTwoNumbers2($l1, $l2) ;
 var_dump(getArray($res));
 var_dump(getString($res));

//把数组形式录入成链表
function getList($arr){
    $list = new ListNode(0);
    $cur = $list;
    foreach ($arr as $key => $value) {
        # code...
        $cur->next = new ListNode($value);
        $cur = $cur->next;
    }
    return $list->next;
}

//把链表返回成数组
function getArray($list){
    $arr = [];
    while($list !=null) {
        $arr[] = $list->val;
        $list = $list->next;
    }
    return $arr;
}

function getString($list){
    $a = '';
    while($list !=null) {
        $a .= $list->val;
        $list = $list->next;
    }
    return $a;
}

1.两数之和

题目要求

/*
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。



示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案


进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
*/

想法

1.遍历 复杂度 O(n2)

2.设计一个辅助数组,用辅助数组的键来保存原数组的值，用辅助数组的值来保存原数组的键
在依次遍历的时候，只需要查询 目标值减去当前遍历到的值  所对应的辅助数组的键存不存在即可
不存在则录入辅助数组，存在则返回辅助数组对应的值（原数组中的数值位置）和当前遍历到的位置

代码

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    //遍历
    function twoSum($nums, $target) {
        $len = count($nums) ;
        for($i=0;$i<$len-1;$i++){
            for ($j=$i+1; $j <$len ; $j++) { 
                if($nums[$i]+$nums[$j] == $target){
                    return [$i,$j] ;
                } 
            }
        }
        return false;
    }

    //辅助数组
    function twoSum2($nums, $target) {
        $tmp = [];
        foreach($nums as $key => $value){
            if(isset($tmp[$target-$value])){
                return [$tmp[$target-$value],$key];
            }
            $tmp[$value] = $key;
        }
        return false;
    }
}

//TEST
$handle = new Solution();
$nums = [0,4,3,0];
$target = 0;
$res = $handle->twoSum($nums, $target) ;
var_dump($res);

总结：

• 方法一：暴力枚举
  • 时间复杂度：O(N2)
  • 空间复杂度：O(1)
• 方法二：哈希表
  • 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
  • 时间复杂度：O(N)
  • 空间复杂度：O(N)

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