一直在磕磕绊绊的刷题路上坚持，现在而言一道题的解决时间要长的多，很少遇到审完题就有思路，半小时就ac的情况了。同时最近工作的繁琐零碎也是心烦的不行，所以从一开始是一天三题，到后来的一天一题，再到现在的三天一题，也不过就这样。但是闲着了还是愿意刷刷题的，单单是开拓开拓思路也是好的。闲话少叙，开始刷题了。
最小基因变化
题目：一条基因序列由一个带有8个字符的字符串表示，其中每个字符都属于 "A", "C", "G", "T"中的任意一个。
假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。
例如，基因序列由"AACCGGTT" 变化至 "AACCGGTA" 即发生了一次基因变化。
与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。
现在给定3个参数 — start, end, bank，分别代表起始基因序列，目标基因序列及基因库，请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1。
注意:
起始基因序列默认是合法的，但是它并不一定会出现在基因库中。
所有的目标基因序列必须是合法的。
假定起始基因序列与目标基因序列是不一样的。
示例 1:
start: "AACCGGTT"
end: "AACCGGTA"
bank: ["AACCGGTA"]
返回值: 1
示例 2:
start: "AACCGGTT"
end: "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
返回值: 2
示例 3:
start: "AAAAACCC"
end: "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]
返回值: 3
思路：这个题怎么说呢，审完题思路是有的，我暂时的想法就是有向图。大概就是从start开始，在数据字典中找差一位数的所有，放到集合里，然后再找和这个差一位的，需要注意的是之前变化过的不能再变化了，不然就是死循环了。依次类推找到变成end最小的数字。如果最后也变不成end就是-1、我感觉我逻辑是没问题的，emmmm...但是代码的实现，这种构图的都麻烦的一批，我去尝试着写代码了
只要思想不滑坡，办法总比问题多。我刚刚的想法没问题，就是细节处理上可以更简单些。因为在做的时候才发现，这个选择过的不能重复选择，是回溯的一大特点啊。所以代码中也是这么做过。一步一步往下改，遇到正好是end的则取最小的结果。中间用了剪枝可以让性能更好点。我直接贴代码：
class Solution {
int res = Integer.MAX_VALUE;
public int minMutation(String start, String end, String[] bank) {
dfs(new HashSet<String>(), 0, start, end, bank);
return (res == Integer.MAX_VALUE) ? -1 : res;
}
private void dfs (HashSet<String> step, int n, String temp, String end, String[] bank){
if(n>=res) return;
if(temp.equals(end)){
res = Math.min(n,res);
return;
}
char[] c = temp.toCharArray();
for(String s:bank){
char[] ss = s.toCharArray();
int num = 0;
for(int i = 0;i<8;i++){
if(c[i]!=ss[i]) num++;
}
if(num == 1 &&!step.contains(s)){
//这个可以是下一个分支
step.add(s);
dfs(step,n+1,s,end,bank);
step.remove(s);
}
}
}
}
这个代码怎么说呢，懂的很简单，不懂的话可能确实很难理解。这句话不是装13,是我想起我刚刷算法的时候，一般只要是递归的题目都得放到编译器里跑好几次才能隐隐的明白。所以这里多说两句：
这个题可以换个想法，从1到50每个数可以用一次，给定一个16个数组成的数组，去获取这个数组是多少。
这个题其实最直接的办法就是每种组合都去走一遍，也就是每个数字都要遍历+递归的解决。第一个数50个选择，第二个数49个选择，第三个48个选择。把所有的可能组合都列出来，总会有给定的密码的。
这种题目就应该用回溯解决。
只不过这两道题的细节是不同的，比如这个题目是每次只能变一个数，最终判断最少次数。但是如果是每次只能变一个数，最终判断能不能变成，是不是两道题更靠近了？都是一个简单的变形而已。（其实说这么多而且东一言西一语的我是想把我的思路解释出来，但是这个确实又是很抽象的东西。我可能没说的那么明白）。
反正就是上面的解法，性能也超过百分百，所以我就不多说了，直接下一题。
无重叠区间
题目：给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
思路：题目很简单啊，起码看一遍看懂了，哈哈。至于做法，我现在有个大胆的想法，就是把包含重叠区间最多的区间去掉，再判断是否有重叠区间，还有的话继续去掉最多的，直到没有重叠区间为止。我暂时的想法是这样，先去实现下看看。这个是第一直觉，不知道会遇到什么坑。
怎么说呢，这个题比我想得还要复杂一点，刚刚上面的思路不能说不对，但是对于代码来说判断一个区间的“长度”是很麻烦的事，所以我这里想的过于简单了。而真正的实现我们可以换一个角度。结尾区间越小的越有更多的可能，下面是图解:
总结一句话;不考虑起点的话选择结尾小的
然後照着这个思路去完善。我直接贴代码：
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if(intervals==null || intervals.length==0) return 0;
//按照起始位置排序
Arrays.sort(intervals, new Comparator<int []>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
});
int n = 1;
int end = Integer.MAX_VALUE;
for (int j = 0; j < intervals.length; j++) {
if(end<=intervals[j][0]) {//开始大于上个的结束，可以续一个
n++;
end = intervals[j][1];
}else {//开头已经排序了，选择结尾最小的
end = Math.min(end, intervals[j][1]);
}
}
return intervals.length-n;
}
}
注意这里的第一个值是开始值，第二个值是结束值。当前结束的值小于等于开始值说明这个区间是能留下的，所以n+1.不然的话说明这个区间和上一个区间冲突了，留下结束值最小的那个。
其实我觉得理解上面的简图，其实就能理解这段代码。这个题就这样了啊，下一题。
寻找右区间
题目：给定一组区间，对于每一个区间 i，检查是否存在一个区间 j，它的起始点大于或等于区间 i 的终点，这可以称为 j 在 i 的“右侧”。
对于任何区间，你需要存储的满足条件的区间 j 的最小索引，这意味着区间 j 有最小的起始点可以使其成为“右侧”区间。如果区间 j 不存在，则将区间 i 存储为 -1。最后，你需要输出一个值为存储的区间值的数组。
注意:
你可以假设区间的终点总是大于它的起始点。
你可以假定这些区间都不具有相同的起始点。
示例 1:
输入: [ [1,2] ]
输出: [-1]
解释:集合中只有一个区间，所以输出-1。
示例 2:
输入: [ [3,4], [2,3], [1,2] ]
输出: [-1, 0, 1]
解释:对于[3,4]，没有满足条件的“右侧”区间。
对于[2,3]，区间[3,4]具有最小的“右”起点;
对于[1,2]，区间[2,3]具有最小的“右”起点。
示例 3:
输入: [ [1,4], [2,3], [3,4] ]
输出: [-1, 2, -1]
解释:对于区间[1,4]和[3,4]，没有满足条件的“右侧”区间。
对于[2,3]，区间[3,4]有最小的“右”起点。
思路：这个题我觉得没有任何条件限制有点出乎意料啊，我不知道是因为这个题确实简单还是我现在思路比较清楚，或者说这个题可能卡在超时上？反正现在的思路是挺清晰的，因为要求满足右区间的最小索引，所以这个原始数组是不能变的，最笨的想法就是n方的比较，一个个找，但是怕超时，所以我打算用额外数组实现。我先去写写试试。
第一版本代码完美的超时了，但是代码绝对是没问题的，17个测试案例都通过了。其实这个题最麻烦的一点就是实现的方式很多，但是怎么能让性能最好反而没思路了。我去尝试优化一下吧。
呵呵呵呵，暴力法都能ac，我辛辛苦苦优化的反而超时了，不想多说什么心情，先上暴力法的代码：
class Solution {
public int[] findRightInterval(int[][] intervals) {
int[] res = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
int min = Integer.MAX_VALUE;
int minindex = -1;
for (int j = 0; j < intervals.length; j++) {
if (intervals[j][0] >= intervals[i][1] && intervals[j][0] < min) {
min = intervals[j][0];
minindex = j;
}
}
res[i] = minindex;
}
return res;
}
}
这个代码是纯暴力破解，也没啥算法，性能也是可怜的一批，至于算法我能想到的就是二分，直接看性能排行第一的代码吧，优化这块我自己是绝望了。
class Solution {
public int[] findRightInterval(int[][] intervals) {
E[] sections = new E[intervals.length];
for(int i=0; i < intervals.length; i++) {
sections[i] = new E(intervals[i][0], intervals[i][1], i);
}
Arrays.sort(sections, (a, b) -> a.s - b.s);
int[] result = new int[intervals.length];
for(int i=0; i < intervals.length; i++) {
int l =0;
int h = intervals.length ;
while(l < h) {
int mid = l + (h-l >> 1);
if (sections[mid].s >= intervals[i][1]) h = mid;
else l = mid + 1;
}
if (l == intervals.length) result[i] = -1;
else result[i] = sections[l].idx;
}
return result;
}
static class E {
int s;
int e;
int idx;
E(int s, int e, int i) {
this.s = s;
this.e = e;
idx = i;
}
}
}
挺好的想法，排序+二分。这个题最开始的思路就是每个数的初始下标，因为这个用E这个数据格式保存了，所以排序也不影响结果。然后判断比end大于等于的值的最小索引用的二分法，我只能这么说，知识点没啥新的，做起来麻烦也是真的。这个题就这么过了吧。下一题，
找到字符串中所有字母的异位词
题目：给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 1:
输入:
s: "cbaebabacd" p: "abc"
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
示例 2:
输入:
s: "abab" p: "ab"
输出:
[0, 1, 2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
思路：没有时间空间复杂度，有可能是问题就是卡性能。因为确定都是小写英文字母，惯性思维就是创建26个元素的int数组来下标表示字母，数值表示字母出现的次数。先把p用数组表示出来。然后去遍历s。从第一个字母开始。当遇到p中不出现的元素则从下一个开始算第一个，如果是某一个元素多了则看看能不能用滑窗，这是初步的想法，我去代码试试。
这个题怎么说呢，比我想的还要简单一些，首先因为这个题目中子串顺序不非要一样，所以可以从一开始就把子串的顺序按照字母顺序排列好，然后去判断。这里用滑窗做性能是更好的，但是我第一版本为了先实现所以用的暴力法，直接贴代码：
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> list = new ArrayList<Integer>();
char[] pp = p.toCharArray();
Arrays.sort(pp);
for(int i = 0;i<=s.length()-pp.length;i++){
String cur = s.substring(i,i+pp.length);
char[] c = cur.toCharArray();
Arrays.sort(c);
if(Arrays.equals(pp, c)){
list.add(i);
}
}
return list;
}
}
感觉好好一个算法题让我写毁了，哈哈，各种生硬代码。但是起码思路是ok的，接下来第二版追求性能啦，我之前的代码性能出在各种sort，substring上。我去用新的思路实现。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
char[] arrS = s.toCharArray();
char[] arrP = p.toCharArray();
// 接收最后返回的结果
List<Integer> ans = new ArrayList<>();
// 定义一个 needs 数组来看 arrP 中包含元素的个数
int[] needs = new int[26];
// 定义一个 window 数组来看滑动窗口中是否有 arrP 中的元素，并记录出现的个数
int[] window = new int[26];
// 先将 arrP 中的元素保存到 needs 数组中
for (int i = 0; i < arrP.length; i++) {
needs[arrP[i] - 'a'] += 1;
}
// 定义滑动窗口的两端
int left = 0;
int right = 0;
// 右窗口开始不断向右移动
while (right < arrS.length) {
int curR = arrS[right] - 'a';
right++;
// 将右窗口当前访问到的元素 curR 个数加 1
window[curR] += 1;
// 当 window 数组中 curR 比 needs 数组中对应元素的个数要多的时候就该移动左窗口指针
while (window[curR] > needs[curR]) {
int curL = arrS[left] - 'a';
left++;
// 将左窗口当前访问到的元素 curL 个数减 1
window[curL] -= 1;
}
// 这里将所有符合要求的左窗口索引放入到了接收结果的 List 中
if (right - left == arrP.length) {
ans.add(left);
}
}
return ans;
}
}
我很不要脸的嫖了人家的代码。毕竟写起来很麻烦，我真的是看性能排行第一的代码写的太明白了，所以直接拿来用了。哈哈，这个题其实也不复杂，就这样了啊。
这篇笔记写了两周才刷了四道题，也是不容易，然后就到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！周末愉快~java技术交流群130031711招人，欢迎各位踊跃加入！
网友评论