Java算法練習題,每天進步一點點(1)
題目描述
字符串的排列
難度:中等
給你兩個字符串 s1 和 s2 ,寫一個函數來判斷 s2 是否包含 s1 的排列。
換句話說,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的排列,所白瞭就是隻要是連續包含s1的字符就行,不考慮順序。
解題思路:
滑動窗口思想,來個need數組,來存所需的字符,同時定義l和r兩個指針,不斷右移右指針,同時更新need數組,如果符合情況就返回true,不符合繼續移動窗口,最後還找不到符合的就返回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; } //創建個need數組,表示所需要的字符以及個數,通過遍歷s1的得到 int[] need = new int[26]; for (int i = 0; i < l1; i++) { need[s1.charAt(i) - 'a']++; } //滑動窗口 int l = 0, r = 0; //如果l=l2-l1就可以停瞭,後面的長度都不夠瞭 while (l <= l2 - l1) { //如果符合條件,即need[s2.charAt(r) - 'a'] > 0,就是當前窗口右端碰到的的是需要的字符 while (r < l + l1 && need[s2.charAt(r) - 'a'] > 0) { //更新所需的字符個數 need[s2.charAt(r) - 'a']--; //擴大窗口范圍 r++; } //找到所符合的個數瞭,就是需要的子串已經找到瞭 if (r == l + l1) { return true; } //移動左窗口,這樣左邊的字符從窗口中退出來瞭,就需要把need[s2.charAt(l) - 'a']++,維護need need[s2.charAt(l) - 'a']++; //移動左邊的指針 l++; } return false; } }
完整代碼【含測試代碼和三種解決方案】
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; } //創建個need數組,表示所需要的字符以及個數,通過遍歷s1的得到 int[] need = new int[26]; for (int i = 0; i < l1; i++) { need[s1.charAt(i) - 'a']++; } //滑動窗口 int l = 0, r = 0; //如果l=l2-l1就可以停瞭,後面的長度都不夠瞭 while (l <= l2 - l1) { //如果符合條件,即need[s2.charAt(r) - 'a'] > 0,就是當前窗口右端碰到的的是需要的字符 while (r < l + l1 && need[s2.charAt(r) - 'a'] > 0) { //更新所需的字符個數 need[s2.charAt(r) - 'a']--; //擴大窗口范圍 r++; } //找到所符合的個數瞭,就是需要的子串已經找到瞭 if (r == l + l1) { return true; } //移動左窗口,這樣左邊的字符從窗口中退出來瞭,就需要把need[s2.charAt(l) - 'a']++,維護need need[s2.charAt(l) - 'a']++; //移動左邊的指針 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; } }
總結
本篇文章就到這裡瞭,希望能給你帶來幫助,也希望您能夠多多關註WalkonNet的更多內容!
推薦閱讀:
- java數組算法例題代碼詳解(冒泡排序,選擇排序,找最大值、最小值,添加、刪除元素等)
- Java中如何正確重寫equals方法
- Java日常練習題,每天進步一點點(64)
- java版十大排序經典算法:完整代碼(4)
- 一文告訴你為什麼要重寫hashCode()方法和equals()方法