LeetCode刷题第2周小结

本周题目汇总：

1.字符串相加

2.判断子序列

3.找不同

4.字符串中的第一个唯一字符

5.快乐数

6.最后一个单词的长度

7.重复的子字符串

关键字：

字符串算法、快慢指针、哈希集合、隐式链表、递归、KMP算法

---

1.字符串相加

难度：★ 链接：力扣

 解题思路：

对两个大整数模拟“竖式加法”的过程，即如下图所示：将两个数的相同数位对齐，从低位到高位相加，如果和超过10则向高位进一。所以我定义一个carry变量来存储这个进位值，由于两个整数的数位不一定相同，当指向某个整数的指针移动至负数时返回0，这样就等价于对数位较短的数字进行“补零”操作，进行下一轮对应数位的相加。特殊情况是：当两个整数的指针都指向了负数即计算到最后一个数位了但是此时进位值carry不为0，还需进行最后一次循环，即0+0+carry将进位值carry放置到结果的最高位。

 

解题代码：

class Solution {
    public String addStrings(String num1, String num2) {
        int i=num1.length()-1;
        int j=num2.length()-1;
        int carry=0;//进位
        StringBuffer result=new StringBuffer();//定义一个字符串容器用于存储最后的答案
        while(i>=0||j>=0||carry!=0){
            //如果其中某个字符已经结束 则将其赋值为0模拟补0操作进行相加
            int x=i>=0?num1.charAt(i)-'0':0;
            int y=j>=0?num2.charAt(j)-'0':0;
            int sum=x+y+carry;
            result.append(sum%10);
            carry=sum/10;
            i--;
            j--;
        }
        result.reverse();
        return result.toString();
    }
}

---

2.判断子序列

难度：★ 链接：力扣

解题思路：

采用双指针法，分别为两个字符串设置指针i ，j  对应主串与模式串，从两个字符串的首个字符进行匹配，若匹配成功，则模式串与主串对应的指针都右移一位；若匹配不成功，则将主串的指针向右移动一位，模式串指针不动。最后判断模式串的指针长度是否等于模式串的串长，如果相等，则说明模式串是主串中的一个子串且与主串中字符的相对位置一致，因为我们是顺序遍历进行匹配的；若不相等则说明模式串不是主串的一个子串。

解题代码：

class Solution {
    public boolean isSubsequence(String s, String t) {
        //双指针法：分别给两个字符串设置其对应的指针，匹配成功则同时右移，否则t右移
        //用其下一个字符去匹配s中当前字符
        int m=s.length(),n=t.length();
        int i=0,j=0;
        //由于是顺序遍历字符串，所以不用担心相对位置发生改变问题
        while(i
            if(s.charAt(i)==t.charAt(j)){
                //匹配成功则子串右移一个字符
                i++;
            }
            //无论匹配成功与否，主串都需要右移一个字符进行下一次的匹配
            j++;
        }
        //如果最后s的指针移动到最后则说明s是t的子序列
        return i==m;
        
    }
}

---

 

3.找不同

难度：★ 链接：力扣

解题思路：

蛮力法，先将字符串转换成字符数组，调用排序方法将其进行排序，然后逐一比对字符找出被添加的那个字符返回即可，思路简单。

解题代码：

class Solution {
    public char findTheDifference(String s, String t) {
        //先将两个字符串进行排序最后逐个字符比对
        char a1[]=s.toCharArray();
        char a2[]=t.toCharArray();
        Arrays.sort(a1);
        Arrays.sort(a2);
        for(int i=0;i
            if(a1[i]!=a2[i]){
                return a2[i];
            }
        }
        //如果循环结束还未找出被添加的字符则说明该字符在末尾处
        return a2[a2.length-1];
    }
}

---

4.字符串中的第一个唯一字符

难度：★ 链接：力扣

 

解题思路：

蛮力法，统计字符串中每个字符出现的频次存放于数组中，然后以字符串的逐个字符为索引依次顺序遍历频次数组，返回第一个频次为1的下标，此时 i 即为字符串中第一个唯一字符的索引。

解题代码：

class Solution {
    public int firstUniqChar(String s) {
        //统计频次 顺序遍历返回第一个频次为1的下标
        int a[]=new int[26];//分别存放26个字母所对应的频次
        int n=s.length();
        //第一次遍历 统计字符串中各个字符的频次
        for(int i=0;i
           a[s.charAt(i)-'a']++;
        }
        //第二次遍历 找出频次为1的字母所对应的下标
        for(int i=0;i
            if(a[s.charAt(i)-'a']==1){
                return i;
            }
        }
        return -1;
    }
}

---

 

5.快乐数

难度：★ 链接：力扣

 

解题思路：

本题解法很多，下面分别分享三种思路：

方法一：哈希集合法

使用哈希集合来存储每一次分解n后得到的各个位上的平方和，利用其无序且不重复的结构特点，如果存入的数有重复则会返回false，循环的结束条件是n为1,如果循环顺利结束说明其实快乐数字返回true

解题代码：

