快捷導(dǎo)航

Java算法練習(xí)題,每天進(jìn)步一點(diǎn)點(diǎn)(1)

更新時(shí)間：2021年07月30日 08:59:16 作者：牛哄哄的柯南

方法下面小編就為大家?guī)?lái)一篇Java算法的一道練習(xí)題(分享)。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧，希望可以幫到你

題目描述

字符串的排列

難度：中等

給你兩個(gè)字符串 s1 和 s2 ，寫一個(gè)函數(shù)來(lái)判斷 s2 是否包含 s1 的排列。

換句話說(shuō)，s1 的排列之一是 s2 的子串。

示例 1：

輸入：s1 = “ab” s2 = “eidbaooo”

輸出：true

解釋：s2 包含 s1 的排列之一 (“ba”).

示例 2：

輸入：s1= “ab” s2 = “eidboaoo”

輸出：false

提示：

1 <= s1.length, s2.length <= 104

s1 和 s2 僅包含小寫字母

解題思路

題目大意：就是看字符串s2是否包含s1的排列，所白了就是只要是連續(xù)包含s1的字符就行，不考慮順序。

解題思路：
滑動(dòng)窗口思想，來(lái)個(gè)need數(shù)組，來(lái)存所需的字符，同時(shí)定義l和r兩個(gè)指針，不斷右移右指針，同時(shí)更新need數(shù)組，如果符合情況就返回true，不符合繼續(xù)移動(dòng)窗口，最后還找不到符合的就返回false。

代碼

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int l1 = s1.length();
        int l2 = s2.length();
        if (l1 > l2 || "".equals(s1) || "".equals(s2)) {
            return false;
        }
        //創(chuàng)建個(gè)need數(shù)組，表示所需要的字符以及個(gè)數(shù)，通過(guò)遍歷s1的得到
        int[] need = new int[26];
        for (int i = 0; i < l1; i++) {
            need[s1.charAt(i) - 'a']++;
        }
        //滑動(dòng)窗口
        int l = 0, r = 0;
        //如果l=l2-l1就可以停了，后面的長(zhǎng)度都不夠了
        while (l <= l2 - l1) {
            //如果符合條件，即need[s2.charAt(r) - 'a'] > 0，就是當(dāng)前窗口右端碰到的的是需要的字符
            while (r < l + l1 && need[s2.charAt(r) - 'a'] > 0) {
                //更新所需的字符個(gè)數(shù)
                need[s2.charAt(r) - 'a']--;
                //擴(kuò)大窗口范圍
                r++;
            }
            //找到所符合的個(gè)數(shù)了，就是需要的子串已經(jīng)找到了
            if (r == l + l1) {
                return true;
            }
            //移動(dòng)左窗口，這樣左邊的字符從窗口中退出來(lái)了，就需要把need[s2.charAt(l) - 'a']++，維護(hù)need
            need[s2.charAt(l) - 'a']++;
            //移動(dòng)左邊的指針
            l++;
        }
        return false;
    }
}

完整代碼【含測(cè)試代碼和三種解決方案】

package com.keafmd.Likou.Day0729;
import java.util.Arrays;
import java.util.HashMap;
/**
 * Keafmd
 *
 * @ClassName: StringArrangement
 * @Description: https://leetcode-cn.com/problems/permutation-in-string/
 * @author: 牛哄哄的柯南
 * @date: 2021-07-29 9:11
 */
public class StringArrangement {
    public static void main(String[] args) {
        String s1 = "hello", s2 = "ooolleooolleh";
        boolean b = new StringArrangementSolution().checkInclusion(s1, s2);
        System.out.println(b);
    }
}
class StringArrangementSolution {
    public boolean checkInclusion(String s1, String s2) {
        int l1 = s1.length();
        int l2 = s2.length();
        if (l1 > l2 || "".equals(s1) || "".equals(s2)) {
            return false;
        }
        //創(chuàng)建個(gè)need數(shù)組，表示所需要的字符以及個(gè)數(shù)，通過(guò)遍歷s1的得到
        int[] need = new int[26];
        for (int i = 0; i < l1; i++) {
            need[s1.charAt(i) - 'a']++;
        }
        //滑動(dòng)窗口
        int l = 0, r = 0;
        //如果l=l2-l1就可以停了，后面的長(zhǎng)度都不夠了
        while (l <= l2 - l1) {
            //如果符合條件，即need[s2.charAt(r) - 'a'] > 0，就是當(dāng)前窗口右端碰到的的是需要的字符
            while (r < l + l1 && need[s2.charAt(r) - 'a'] > 0) {
                //更新所需的字符個(gè)數(shù)
                need[s2.charAt(r) - 'a']--;
                //擴(kuò)大窗口范圍
                r++;
            }
            //找到所符合的個(gè)數(shù)了，就是需要的子串已經(jīng)找到了
            if (r == l + l1) {
                return true;
            }
            //移動(dòng)左窗口，這樣左邊的字符從窗口中退出來(lái)了，就需要把need[s2.charAt(l) - 'a']++，維護(hù)need
            need[s2.charAt(l) - 'a']++;
            //移動(dòng)左邊的指針
            l++;
        }
        return false;
    }
}
class StringArrangementSolution2 {
    public boolean checkInclusion(String s1, String s2) {
        int l1 = s1.length();
        int l2 = s2.length();
        if (s1 == null || s2 == null || l1 > l2 || s1 == "" || s2 == "") {
            return false;
        }
        int[] need = new int[26];
        for (int i = 0; i < l1; i++) {
            need[s1.charAt(i) - 'a']--;
        }
        int l = 0, r = 0;
        int count = 0;
        while (r < l2) {
            int x = s2.charAt(r) - 'a';
            need[x]++;
            while (need[x] > 0) {
                need[s2.charAt(l) - 'a']--;
                l++;
            }
            if (r - l + 1 == l1) {
                return true;
            }
            r++;
        }
        return false;
    }
}

class StringArrangementSolution1 {
    public boolean checkInclusion(String s1, String s2) {
        int l1 = s1.length();
        int l2 = s2.length();
        if (s1 == null || s2 == null || l1 > l2 || s1 == "" || s2 == "") {
            return false;
        }
        int[] num1 = new int[26];
        int[] num2 = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            num1[s1.charAt(i) - 'a']++;
            num2[s2.charAt(i) - 'a']++;
        }
        if (Arrays.equals(num1, num2)) {
            return true;
        }

        int l = 0, r = 0;
        int count = 0;
        for (int i = l1; i < l2; i++) {
            num2[s2.charAt(i) - 'a']++;
            num2[s2.charAt(i - l1) - 'a']--;
            if (Arrays.equals(num1, num2)) {
                return true;
            }
        }
        return false;
    }
}