个人中心
gpt4 book ai didi

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

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 26 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章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.

代码

  。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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 ;
     }
}

完整代码【含测试代码和三种解决方案】 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
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 ;
     }
}

总结

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

原文链接：https://blog.csdn.net/weixin_43883917/article/details/119219733 。

最后此篇关于Java算法练习题,每天进步一点点(1)的文章就讲到这里了,如果你想了解更多关于Java算法练习题,每天进步一点点(1)的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

26 4 0
文章推荐： Java8中List转Map(Collectors.toMap) 的技巧分享
文章推荐： iOS关于多张图片上传、地址返回顺序问题及解决方案
文章推荐： 动漫很卡哇伊的二次元可爱卡通头像最新 夏天温柔的晚风一定能吹散很多不愉快
文章推荐： iOS中如何使用iconfont图标实例详解
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com