其他算法

哈希表

快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

思路：

递归+哈希表
使用哈希表存储已经出现过的数，通过递归计算下一个数。当数变为1时返回true，当数出现重复（即在哈希表中已经存在），则为false。
快慢指针
类比于链表成环的思路。这个题最终必有环，只是说这个环节点是1还是其他值。为1代表true，其他则是false。但是不同于链表成环2的是，这个如果是1的话，环内元素只有1，因此slow和fast相遇必是1；但如果节点不是1，则有可能是其他任意值。因此只需要判断成环那一刻，slow是不是1即可。

class Solution {
    HashSet<Integer> set=new HashSet<>();
    public boolean isHappy(int n) {
        if(n==1){
            return true;
        }
        if(set.contains(n)){
            return false;
        }else{
            set.add(n);
        }
        int sum=0;
        while(n!=0){
            sum=sum+(n%10)*(n%10);
            n=n/10;
        }
        return isHappy(sum);
    }
}

class Solution {
    public boolean isHappy(int n) {
        int slow=n,fast=n;
        do{
            slow=step(slow);
            fast=step(fast);
            fast=step(fast);
        }while(slow!=fast);
        return slow==1;
    }

    private int step(int n){
        int sum=0;
        while(n!=0){
            sum=sum+(n%10)*(n%10);
            n=n/10;
        }
        return sum;
    }
}

字符串

右旋字符串

右旋字符串 | 代码随想录

对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。

思路：

旋转整个字符串，旋转前n个字符，旋转len-n个字符。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        Integer index=scanner.nextInt();
        String str=scanner.next();
        index=index%str.length();
        char[] arr=str.toCharArray();
        rotate(arr,0,str.length()-1);
        rotate(arr,0,index-1);
        rotate(arr,index,str.length()-1);
        System.out.println(new String(arr));
    }
    public static void rotate(char[] arr,int left,int right){
        while(left<right){
            char temp=arr[left];
            arr[left]=arr[right];
            arr[right]=temp;
            left++;right--;
        }
    }
}

旋转字符串

思路：

找到两个字符串的第一个字符，指针1指向s字符串的首位字符，指针2指向goal字符串“找到的第一个字符” 让两个指针同时朝一个方向移动，指针2移动到最右侧后回到最左侧。在移动的过程中判断两个指针指向的内容是否相等，如果不等，表明字符串goal“找到的第一个字符”不对；然后寻找goal字符串下一个可能的第一个字符，当goal尝试完所有的情况都不对之后，返回结果则为false。但如果指向字符串s的指针能从头走到尾，那表明两个字符串是相等的。

class Solution {
    public boolean rotateString(String s, String goal) {
        if(s.equals(goal)){
            return true;
        }else if(s.length()!=goal.length()){
            return false;
        }
        int start=0;
        //找到第二个字符串中可能的最开始的位置
        for(int second=0;second<goal.length();second++){
            start=0;
            if(goal.charAt(second)!=s.charAt(start)){
                continue;
            }
            //让第一个指针和第二个指针同时往右走，假设第一个指针能走到头，那证明可以
            int temp=second;
            while(start<s.length()){
                //一旦同一时刻，两个指针的内容不同，表明当前找到的second指针是不对的
                if(s.charAt(start)!=goal.charAt(temp)){
                    break;
                }
                start++;temp++;
                //走到最右侧之后再走回来
                if(temp>=goal.length()){
                    temp=0;
                }
            }
            if(start==s.length()){
                return true;
            }
        }
        //所有的second指针都是不对的
        return false;
    }
}

思路2：

大佬的思路

由于每次旋转操作都是将最左侧字符移动到最右侧，因此如果 goal 可由 s 经过多步旋转而来，那么 goal 必然会出现在 s + s 中，即满足 (s + s).contains(goal)，同时为了 s 本身过长导致的结果成立，我们需要先确保两字符串长度相等。

作者：宫水三叶链接：https://leetcode.cn/problems/rotate-string/solutions/1400369/by-ac_oier-bnkx/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

return s.length()==goal.length()&&(s+s).contains(goal);

