代码随想录算法训练营第五天 | leetcode：有效的字母异位词,两个数组的交集,快乐数,两数之和
0 / 0 / 创建于 1年前 /
_zzh 的个人博客
Problem: 151. 反转字符串中的单词
需要注意的问题
- 注意理解字母异位词的意思。字母异位词是由相同的字母组成，但字母位置不同的两个单词或短语。如：“heart”和“earth”。
- 字符串中元素是存在重复的。
解题方法
- 因为字符a到字符z的ASCII是26个连续的数值，所以使用各个字母到 a 的差值作为key。依次表示a-z，并且赋初始值0。在遍历字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对差值就可以了。这样就将字符串s中字符出现的次数，统计出来了。
- 在遍历字符串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. 两个数组的交集
需要注意的问题
- 输出结果中的每个元素一定是 唯一 的。
- 可以 不考虑输出结果的顺序 。
解题方法
字母异位词的解法异曲同工，构建对照组，以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. 两数之和
需要注意的问题
- 数组中同一个元素在答案里不能重复出现。
- 可以按任意顺序返回答案。
- 只会存在一个有效答案。
解题方法
- 可以直接暴力解法，双层for循环，判断$nums[$i]+$nums[$j] == $target则返回下标
- 使用哈希对照组$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，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
- 如何计算每个位置上的数字的平方和
解题方法
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。
所以这道题目使用哈希法，来判断这个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 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号