排序系列
前言
大家好，我是老马。
以前从工程的角度，已经梳理过一次排序算法。
这里从力扣算法的角度，重新梳理一遍。
核心内容包含：
1）常见排序算法介绍
2）背后的核心思想
3）leetcode 经典题目练习+讲解
4）应用场景、优缺点等对比总结
5）工程 sdk 包，这个已经完成。
6) 可视化
242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。
示例 1:
输入: s = “anagram”, t = “nagaram” 输出: true 示例 2:
输入: s = “rat”, t = “car” 输出: false
提示:
1 <= s.length, t.length <= 5 * 10^4 s 和 t 仅包含小写字母
进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
字母异位词
字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。
v1-计数排序
思路
这个本质其实就是对应的字符，计数相同就行。
唯一用到的技巧就是 c-‘a’ 对应下标。
实现
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()) {
return false;
}
int[] count1 = getCharsCount(s);
int[] count2 = getCharsCount(t);
// 对比
for(int i = 0; i < 26; i++) {
if(count1[i] != count2[i]) {
return false;
}
}
return true;
}
private int[] getCharsCount(String s) {
int[] ints = new int[26];
char[] chars = s.toCharArray();
for(char c : chars) {
int index = c-'a';
int count = ints[index];
ints[index] = count+1;
}
return ints;
}
效果
2ms 击败 88.94%
嗯？竟然不是第一解法。
v2-进阶解法
思路
我们来解答下进阶问题: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
此时如果还是用一个大数组，大部分字符可能都是空的，比较浪费。
我们用 HashMap 来解决。
解法
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()) {
return false;
}
Map<Character, Integer> count1 = getCharsCount(s);
Map<Character, Integer> count2 = getCharsCount(t);
// 对比
for(Map.Entry<Character, Integer> entry : count1.entrySet()) {
Integer val2 = count2.get(entry.getKey());
if(!entry.getValue().equals(val2)) {
return false;
}
}
return true;
}
private Map<Character, Integer> getCharsCount(String s) {
Map<Character, Integer> map = new HashMap<>();
char[] chars = s.toCharArray();
for(char c : chars) {
int count = map.getOrDefault(c, 0);
map.put(c, ++count);
}
return map;
}
效果
21ms 击败 5.70%
适用性很高，性能垫底。
v3-计数的改进
思路
看了下第一的算法，其实是节省了一次数组的创建。
我们可以 s 增加，t 减少。
如果最后刚好全部是0，则说明刚好抵消。
实现
static {
for (int i = 0; i < 500; i++) {
isAnagram("", "s");
}
}
public static boolean isAnagram(String s, String t) {
if(s.length() != t.length()) {
return false;
}
int[] tempCount = new int[26];
int length = s.length();
for(int i = 0; i< length; i++) {
int ix1 = s.charAt(i) - 'a';
int ix2 = t.charAt(i) - 'a';
tempCount[ix1]++;
tempCount[ix2]--;
}
// 对比
for(int i = 0; i < 26; i++) {
if(tempCount[i] != 0) {
return false;
}
}
return true;
}
效果
0ms 100%
猜一猜
大家猜一猜，下面的代码有什么用？
static {
for (int i = 0; i < 500; i++) {
isAnagram("", "s");
}
}
如果把这段代码去掉，那么其实就会变得很普通。
这段代码的作用是 JIT 编译的预热机制，我只能说，太秀了。
忽然想到，以后我都加上这个技巧，不是无敌了。
什么是 JIT 编译的预热机制?
JIT 编译的预热机制
Java 的运行时性能，受到 JVM 的 JIT（Just-In-Time）即时编译器 影响。
初次执行一个方法时，JVM 会以解释执行为主，性能比较低。
但如果一个方法被频繁调用，JVM 会把它 标记为“热点方法”，然后用 JIT 编译成本地机器码，执行速度大幅提升。
static 代码块的核心目的：
让 JVM 提前 JIT 编译目标方法，进入“热点”状态，提高后续真正测试时的执行性能。
在 LeetCode 环境中，这段代码能带来什么？
在 LeetCode 上，OJ（Online Judge）测试你的代码时：
-
会调用你的方法很多次（例如不同测试用例）
-
每次执行时间都可能受到 JIT 编译的影响
提前用 static block 触发 JIT，可以让你正式测试开始前方法已经优化完毕，从而在毫秒级性能题中获得 更快的运行时间，甚至在某些比赛或榜单中冲击更好的排名。
注意
这不是业务代码中推荐的写法，只在「力扣/竞赛环境中刷题、追求更高性能」时才会用到。
实际项目开发中不需要这样做，JVM 自己会逐步优化热点方法。
总结
| 项目 | 说明 |
|---|---|
| 作用 | 提前触发 JVM 的 JIT 编译，让方法进入“热点”优化状态 |
| 适用 | 竞赛/LeetCode 中追求极限执行时间 |
| 原理 | JVM 对热点代码会优化成本地机器码，static 块提前“预热” |
| 风险 | 没有逻辑副作用，但不适合用在真实业务代码中 |
小结
希望本文对你有帮助，如果有其他想法的话，也可以评论区和大家分享哦。
各位极客的点赞收藏转发，是老马持续写作的最大动力！
感兴趣的小伙伴可以关注一波，精彩内容，不容错过。
