代码随想录算法训练营第五天 | 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 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!