Home

JVM程序计数器

一、先来看看概念

多线程的Java应用程序:为了让每个线程正常工作就提出了程序计数器(Programe Counter Register),每个线程都有自己的程序计数器这样当线程执行切换的时候就可以在上次执行的基础上继续执行,仅仅从一条线程线性执行的角度而言,代码是一条一条的往下执行的,这个时候就是程序计数器;JVM就是通过读取程序计数器的值来决定下一条需要执行的字节码指令,进而进行选择语句、循环、异常处理等;

这个还没看懂的话不要紧,继续往下走咯。

二、简单粗暴的举例

1.生活中的案例

比如老王正在看电影,他看到三十五分钟的时候,突然他的QQ好友给他开视频聊天,这时候肯定打断他看电影了,假设他qq好友和他视频完了,他肯定要接着他那35分钟的进度去继续看,这时候他怎么知道我看到35分钟了?这时候程序计数器就起了作用,他负责管理进度。

是不是略微懂了一点呢?

2.代码层面的案例

将上面的例子转换成代码,是这样的:

A线程正在执行HelloWorld.class的第三十五行。这时候CPU时间片被B线程抢走了,当A线程重新被分配到时间片时,他怎么知道我的class运行到哪了?这时候他可以看程序计数器在哪个位置。

这下总该明白了吧?

三、JVM程序计数器的总结

程序计数器作用不多说了,我个人感觉他是为了多线程而生的,单线程情况下完全不需要他。从案例中不难发现,程序计数器是每个线程独有的,并非线程共享的,所以是线程安全的!

Read more

Spring源码编译

1.基本环境

  • jdk 1.8.241 (必须1.8及以上版本)
  • gradle 6.5

2.spring下载

使用 git 下载 spring-framework

下载地址:spring-framework

2.使用ide 导入spring-framework 源码

