力扣题集（第一弹）

一日练,一日功;一日不练十日空。

学编程离不开刷题，接下来让我们来看几个力扣上的题目。

1. 242. 有效的字母异位词

题目描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:输入: s = "anagram", t = "nagaram"
输出: true
示例 2:输入: s = "rat", t = "car"
输出: false提示:1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

给定函数

bool isAnagram(char* s, char* t) 
{}

题意分析

有题目描述与示例可知：

给定的两个字符串具有以下特征：

< 1 > 两个字符串长度必然相同

< 2 > 两个字符串中每个字符出现的次数都相同（两个字符串中字符出现的种类和次数均相等）

< 3 > 两字符串都仅包含小写字母

如果两字符串属于字母异位词返回true，反之返回false。

解题思路详解

对于这一题目，我们采用哈希表解题法。由于一共只存在26个小写字母，因此我们可以创建一个长度为26的频次数组arr。

（1）判断两字符串长度是否相等，不等则返回false；

（2）创建一个长度为26的频次数组，计量字符串中每个字符出现的频次；

（3）先遍历s字符串，记录s字符串每个字符出现的频次；

（4）遍历t字符串，减去t字符串每个字符出现的频次

（一增一减之后，频次数组arr每个元素都应为0）；

（5）遍历频次数组arr，如果有元素不等于0，则两字符串不是字母异位词。

代码实现

bool isAnagram(char* s, char* t)
{int n = strlen(s);int m = strlen(t);if (n != m)//如果两字符串长度不同，则必然不是字母异位词{return false;}int arr[26];memset(arr, 0, sizeof(arr));//字母 - ‘a’即字母之间ascll值相减，对应0~26for (int i = 0; i < n; i++)//计数法，出现则加一{arr[s[i] - 'a'] ++;}for (int i = 0; i < n; i++)//出现减一{arr[t[i] - 'a'] --;}for (int i = 0; i < 26; i++)//如果两字符串中字母出现次数相同，则数组每个元素仍为0{if (arr[i] != 0){return false;}}return true;
}

2.389. 找不同

由于这一题与上面的题最为相似，就粗略讲一下。

题目描述

给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例 1：输入：s = "abcd", t = "abcde"
输出："e"
解释：'e' 是那个被添加的字母。
示例 2：输入：s = "", t = "y"
输出："y"提示：0 <= s.length <= 1000
t.length == s.length + 1
s 和 t 只包含小写字母

给定函数

char findTheDifference(char* s, char* t) 
{}

题意分析

这一题与上一题基本类似，总结以下特征：

< 1 > 题中的字符串都只存在小写字母；

< 2 > t字符由s字符打乱重排，然后在随机位置插入一个随即小写字母。

找出插入的字符并返回。

解题思路详解

与上一题的字母异位词有异曲同工之妙，唯一不同的地方就是这里的频次数组有一个元素一定是为1的，我们只需要返回这个元素下标对应的字符。

（1）创建一个长度为26的频次数组，计量字符串中每个字符出现的频次；

（2）先遍历s字符串，记录s字符串每个字符出现的频次；

（3）遍历t字符串，减去t字符串每个字符出现的频次

（一增一减之后，频次数组arr有一个元素一定是为1）；

（4）遍历频次数组arr，如果有元素等于1，则返回这个元素下标对应的字符。

注意：此处t字符串字符个数必然比s字符串个数多一个，因此在这里我们不需要遍历整个数组，只需要随t字符串的遍历寻找为1的元素。

代码实现

char findTheDifference(char* s, char* t) 
{int cnt[26]={0};int n=strlen(s), m=strlen(t);for(int i=0;i<n;i++){cnt[s[i]-'a']++;}for(int j=0;j<m;j++) 此处m必然比n大1，因此在这一循环内寻找为1的元素即可{cnt[t[j]-'a']--;if(cnt[t[j]-'a']<0){return t[j];}}return ' ';
}

3.283. 移动零

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:输入: nums = [0]
输出: [0]提示:1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

题意分析

本题是一个非常简单的数组元素移动问题，将一个数组内的非零数全部迁移至左侧，零迁移至右侧。

但要求不能复制数组。

解题思路详解

思路一

//本题要将所有非零数挪到数组左侧，所有为0的数移到数组右侧
//那么只需要将所有为0的数填充到左侧，右侧0补齐

//将所有非零数移动到数组前端，再用零补全数组

这个思路极为简单，操作也相对方便，但时间复杂度为O(n+m)。 < m为用零补全数组的消耗 >

思路二

采用双指针法< 快慢指针法 >

定义左右两个指针，同时位于下标0处。遍历整个数组，使得左指针左侧均为非零数的序列，左指针与右指针之间均为0。遍历完整个数组后，左指针指向第一个零，右指针指向数组末尾。

这个思路相比于思路一难一点，但时间复杂度为O(n)，只需遍历一遍数组。

具体做法

定义左右指针都为0，
左指针左边全为非零数序列，右指针与左指针之间均为0
右指针遇到非零数与左指针交换并同时++
右指针遇到0，右指针++，左指针不变
逐渐将非零数移动至左指针左侧序列
直到遍历完整个数组

代码实现

思路一

void moveZeroes(int* nums, int numsSize)
{int n = 0;//作为操作下标for (int i = 0; i < numsSize; i++)//将所有非零数移动到数组前端{if (nums[i] != 0){nums[n++] = nums[i];}}for (int i = n; i < numsSize; i++)//再用零补全数组{nums[n++] = 0;}
}

思路二（进阶）

void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}void moveZeroes(int* nums, int numsSize)
{int left = 0, right = 0;while (right < numsSize){if (nums[right]){Swap(&nums[left], &nums[right]);{left++;}}right++;}
}