o reilly的java编程基础系列

科技前沿 • 2024-12-30 09:51 • 阅读 124

大家好，我是讯享网，很高兴认识大家。

reverse words in a string

leetcode 151

assume the space complexity is O(1)

erase time complexity is O(n)

String.trim() O(n)

String.split("\s+") O(n)

StringBuild.append O(1)

StringBuilder.charAt()

StringBuilder to String => sb.toString()

SB to Array => sb.toCharArray()

in java, have to use String Builder, because we cannot directly change the original String in Java

讯享网

Right rotate a string

kamacoder.com 55

assume we can only use O(1) space, but in java we cannot do any changes in the original array

in other languages, we can use the methods:

full reversal + partial reversal

Details:

1. String to Int: Integer.parseInt(String)

2. public static void main(String[] args)

3. Scanner sc = new Scanner(System.in);

dont forget the content inside the parentheses.

4. If you want to call other methods from the method without creating an instance of the class, those methods must also be

讯享网

KMP Algorithm

leetcode 28 Find the Index of the First Occurrence in a String

prefix table：就是求最长相等前后缀

kmp algorithm, we have to construct the next array

i: end of the prefix

j: end of the suffix

directly check the video for kmp algorithm, it is hard to understand this answer directly

time complexity O(m + n)

Repeated substring pattern

leetcode 459

核心：最长相等前后缀不包含的子串是字符串s的最小重复子串

最长相等先后缀是什么？

example：

ababab

prefix: abab

suffix: o reilly的java编程基础系列 abab

前后缀相等！

prefix: 一定包含首字母，不包含尾字母

suffix：一定包含尾字母，不包含首字母

next数组，最后一个元素next[next.length - 1]就是最长相等前后缀

然后判断原字符串是否可以整除不包含的字串，可以整除的话就是ok

讯享网

要注意j回退不是j--回退，而是 j= next[j - 1]这样回退

o reilly的java编程基础系列

reverse words in a string

Right rotate a string

KMP Algorithm

Repeated substring pattern

相关推荐