4.需要修改个配置 (看到 // 即为需要注释的代码)

4.1 build.gradle

//	apply from: "${rootDir}/gradle/ide.gradle"
...

publishing {
		publications {
			mavenJava(MavenPublication) {
//				artifact docsZip
//				artifact schemaZip
//				artifact distZip
			}
		}
	}

4.2. spring-aspects.gradle

//eclipse.project {
//	natures += "org.eclipse.ajdt.ui.ajnature"
//	buildCommands = [new org.gradle.plugins.ide.eclipse.model.BuildCommand("org.eclipse.ajdt.core.ajbuilder")]
//}

4.3. kotlin-coroutines.gradle

//eclipse {
//	project {
//		buildCommand "org.jetbrains.kotlin.ui.kotlinBuilder"
//		buildCommand "org.eclipse.jdt.core.javabuilder"
//		natures "org.jetbrains.kotlin.core.kotlinNature"
//		natures "org.eclipse.jdt.core.javanature"
//		linkedResource name: "kotlin_bin", type: "2", locationUri: "org.jetbrains.kotlin.core.filesystem:/" + project.name + "/kotlin_bin"
//	}
//	classpath {
//		containers "org.jetbrains.kotlin.core.KOTLIN_CONTAINER"
//	}
//}

修改 .gradle 可手动编译 也可以 选择 auto 自动编译 和maven一样

Read more

深入理解Spring两大特性:IoC和AOP

众所周知,Spring拥有两大特性:IoC和AOP。IoC,英文全称Inversion of Control,意为控制反转。AOP,英文全称Aspect-Oriented Programming,意为面向切面编程。

Spring核心容器的主要组件是Bean工厂(BeanFactory),Bean工厂使用控制反转(IoC)模式来降低程序代码之间的耦合度,并提供了面向切面编程(AOP)的实现。

简单来说,Spring是一个轻量级的控制反转(IoC)和面向切面编程(AOP)的容器框架。

下面,我们简要说明下这两大特性。

 

1. Spring常用注解

在具体介绍IoC和AOP之前,我们先简要说明下Spring常用注解

1、@Controller:用于标注控制器层组件

2、@Service:用于标注业务层组件

3、@Component : 用于标注这是一个受 Spring 管理的组件,组件引用名称是类名,第一个字母小写。可以使用@Component(“beanID”) 指定组件的名称

4、@Repository:用于标注数据访问组件,即DAO组件

5、@Bean:方法级别的注解,主要用在@Configuration和@Component注解的类里,@Bean注解的方法会产生一个Bean对象,该对象由Spring管理并放到IoC容器中。引用名称是方法名,也可以用@Bean(name = “beanID”)指定组件名

6、@Scope(“prototype”):将组件的范围设置为原型的(即多例)。保证每一个请求有一个单独的action来处理,避免action的线程问题。

由于Spring默认是单例的,只会创建一个action对象,每次访问都是同一个对象,容易产生并发问题,数据不安全。

7、@Autowired:默认按类型进行自动装配。在容器查找匹配的Bean,当有且仅有一个匹配的Bean时,Spring将其注入@Autowired标注的变量中。

8、@Resource:默认按名称进行自动装配,当找不到与名称匹配的Bean时会按类型装配。

 

简单点说,就是,能够明确该类是一个控制器类组件的,就用@Controller;能够明确是一个服务类组件的,就用@Service;能够明确该类是一个数据访问组件的,就用@Repository;不知道他是啥或者不好区分他是啥,但是就是想让他动态装配的就用@Component。

@Controller、@Service、@Component、@Repository都是类级别的注解,__如果一个方法也想动态装配,就用@Bean。

当我们想按类型进行自动装配时,就用@Autowired;当我们想按名称(beanID)进行自动装配时,就用@Resource;当我们需要根据比如配置信息等来动态装配不同的组件时,可以用getBean(“beanID”)。__

到这里,如果对这些注解,或是自动装配不太理解,可以继续往下,看完 控制反转(IoC) 内容后再回来理解这里的内容。

 

2. 控制反转(IoC)

控制反转,简单点说,就是创建对象的控制权,被反转到了Spring框架上。

通常,我们实例化一个对象时,都是使用类的构造方法来new一个对象,这个过程是由我们自己来控制的,而控制反转就把new对象的工交给了Spring容器。

《expert ONE-ON-ONE J2EE Development without EJB》第6章中指出

P128

IoC Implementation Strategies

IoC is a broad concept that can be implemented in different ways. There are two main types:

Dependency Lookup: The container provides callbacks to components, and a lookup context.This is the EJB and Apache Avalon approach. It leaves the onus on each component to use container APIs to look up resources and collaborators. The Inversion of Control is limited to the container invoking callback methods that application code can use to obtain resources.

Dependency Injection: Components do no look up; they provide plain Java methods enabling the container to resolve dependencies. The container is wholly responsible for wiring up components, passing resolved objects in to JavaBean properties or constructors. Use of JavaBean properties is called Setter Injection; use of constructor arguments is called Constructor Injection.


P130

The second IoC strategy-Dependency Injection-is usually preferable.

主要意思为:

IoC的主要实现方式有两种:依赖查找、依赖注入。

依赖注入是一种更可取的方式。

那么依赖查找和依赖注入有什么区别呢?

依赖查找,主要是容器为组件提供一个回调接口和上下文环境。这样一来,组件就必须自己使用容器提供的API来查找资源和协作对象,控制反转仅体现在那些回调方法上,容器调用这些回调方法,从而应用代码获取到资源。

依赖注入,组件不做定位查询,只提供标准的Java方法让容器去决定依赖关系。容器全权负责组件的装配,把符合依赖关系的对象通过Java Bean属性或构造方法传递给需要的对象。

2.1 IoC容器

IoC容器:具有依赖注入功能的容器,可以创建对象的容器。IoC容器负责实例化、定位、配置应用程序中的对象并建立这些对象之间的依赖。

2.2 依赖注入

DI,英文全称,Dependency Injection,意为依赖注入。

依赖注入:由IoC容器动态地将某个对象所需要的外部资源(包括对象、资源、常量数据)注入到组件(Controller, Service等)之中。简单点说,就是IoC容器会把当前对象所需要的外部资源动态的注入给我们。

Spring依赖注入的方式主要有四个,基于注解注入方式、set注入方式、构造器注入方式、静态工厂注入方式。推荐使用基于注解注入方式,配置较少,比较方便。

基于注解注入方式

服务层代码

@Service
public class AdminService {
    //code
}

控制层代码

@Controller
@Scope("prototype")
public class AdminController {

    @Autowired
    private AdminService adminService;

    //code
}

@Autowired与@Resource都可以用来装配Bean,都可以写在字段、setter方法上。他们的区别是:

@Autowired默认按类型进行自动装配(该注解属于Spring),默认情况下要求依赖对象必须存在,如果要允许为null,需设置required属性为false,例:@Autowired(required=false)。如果要使用名称进行装配,可以与@Qualifier注解一起使用。

@Autowired
@Qualifier("adminService")
private AdminService adminService; @Resource默认按照名称进行装配(该注解属于J2EE),名称可以通过name属性来指定。如果没有指定name属性,当注解写在字段上时,默认取字段名进行装配;如果注解写在setter方法上,默认取属性名进行装配。当找不到与名称相匹配的Bean时,会按照类型进行装配。但是,name属性一旦指定,就只会按照名称进行装配。 ```java @Resource(name = "adminService") private AdminService adminService;  ```

除此之外,对于一些复杂的装载Bean的时机,比如我们需要根据配置装载不同的Bean,以完成不同的操作,可以使用getBean(“beanID”)的方式来加载Bean。

通过BeanID加载Bean方法如下:

@Component
public class BeanUtils implements ApplicationContextAware {

    private static ApplicationContext applicationContext;

    @Override
    public void setApplicationContext(ApplicationContext applicationContext) {
        if (BeanUtils.applicationContext == null) {
            BeanUtils.applicationContext = applicationContext;
        }
    }

    public static ApplicationContext getApplicationContext() {
        return applicationContext;
    }

    public static Object getBean(String id) throws Exception {
        try {
            return applicationContext.containsBean(id) ? applicationContext.getBean(id) : null;
        } catch (BeansException e) {
            e.printStackTrace();
            throw new Exception("not found bean id: " + id);
        }
    }
}

我们在需要装载Bean的地方调用该方法即可

public class BaseController {

    protected IService loadService(String id) throws Exception {
        IService iService = (IService) BeanUtils.getBean(id);
        if (iService != null) {
            return iService;
        } else {
            throw new Exception("加载Bean错误");
        }
    }
}

3. 面向切面编程(AOP)

面向切面编程(AOP)就是纵向的编程。比如业务A和业务B现在需要一个相同的操作,传统方法我们可能需要在A、B中都加入相关操作代码,而应用AOP就可以只写一遍代码,A、B共用这段代码。并且,当A、B需要增加新的操作时,可以在不改动原代码的情况下,灵活添加新的业务逻辑实现。

在实际开发中,比如商品查询、促销查询等业务,都需要记录日志、异常处理等操作,AOP把所有共用代码都剥离出来,单独放置到某个类中进行集中管理,在具体运行时,由容器进行动态织入这些公共代码。

AOP主要一般应用于签名验签、参数校验、日志记录、事务控制、权限控制、性能统计、异常处理等。

3.1 AOP涉及名词

切面(Aspect):共有功能的实现。如日志切面、权限切面、验签切面等。在实际开发中通常是一个存放共有功能实现的标准Java类。当Java类使用了@Aspect注解修饰时,就能被AOP容器识别为切面。

通知(Advice):切面的具体实现。就是要给目标对象织入的事情。以目标方法为参照点,根据放置的地方不同,可分为前置通知(Before)、后置通知(AfterReturning)、异常通知(AfterThrowing)、最终通知(After)与环绕通知(Around)5种。在实际开发中通常是切面类中的一个方法,具体属于哪类通知,通过方法上的注解区分。

连接点(JoinPoint):程序在运行过程中能够插入切面的地点。例如,方法调用、异常抛出等。Spring只支持方法级的连接点。一个类的所有方法前、后、抛出异常时等都是连接点。

切入点(Pointcut):用于定义通知应该切入到哪些连接点上。不同的通知通常需要切入到不同的连接点上,这种精准的匹配是由切入点的正则表达式来定义的。

比如,在上面所说的连接点的基础上,来定义切入点。我们有一个类,类里有10个方法,那就产生了几十个连接点。但是我们并不想在所有方法上都织入通知,我们只想让其中的几个方法,在调用之前检验下入参是否合法,那么就用切点来定义这几个方法,让切点来筛选连接点,选中我们想要的方法。切入点就是来定义哪些类里面的哪些方法会得到通知。

目标对象(Target):那些即将切入切面的对象,也就是那些被通知的对象。这些对象专注业务本身的逻辑,所有的共有功能等待AOP容器的切入。

代理对象(Proxy):将通知应用到目标对象之后被动态创建的对象。可以简单地理解为,代理对象的功能等于目标对象本身业务逻辑加上共有功能。代理对象对于使用者而言是透明的,是程序运行过程中的产物。目标对象被织入共有功能后产生的对象。

织入(Weaving):将切面应用到目标对象从而创建一个新的代理对象的过程。这个过程可以发生在编译时、类加载时、运行时。Spring是在运行时完成织入,运行时织入通过Java语言的反射机制与动态代理机制来动态实现。

3.2 Pointcut用法

Pointcut格式为:

execution(modifier-pattern? ret-type-pattern declaring-type-pattern? name-pattern(param-pattern) throws-pattern?)

修饰符匹配 modifier-pattern? 例:public private

返回值匹配 ret-type-pattern 可以用 * 表示任意返回值

类路径匹配 declaring-type-pattern? 全路径的类名

方法名匹配 name-pattern 可以指定方法名或者用 * 表示所有方法;set* 表示所有以set开头的方法

参数匹配 (param-pattern) 可以指定具体的参数类型,多个参数用“,”分隔;可以用 * 表示匹配任意类型的参数;可以用 (..) 表示零个或多个任意参数

异常类型匹配throws-pattern? 例:throws Exception

其中后面跟着 ? 表示可选项

例:

@Pointcut("execution(public * cn.wbnull. springbootdemo.controller.*.*(..))")
private void sign() {

}

 

3.3 一个例子

以 Spring Boot入门:使用AOP实现拦截器 中的AOP为例

@Aspect
@Component
public class SignAop {

}

SignAop类使用了@Aspect注解,则该类可以被AOP容器识别为切面。

 

@Aspect
@Component
public class SignAop {

    @Pointcut("execution(public * cn.wbnull.springbootdemo.controller.*.*(..))")
    private void signAop() {

    }
}

@Pointcut声明一个切入点,范围为controller包下所有的类的所有方法

注:作为切入点签名的方法必须返回void类型

 

@Aspect
@Component
public class SignAop {

    @Pointcut("execution(public * cn.wbnull.springbootdemo.controller.*.*(..))")
    private void signAop() {

    }

    @Before("signAop()")
    public void doBefore(JoinPoint joinPoint) throws Exception {
        //code
       }

    @AfterReturning(value = "signAop()", returning = "params")
    public JSONObject doAfterReturning(JoinPoint joinPoint, JSONObject params) {
        //code
        }
}

doBefore()方法使用@Before(“signAop()”)注解,表示前置通知(在某连接点之前执行的通知),但这个通知不能阻止连接点之前的执行流程,除非它抛出一个异常。

doAfterReturning()方法使用@AfterReturning(value = “signAop()”, returning = “params”)注解,表示后置通知(在某连接点正常完成后执行的通知),通常在一个匹配的方法返回的时候执行。

实际运行时,在进入controller包下所有方法前,都会进入doBefore()方法,在controller包下方法执行完成后,都会进入doAfterReturning()方法。

Read more

Shiro框架中有三个核心概念:Subject ,SecurityManager和Realms

2.1.1    Subject

Subject 一词是一个安全术语,其基本意思是“当前的操作用户”。称之为“用户”并不准确,因为“用户”一词通常跟人相关。在安全领域,术语“Subject”可以是人,也可以是第三方进程、后台帐户(Daemon Account)、定时作业(Corn Job)或其他类似事物。它仅仅意味着“当前跟软件交互的东西”。但考虑到大多数目的和用途,你可以把它认为是 Shiro 的“用户”概念。 在程序中你都能轻易的获得 Subject ,允许在任何需要的地方进行安全操作。每个 Subject 对象都必须与一个 SecurityManager 进行绑定,你访问Subject对象其实都是在与 SecurityManager 里的特定 Subject 进行交互。

22.1.2    SecurityManager

Subject 的“幕后”推手是 SecurityManager Subject 代表了当前用户的安全操作,SecurityManager 则管理所有用户的安全操作。它是Shiro框架的核心,充当“保护伞”,引用了多个内部嵌套安全组件,它们形成了对象图。但是,一旦 SecurityManager 及其内部对象图配置好,它就会退居幕后,应用开发人员几乎把他们的所有时间都花在Subject API调用上。 那么,如何设置SecurityManager呢?嗯,这要看应用的环境。例如,Web应用通常会在Web.xml中指定一个Shiro Servlet Filter,这会创建SecurityManager实例,如果你运行的是一个独立应用,你需要用其他配置方式,但有很多配置选项。 一个应用几乎总是只有一个 SecurityManager 实例。它实际是应用的Singleton(尽管不必是一个静态Singleton)。跟Shiro里的几乎所有组件一样,SecurityManager 的缺省实现是POJO,而且可用POJO兼容的任何配置机制进行配置 - 普通的Java代码、Spring XML、YAML、.properties和.ini文件等。基本来讲,能够实例化类和调用JavaBean兼容方法的任何配置形式都可使用。

22.1.3    Realms

Shiro的第三个也是最后一个概念是RealmRealm充当了Shiro与应用安全数据间的“桥梁”或者“连接器”。也就是说,当与像用户帐户这类安全相关数据进行交互,执行认证(登录)和授权(访问控制)时,Shiro会从应用配置的Realm中查找很多内容。 从这个意义上讲,Realm实质上是一个安全相关的DAO:它封装了数据源的连接细节,并在需要时将相关数据提供给Shiro。当配置Shiro时,你必须至少指定一个Realm,用于认证和(或)授权。配置多个Realm是可以的,但是至少需要一个。 Shiro内置了可以连接大量安全数据源(又名目录)的Realm,如LDAP、关系数据库(JDBC)、类似INI的文本配置资源以及属性文件 等。如果缺省的Realm不能满足需求,你还可以插入代表自定义数据源的自己的Realm实现。 象其他内部组件一样,由SecurityManager来管理如何使用Realms来获取安全的身份数据。

Read more

shiro 中 AuthorizingRealm 的执行时机

1.doGetAuthenticationInfo执行时机如下

当调用Subject currentUser = SecurityUtils.getSubject();

currentUser.login(token);

2.doGetAuthorizationInfo执行时机有三个,如下:

  1. subject.hasRole(“admin”) 或 subject.isPermitted(“admin”):自己去调用这个是否有什么角色或者是否有什么权限的时候;

  2. @RequiresRoles(“admin”) :在方法上加注解的时候;

  3. [@shiro.hasPermission name = “admin”][/@shiro.hasPermission]:在页面上加shiro标签的时候,即进这个页面的时候扫描到有这个标签的时候。

Read more

什么是双亲委派机制

当某个类加载器需要加载某个.class文件时,它首先把这个任务委托给他的上级类加载器,递归这个操作,如果上级的类加载器没有加载,自己才会去加载这个类。

类加载器的类别

BootstrapClassLoader(启动类加载器)

c++编写,加载java核心库 java.*,构造ExtClassLoader和AppClassLoader。由于引导类加载器涉及到虚拟机本地实现细节,开发者无法直接获取到启动类加载器的引用,所以不允许直接通过引用进行操作

ExtClassLoader (标准扩展类加载器)

java编写,加载扩展库,如classpath中的jre ,javax.*或者 java.ext.dir 指定位置中的类,开发者可以直接使用标准扩展类加载器。

AppClassLoader(系统类加载器)

java编写,加载程序所在的目录,如user.dir所在的位置的class

CustomClassLoader(用户自定义类加载器)

java编写,用户自定义的类加载器,可加载指定路径的class文件

源码分析

protected Class<?> loadClass(String name, boolean resolve)
            throws ClassNotFoundException
    {
        synchronized (getClassLoadingLock(name)) {
            // 首先检查这个classsh是否已经加载过了
            Class<?> c = findLoadedClass(name);
            if (c == null) {
                long t0 = System.nanoTime();
                try {
                    // c==null表示没有加载,如果有父类的加载器则让父类加载器加载
                    if (parent != null) {
                        c = parent.loadClass(name, false);
                    } else {
                        //如果父类的加载器为空 则说明递归到bootStrapClassloader了
                        //bootStrapClassloader比较特殊无法通过get获取
                        c = findBootstrapClassOrNull(name);
                    }
                } catch (ClassNotFoundException e) {}
                if (c == null) {
                    //如果bootstrapClassLoader 仍然没有加载过,则递归回来,尝试自己去加载class
                    long t1 = System.nanoTime();
                    c = findClass(name);
                    sun.misc.PerfCounter.getParentDelegationTime().addTime(t1 - t0);
                    sun.misc.PerfCounter.getFindClassTime().addElapsedTimeFrom(t1);
                    sun.misc.PerfCounter.getFindClasses().increment();
                }
            }
            if (resolve) {
                resolveClass(c);
            }
            return c;
        }
    }

委派机制的流程图

pic1

双亲委派机制的作用

1、防止重复加载同一个.class。通过委托去向上面问一问,加载过了,就不用再加载一遍。保证数据安全。 2、保证核心.class不能被篡改。通过委托方式,不会去篡改核心.clas,即使篡改也不会去加载,即使加载也不会是同一个.class对象了。不同的加载器加载同一个.class也不是同一个Class对象。这样保证了Class执行安全。

Read more

238. 除自身以外数组的乘积

  • 难度中等
  • 本题涉及算法
  • 思路乘积 = 左边乘积 * 右边乘积
  • 类似题型:

题目 238. 除自身以外数组的乘积

给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。  

示例:

输入: [1,2,3,4]     
输出: [24,12,8,6]

提示:题目数据保证数组之中任意元素的全部前缀元素和后缀(甚至是整个数组)的乘积都在 32 位整数范围内。

说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。

进阶:
你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)

