代码随想录算法训练营第五天 | leetcode:有效的字母异位词,两个数组的交集,快乐数,两数之和

Problem: 151. 反转字符串中的单词#

需要注意的问题#

  1. 注意理解字母异位词的意思。字母异位词是由相同的字母组成,但字母位置不同的两个单词或短语。如:“heart” 和 “earth”。
  2. 字符串中元素是存在重复的。

解题方法#

  1. 因为字符 a 到字符 z 的 ASCII 是 26 个连续的数值,所以使用各个字母到 a 的差值作为 key。依次表示 a-z,并且赋初始值 0。在遍历字符串 s 的时候,只需要将 s [i] - ‘a’ 所在的元素做 + 1 操作即可,并不需要记住字符 a 的 ASCII,只要求出一个相对差值就可以了。这样就将字符串 s 中字符出现的次数,统计出来了。
  2. 在遍历字符串 t 的时候,对 t 中出现的字符映射哈希表索引上的数值再做 - 1 的操作。最后检查一下,record 数组如果有的元素不为零 0,说明字符串 s 和 t 一定是谁多了字符或者谁少了字符,return false。

复杂度#

时间复杂度:

O(n)

空间复杂度:

O(1)

解法 1#

 function isAnagram($s, $t) {
        if(mb_strlen($s) != mb_strlen($t)){
            return false;
        }
        $keys = range(0, 25); // 生成一个从0到25的数组
        $initial_value = 0; // 初始值设为0
        $newArr = array_fill_keys($keys, $initial_value);
        $sArr = str_split($s);
        $tArr = str_split($t);
        foreach($sArr as $val){
            //求相对差值作为key
            $sIdex = ord($val)-ord('a');
            //数组s出现的值++
            $newArr[$sIdex]++;
        }
        foreach($tArr as $item){
            //求相对差值作为key
            $tIndex = ord($item)-ord('a');
            //循环t数组,出现的值--
            if(!empty($newArr[$tIndex])){
                $newArr[$tIndex]--;
            }
        }
        //最后计算对照组是否==0
        if(array_sum($newArr) == 0){
            return true;
        }
        return false;
    }

解法 2#

  function isAnagram($s, $t) {
         if(strlen($s)!=strlen($t)){
            return false;
        }
        if($s==$t){
            return true;
        }
        $sArr=$tArr=[];
        //字符串可以通过数组的下标方式拿到对应位置的字母
        for($i=0;$i<strlen($s);$i++){
            $sArr[$s[$i]][]=$s[$i];
            $tArr[$t[$i]][]=$t[$i];
        }
        return $sArr==$tArr;
    }

Problem: 349. 两个数组的交集#

需要注意的问题#

  1. 输出结果中的每个元素一定是 唯一 的。
  2. 可以 不考虑输出结果的顺序 。

解题方法#

字母异位词的解法异曲同工,构建对照组,以 num1 的值为对照组的 key。1 方面方便 nums2 的对照,以及可以起到去重 nums1 的作用。遍历 nums2 的过程中,判断对照组中是否存在对应值,存在的话,将值存入结果组中,同时注意 unset 已对比的数据。

复杂度#

时间复杂度:

O(n)

空间复杂度:

O(n)

code#

function intersection($nums1, $nums2) {
        $hash = [];
        $res = [];

        foreach($nums1 as $item){
            //构建对照组 以num1的值作为对照组的key,去重作用
            $hash[$item] = 1;
        }
        foreach($nums2 as $val){
            if($hash[$val]){
                //输出目标组
                $res[] = $val;
            }
            //清除已对比数据
            unset($hash[$val]);
        }
        return $res;
    }

Problem: 1. 两数之和#

需要注意的问题#

  1. 数组中同一个元素在答案里不能重复出现。
  2. 可以按任意顺序返回答案。
  3. 只会存在一个有效答案。

解题方法#

  1. 可以直接暴力解法,双层 for 循环,判断 $nums [$i]+$nums [$j] == $target 则返回下标
  2. 使用哈希对照组 $hash,构建以 nums 的值作为对照组的 key,值为 nums 的 key 哈希对照组。再次循环遍历 nums, 寻找 hash 对照组中 key + 循环中 nums 值 = target 的值。即:$hash [$target-$val] 存在,则返回 $hash [$target-$val] 与循环中的 key 值。

复杂度#

时间复杂度:

O(n)

空间复杂度:

O(n)

解法 1#

 function twoSum($nums, $target) {
        for($i = 0; $i < count($nums)-1;$i++){
            for($j = $i+1; $j < count($nums);$j++){
                if($nums[$i]+$nums[$j] == $target){
                    return [$i,$j];
                }
            }
        }
        return [];
    }

解法 2#

function twoSum($nums, $target) {
  $hash = [];//存放key,val反转的数组;
        foreach($nums as $key=>$val){
            $hash[$val] = $key;
        }
        foreach($nums as $key1=>$val1){
            //用减法去寻找hash 数组里面相加==target的key值, 且不能自身相加==target
            if($hash[$target-$val1] != $key1 && $hash[$target-$val1]){
                return [$hash[$target-$val1],$key1];
            }
        }
}

解法 2 优化版#

function twoSum(array $nums, int $target): array
{
    $map = [];
    foreach($nums as $i => $num) {
        if (isset($map[$target - $num])) {
            return [
                $i,
                $map[$target - $num]
            ];
        } else {
            $map[$num] = $i;
        }
    }
    return [];
}

Problem: 202. 快乐数#

需要注意的问题#

  1. 也可能是无限循环,但始终变不到 1,那么也就是说求和的过程中,sum 会重复出现,这对解题很重要!
  2. 如何计算每个位置上的数字的平方和

解题方法#

当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法了。
所以这道题目使用哈希法,来判断这个 sum 是否重复出现,如果重复了就是 return false, 否则一直找到 sum 为 1 为止。

复杂度#

时间复杂度:

O(logn)

空间复杂度:

O(logn)

code#

function isHappy($n) {
        $table = [];
        //循环退出条件平方和==1 活着哈希表中存在重复数据表示数据进入死循环
        while ($n != 1 && !isset($table[$n])) {
            $table[$n] = 1;
            $n = self::getNextN($n);
        }
        return $n == 1;
    }

    function getNextN(int $n) {
        $res = 0;
        while ($n > 0) {
           //求余从个位数算起
            $temp = $n % 10;
            //计算平方和
            $res += $temp * $temp;
            //除以十,往前进一位
            $n = floor($n / 10);
        }
        return $res;
    }
本作品采用《CC 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。