前言：考虑到本人是能力有限，算法题解只能示例一种本人能够理解和实现的方式，可能不是最优的。
一、前K个高频元素（题号：347）
描述：给定一个非空的整数数组，返回其中出现频率前K高的元素。
示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2: 输入: nums = [1], k = 1 输出: [1]
说明：
1）你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
2）你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
解题思路：这个题，在数据处理场景中很常见；统计词频，然后去TOP N。我们就用hashMap保存词频，然后在排序即可。
public class TestMain {
public static void main(String[] args) {
int[] source = {1,1,1,2,2,3};
System.out.println(execute(source,3));
}
/**
* 比较常规的方法，有点类似于大数据的中的TOP N算法解释
* 用hashMap保存计数器
* 窗口buffer内，排序遍历一次即可。
* @param source
* @param k
* @return
*/
private static List<Integer> execute(int[] source, int k) {
Map<Integer, Integer> container = new HashMap();
for (int i : source) {
Integer value = container.getOrDefault(i,0);
container.put(i,value + 1);
}
//倒叙排列
Comparator<Map.Entry<Integer, Integer>> comparator = (o1,o2) -> {
return o2.getValue().compareTo(o1.getValue());
};
//权重队列
Queue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(comparator);
container.entrySet().forEach(entry -> {
queue.offer(entry);
});
List<Integer> res = new ArrayList();
int i = 0;
while (i < k) {
res.add(queue.poll().getKey());
i++;
}
return res;
}
}
二、将数据流变为多个不想交间隔（题号：352）
描述：给定一个非负整数的数据流输入 a1，a2，…，an，…，将到目前为止看到的数字总结为不相交的间隔列表。例如，假设数据流中的整数为 1，3，7，2，6，…，每次的总结为：
输入1后：[1, 1] 输入3后：[1, 1], [3, 3] 输入7后：[1, 1], [3, 3], [7, 7] 输入2后：[1, 3], [7, 7] 输入6后：[1, 3], [6, 7]
解题思路：区间合并、元素排序查找，以及在有序结果中任意次数的插入（并保持顺序），以及有序结果中获取大于、小于某个值或者某两个值之间的子集，等等这种场景，我们需要使用二叉树（二叉搜索树，BST），此题比较契合（部分情况，跳跃表也能搞定）。
public class TestMain {
public static void main(String[] args) {
int[] source = {1,3,7,2,6};
SummaryRanges sr = new SummaryRanges();
for (int i : source) {
sr.add(i);
}
List<Interval> result = sr.get();
System.out.println(result);
}
/**
* 对于区间计算，比如获取：
* 1）大于、小与某个key的数据列表。
* 2）两个key之间的数据列表。
* 3）对key的正序、倒叙排列的数据列表。（sortedSet）
* 我们均可以使用treeMap来解决，treeMap为排序二叉树（二叉搜索树，BST）,便捷而且性能可靠。
*/
public static class SummaryRanges {
private TreeMap<Integer, Interval> container = new TreeMap<>();
public void add(int value) {
if (container.containsKey(value)) {
return;
}
//获取比值小的key
Entry<Integer,Interval> lower = container.lowerEntry(value);
//获取比此值大的key
Entry<Integer,Interval> higher = container.higherEntry(value);
//比起大、小的都不存在，则直接构建当前区间
if (lower == null && higher == null) {
container.put(value,new Interval(value,value));
return;
}
Interval hi = (higher == null) ? null : higher.getValue();
Interval li = (lower == null) ? null : lower.getValue();
//如下判断逻辑，或许有更简洁的表达方式，本人基于易于理解、从特殊到普通场景的思考路径来实现。
// 如果都存在
if (lower != null && higher != null) {
//如果当前value为大、小区间的衔接值，则直接串联
if (value == li.end + 1 && value == hi.start - 1) {
container.remove(higher.getKey());
li.end = hi.end;
return;
} else if (value == li.end + 1) {
//如果当前值为小区间的衔接值，直接扩大小区间
li.end = value;
} else if (value == hi.start - 1) {
//如果为大区间的衔接值，则移除大区间，并降级
container.remove(higher.getKey());
hi.start = value;
container.put(value,hi);
} else {
//非任何衔接值时，即在大、小区间的中间，则构建新区间。
container.put(value, new Interval(value, value));
}
return;
}
//如果只存在大区间
if (higher != null) {
Integer hk = higher.getKey();
if (value == hk - 1) {
hi.start = value;
container.remove(hk);
container.put(value,hi);
return;
} else {
container.put(value, new Interval(value, value));
}
return;
}
//如果只存在小区间
if (lower != null) {
if (value == li.end + 1) {
li.end = value;
} else {
container.put(value,new Interval(value,value));
}
}
}
public List<Interval> get() {
return new ArrayList<Interval>(container.values());
}
}
public static class Interval {
int start;
int end;
public Interval(int start,int end) {
this.start = start;
this.end = end;
}
@Override
public String toString() {
return "[" + start + "," + end + "]";
}
}
}
三、俄罗斯套娃信封问题（题号：354）
描述：给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
说明:不允许旋转信封。
示例: 输入: envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出: 3 解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
解题思路：这种存在区间比较的题，还是BST即TreeMap比较合适；不过此题还需要结合动态规划的方式才能解决。
public class TestMain {
public static void main(String[] args) {
int[][] source = {{5,4},{6,4},{6,7},{2,3}};
System.out.println(execute(source));
}
public static int execute(int[][] source) {
//对于区间比较，我们优先使用treeMap
TreeMap<Integer,Pair> container = new TreeMap<>();
for (int i = 0; i < source.length; i++) {
int[] pair = source[i];
//key为一个边，既然不允许旋转，我们就约定0元素为key
container.put(pair[0],new Pair(pair[0],pair[1]));
}
//基于动态规划方式，首先从最小的边开始，即第一个key
Stack<Pair> result = dp(container,null,null);
System.out.println(result);
return result.size();
}
/**
*
* @param container BST
* @param key 其中一边
* @param result
* @return
*/
private static Stack<Pair> dp(TreeMap<Integer,Pair> container, Integer key, Stack<Pair> result) {
//兼容首次，如果key为空，则使用首个key
if (key == null) {
key = container.firstKey();
}
//如果历史计算结果为null，则之计初始化，主要兼容首次
if (result == null) {
result = new Stack<>();
}
//兼容首次
if (result.isEmpty()){
result.push(container.get(key));
}
Pair current = result.peek();
Entry<Integer,Pair> higher = container.higherEntry(key);
//如果没有比边更大的，表示后续不可能存在"套娃"
if (higher == null) {
return result;
}
Pair target = higher.getValue();
Stack<Pair> next = new Stack<>();
if (target.w > current.w && target.h > current.h) {
result.push(target);
//历史
dp(container,higher.getKey(),result);
} else {
//当前"套娃"仍然可以作为起点，用于匹配后续元素
dp(container, higher.getKey(), next);
}
//返回较大数量的结果
return result.size() >= next.size() ? result : next;
}
public static class Pair {
int w;
int h;
public Pair(int w,int h) {
this.w = w;
this.h = h;
}
}
}
四、设计推特（题号：355）
设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近十条推文。你的设计需要支持以下的几个功能：
1）postTweet(userId, tweetId): 创建一条新的推文。
2）getNewsFeed(userId): 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。
3）follow(followerId, followeeId): 关注一个用户。
4）unfollow(followerId, followeeId): 取消关注一个用户。
解题思路：这个问题并不是一个算法层面的题，可以说是一个架构设计的事情。
public class TestMain {
public static void main(String[] args) {
Twitter twitter = new Twitter();
twitter.postTweet(1,1);
twitter.postTweet(2,2);
twitter.follow(1,2);
System.out.println(twitter.getNewsFeed(1));
twitter.unfollow(1,2);
System.out.println(twitter.getNewsFeed(1));
}
/**
* 对外API
* 这种设计，基于拉的方式，即在获取feeds时再整合有关"关注人"的消息和负责排序。
* 还有一种方式，就是推，即用户发feed时，将feed同时添加到关注者的各自的feeds列表中，
* 这样用户只需要从各自的feeds列表中获取即可，时则不需要再进行排序和用户关系查找了。
*
* 各有优缺点，通常是推、拉协作。
* 拉：用户关注的人数不多、且它们的feeds个数较少；无分页场景。其实这种方式，不太实用，特别是feeds需要持久存储时。
* 推：用户关注的人数较多，feeds个数不确定，有分页场景；但是用户关系相对稳定，频繁关注、取消关注或许有影响；缺点是额外的存储成本
*/
public static class Twitter {
//用户列表
private final Map<Integer, User> users = new HashMap<>();
/**
* 发布推文
* @param userId
* @param tweetId
*/
public void postTweet(int userId, int tweetId) {
if (!users.containsKey(userId)) {
User user = new User(userId);
users.put(userId, user);
}
users.get(userId).postTweet(tweetId);
}
/**
* 根据用户ID，获取其可以浏览的最新的10条推文
* @param userId
* @return
*/
public List<Integer> getNewsFeed(int userId) {
List<Integer> newsFeed = new LinkedList<>();
User user = users.get(userId);
if (user == null) {
return newsFeed;
}
//获取其关注的用户列表,至少会包含自己
Set<Integer> fu = user.followed;
PriorityQueue<Tweet> heap = new PriorityQueue<>(10,(t1, t2) -> t2.time.compareTo(t1.time));
//将其关注的用户推文列表的head加入排序队列。
for (int f : fu) {
Tweet tweet = users.get(f).tweetHead;
if (tweet != null) {
heap.offer(tweet);
}
}
int count = 0;
while (!heap.isEmpty() && count < 10) {
Tweet tweet = heap.poll();
//移除一条之后，遍历指针下移一次
//触发重新排序一次
newsFeed.add(tweet.id);
count++;
if (tweet.next != null) {
heap.offer(tweet.next);
}
}
return newsFeed;
}
public void follow(int followerId, int followeeId) {
if (!users.containsKey(followeeId)) {
User user = new User(followeeId);
users.put(followeeId, user);
}
if (!users.containsKey(followerId)) {
User user = new User(followerId);
users.put(followerId, user);
}
users.get(followerId).follow(followeeId);
}
public void unfollow(int followerId, int followeeId) {
if (!users.containsKey(followerId) || followeeId == followerId) {
return;
}
users.get(followerId).unfollow(followeeId);
}
}
/**
* 推文，一条消息
*/
private static class Tweet {
public Long time = System.currentTimeMillis();
public int id;
public Tweet next;//在内存中表示为链表
public Tweet(int id) {
this.id = id;
}
}
private static class User {
public int id;
public Set<Integer> followed;
public Tweet tweetHead;
public User(int id) {
this.id = id;
followed = new HashSet<>();
followed.add(id);
this.tweetHead = null;
}
public void follow(int followeeId) {
followed.add(followeeId);
}
public void unfollow(int followeeId) {
followed.remove(followeeId);
}
public void postTweet(int tweetId) {
Tweet head = new Tweet(tweetId);
head.next = tweetHead;
tweetHead = head;//表头，总是最新的
}
}
}
五、计算各个位数不同的数字（题号：357）
描述：给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10^n 。
示例: 输入: 2 输出: 91 解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。
解题思路：就是一个数字排列组合的问题，需要注意最高位排除0。
public class TestMain {
public static void main(String[] args) {
for(int i = 0; i <= 10; i++) {
System.out.println(execute(i));
}
}
/**
* 推测规律，其实就是排列组合，每位占用一个，最高位排除0
* 一位数：10个
* 二位数：（一位数） + [十位数9个] * [个位数9个]
* 三位数：（二位数） + [百位数9个】 * [十位数9个] * [个位数8个]
*
* 可以使用for循环累加，也可以使用回溯法解决
* @param n
* @return
*/
public static int execute(int n) {
if (n == 0) {
return 1;
}
//个位数，一共10个，直接计算
int result = 10;
int unique = 9;
int remainder = 9;
while (n-- > 1 && remainder > 0) {
unique = unique * remainder;
result += unique;
remainder--;
}
return result;
}
}
六、水壶问题（题号：365）
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
你允许：
1）装满任意一个水壶
2）清空任意一个水壶
3）从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例 1: (From the famous "Die Hard" example) 输入: x = 3, y = 5, z = 4 输出: True 示例 2: 输入: x = 2, y = 6, z = 5 输出: False
解题思路：需要注意，z升水最终需要用x和y两个水壶承载，中间过程倒出的水不算，而且除了x和y之外不能使用其他的容器交换；换句话说，如果还有一个容器，用于存储z升水，那么算法的实现将完全不同。此题最终是个数据问题，思路可以参考代码注释部分。
public class TestMain {
public static void main(String[] args) {
System.out.println(execute(3,5,4));
System.out.println(execute(2,6,5));
System.out.println(execute(2,7,11));
}
/**
* 首先需要注意，z升水必须最终被两个容器容纳，中间过程倒出的水不计算结果。
*
* 数据模型：
*
* 倒入A次
* ------->>
* | | 交换
* | x | ---->> | |
* | | | y | 倒出B次
* |---| |---| ------->>
*
* 无论"倒入"和"倒出"多少次，最终两个容器的存量等于z，前提是z <= x + y
* 最终是个数学问题：
* z = A * x + B * y => z = m(a * x + b * y)
* 以上述模型，A为非负数，B为非正数。
* 我们从x、y提取最大公约数m，如果z能整除m，则结果成立。
*
* @param x
* @param y
* @param z
* @return
*/
public static boolean execute(int x,int y,int z) {
if (x + y < z) {
return false;
}
if (z == 0 || x == z || y == z) {
return true;
}
return z % gcd(x, y) == 0;
}
/**
* 最大公约数
* @param x
* @param y
* @return
*/
public static int gcd(int x, int y)
{
return y == 0 ? x : gcd(y, x % y);
}
}
七、有效的完全平方数（题号：367）
给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如 sqrt。
示例 1： 输入：16 输出：True 示例 2： 输入：14 输出：False
解题思路：首先知道什么是完全平方数，然后找规律即可。除了如下例子的解题方式之外，还可以直接从1遍历，用n相除，查看结果与当前值的大小关系决定是否继续遍历。
public class TestMain {
public static void main(String[] args) {
for (int i = 1; i < 20; i++) {
System.out.println(i + ":" + execute(i));
}
}
/**
* 完全平方数：即n为正整数x的平方。
* 我们通过规律可见：
* 1 -> 1 * 1
* 4 -> 2 * 2
* 9 -> 3 * 3
* 16 -> 4 * 4
*
* 相邻平方数的差，总是 2x - 1，所以这是一个累加计算过程
* @param n
* @return
*/
public static boolean execute(int n) {
int t = 1;
int c = 0;
while (c < n) {
c += 2 * t - 1;
t++;
}
return c == n;
}
}
八、组合总和（题号：377）
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例: nums = [1, 2, 3] target = 4 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。 因此输出为 7。
解题思路：这是个典型的回溯法，每个元素都可以重复出现。
public class TestMain {
public static void main(String[] args) {
int[] source = {1,2,3};
System.out.println(execute(source,4));
}
/**
* 比较常规的回溯法
* @param source
* @param target 余数
* @return 符合要求的组合数
*/
private static int execute(int[] source, int target) {
if (target == 0) {
return 1;
}
int count = 0;
for (int value : source) {
if (value > target) {
continue;
}
int nc = execute(source,target - value);
count += nc;
}
return count;
}
}
九、判断子序列（题号：392）
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1: s = "abc", t = "ahbgdc" 返回 true. 示例 2: s = "axc", t = "ahbgdc" 返回 false.
解题思路：双指针法，注意边界判断。
public class TestMain {
public static void main(String[] args) {
System.out.println(execute("abc","ahbgdc"));
System.out.println(execute("axc","ahbgdc"));
}
/**
* 双指针法，比较易于理解和实现
* @param s
* @param t
* @return
*/
private static boolean execute(String s,String t) {
if(s == null || t == null) {
return false;
}
int j = 0;
for (int i = 0; i < s.length(); i++) {
char sv = s.charAt(i);
boolean status = false;
while (j < t.length()) {
if (sv == t.charAt(j)) {
status = true;
break;
}
j++;
}
if (!status) {
return false;
}
}
return true;
}
}
十、至少有K个重复字符的最长字串（题号：395）
找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
示例 1: 输入: s = "aaabb", k = 3 输出: 3 最长子串为 "aaa" ，其中 'a' 重复了 3 次。 示例 2: 输入: s = "ababbc", k = 2 输出: 5 最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
解题思路：使用回溯法其实也可以，只是实现起来略麻烦；我们使用两次遍历来解决。
public class TestMain {
public static void main(String[] args) {
System.out.println(execute("aaabb",3));
System.out.println(execute("ababbc",2));
}
private static int execute(String source,int k) {
if (source == null || k <= 0) {
return 0;
}
//将每个字符出现的次数，存放在map中。
Map<Character,Integer> container = new HashMap<>();
for (int i = 0; i < source.length();i++) {
char value = source.charAt(i);
int count = container.getOrDefault(value,0);
container.put(value,++count);
}
int si = -1;
int ei = 0;
int max = -1;
for (int i = 0; i < source.length(); i++) {
char value = source.charAt(i);
if (container.get(value) >= k) {
if (si < 0) {
si = i;
}
ei = si;
max = Math.max(max,ei - si) + 1;
} else {
System.out.println(si + "," + ei);
si = -1;
}
}
return max;
}
}
相关推荐
如何正确刷题？LeetCode刷题误区和刷题方法论分享【LeetCode刷题套路教程1】
Backtracking回溯解题套路【LeetCode刷题套路教程18】
Heap堆解题套路【LeetCode刷题套路教程6】
一些java基础算法、leetcode刷题 Java学习资料
主要介绍了如何在Intellij中安装LeetCode刷题插件方便Java刷题,本文通过图文并茂的形式给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下
Stack堆栈解题套路【LeetCode刷题套路教程5】
这个是自己收藏的一个leetcode刷题记录，分享给需要的亲。非原创，自己也正在学习中。
哈希表HashMap解题套路【LeetCode刷题套路教程7】
DynamicProgramming2D解题套路【LeetCode刷题套路教程15】
树Tree题型广度优先搜索BFS套路【LeetCode刷题套路教程8】
Array题型_双指针Two_Pointers套路【LeetCode刷题套路教程2】
二分查找Binary_Search套路和解题模板【LeetCode刷题套路教程3】
DynamicProgramming1D解题套路【LeetCode刷题套路教程14】
DynamicProgramming2D高级解题套路【LeetCode刷题套路教程17】
DynamicProgramming2D进阶解题套路【LeetCode刷题套路教程16】
Search,_Dynamic_Programming1【LeetCode刷题套路教程13】
Graph图BFS广度优先搜索套路【LeetCode刷题套路教程10】
Graph图DFS深度优先搜索题型套路【LeetCode刷题套路教程12】
树Tree深度优先搜索DFS解题套路【LeetCode刷题套路教程9】
Graph图Best-First_Search题型套路【LeetCode刷题套路教程11】