算法热题，JVM、JUC问答
package code3;
import java.util.Scanner;
/**
* 快速排序
*
* @author WYF
* @date 2020/02/06
*/
public class Main4 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] a = new int[100];
int length = 0;
while (length < 100) {
int temp = scanner.nextInt();
if (temp == 0) {
break;
}
a[length] = temp;
length++;
}
sort(a, 0, length - 1);
for (int i = 0; i < length; i++) {
System.out.print(a[i] + " ");
}
}
private static void sort(int[] a, int low, int high) {
int i, j, temp, t;
if (low > high) {
return;
}
temp = a[low];
i = low;
j = high;
while (i < j) {
while (a[j] >= temp && i < j) {
//先比较后移动
j--;
}
while (a[i] <= temp && i < j) {
//这里好像多了一步和自己比较，但是没关系，反正也是i++ 会通过的
i++;
}
if (i < j) {
t = a[j];
a[j] = a[i];
a[i] = t;
}
}
//核心1：上面这两个循环， 不是找一次就OK，一直找一直交换，找到i<j为止
//核心2：循环结束了，到了考虑临界的情况，上面的i<j挺精髓的，每一步都设置了i不能大于j
//那么 一种只有一种情况就是i==j
if (i == j) {
t = a[low];
a[low] = a[i];
a[i] = t;
}
//核心3 递归嘛 我干一点然后交给别人去干就行了
sort(a, low, i - 1);
sort(a, j + 1, high);
}
}
//注意：
// 1.
// <=、>=和<、>的区别，可以说整个是整个算法的灵魂，如果换成<和 >
// 就是另一种快速排序了，一直拿第一个数字比较的那种，不去掉就是浪费时间效率
//2.
// int temp1 = a[low];
// a[low] = a[j];
// a[j] = temp1;
//是a[low] 与a[j]交换不是a[j]与temp交换
//3.
//右边的兵必须先移动，才能保证左边的是小的
2、堆排序
package code3.com.sort;
import java.util.Arrays;
/**
* @Author: WYF
* @Description: 构造小根堆（注意：小根堆就要先初始化大根堆，这样沉底出来才是小根堆）
* @Create: 2020/4/2 21:02
* @Version: 1.0
*/
public class HeapSort {
public static void main(String[] args) {
int[] arr = {9,8,7,6,5,4,3,2,1};
sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
/** 1.构造大根堆
* 为什么是arr.len/2-1?废话，只有arr.len/2-1才能保证他是非叶子节点
* 注意：索引从0开始
*/
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
System.out.println(Arrays.toString(arr));
/**
* 2.大根堆的堆顶沉底，重新调整结构
* i不断减小，确定的元素不断增多
*/
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
/**
* 此处为何是0，次大的数字一定在堆顶的俩边
*/
adjustHeap(arr, 0, i);
}
}
public static void swap(int[] arr, int i, int i1) {
int temp = arr[i];
arr[i] = arr[i1];
arr[i1] = temp;
}
/**
* @Description: 对该节点调整，以保证该节点：根>左>右
* 最优：取根节点为保存在temp，左右找一个大的来和temp比较，比较成功就交换，否则不变
* @Param: [arr, i, length]
* @Return: void
* @Author: WYF
* @Date: 2020/4/2 21:32
*/
private static void adjustHeap(int[] arr, int i, int length) {
/**这里我发现数组存放的二叉树的节点可以从0开始，也可以从1
* 这两种对应的子节点不一样的，有个是i/2+1和i/2+2（从0开始），有个是i/2和i/2+1（从一开始）
* 先取出当前元素i
*/
int temp = arr[i];
/**
* 从i结点的左子结点开始，也就是2i+1处开始
* 这个循环很有意义，是标志着重新调整结构，因为有可能被这么一整，顺序乱了
*/
//多此比较 直到把temp找到一合适的位置，即调整堆结构，让它还是一个堆，不会因为头尾交换改变结构
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
if (k + 1 < length && arr[k] < arr[k + 1]) {
k++;
}
/**
* 如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
*/
if (arr[k] > temp) {
arr[i] = arr[k];
i = k;
} else {
break;
}
}
/**
* 放回去
*/
arr[i] = temp;
}
}
/**
* @Author: WYF
* @Description: 归并排序
* https://www.cnblogs.com/chengxiao/p/6194356.html
* @Create: 2020/4/29 13:37
* @Version: 1.0
*/
public class MergeSort {
public static void main(String []args){
int []arr = {9,8,7,6,5,4,3,2,1};
sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
int[] temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr, int left, int right, int[] temp) {
if (left<right) {
int mid = left+(right-left)/2;
sort(arr,left,mid,temp);
sort(arr,mid+1,right,temp);
merge(arr,left,mid,right,temp);
}
}
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while(j<=right){//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}
} 算法热题
难度中等5026
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = "" 输出: 0
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;
}
}
看题解
-
无重复字符的最长子串
-
k个一组翻转链表
-
反转链表
-
top k（这个题目重点，https://leetcode-cn.com/problems/top-k-frequent-elements/，https://leetcode-cn.com/problems/smallest-k-lcci/）
-
三数之和
-
股票问题（有好多题目）
-
LRU
-
两数之和
-
相交链表
-
背包问题（01背包、完全背包、多重背包）
JVM
jvm注意几个之点：
1、jvm5个部分是什么样的，每个部分的作用；
2、jmm模型，三个特性；
3、垃圾收集算法（比如年轻代用复制算法、老年待用什么算法）
4、双亲委派机制是什么样的？
5、 垃圾收集器有哪写？
juc等其他
1.HashMap 1.7使用数组加链表，节点是内部类Entry节点，使用的是头插法 扩容resize方法调用transfer方法，造成Entry的rehash，可能形成循环链表。 下次get得到死循环。另外，没有加锁容易造成线程不安全
1.8链表、数组加红黑树，Entry节点—》Note节点,在put的时候就行优化
1.7成链的机制， 假设两个线程执行put方法拆入节点，当一个线程要进行扩容，调用resize，resize调用transfer方法， 两个另一个线程插入了节点，造成了重新 rehash 之后链表的顺序被反转 这时候，transfer方法重新获得线程，这时候，就造成了插入的两个结点形成一个环
2.他的扩容机制？ 初始化 HaspMap，若无设置capacity，默认的容量是16， 负载因子0.75 计算一个出来一个扩容的阈值， put的时候判断，当前的size是不是大于这个阈值，大于的时候就扩容成原来两杯。
原来的Entry就行resize
3.java1.7是头插法、1.8是尾插法，1.8就安全？ 不是，只是尾插法没有改变原来的顺序，不会出现链表循环的过程
4.线程不安全 Hashtable private Hashtable<String,Object> hashtable = new Hashtable<>(); 对于Hashtable，源码里面对他的get/put方法都做了Synchronized修饰， 方法级别的阻塞，同一个时刻，只有一个线程进行get/put，效率低。
synchronizedMap private Map<String, Object> map = Collections.synchronized(new HashMap<String,Object>); 用工具类将HashMap封装，SynchronizedMap的实现方式是加了个！对象锁！，每次对HashMap的操作都要先获取这个mutex的对象锁才能进入，所以性能也不会比HashTable好到哪里去，也不建议使用。
coucurrentHashMap 推荐使用， 在jdk8之前是使用分段加锁的一个方式，分成16个桶，每次只加锁其中一个桶，而在jdk8又加入了红黑树和CAS算法来实现。 每次只会锁目前一个segment，用synchronized+CAS，效率更高了，并发度更高。
5.锁升级： 无锁 偏向，获取这个锁的线程，优先再去获取这个锁 获取不到-> 轻量级、乐观锁CAS 获取不到， 进行自旋，到底一定程度 synchronized
6.事务隔离级别：未提交读、读已提交，可重复读、串行化
7.AOP实现方式： 动态代理 JDK的proxy 接口类，没有接口就不太合适 cglib 生成目标类的子类，然后去实现代理 性能：cglib在创建的时候慢，运行的时候快