文章目录
引言
- 今天本来想完成指标的，但是做着做着，发现大部分做的比较舒服的题目都是通过模板做的，然后花时间去整理模板了，之前没弄懂的数组表示的链表的模板好好重新画了一下，差不多花了两个多小时。不过没有找到相关的题目。这里就暂时不贴了，这里觉得还是得按照章节来做，然后找到一个靠谱的模板，然后按照模板来刷，效率会高很多！
- 这里算是又走了一个弯路吧！真的是！好吧！
- 今天就做两题，不然没有时间去完成我的项目了！得调整一下，保证项目的事件不能改变！
模板——滑动窗口/双指针
- 这类问题主要针对以下两种情况
- 对于一个序列，用两个指针维护一段区间
- 对于俩个序列，维护某种次序
- 使用for循环同时定义一个双指针
for(int r = 0,l = 0;r <n;r ++)
{
while(l < r && check(l,r)) l ++;
}
}
复习
无重复最长子串
复习实现
class Solution {
public int lengthOfLongestSubstring(String s) {
// define the hashmap to remove duplication
Map<Character,Integer> map = new HashMap<>();
// traverse the string with the windows
int res = 0;
for(int l = 0,r = 0;r < s.length();r ++){
char rChar = s.charAt(r);
map.put(rChar,map.getOrDefault(rChar,0) + 1);
// move the r
while(map.getOrDefault(rChar,0) > 1){
char lChar = s.charAt(l);
System.out.println(map.get(lChar));
map.put(lChar,map.get(lChar) - 1);
l ++;
}
res = Math.max(res,r- l + 1);
}
return res;
}
}
新作
相交链表
个人实现
- 就是一个哈希表的问题
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// define the map to store the node of the headA
ListNode ADummy = headA;
ListNode BDummy = headB;
Map<ListNode,Boolean> map = new HashMap<>();
// traverse the List A
while(ADummy != null){
map.put(ADummy,true);
ADummy = ADummy.next;
}
// judge whether contains
while(BDummy != null){
if(map.containsKey(BDummy)) return BDummy;
BDummy = BDummy.next;
}
return null;
}
}
感觉的我的时间复杂度不是O（1），时间复杂度是O（m + n）
参考实现
- 太牛了，我一看没有环，就没有想过使用双指针进行遍历，如果使用交叉的双指针，确实能够在O（1）的空间复杂度内解决问题。
- 下面的证明太精彩了，有点累了，刷算法刷疲惫了！就不推导了，直接复制了！
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
// define the map to store the node of the headA
ListNode ADummy = headA;
ListNode BDummy = headB;
// traverse the List
while(ADummy != BDummy){
ADummy = (ADummy == null ? headB : ADummy.next);
BDummy = (BDummy == null ? headA : BDummy.next);
}
return ADummy;
}
}
环形链表
个人实现
使用hash表，重复包含就算是重合了，对象在堆中是唯一的
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
Map<ListNode , Boolean> map = new HashMap<>();
ListNode temp = head;
while(temp != null){
if(map.containsKey(temp)) return true;
map.put(temp,true);
temp = temp.next;
}
return false;
}
}
参考实现——快慢指针
- 这里使用一个快慢指针重合的方式
- 快指针一次遍历两个节点
- 慢指针一次遍历一个节点
- 两个指针重合，说明出现了环，没有环，有一个会为空
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
// define first and slow pointer to traverse the list
if(head == null || head.next == null) return false;
ListNode f = head.next;
ListNode s = head;
while(f != null && s != null){
// judge whether s == f
if(s == f) return true;
f = f.next;
if(f == null ) return false;
f = f.next;
s = s.next;
}
return false;
}
}
下面是参考他的代码写的，原来的代码有点问题，因为没有考虑到会有为空的情况出现
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
// define first and slow pointer to traverse the list
if(head == null || head.next == null) return false;
ListNode f = head.next;
ListNode s = head;
while(f != s){
// judge whether s == f
if(s == null || f == null) return false;
f = f.next;
if(f == null ) return false;
f = f.next;
s = s.next;
}
return true;
}
}
找到字符串中所有字母的异位词
注意
- 会出现仅仅包含一个字符的情况，需要特殊考虑
个人实现
- 这道题我应该会创建两个字典，分别对应p和s
- 对应p的字典，用来比较目标字符串中应该有哪些字符
- 对应s的字典，用来对各个字符的情况进行计数，保证每一个字符都是符合p中的字典数量。
- 处理步骤
- 如果当前字符不在需要匹配的字符串中的，直接移动l和r，并且清空字典
- 判定出现次数已经超过了或者重复出现了，那就移动l，直到满足要求的
class Solution {
public List<Integer> findAnagrams(String s, String p) {
// define the result
List<Integer> res = new ArrayList<>();
// define two maps of p and s
Map<Character ,Integer> pMap = new HashMap<>();
Map<Character ,Integer> sMap = new HashMap<>();
// reaverse p string as goal to compare
for(int i = 0;i < p.length();i ++) pMap.put(p.charAt(i),pMap.getOrDefault(p.charAt(i),0) + 1 );
// traverse the string s
for(int l = 0, r = 0;r < s.length();r ++){
// put rChar to the map
char rChar = s.charAt(r);
if(!pMap.containsKey(rChar)) {
l = r + 1;
sMap.clear();
continue;
}
sMap.put(rChar,sMap.getOrDefault(rChar,0) + 1);
// control num of the r
while(sMap.getOrDefault(rChar , 0 ) > pMap.getOrDefault(rChar , 0 )) {
char lChar = s.charAt(l);
int num = sMap.get(lChar) - 1;
if(num == 0) sMap.remove(lChar);
else sMap.put(lChar,num);
l ++;
}
// compare the legnth and content of the map to cal the res
int len = r - l + 1;
if(sMap.size() == pMap.size() && len == p.length()){
res.add(l);
}
}
return res;
}
}
参考实现
- 他的颗粒度更高，不像我是匹配每一个字母类型，他是以满足要求的字母类型数作为判定的标准，然后需要匹配的快。
- 同时共用一个map，正数表示需要匹配的字符串，负数表示待匹配的字符串中匹配到的字符串，需要最终为零，才是满足条件。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
// define the result
List<Integer> res = new ArrayList<>();
// define two maps of p and s
Map<Character ,Integer> pMap = new HashMap<>();
// reaverse p string as goal to compare
for(int i = 0;i < p.length();i ++) pMap.put(p.charAt(i),pMap.getOrDefault(p.charAt(i),0) + 1 );
// traverse the string s
int tot = pMap.size();
for(int l = 0, r = 0,satisfy = 0;r < s.length();r ++){
// put the rChar into map and cal the number of the types in the string
char rChar = s.charAt(r);
pMap.put(rChar,pMap.getOrDefault(rChar,0) - 1);
if(pMap.get(rChar) == 0) satisfy ++;
// move l to meet the required len of p
while(r - l + 1 > p.length()){
char lChar = s.charAt(l);
if(pMap.get(lChar) == 0) satisfy --;
pMap.put(lChar,pMap.getOrDefault(lChar,0) + 1);
l ++;
}
if(satisfy == tot) res.add(l);
}
return res;
}
}
总的来说，这个算法相当于是优化版的滑动窗口，效果会更好的
总结
- 今天看了滑动窗口和两个关于链表的简单题，关于滑动窗口，大概框架能够写出来，然后就是条件的思考判定。关于链表的题目虽然简单，但是使用双指针的两个思路真的棒！
- 今天又花了很多时间在算法上，不能在浪费这么多时间了！
- 总结了一下，有模板可以给我一个大概的思维框架，保证我能写出来，可能不够灵活的，方法不一定是最有效的，但是一定能够写出来！
- 后续应该抓紧看我的项目了，准备投提前批了，能过就行了，！
