438.找到字符串中所有的字母异位词
思路：固定窗口
点击查看代码
class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> result = new ArrayList<>();if (s.length() < p.length()) {return result;}// 统计pMap<Character, Integer> needMatch = new HashMap<>();// 统计windowMap<Character, Integer> window = new HashMap<>();// 初始化needMatchfor (char c : p.toCharArray()) {needMatch.put(c, needMatch.getOrDefault(c, 0) + 1);}int left = 0;int match = 0;for(int right = 0; right < s.length(); right++){char c = s.charAt(right);char l = s.charAt(left);//2hashif(needMatch.containsKey(c)){window.put(c, window.getOrDefault(c,0) + 1);if(needMatch.get(c).intValue() == window.get(c).intValue()){match++;}}if(right-left + 1 == p.length()){if(match == needMatch.size()){result.add(left);}//2hashif(needMatch.containsKey(l)){if(needMatch.get(l).intValue() == window.get(l).intValue()){match--;}window.put(l, window.get(l) - 1);}left++;}}return result;}
}
反转链表
思路：pre指针，cur指针，记录next。更改当前的，移动pre和cur。
点击查看代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;while(cur != null){ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}
}
92.反转链表II
点击查看代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummy = new ListNode(0, head);ListNode p0 = dummy;for(int i = 0; i < left - 1; i++){p0 = p0.next;}ListNode pre = null;ListNode cur = p0.next;for(int i = 0; i < right - left + 1; i++){ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}p0.next.next = cur;p0.next = pre;return dummy.next;}
}