• 中文
    • English
  • 注册
  • 查看作者
  • 7分钟带你细致解析4个Java算法必刷题

    1.两数之和

    给定一个整数数组   和一个整数目标值  ,请你在该数组中找出  和为目标值    的那  两个  整数,并返回它们的数组下标。

    你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

    你可以按任意顺序返回答案。

    示例 1:

    示例 2:

    示例 3:

    提示:

    • 只会存在一个有效答案

    **进阶:**你可以想出一个时间复杂度小于   的算法吗?

    解题

    1.双层循环(时间复杂度  )

    提交截图

    7分钟带你细致解析4个Java算法必刷题

    2.使用对象来装进行判断(时间复杂度  )

    提交截图

    7分钟带你细致解析4个Java算法必刷题

    2.两数相加

    给你两个  非空  的链表,表示两个非负的整数。它们每位数字都是按照  逆序  的方式存储的,并且每个节点只能存储  一位  数字。

    请你将两个数相加,并以相同形式返回一个表示和的链表。

    你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

    示例 1:

    7分钟带你细致解析4个Java算法必刷题

    示例 2:

    示例 3:

    提示:

    • 每个链表中的节点数在范围   内

    • 题目数据保证列表表示的数字不含前导零

    解题(链表)

    提交截图

    7分钟带你细致解析4个Java算法必刷题

    3.无重复字符的最长子串

    给定一个字符串   ,请你找出其中不含有重复字符的  最长子串  的长度。

    示例 1:

    示例 2:

    示例 3:

    提示:

    •  由英文字母、数字、符号和空格组成

    解题

    1.暴力破解(以每个字符串为开头遍历一遍,也就是总共遍历两遍。 )

    提交截图

    7分钟带你细致解析4个Java算法必刷题

    2.贪心算法(将不重复的字符串长度记录等有重复字符串的时候将前面的截取 比对长度记录最大值 从这个字符开始继续前面的操作  )

    2.1 代码

    2.2 代码

    2.3 代码

    提交截图(以上三种的思想和速度差不多)

    7分钟带你细致解析4个Java算法必刷题

    4.最长回文子串

    给你一个字符串  ,找到   中最长的回文子串。

    示例 1:

    示例 2:

    提示:

    •  仅由数字和英文字母组成

    解题

    回文字概述

    从两边向中间,不断比较头尾字符是否相同,也就是对应的内容是否对称。

    7分钟带你细致解析4个Java算法必刷题

    中心扩展方法

    中心扩展方法的思路:

    遍历每一个字符,向两边扩展找到以其为中心的最长回文子串, 最后比较所有的回文字的长度得到最长。

    7分钟带你细致解析4个Java算法必刷题

    回文字也分俩种情况

    一种是奇数

    7分钟带你细致解析4个Java算法必刷题

    一种是偶数

    7分钟带你细致解析4个Java算法必刷题

    实现代码

    提交截图

    7分钟带你细致解析4个Java算法必刷题

    马拉车算法 Manacher

    Manachar算法主要是处理字符串中关于回文串的问题的,它可以在 O(n) 的时间处理出以字符串中每一个字符为中心的回文串半径,由于将原字符串处理成 两倍长度的新串 ,在每两个字符之间 加入一个特定的特殊字符 ,因此原本长度为偶数的回文串就成了以中间特殊字符为中心的 奇数长度的回文串 了。

    如图:我们可以在每个字符间插入”#”,并且为了使得扩展的过程中,到边界后自动结束,在两端分别插入 “^” 和 “$”,两个不可能在字符串中出现的字符,这样中心扩展的时候,判断两端字符是否相等的时候,如果到了边界就一定会不相等,从而出了循环。经过处理,字符串的长度永远都是奇数了。

    7分钟带你细致解析4个Java算法必刷题

    首先我们用一个数组 P 保存从中心扩展的最大个数,而它刚好也是去掉 “#” 的原字符串的总长度。例如下图中下标是 6 的地方。可以看到 P[ 6 ] 等于 5,所以它是从左边扩展 5 个字符,相应的右边也是扩展 5 个字符,也就是 “#c#b#c#b#c#”。而去掉 # 恢复到原来的字符串,变成 “cbcbc”,它的长度刚好也就是 5。

    7分钟带你细致解析4个Java算法必刷题

    求原字符串下标

    用 P 的下标 i 减去 P [ i ],再除以 2 ,就是原字符串的开头下标了。

    例如我们找到 P[ i ] 的最大值为 5 ,也就是回文串的最大长度是 5 ,对应的下标是 6 ,所以原字符串的开头下标是 (6 – 5 )/ 2 = 0 。所以我们只需要返回原字符串的第 0 到 第 (5 – 1)位就可以了。

    求每个 P [ i ]

    接下来是算法的关键了,它充分利用了回文串的对称性。

    我们用 C 表示回文串的中心,用 R 表示回文串的右边半径。所以 R = C + P[ i ] 。C 和 R 所对应的回文串是当前循环中 R 最靠右的回文串。

    让我们考虑求 P [ i ] 的时候,如下图。

    用 i_mirror 表示当前需要求的第 i 个字符关于 C 对应的下标。

    7分钟带你细致解析4个Java算法必刷题

    我们现在要求 P [ i ], 如果是用中心扩展法,那就向两边扩展比对就行了。但是我们其实可以利用回文串 C 的对称性。i 关于 C 的对称点是 i_mirror ,P [ i_mirror ] = 3,所以 P [ i ] 也等于 3 。

    但是有三种情况将会造成直接赋值为 P [ i_mirror ] 是不正确的,下边一一讨论。

    1. 超出了 R

    7分钟带你细致解析4个Java算法必刷题

    当我们要求 P [ i ] 的时候,P [ mirror ] = 7,而此时 P [ i ] 并不等于 7 ,为什么呢,因为我们从 i 开始往后数 7 个,等于 22 ,已经超过了最右的 R ,此时不能利用对称性了,但我们一定可以扩展到 R 的,所以 P [ i ] 至少等于 R – i = 20 – 15 = 5,会不会更大呢,我们只需要比较 T [ R+1 ] 和 T [ R+1 ]关于 i 的对称点就行了,就像中心扩展法一样一个个扩展。

    1. P [ i_mirror ] 遇到了原字符串的左边界

    7分钟带你细致解析4个Java算法必刷题

    此时P [ i_mirror ] = 1,但是 P [ i ] 赋值成 1 是不正确的,出现这种情况的原因是 P [ i_mirror ] 在扩展的时候首先是 “#” == “#” ,之后遇到了 “^”和另一个字符比较,也就是到了边界,才终止循环的。而 P [ i ] 并没有遇到边界,所以我们可以继续通过中心扩展法一步一步向两边扩展就行了。

    1. i 等于了 R

    此时我们先把 P [ i ] 赋值为 0 ,然后通过中心扩展法一步一步扩展就行了。

    考虑 C 和 R 的更新

    就这样一步一步的求出每个 P [ i ],当求出的 P [ i ] 的右边界大于当前的 R 时,我们就需要更新 C 和 R 为当前的回文串了。因为我们必须保证 i 在 R 里面,所以一旦有更右边的 R 就要更新 R。

    7分钟带你细致解析4个Java算法必刷题

    此时的 P [ i ] 求出来将会是 3 ,P [ i ] 对应的右边界将是 10 + 3 = 13,所以大于当前的 R ,我们需要把 C 更新成 i 的值,也就是 10 ,R 更新成 13。继续下边的循环。

    代码

    提交截图

    7分钟带你细致解析4个Java算法必刷题

    动态规划(DP)此处效率过低

    提交截图

    7分钟带你细致解析4个Java算法必刷题

  • 0
  • 0
  • 0
  • 8
  • 请登录之后再进行评论

    登录
  • 任务
  • 实时动态
  • 发布
  • 单栏布局 侧栏位置: