第8章 常用容器
笔记
List
接口：java.util.List<>
实现：
java.util.ArrayList<>：变长数组java.util.LinkedList<>：双链表
方法：
add()：在末尾添加一个元素clear()：清空size()：返回长度isEmpty()：是否为空get(i)：获取第i个元素set(i, val)：将第i个元素设置为val
栈
类：java.util.Stack<>
方法：
push()：压入元素pop()：弹出栈顶元素，并返回栈顶元素peek()：返回栈顶元素size()：返回长度empty()：栈是否为空clear()：清空
队列
接口：java.util.Queue<>
实现：
java.util.LinkedList<>：双链表java.util.PriorityQueue<>：优先队列，默认是小根堆，大根堆写法：new PriorityQueue<>(Collections.reverseOrder())
方法：
add()：在队尾添加元素remove()：删除并返回队头isEmpty()：是否为空size()：返回长度peek()：返回队头clear()：清空
Set
接口：java.util.Set<K>
实现：
java.util.HashSet<K>：哈希表java.util.TreeSet<K>：平衡树
方法：
add()：添加元素contains()：是否包含某个元素remove()：删除元素size()：返回元素数isEmpty()：是否为空clear()：清空
java.util.TreeSet中额外的方法：
ceiling(key)：返回大于等于key的最小元素，不存在则返回nullfloor(key)：返回小于等于key的最大元素，不存在则返回null
Map
接口：java.util.Map<K, V>
实现：
java.util.HashMap<K, V>：哈希表java.util.TreeMap<K, V>：平衡树
方法：
put(key, value)：添加关键字和其对应的值get(key)：返回关键字对应的值containsKey(key)：是否包含关键字remove(key)：删除关键字size()：返回元素数isEmpty()：是否为空clear()：清空entrySet()：获取Map中的所有对象的集合Map.Entry<K, V>：Map中的对象类型getKey()：获取关键字getValue()：获取值
java.util.TreeMap<K, V>中额外的方法：
ceilingEntry(key)：返回大于等于key的最小元素，不存在则返回nullfloorEntry(key)：返回小于等于key的最大元素，不存在则返回null
习题
AcWing 828. 模拟栈
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
Stack<Integer> stack = new Stack<Integer>();
while(n-- > 0) {
String op = scanner.next();
switch (op) {
case "push":
int x = scanner.nextInt();
stack.push(x);
break;
case "query":
System.out.println(stack.peek());
break;
case "pop":
stack.pop();
break;
case "empty":
if (stack.isEmpty()) System.out.println("YES");
else System.out.println("NO");
break;
}
}
scanner.close();
}
}
AcWing 67. 数字在排序数组中出现的次数
class Solution {
public int getNumberOfK(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums) {
if (!map.containsKey(num)) map.put(num, 1);
else map.put(num, map.get(num) + 1);
}
if (map.containsKey(k)) return map.get(k);
else return 0;
}
}
AcWing 68. 0到n-1中缺失的数字
class Solution {
public int getMissingNumber(int[] nums) {
for (int i = 0; i < nums.length; i++)
if (nums[i] != i)
return i;
return nums.length;
}
}
笔记
- 由于数组是有序的，因此如果
nums[i] != i时，说明缺的就是这个数字。否则缺的就是nums.length - 特别的，当数组为空时，答案为
0
AcWing 32. 调整数组顺序使奇数位于偶数前面
class Solution {
public void reOrderArray(int[] array) {
int i = 0, j = array.length - 1;
while(i < j) {
while(i < array.length && array[i] % 2 != 0) i++;
while(j >= 0 && array[j] % 2 == 0) j--;
if (i < j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
}
AcWing 20. 用两个栈实现队列
class MyQueue {
private Stack<Integer> s1, s2;
/** Initialize your data structure here. */
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
while(!s2.isEmpty()) s1.push(s2.pop());
s1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
while(!s1.isEmpty()) s2.push(s1.pop());
return s2.pop();
}
/** Get the front element. */
public int peek() {
while(!s1.isEmpty()) s2.push(s1.pop());
return s2.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return s1.empty() && s2.empty();
}
}
AcWing 829. 模拟队列
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
Queue<Integer> queue = new LinkedList<>();
while(n-- > 0) {
String op = scanner.next();
switch (op) {
case "push":
int x = scanner.nextInt();
queue.add(x);
break;
case "query":
System.out.println(queue.peek());
break;
case "pop":
queue.remove();
break;
case "empty":
if (queue.isEmpty()) System.out.println("YES");
else System.out.println("NO");
break;
}
}
scanner.close();
}
}
AcWing 53. 最小的k个数
class Solution {
public List<Integer> getLeastNumbers_Solution(int[] input, int k) {
Queue<Integer> heap = new PriorityQueue<>();
for (int elem : input) heap.add(elem);
List<Integer> res = new ArrayList<>();
while(k-- > 0) res.add(heap.remove());
return res;
}
}
AcWing 75. 和为S的两个数字
class Solution {
public int[] findNumbersWithSum(int[] nums, int target) {
Set<Integer> set = new HashSet<>();
for (int elem: nums)
if (set.contains(target - elem)) return new int[]{target - elem, elem};
else set.add(elem);
return new int[]{-1, -1};
}
}
AcWing 26. 二进制中1的个数
class Solution {
public int NumberOf1(int n) {
int res = 0;
for (int i = 0; i < 32; i++)
res += n >> i & 1;
return res;
}
}
AcWing 136. 邻值查找
import com.sun.source.tree.Tree;
import java.io.*;
import java.util.Map;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String line = bufferedReader.readLine();
int n = Integer.parseInt(line);
int[] a = new int[n];
String[] nums = bufferedReader.readLine().split(" ");
for (int i = 0; i < n; i++) a[i] = Integer.parseInt(nums[i]);
bufferedReader.close();
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
TreeMap<Integer, Integer> map = new TreeMap<>();
map.put(a[0], 0);
for (int i = 1; i < n; i++) {
Map.Entry<Integer, Integer> up = map.ceilingEntry(a[i]);
Map.Entry<Integer, Integer> down = map.floorEntry(a[i]);
int d = Integer.MAX_VALUE, pos = -1;
if (up != null) {
d = up.getKey() - a[i];
pos = up.getValue();
}
if (down != null && a[i] - down.getKey() <= d) {
d = a[i] - down.getKey();
pos = down.getValue();
}
bufferedWriter.write(d + " " + (pos + 1) + '\n');
map.put(a[i], i);
}
bufferedWriter.flush(); // 需要手动刷新缓冲区
bufferedReader.close();
}
}
笔记
- 可用平衡树快速查找大于等于某个元素的最小值，以及小于等于某个元素的最大值。由于本题需要获取下标，因此本题需要用带有键值对的
Map平衡树。 - 注意
i从1开始取值，因为i>j - 本题数据较多，需要用
BufferedReader优化输入以及BufferedWriter优化输出
