CD79 一种消息接收并打印的结构设计
public class CD79_1
{
public static class Node
{
public int num;
public Node next;
public Node(int num)
{
this.num = num;
}
}
public static class MessageBox
{
private HashMap<Integer, Node> headMap;
private HashMap<Integer, Node> tailMap;
private int lastPrint;
public MessageBox()
{
headMap = new HashMap<Integer, Node>();
tailMap = new HashMap<Integer, Node>();
lastPrint = 0;
}
public void receive(int num)
{
if (num < 1) return;
Node cur = new Node(num);
headMap.put(num, cur);
tailMap.put(num, cur);
if (tailMap.containsKey(num - 1))
{
tailMap.get(num - 1).next = cur;
tailMap.remove(num - 1);
headMap.remove(num);
}
if (headMap.containsKey(num + 1))
{
cur.next = headMap.get(num + 1);
tailMap.remove(num);
headMap.remove(num + 1);
}
if (headMap.containsKey(lastPrint + 1))
print(num);
}
private void print(int num)
{
Node node = headMap.get(++lastPrint);
headMap.remove(lastPrint);
while (node != null)
{
System.out.println(node.num + " " + num);
node = node.next;
lastPrint++;
}
tailMap.remove(--lastPrint);
}
}
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
MessageBox messageBox = new MessageBox();
int n = in.nextInt();
for (int i = 0; i < n; i++)
messageBox.receive(in.nextInt());
}
}
CD80 随时找到数据流的中位数
public class CD80_1
{
public static PriorityQueue<Integer> minHeap = new PriorityQueue<>();
public static PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
public static int count = 0;
public static void Insert(Integer num)
{
count++;
if (count % 2 != 0)
{
minHeap.add(num);
maxHeap.add(minHeap.poll());
}
else
{
maxHeap.add(num);
minHeap.add(maxHeap.poll());
}
}
public static Double GetMedian()
{
if (minHeap.size() == maxHeap.size())
return (minHeap.peek() + maxHeap.peek()) / 2.0;
else
return maxHeap.peek() * 1.0;
}
}
CD81 在两个长度相等的排序数组中找到上中位数❓
/*❓*/
public class CD81_1
{
public static int solution(int[] arr1, int[] arr2)
{
if (arr1 == null || arr2 == null || arr1.length != arr2.length)
{
throw new RuntimeException("Your arr is invalid!");
}
int start1 = 0;
int end1 = arr1.length - 1;
int start2 = 0;
int end2 = arr2.length - 1;
int mid1 = 0;
int mid2 = 0;
int offset = 0;
while (start1 < end1)
{
mid1 = (start1 + end1) / 2;
mid2 = (start2 + end2) / 2;
// 元素个数为奇数，则 offset 为 0；
// 元素个数为偶数，则 offset 为 1
offset = ((end1 - start1 + 1) & 1) ^ 1;
if (arr1[mid1] > arr2[mid2])
{
end1 = mid1;
start2 = mid2 + offset;
}
else if (arr1[mid1] < arr2[mid2])
{
start1 = mid1 + offset;
end2 = mid2;
}
else
return arr1[mid1];
}
return Math.min(arr1[start1], arr2[start2]);
}
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr1 = new int[n];
int[] arr2 = new int[n];
for (int i = 0; i < n; i++)
arr1[i] = in.nextInt();
for (int i = 0; i < n; i++)
arr2[i] = in.nextInt();
System.out.println(solution(arr1, arr2));
}
}
CD82 在两个排序数组中找到第 k 小的数❓
/*❓*/
public class CD82_1
{
public static int solution(int[] arr1, int[] arr2, int kth)
{
if (arr1 == null || arr2 == null)
throw new RuntimeException("Your arr is invalid!");
if (kth < 1 || kth > arr1.length + arr2.length)
throw new RuntimeException("K is invalid!");
int[] longs = arr1.length >= arr2.length ? arr1 : arr2;
int[] shorts = arr1.length < arr2.length ? arr1 : arr2;
int l = longs.length;
int s = shorts.length;
if (kth <= s)
return getUpMedian(shorts, 0, kth - 1, longs, 0, kth - 1);
if (kth > l)
{
if (shorts[kth - l - 1] >= longs[l - 1])
return shorts[kth - l - 1];
if (longs[kth - s - 1] >= shorts[s - 1])
return longs[kth - s - 1];
return getUpMedian(shorts, kth - l, s - 1, longs, kth - s, l - 1);
}
if (longs[kth - s - 1] >= shorts[s - 1])
return longs[kth - s - 1];
return getUpMedian(shorts, 0, s - 1, longs, kth - s, kth - 1);
}
public static int getUpMedian(int[] a1, int s1, int e1, int[] a2, int s2, int e2)
{
int mid1 = 0;
int mid2 = 0;
int offset = 0;
while (s1 < e1)
{
mid1 = (s1 + e1) / 2;
mid2 = (s2 + e2) / 2;
offset = ((e1 - s1 + 1) & 1) ^ 1;
if (a1[mid1] > a2[mid2])
{
e1 = mid1;
s2 = mid2 + offset;
}
else if (a1[mid1] < a2[mid2])
{
s1 = mid1 + offset;
e2 = mid2;
}
else
return a1[mid1];
}
return Math.min(a1[s1], a2[s2]);
}
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt(), k = in.nextInt();
int[] arr1 = new int[n];
int[] arr2 = new int[m];
for (int i = 0; i < n; i++)
arr1[i] = in.nextInt();
for (int i = 0; i < m; i++)
arr2[i] = in.nextInt();
System.out.println(solution(arr1, arr2, k));
}
}
CD83 两个有序数组间相加和的 Top k 问题
public class CD83_1
{
public static class Node implements Comparable<Node>
{
public int index1;
public int index2;
public int val;
public Node(int index1, int index2, int val)
{
this.index1 = index1;
this.index2 = index2;
this.val = val;
}
@Override
public int compareTo(Node o)
{
return o.val - this.val;
}
}
public static int[] solution(int[] arr1, int[] arr2, int k)
{
PriorityQueue<Node> que = new PriorityQueue<>();
HashSet<String> set = new HashSet<>();
int res[] = new int[k];
int len1 = arr1.length - 1, len2 = arr2.length - 1, index = -1;
que.add(new Node(len1, len2, arr1[len1] + arr2[len2]));
while (++index < k)
{
Node pollNode = que.poll();
int curIdx1 = pollNode.index1, curIdx2 = pollNode.index2;
res[index] = pollNode.val;
if (!set.contains(curIdx1 + "_" + (curIdx2 - 1)))
{
set.add(curIdx1 + "_" + (curIdx2 - 1));
que.add(new Node(curIdx1, curIdx2 - 1, arr1[curIdx1] + arr2[curIdx2 - 1]));
}
if (!set.contains((curIdx1 - 1) + "_" + curIdx2))
{
set.add((curIdx1 - 1) + "_" + curIdx2);
que.add(new Node(curIdx1 - 1, curIdx2, arr1[curIdx1 - 1] + arr2[curIdx2]));
}
}
return res;
}
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n = in.nextInt(), k = in.nextInt();
int[] arr1 = new int[n];
int[] arr2 = new int[n];
for (int i = 0; i < n; i++)
arr1[i] = in.nextInt();
for (int i = 0; i < n; i++)
arr2[i] = in.nextInt();
int[] res = solution(arr1, arr2, k);
System.out.println(Arrays.stream(res).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
}
}
CD84 出现次数的 Top k 问题
public class CD84_1
{
public static class Node implements Comparable<Node>
{
public String str;
public int times;
public Node(String s, int t)
{
str = s;
times = t;
}
@Override
public int compareTo(Node o)
{
if (this.times != o.times)
return o.times - this.times;
else
return this.str.compareTo(o.str);
}
}
public static void solution(String[] arr, int topK)
{
HashMap<String, Integer> map = new HashMap<>();
PriorityQueue<Node> que = new PriorityQueue<>();
for (String word : arr)
{
if (!map.containsKey(word))
map.put(word, 1);
else
map.put(word, map.get(word) + 1);
}
for (String word : map.keySet())
que.add(new Node(word, map.get(word)));
while (topK-- > 0)
{
Node pollNode = que.poll();
System.out.println(pollNode.str + " " + pollNode.times);
}
}
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n = in.nextInt(), k = in.nextInt();
in.nextLine();
String[] arr = new String[n];
for (int i = 0; i < n; i++)
arr[i] = in.nextLine();
solution(arr, k);
}
}
CD85 Manacher 算法
CD86 Manacher 算法（进阶）
CD87 KMP 算法
CD88 丢棋子问题
CD89 画匠问题
CD90 邮局选址问题