力扣题集（第一弹）

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

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

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~26
    for (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++;
    }
}