Java算法练习题,每天进步一点点(1)

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 (Arrahttp://ys.equals(num1, num2)) {

return true;

}

}

return false;

}

}

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。