Java基础复习
- Java数组的声明与初始化
- Java ArrayList
- Java HashMap
- Java String 类
- Java LinkedList
- Java Deque继承LinkedList
- Java Set
- Java 队列
- 优先队列:第二题用到了
第一题：215. 数组中的第K个最大元素
可以直接使用Arrays.sort()快排，然后return nums[n-k];
或者手动实现快速选择的内容：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
class Solution {
int quickselect(int[] nums, int l, int r, int k) {
if (l == r) return nums[k];
int x = nums[l], i = l - 1, j = r + 1; //选最左边的为基准。
while (i < j) {
do{
i++;
}while(nums[i] < x);//左边的都小于x
do{
j--;
}while(nums[j] > x);//右边的都大于x
if (i < j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
if (k <= j) return quickselect(nums, l, j, k); //一趟排序后，基准比第k大的大，那么在基准左边找。
else return quickselect(nums, j + 1, r, k);//否则在基准右边找。
}
public int findKthLargest(int[] _nums, int k) {
int n = _nums.length;
return quickselect(_nums, 0, n - 1, n - k);
}
}
另一种解法就是堆排序：参考：https://pdai.tech/md/algorithm/alg-sort-x-heap.html
逻辑结构是完全二叉树，存储结构是数组。之间的联系如下：
算法实现步骤就是， ① 初始化堆: 将数列a[1…n]构造成最大堆。 ② 交换数据: 将a[1]和a[n]交换，使a[n]是a[1…n]中的最大值；然后将a[1…n-1]重新调整为最大堆。 接着，将a[1]和a[n-1]交换，使a[n-1]是a[1…n-1]中的最大值；然后将a[1…n-2]重新调整为最大值。 依次类推，直到整个数列都是有序的。
public static void maxHeapDown(int[] a, int start, int end) {
int c = start; // 当前(current)节点的位置
int l = 2*c + 1; // 左(left)孩子的位置
int tmp = a[c]; // 当前(current)节点的大小
for (; l <= end; c=l,l=2*l+1) {
// "l"是左孩子，"l+1"是右孩子
if ( l < end && a[l] < a[l+1])
l++; // 左右两孩子中选择较大者，即m_heap[l+1]
if (tmp >= a[l])
break; // 调整结束
else { // 交换值
a[c] = a[l];
a[l]= tmp;
}
}
}
/*
* 堆排序(从小到大)
*
* 参数说明:
* a -- 待排序的数组
* n -- 数组的长度
*/
public static void heapSortAsc(int[] a, int n) {
int i,tmp;
// 从(n/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个(最大)二叉堆。
for (i = n / 2 - 1; i >= 0; i--)
maxHeapDown(a, i, n-1);
// 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
for (i = n - 1; i > 0; i--) {
// 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。
tmp = a[0];
a[0] = a[i];
a[i] = tmp;
// 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。
// 即，保证a[i-1]是a[0...i-1]中的最大值。
maxHeapDown(a, 0, i-1);
}
}
提交代码：
class Solution {
public static void heapSortAsc(int[] a, int n){
for(int i=n/2-1; i>=0; i--){
maxHeapDown(a, i, n-1);
}
for (int i = n - 1; i > 0; i--) {
// 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。
int tmp = a[0];
a[0] = a[i];
a[i] = tmp;
// 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。
// 即，保证a[i-1]是a[0...i-1]中的最大值。
maxHeapDown(a, 0, i-1);
}
}
public static void maxHeapDown(int[] a, int start, int end) {
int c = start; // 当前(current)节点的位置
int l = 2*c + 1; // 左(left)孩子的位置
int tmp = a[c]; // 当前(current)节点的大小
for (; l <= end; c=l,l=2*l+1) {
// "l"是左孩子，"l+1"是右孩子
if ( l < end && a[l] < a[l+1])
l++; // 左右两孩子中选择较大者，即m_heap[l+1]
if (tmp >= a[l])
break; // 调整结束
else { // 交换值
a[c] = a[l];
a[l]= tmp;
}
}
}
public int findKthLargest(int[] _nums, int k) {
int n = _nums.length;
heapSortAsc(_nums, n);
return _nums[n-k];
}
}
第二题：373. 查找和最小的 K 对数字
以下写法超出内存限制：
class Solution {
public static void heapSortAsc(int[][] a, int n){
for(int i=n/2-1; i>=0; i--){
maxHeapDown(a, i, n-1);
}
for (int i = n - 1; i > 0; i--) {
// 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。
int[] tmp = a[0];
a[0] = a[i];
a[i] = tmp;
// 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。
// 即，保证a[i-1]是a[0...i-1]中的最大值。
maxHeapDown(a, 0, i-1);
}
}
public static void maxHeapDown(int[][] a, int start, int end) {
int c = start; // 当前(current)节点的位置
int l = 2*c + 1; // 左(left)孩子的位置
int[] tmp = a[c]; // 当前(current)节点的大小
for (; l <= end; c=l,l=2*l+1) {
// "l"是左孩子，"l+1"是右孩子
if ( l < end && (a[l][0] + a[l][1]) < (a[l+1][0] + a[l+1][1]))
l++; // 左右两孩子中选择较大者，即m_heap[l+1]
if ((tmp[0]+tmp[1]) >= (a[l][0] + a[l][1]))
break; // 调整结束
else { // 交换值
a[c] = a[l];
a[l] = tmp;
}
}
}
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
int n = nums1.length*nums2.length;
int[][] a = new int[n][2];
int idx = 0;
for(int i=0; i<nums1.length; i++){
for(int j=0; j<nums2.length; j++){
a[idx][0] = nums1[i];
a[idx++][1] = nums2[j];
}
}
heapSortAsc(a, n);
List<List<Integer>> results = new ArrayList<List<Integer>>();
for(int i=0; i<k; i++){
List<Integer> tmp = new ArrayList<Integer>();
tmp.add(a[i][0]);
tmp.add(a[i][1]);
results.add(tmp);
}
return results;
}
}
参考：灵茶山艾府的题解
觉得这样的大神，每次写得代码都很简洁。哭唧唧。我和这篇的问题，就在于，我使用的代码的堆，没办法随时调整。
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> ans = new ArrayList<>(k); // 预分配空间
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.add(new int[]{nums1[0] + nums2[0], 0, 0});
while (ans.size() < k) {
int[] p = pq.poll();
int i = p[1];
int j = p[2];
ans.add(List.of(nums1[i], nums2[j]));
if (j == 0 && i + 1 < nums1.length) {
pq.add(new int[]{nums1[i + 1] + nums2[0], i + 1, 0});
}
if (j + 1 < nums2.length) {
pq.add(new int[]{nums1[i] + nums2[j + 1], i, j + 1});
}
}
return ans;
}
}
这里自己仿照源码写了一份优先队列
class Solution {
class MyPriorityQueue{
//仿照源码编写自己的
private int[][] queue;
private int size;
MyPriorityQueue(){
queue=new int[0][0];
size = 0;
}
private int Mycompare(int[] a, int[] b){
return a[0]-b[0];
}
public void offer(int[] e){
int i = size;
if (i >= queue.length)
queue = Arrays.copyOf(queue, i+1);
size = i + 1;
if (i == 0)//队列原来为空，这是插入的第一个元素
queue[0] = e;
else
siftUp(i, e);//调整
}
private void siftUp(int k, int[] x) { //找到x该待的位置
while (k > 0) {
int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
int[] e = queue[parent];
if (Mycompare(x, e) >= 0) break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
public int[] peek() {
if (size == 0)
return null;
return queue[0];//0下标处的那个元素就是最小的那个
}
public int[] poll() {
if (size == 0)
return null;
int s = --size;
int[] result = queue[0];//0下标处的那个元素就是最小的那个
int[] x = queue[s]; //最后一个叶子结点
queue[s] = null;
if (s != 0) //队列不为空要调整
siftDown(0, x);//调整
return result;
}
private void siftDown(int k, int[] x) {
int half = size >>> 1; //size/2
while (k < half) {
//首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标
int child = (k << 1) + 1;//leftNo = parentNo*2+1
int[] c = queue[child];
int right = child + 1;
if (right < size && Mycompare(c, queue[right]) > 0)
c = queue[child = right];
if (Mycompare(x, c) <= 0)
break;
queue[k] = c;//然后用c取代原来的值
k = child;
}
queue[k] = x;
}
}
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> ans = new ArrayList<>(k); // 预分配空间
MyPriorityQueue pq = new MyPriorityQueue();
pq.offer(new int[]{nums1[0] + nums2[0], 0, 0});
while (ans.size() < k) {
int[] p = pq.poll();
int i = p[1];
int j = p[2];
ans.add(List.of(nums1[i], nums2[j]));
if (j == 0 && i + 1 < nums1.length) {
pq.offer(new int[]{nums1[i + 1] + nums2[0], i + 1, 0});
}
if (j + 1 < nums2.length) {
pq.offer(new int[]{nums1[i] + nums2[j + 1], i, j + 1});
}
}
return ans;
}
}
第三题：264. 丑数 II
首先明确一下质因子是什么？
质因子（或质因数）在数论里是指能整除给定正整数的质数。
只有两个正因数（1和它本身）的自然数即为质数。（2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97…）
仔细想想还是不难的，就是用小顶堆，弹出一个x，添加2x，3x，5x进去。
class Solution {
int[] NUMS = new int[]{2, 3, 5};
class MyPriorityQueue{
//仿照源码编写自己的
private long[] queue;
private int size;
MyPriorityQueue(){
queue=new long[0];
size = 0;
}
private long Mycompare(long a, long b){
return a-b;
}
public void offer(long e){
int i = size;
if (i >= queue.length)
queue = Arrays.copyOf(queue, i+1);
size = i + 1;
if (i == 0)//队列原来为空，这是插入的第一个元素
queue[0] = e;
else
siftUp(i, e);//调整
}
private void siftUp(int k, long x) { //找到x该待的位置
while (k > 0) {
int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
long e = queue[parent];
if (Mycompare(x, e) >= 0) break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
public long peek() {
return queue[0];//0下标处的那个元素就是最小的那个
}
public long poll() {
int s = --size;
long result = queue[0];//0下标处的那个元素就是最小的那个
long x = queue[s]; //最后一个叶子结点
queue[s] = -1;
if (s != 0) //队列不为空要调整
siftDown(0, x);//调整
return result;
}
private void siftDown(int k, long x) {
int half = size >>> 1; //size/2
while (k < half) {
//首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标
int child = (k << 1) + 1;//leftNo = parentNo*2+1
long c = queue[child];
int right = child + 1;
if (right < size && Mycompare(c, queue[right]) > 0)
c = queue[child = right];
if (Mycompare(x, c) <= 0)
break;
queue[k] = c;//然后用c取代原来的值
k = child;
}
queue[k] = x;
}
}
public int nthUglyNumber(int n) {
//我目前的思路就是得到一组序列，长度为n，就是从1开始算，找到第n个满足条件的就行。
int[] result = new int[n+1];
result[1] = 1;
if(n==1){
return result[n];
}
int sum=2;
MyPriorityQueue queue = new MyPriorityQueue();
Set<Long> had = new HashSet<>();
queue.offer(2); had.add(2l);
queue.offer(3); had.add(3l);
queue.offer(5); had.add(5l);
while(sum<=n){
long tmp = queue.poll();
result[sum] = (int)tmp;
for(int i=0; i<NUMS.length; i++){
if(!had.contains(tmp*NUMS[i])){
had.add(tmp*NUMS[i]);
queue.offer(tmp*NUMS[i]);
}
}
sum++;
}
return result[n];
}
}
第四题：218.天际线问题
算术评级是9，我就看一看，凑个热闹。
莫名想接雨水，但是接雨水好像是维护一个单调队列。
后期有时间再补。先把简单题和中等题搞明白。o(╥﹏╥)o。
