1 | 给定一个二维网格和一个单词,找出该单词是否存在于网格中。 |
主要思路
本题本质上还是回溯算法的运用,啊啊啊啊,回溯好难啊,今天的卡点在于怎么正确的在回溯过程中设置返回值,有进步的在于整体思路还是没得问题,重点在于返回值的确定,多刷题,多看吧
技巧:利用二维偏移量数组来简化代码
1 | class Solution { |
1 | 给定一个二维网格和一个单词,找出该单词是否存在于网格中。 |
主要思路
本题本质上还是回溯算法的运用,啊啊啊啊,回溯好难啊,今天的卡点在于怎么正确的在回溯过程中设置返回值,有进步的在于整体思路还是没得问题,重点在于返回值的确定,多刷题,多看吧
技巧:利用二维偏移量数组来简化代码
1 | class Solution { |
1 | 给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 |
此题目的
学会熟练使用java中字符串中的一些操作API函数,例如本题的spilt,trim函数等,此外,String类以及字符串都不提供反转操作,但StringBuffer中有此操作,所以可以转换成StringBuffer再转成String
1 | class Solution { |
1 | 给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。 |
主要思路:
本题是KMP算法的一种运用,利用Next数组解题法宝,利用KMP求解最长回文前缀
例如abc这个字符串,前缀加上cba,由于a一个字符可以看作是回文的,所以我们删除a,只用加上cb构成cbabc这个最短的回文字符串,再比如cbjbcb这个字符串,先反转得到bcbjbc,由于cbjbc本身就是回文的,反转后还是本身,所以这个删除两个字符串重叠的部分,得到bcbjbcb这个最短的回文子串
继续分析,其实我们就是求s的最长回文前缀,那么我们怎么求解这个最长回文前缀呢?
我们将s反转后s的前缀将会变成后缀,所以我们将s和s的反转字符串拼在一起,就是寻找这个新字符串的最长公共前后缀,然后return reverse删除公共部分+s原字符串即为答案
tips: 这里我们在拼接两个字符串时,加了一个‘#’号,如果不加,例如aaa这种情况,拼接后变成aaaaaa,利用KMP求得为6,其实最长回文前缀为3,可以有效防止此类特殊情况出现
1 | public class ShortestPalindrome { |
这是我第三次再次尝试学习KMP算法,以前总觉得是一个拦路虎,面对比我整个人还长的文章长度直接劝退,当再次遇到KMP后,痛定思痛下定决心来学习KMP算法,现在回头来看,只要静下心来对于聪明的你来说,一定不是难题
按照惯例,我们先来看一下暴力匹配是如何工作的
如下图所示我们利用双指针,i指向模板链的头部,j指向目标链的头部,开始逐个遍历是否相等,当不相等时,我们会令i回溯到i-j+1即模板链的下一个位置,j回溯到目标链的开头,重新开始匹配
当完全匹配时返回目标链在模板链中的位置
1 | public int bfSearch(String s1,String s2){ |
在上述的暴力算法中,当目标链和模板链失配时,i会回溯到下一个位置再重新匹配,时间效率非常底下,那我们有没有办法不让i去回溯,只令指针j去移动目标链,这就是KMP算法的精髓所在,在KMP算法中我们利用部分匹配表,next数组来确定下一次j移动的位置
这也正是KMP算法的核心,部分匹配表
下面我们来解释一下什么是部分匹配表,例如字符串”abababca”的匹配表如下
例如:
index等于3对应的value值为2,表示以index等于3之前的字符串“abab”最长的公共前缀和后缀的长度
abab的前缀有a,ab,aba(不包括自身),后缀有b,ab,bab,最长公共部分ab长度为2,所以index=3位置对应的value为2,其他部分同理
了解了什么是部分匹配表,那么如何用部分比配表来加速匹配呢
如图所示,当失配时,我们发现只有最后一位是失配的,如果暴力解将i回溯会浪费大量的时间,此处我们利用next数组来是i的指针不发生回溯,只移动j指针,下面我们来分析利用next数组下一次将会移动到什么位置
如果指针能移动到_和D的对比处说明D之前的字符是匹配的,所以括号括起来的位置是相等的,又因为在目标链中,AB恰巧有一个相同的前缀AB,那么说明目标链的前缀和模板链的AB是相等的
即斜体下划线处不用再比较了,所以直接将目标链移动到如下位置
所以我们将这个过程通解化,即主字符串中i指针之前的 PMT[j −1] 位就一定与模式字符串的第 0 位至第 PMT[j−1] 位是相同的,保持i指针不动,然后将j指针指向模式字符串的PMT[j −1]位即可
为了利于程序的编写,我们将PMT数组做一些优化
我们发现,当字符失配时,影响j指针移动的是next[j-1],所以我们将next数组整体后移一位,并将next[0]默认值设为-1,为什么设为-1呢?
如图所示我们再首位就发现失配了,按照规则我们无法移动j指针,此时我们只能移动i指针去继续匹配,当我们执行i++,j++代码后,i后移,j不变,实现移动i指针
所以KMP的代码就呼之欲出了,此处我们假设next数组已知,下文中我们将解释如何求解
1 | public int KMP(String s1,String s2) { |
那么next数组应该怎么求呢?
我们使用错位法来求解,接下来我们将以字符串“abababca”来讲解如何求next数组
我们错开后可以看作i瞄准的是字符串的后缀(因为后缀不包括自身),同理j瞄准的就是前缀,前后缀的公共部分就是next的值,这个过程也可以看作是KMP的求解过程,其中我们要注意因为我们将next数组后移了一位,所以next[2]看的是i=1处的最长公共字串




1 | public static void getNext(int[] next,String s) { |
至此,KMP算法结束!!!!!!!!!!!!
1 | 给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。 |
首先我们先明白一个概念,什么是欧拉图,什么是欧拉路径
欧拉路径: 图M中一条路径能够经过图的每一条边,每一条边有且仅通过一次
欧拉回路: 就是一条封闭的欧拉路径
欧拉图: 含有欧拉回路的图
有向图欧拉图:
欧拉路径:有一个点出度比入度多1(起点),有一个点入度比出度多1(终点),其余点出度等于入度;
欧拉回路:每个顶点出度等于入度;
无向图欧拉图:
欧拉路径:有且仅有两个点的入度为1,分别是起点和终点;
欧拉回路:图中所有顶点的度数都是偶数,并且该图是连通图;
主要思路:
本体的题意表明至少存在一条欧拉路径,当存在多条欧拉路径时,我们输出字典序最小的哪一条路径,为了保证最终的结果是字典序最小的路径,我们贪心的去选择下一次目的地。
1.从题目中给定的“JFK”为起点开始遍历整张图
2.接下来我们dfs遍历这些节点的邻接节点,并且将已经遍历过的边给删除
3.当我们使一个节点没有邻接边时,说明此点已经进入死胡同,那么我们将其加入到结果集中
4.随着递归的出栈就能的到一道“JDK”为起点的欧拉路径
所用的数据结构
由于map中的key可能对应多个值,且这些值明显的具有字典序,那么我们使用优先队列,优先队列默认是小顶堆,poll出堆顶字典序最小的元素,很明显复合我们这个题目的要求
具体代码
1 | class Solution { |
1 | 给定一个仅包含数字2-9的字符串,返回所有它能表示的字母组合。 |
主要思路:
类似于这种回溯排列问题都有固定的模板,难点在于书写搜索范围,本题思路与递增子序列问题大同小异,我们用map存放数字映射的字母,具体代码如下:
1 | class Solution { |
1 | 给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。 |
主要思路:
本题主要考察回溯算法的理解,类似于全排列的思路,根据题目进行剪枝,最主要是如何去重,因为数组中存在重复的数字所以在选择的过程中可能会出现重复的子序列,所以根据去重的思路我们主要分为两种,关于选数的分递归可以用for循环和选与不选两种思路,此处我们Set方法用for循环,剪枝用选与不选的方法
一、Set去重
1 | class Solution { |
二、剪枝去重
那如何保证没有重复呢?我们需要给「不选择」做一个限定条件,只有当当前的元素不等于上一个选择的元素的时候,才考虑不选择当前元素,直接递归后面的元素。因为如果有两个相同的元素,我们会考虑这样四种情况:
前者被选择,后者被选择
前者被选择,后者不被选择
前者不被选择,后者被选择
前者不被选择,后者不被选择
其中第二种情况和第三种情况其实是等价的,我们这样限制之后,舍弃了第二种,保留了第三种,于是达到了去重的目的。
1 | class Solution { |
1 | 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 |
主要思路:
这是一道经典且入门级的回溯算法题目,实质就是利用递归来实现遍历的效果,回溯的过程体现在如何去撤销选择,使状态恢复到上一次递归之前,回溯的另一重要特性就是剪枝,通过剪枝优化算法,是的遍历的次数减少,这在以后的刷题中慢慢会理解的更深,还有对java值传递的特性一步更深的理解
1 | public static List<List<Integer>> permute(int[] nums) { |
今天是8.24日,距离大二开学还有3天的时间,总觉得自己要有点压迫力才能去认真学习,来自同龄人的压力,来自将来马上步入社会,离开象牙塔的压力
总觉得自己能做成一番事件,自学对自己来说并不是一项挑战,但混乱的学习路线,悠然悠然的学习进度,还有来自大学无用的课程设置,总让自己心烦意乱,害呀,心好烦啊,所以开设此学习目标的子博客,督促自己完成近期目标
九月目标
1.()8.27-9.11完成期末考试,期间不要被室友的压力而心慌意乱,每天一到leetcode,目前73题,考试结束前必须达到90题
2.()9.11-9.13完成剩余的jdbc课程,并整理博客
3.()9.14-9.16复习反射和IO流,整理博客
4.()9.16-9.18复习HTML.CSS.JS
5.()9.19-9.22 jquary
6.()9.22-9.25 ajax
剩余时间用来完成上述任务,并参加一次leetcode周赛
1 | 给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。 |
思路分析:
一、暴力法:
经过分析我们不难发现
1.s的循环节一定是s字符串的前缀字符串
2.s的长度一定是循环节的n倍
3.最长循环节的长度不会超过总长的一半(可用于优化暴力法)
1 | public static boolean repeatedSubstringPattern(String s) { |
二、暴力法的优化:
其实我们并不需要取截取字符串,我们可以用双指针用来确定字符串的头尾
1 | public static boolean repeatedSubstringPattern(String s) { |
三、构建双字符串的方法:两行代码搞定
1 | public static boolean repeatedSubstringPattern(String s) { |
缺失模块。
1、请确保node版本大于6.2
2、在博客根目录(注意不是yilia根目录)执行以下命令:
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置:
jsonContent:
meta: false
pages: false
posts:
title: true
date: true
path: true
text: false
raw: false
content: false
slug: false
updated: false
comments: false
link: false
permalink: false
excerpt: false
categories: false
tags: true