[toc]
两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
HashMap解法
class Solution {public int[] twoSum(int[] nums, int target) {HashMap<Integer, Integer> map = new HashMap<>();int n = nums.length;for (int i = 0; i < n; ++i) {if (map.containsKey(target - nums[i])) {return new int[]{map.get(target- nums[i]), i};} else {map.put(nums[i], i);}}return null;}}
存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
解法
class Solution {
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
if (set.contains(num)) {
return true;
}
set.add(num);
}
return false;
}
}
剑指 Offer 48. 最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
s.length <= 40000
滑动窗口
什么是滑动窗口？
其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！
如何移动？
我们只要把队列的左边的元素移出就行了，直到满足题目要求！
一直维持这样的队列，找出队列出现最长的长度时候，求出解！
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length() == 0) {
return 0;
}
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max = 0;
int left = 0;
for (int i = 0; i < s.length(); i++) {
if (map.containsKey(s.charAt(i))) {
left = Math.max(left, map.get(s.charAt(i)) + 1);
}
map.put(s.charAt(i), i);
max = Math.max(max, i - left + 1);
}
return max;
}
}
剑指 Offer 50. 第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例:
s = "abaccdeff"
返回 "b"
s = ""
返回 " "
限制：
0 <= s 的长度 <= 50000
hashmap
class Solution {
public char firstUniqChar(String s) {
Map<Character, Boolean> map = new HashMap<>();
int length = s.length();
for (int i = 0; i < length; i++) {
map.put(s.charAt(i), !map.containsKey(s.charAt(i)));
}
for (int i = 0; i < length; i++) {
if (map.get(s.charAt(i))) {
return s.charAt(i);
}
}
return ' ';
}
}
560. 和为K的子数组
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
前缀和+哈希表
详解见leetcode
class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, pre = 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
if (map.containsKey(pre - k)) {
count += map.get(pre - k);
}
map.put(pre, map.getOrDefault(pre, 0) + 1);
}
return count;
}
}
最长和谐子序列
和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。
现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。
示例 1:
输入: [1,3,2,2,5,2,3,7]
输出: 5
原因: 最长的和谐数组是：[3,2,2,2,3].
说明: 输入的数组长度最大不超过20,000.
解法
class Solution {
public int findLHS(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
int res = 0;
for (int num : map.keySet()) {
if (map.containsKey(num + 1)) {
res = Math.max(res, map.get(num + 1) + map.get(num));
}
}
return res;
}
}
49. 字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
解法
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs.length == 0) {
return new ArrayList();
}
Map<String, List> ans = new HashMap<String, List>();
int[] count = new int[26];
for (String s : strs) {
Arrays.fill(count, 0);
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
StringBuilder sb = new StringBuilder("");
for (int i = 0; i < 26; i++) {
sb.append('#');
sb.append(count[i]);
}
String key = sb.toString();
if (!ans.containsKey(key)) {
ans.put(key, new ArrayList());
}
ans.get(key).add(s);
}
return new ArrayList(ans.values());
}
}
最长连续序列
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
解法
先将数组元素存入set集合，然后再遍历数组，从num最小开始，依次num++，找到最长连续序列。
class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int res = 0;
for (int num : nums) {
if (!set.contains(num - 1)) {
int cur = 1;
while (set.contains(++num)) {
cur++;
}
res = Math.max(res, cur);
}
}
return res;
}
}
146. LRU缓存机制
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得关键字 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得关键字 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
哈希表和双向链表
使用哈希表可以快速定位LRU里面有的节点，get时很快，使用双向链表可以很快速地插入、删除链表中的节点。
class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {};
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 使用伪头部和伪尾部节点
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 如果 key 存在，先通过哈希表定位，再移到头部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
// 如果 key 不存在，创建一个新的节点
DLinkedNode newNode = new DLinkedNode(key, value);
// 添加进哈希表
cache.put(key, newNode);
// 添加至双向链表的头部
addToHead(newNode);
size++;
if (size > capacity) {
// 如果超出容量，删除双向链表的尾部节点
DLinkedNode removeNode = removeTail();
// 删除哈希表中对应的项
cache.remove(removeNode.key);
size--;
}
} else {
// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
node.value = value;
moveToHead(node);
}
}
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
460. LFU 缓存
请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。
实现 LFUCache 类：
LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
int get(int key) - 如果键存在于缓存中，则获取键的值，否则返回 -1。
void put(int key, int value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。
注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。
当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。
示例：
输入：
[“LFUCache”, “put”, “put”, “get”, “put”, “get”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
提示：
0 <= capacity, key, value <= 104
最多调用 105 次 get 和 put 方法
进阶：你可以为这两种操作设计时间复杂度为 O(1) 的实现吗？
哈希表和双向链表
- 用一个哈希表存储节点
- 用另一个哈希表存储被操作次数相同的节点组成的链表
class LFUCache {
// 节点结构
class Node {
int key;
int value;
int freq = 1;
Node prev;
Node next;
public Node() { }
public Node (int key, int value) {
this.key = key;
this.value = value;
}
}
// 链表结构
class DLinkedNode {
Node head, tail;
public DLinkedNode () {
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
}
void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
void addNode(Node node) {
node.next = head.next;
head.next.prev = node;
node.prev = head;
head.next = node;
}
}
// cache存储key、value
Map<Integer, Node> cache;
// freqMap存储key是操作的次数，value是操作次数为key的所有节点组成的链表
Map<Integer, DLinkedNode> freqMap;
// size 是cache里面的实际容量
int size;
// capacity是cache最大容量
int capacity;
// min是最小操作次数，也就是最久未使用
int min;
public LFUCache(int capacity) {
cache = new HashMap<>(capacity);
freqMap = new HashMap<>();
this.capacity = capacity;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1;
}
// 更新node节点的操作次数和对应的位置
freqUpdate(node);
return node.value;
}
public void put(int key, int value) {
if (capacity == 0) {
return;
}
Node node = cache.get(key);
if (node != null) {
node.value = value;
freqUpdate(node);
} else {
if (size == capacity) {
DLinkedNode minLinkedNode = freqMap.get(min);
cache.remove(minLinkedNode.tail.prev.key);
minLinkedNode.removeNode(minLinkedNode.tail.prev);
// 这里不需要维护min, 因为下面add了newNode后min肯定是1.
size--;
}
Node newNode = new Node(key, value);
cache.put(key, newNode);
DLinkedNode list = freqMap.get(1);
if (list == null) {
list = new DLinkedNode();
freqMap.put(1, list);
}
list.addNode(newNode);
size++;
min = 1;
}
}
void freqUpdate(Node node) {
// 从原freq对应的链表里移除, 并更新min
int freq = node.freq;
DLinkedNode list = freqMap.get(freq);
list.removeNode(node);
if (freq == min && list.head.next == list.tail) {
min = freq + 1;
}
// 加入新freq对应的链表
node.freq++;
list = freqMap.get(freq + 1);
if (list == null) {
list = new DLinkedNode();
freqMap.put(freq + 1, list);
}
list.addNode(node);
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
1044. 最长重复子串
给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。
返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 “”。）
示例 1：
输入："banana"
输出："ana"
示例 2：
输入："abcd"
输出：""
提示：
2 <= S.length <= 10^5
S 由小写英文字母组成。
解法
class Solution {
private static final long P = 805306457;
private static final long MOD = (int) (1e9+7);
private long[] hash;
private long[] power;
private int[] ansPos;
private void calcHashAndPower(char[] arr) {
hash[0] = arr[0];
power[0] = 1;
for (int i = 1; i < arr.length; i++) {
hash[i] = (hash[i-1] * P + arr[i]) % MOD;
power[i] = (power[i-1] * P) % MOD;
}
}
private long getSubStrHash(int l, int r) {
if (l == 0) {
return hash[r];
}
return ((hash[r] - power[r-l+1] * hash[l-1]) % MOD + MOD) % MOD;
}
private boolean hasTrueExist(char[] arr, int l1, int l2, int subLen) {
for (int i = 0; i < subLen; i++) {
if (arr[l1 + i] != arr[l2 + i]) {
return false;
}
}
return true;
}
/**
* 判断是否存在指定长度的重复子串
* 由于不同子串可能存在相同的hash值，因此需要解决hash冲突
*/
private boolean hasDuplicatedStr(char[] arr, int subLen) {
Map<Long, List<Integer>> map = new HashMap<>();
for (int l = 0; l <= arr.length - subLen; l++) {
long strHash = getSubStrHash(l, l + subLen - 1);
if (map.containsKey(strHash)) {
List<Integer> oldPosList = map.get(strHash);
for (Integer oldPos : oldPosList) {
if (hasTrueExist(arr, oldPos, l, subLen)) {
ansPos[0] = l;
ansPos[1] = l + subLen;
return true;
}
}
oldPosList.add(l);
} else {
List<Integer> posList = new ArrayList<>();
posList.add(l);
map.put(strHash, posList);
}
}
return false;
}
public String longestDupSubstring(String str) {
char[] arr = str.toCharArray();
int len = arr.length;
hash = new long[len];
power = new long[len];
ansPos = new int[2];
calcHashAndPower(arr);
// 二分+滑动窗口
// 其中二分确定长度，因为当一个长串出现重复串，那么它的子串必定出现重复串。因此可以用二分去猜最大长度
int low = 1;
int high = len;
while (low <= high) {
int mid = (low + high) >>> 1;
boolean hasDuplicated = hasDuplicatedStr(arr, mid);
if (hasDuplicated) {
low = mid + 1;
} else {
high = mid - 1;
}
}
if (ansPos[0] == ansPos[1]) {
return "";
}
return str.substring(ansPos[0], ansPos[1]);
}
}
推荐阅读
欢迎关注我的公众号呦，率先更新内容，并且后续还有一些源码级的免费教程推出。
若有收获，就点个赞吧
0 人点赞