方法一 乘积 = 左边乘积 * 右边乘积

  • 解题思路
    • 第一印象,想用除法,$(所有数乘积/nums[i])$ ,同时需要对 0 做判断;
    • 第二印象,想试试滑动窗口,但是复杂度会变成 $n^2$;
    • 沿着滑动窗口的思路,改良下得出 乘积 = 当前数左边的乘积 * 当前数右边的乘积
  • 复杂度分析
    • 时间复杂度:$O(n)$, $n$ 代表数组的长度
    • 空间复杂度:$O(1)$, 排除返回数组空间为 $n$

java

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length]; // 初始化长度为 nums.length 的数组
        int r = 1; // 右边的乘积
        for(int i=nums.length-1;i>=0;i--) {
            r *= nums[i];
            res[i] = r;
        }
        int l = 1; //左边的乘积
        for(int i = 0;i<nums.length-1;i++) {
            res[i] = l * res[i+1];
            l *= nums[i];
        }
        res[nums.length-1] = l;
        return res;

    }
}

python

class Solution(object):
    def productExceptSelf(self, nums):
        res = [1] * len(nums) # 初始化长度为 le(nums) 的数组
        r = 1 # 右边的乘积
        for i in range(len(nums)-1,-1,-1):
            r *= nums[i]
            res[i] = r

        l = 1 # 左边的乘积
        for i in range(len(nums)-1):
            res[i] = res[i+1] * l
            l *= nums[i]
        res[-1] = l
        return res

Read more

28. 实现 strStr()


题目 28. 实现 strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回  -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明:

当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

方法一 滑动窗口

  • 解题思路
    • 这种字符串或数组中,进行比较或者找子集,很容易使用 使用活动窗口很容易解决 (KMP我不懂阿)
  • 复杂度分析
    • 时间复杂度:$O(H-N+1)$, $H$ 是 haystack 的长度, $N$ 是 needle 的长度
    • 空间复杂度:$O(1)$。

python

class Solution(object):
    def strStr(self, haystack, needle):
        # 滑动窗口
        ans = -1
        haystack_len = len(haystack)
        needle_len = len(needle)
        if needle_len == 0:
            return 0
        if needle_len > haystack_len:
            return ans
        for i in range(haystack_len - needle_len + 1):
            if haystack[i:i+needle_len] == needle:
                ans = i
                break
        return ans

Read more