方法下面小编就为大家带来一篇Java算法的一道练习题(分享)。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧，希望可以帮到你
题目描述
字符串的排列
难度：中等
给你两个字符串 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 0，就是当前窗口右端碰到的的是需要的字符 while (r 0) { //更新所需的字符个数 need[s2.charAt(r) - 'a']--; //扩大窗口范围 r++; } //找到所符合的个数了，就是需要的子串已经找到了 if <strong style="color:transparent">来源gao@daima#com搞(%代@#码@网</strong>(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 0，就是当前窗口右端碰到的的是需要的字符 while (r 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 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; } }
总结
本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注gaodaima搞代码网的更多内容！
以上就是Java算法练习题,每天进步一点点(1)的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：Java算法练习题,每天进步一点点(1)
转载请注明原文链接：Java算法练习题,每天进步一点点(1)