class Solution {
    public boolean isHappy(int n) {
        //使用哈希集合来判断是否有重复的元素，从而判断其是否进入了无限循环
        Sets=new HashSet<>();
        s.add(n);
        while(n!=1){
            n=squaresum(n);
            if(!s.add(n)){
                return false;
            }
        }
        return true;
    }
    //数位分离，求n的平方和
    public int squaresum(int n){
        int sum=0;
        while(n!=0){
            sum+=(n%10)*(n%10);
            n/=10;
        }
        return sum;
    }
}

方法二： 快慢指针法

先来看两个例子：

（1）以7为例，根据题目要求可以先出如下过程：

 可以看到最后各位数的平方和为1，所以7是一个快乐数。

（2）下面以116为例，过程图如下：

 

可以看到，等到算到58的时候，经过一番循环最终又回到了58，即它 构成了一个“环”，我们可以将其视为一个“隐式链表”，因为其没有真正意义上的的链表节点和指针，但是其数据形成了链表结构。所以问题转换成了判断该“隐式链表”中是否存在一个“环”，若存在环则会进入一个无限循环最终永远不可能到达1，所以有环的情况下肯定不是快乐数。如果无环，则快指针会先到达1，慢指针后到达1，最终判断慢指针是否到达1即可。

解题代码：

class Solution {
    public boolean isHappy(int n) {
        //将该数组视为链表，设置快慢指针来判断其是否是环，即是否存在重复的元素
        int slow=n,fast=n;
        do{
            //慢指针走1步
            slow=squaresum(slow);
            //快指针走2步
            fast=squaresum(fast);
            fast=squaresum(fast);
        }while(slow!=fast);
        //如果存在重复元素则会进入一个环，快慢指针终会相遇，但快慢指针的值都不为1 
        //如果不存在环，那么快指针先到达1，慢指针后
        return (slow==1);
    }
    //数位分离，求n的平方和
    public int squaresum(int n){
        int sum=0;
        while(n!=0){
            sum+=(n%10)*(n%10);
            n/=10;
        }
        return sum;
    }
}

方法三：蛮力法＋递归

之所以说是含有暴力思想在里面，是因为一开始我没有全部通过全部样例，最后卡在了输入7这个点，于是手算了下7确实是一个快乐数，于是在递归终止条件里面加上了这个点，再次测试全部通过了。然后递归地询问每一次n分解后各个位数的平方和是否是快乐数

解题代码：

class Solution {
    public boolean isHappy(int n) {
        //递归终止条件
        if(n==1||n==7||squaresum(n)==1){
            return true;
        }
        //个位数会无限平方和循环，肯定不是快乐数
        if(n>1&&n<10){
            return false;
        }
        return isHappy(squaresum(n));
        
    }
    public int squaresum(int n){
        int sum=0;
        while(n!=0){
            sum+=(n%10)*(n%10);
            n/=10;
        }
        return sum;
    }
}

---

 

6.最后一个单词的长度

难度：★ 链接：力扣

 

解题思路：

蛮力法+逆向思维：题目要求求最后一个单词的长度，显然没有必要正向遍历，当然是反向遍历，设置一个变量index将其移动到反向第一个字符的位置，该位置就是最后一个单词的最后一个字母，下面就是在其中将空格筛选出去统计字母的个数计算最后一个单词的长度

解题代码：

class Solution {
    public int lengthOfLastWord(String s) {
        int n=s.length();
        int index=n-1;
        //反向遍历数组，计算出最后一个单词的长度
        while(s.charAt(index)==' '){
           index--;
        }
        //循环结束时，此时index位置即为反向第一个单词的最后一个字母
        int lastword=0;
        while(index>=0&&s.charAt(index)!=' '){
            lastword++;
            index--;
        }
        return lastword;
        //思考：如果要求出字符串s中最长单词的长度呢？
    }
}

 

---

 

7.重复的子字符串

难度：★ 链接：力扣

 

解题思路：

如果一个长度为n的字符串s可以由它的长度为m的字串s'重复多次构成，那么有以下几点结论：

• n一定是m的倍数
• s'一定是s的前缀
• 对于任意在m和n范围内的i，有s[i]=s[i-m]

上面这三点是解题的关键，可以这么理解，s中长度为m的前缀就是s'，并且在这之后的每一个位置上的字符s[i] ,都需要与它前面的第m个字符s[i-m]相同。所以可以从小到大枚举m，对字符串s进行遍历，进行上述的判断。一个小细节就是，因为字串至少需要重复一次，suoyim不会大于n的一半，所以只需要在[1,n/2]范围内枚举长度为m的字串进行判断即可

解题代码：

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        //枚举
        int n=s.length();
        for(int i=1;i<=(n/2);i++){
            if(n%i==0){
                //是否是重复的子字符串
                boolean flag=true;
                for(int j=i;j
                    if(s.charAt(j)!=s.charAt(j-i)){
                        flag=false;
                        break;
                    }
                }
                if(flag){
                    return true;
                }
            }
        }
        return false;
    }
}

 本周重点学习了字符串匹配的相关算法，包括最经典最晦涩难懂的KMP算法，这里我推荐一篇文章供大家学习，文章很棒，仔细阅读，结合在纸上模拟与推导，KMP算法直接拿下！

KMP算法真的有这么难吗？（清晰详细版）

下周继续，每日一题，让刷题成为一种习惯！