strStr|indexOf

indexOf

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

暴力解法

class Solution {
    public int strStr(String haystack, String needle) {
        for(int i=0;i<=haystack.length()-needle.length();i++){
            int k=0;
            for(int j=i;j<i+needle.length();j++,k++){
                if(haystack.charAt(j)!=needle.charAt(k)){
                    break;
                }
            }
            if(k==needle.length()){
                return i;
            }
        }
        return -1;
    }
}

KMP

class Solution {
    public int strStr(String haystack, String needle) {
        int[] next=buildNext(needle);
        for(int i=0,j=0;i<haystack.length();i++){
            while(j>0&&haystack.charAt(i)!=needle.charAt(j)){
                //冲突的时候，会去找next数组前一位的值
                j=next[j-1];
            }
            if(haystack.charAt(i)==needle.charAt(j)){
                j++;
            }
            if(j==needle.length()){
                return i-j+1;
            }

        }
        return -1;
    }

    private int[] buildNext(String needle){
        //最长公共前后缀的下一位（或者说最大公共前后缀的位数），初始值为0
        int prefixNext=0;
        int[] next=new int[needle.length()];
        //因为第一个字符串是首尾相继，因此最大公共前后缀的位数就是0.
        next[0]=prefixNext;
        //cur表明是后缀最后一位，即要比较的数
        //比较的逻辑也是先比较next[cur-1]和cur是否相等，相等的话公共前后缀的长度+1，cur的next数组值就是next[cur-1]+1
        //假如不等，就要找到前一位next数组的位置
        //比如aabaaf，假设cur为f的话，比较的就是b和f这两位
        for(int cur=1;cur<needle.length();cur++){
            while(prefixNext>0&&needle.charAt(cur)!=needle.charAt(prefixNext)){
                //这里作何分析？
                //虽然是在构建next数组，但本质上也是一个字符串匹配的过程,比如aabaaf,当b和f比较时，可以视作匹配串是aab，待比较串是aabaaf，b和f冲突了，我们会看aab的next数字的前一位的next数组值，视作不变量
                prefixNext=next[prefixNext-1];
            }
            if(needle.charAt(cur)==needle.charAt(prefixNext)){
                prefixNext++;
            }
            next[cur]=prefixNext;
        }
        return next;
    }
}

重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成，如abababab

暴力算法

暴力算法也有不同的暴力处理

比如我首先想到的是，找到个首字符相等的字符位置j，假设前j个字符为重复子串，循环判断[j,2j][2j,3j]是否和[0,j]相等。如果一旦有不等的，那就找一下可能的子串，当j的位置大于s.length/2时，一定为false。而假设比较完所有区间全部相等，此时j==s.length，返回结果则为false。这种方案我内循环比较的时候使用的是substring，但下面的方案可以算作优化。

假设重复字符串为[x1,x2,x3]，那么在[x1…xn]中，[x7..x9]=[x4..x6]=[x1..x3]，因此假如从j开始，前j个字符串为重复子串,长度为l，那么一旦str[j]!=str[j-l]，那么就为false。就可以找寻下一个j了，当j大于s.length/2时,为false;

public boolean repeatedSubstringPattern(String s) {
        int j=1;
        while(true){
            while(j<s.length()&&s.charAt(0)!=s.charAt(j)){
                        j++;
            }
            if(j>s.length()/2){
                return false;
            }
            int k=0;
            boolean match=true;
            for(k=j;k<s.length();k++){
                //这里需要判断s.length()%j的原因是存在abcabcab的情况
                if(s.length()%j!=0||s.charAt(k)!=s.charAt(k-j)){
                    match=false;
                    break;
                }
            }
            if(match){
                return true;
            }
            j++;
        }
    }

其他神仙方案:

参考力扣题解和代码随想录

字符串为s，假设s+s去掉首位和末位字符后依然包含s，那么就证明是由重复子串构成
可以使用KMP，判断kmp(s+s,s)，但是内循环比较的时候要注意从1到n-2；
KMP 最长公共前缀和最长公共后缀的差即是重复子串：求取结果为： len-next(n-1)