用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的 Push 和 Pop 操作。
- 棧先入后出，隊(duì)列先進(jìn)先出。
所以入棧一次出一次，序列相反。再入棧一次出棧一次，成序列相同。
第一次：入1-2-3 出3-2-1
第二次：入3-2-1 出1-2-3
Stack<Integer> in = new Stack<Integer>();
out.isEmpty()
in.push(node);
out.push(in.pop());
包含 min 函數(shù)的棧
實(shí)現(xiàn)一個(gè)包含 min() 函數(shù)的棧，該方法返回當(dāng)前棧中最小的值。
- 2個(gè)棧，一個(gè)直接放數(shù)據(jù)。一個(gè)進(jìn)行比較，將較小的數(shù)據(jù)放入第二個(gè)棧中去。
minStack.push(minStack.isEmpty() ? node : Math.min(minStack.peek(), node));
//感覺像固定寫法
public void pop() {
dataStack.pop();
minStack.pop();
}
棧的壓入、彈出序列
輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。
- 入棧的時(shí)候比較一下是不是出棧序列的當(dāng)前值，是的話，出了，不是的話，繼續(xù)加。到最后看有沒有出完即可。
return stack.isEmpty();
最小的 K 個(gè)數(shù)
給定一個(gè)長(zhǎng)度為 n 的可能有重復(fù)值的數(shù)組，找出其中不去重的最小的 k 個(gè)數(shù)。例如數(shù)組元素是4,5,1,6,2,7,3,8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1,2,3,4(任意順序皆可)。
要求：空間復(fù)雜度 O(n)O(n) ，時(shí)間復(fù)雜度 O(nlogn)O(nlogn)
- 大小為k的最小堆
- 構(gòu)建一個(gè)大頂堆，取大頂堆前幾位。
- 初始化實(shí)現(xiàn)大頂堆，不設(shè)置則默認(rèn)為小頂堆。
- PriorityQueue<Integer> maxHeap = new PriorityQueue<>
((o1, o2) -> o2 - o1); - 輸出第一個(gè)數(shù)，并刪除。
maxHeap.poll();
返回堆的隊(duì)列
return new ArrayList<>(maxHeap);
- 快排
- 快速排序的方法，找到第K的數(shù)的位置。
- 每執(zhí)行一次快排，某個(gè)數(shù)之前一定是小于它的，之后一定是大于它的。
數(shù)據(jù)流中的中位數(shù)
如何得到一個(gè)數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個(gè)數(shù)的平均值。
- 大小頂堆
- 數(shù)據(jù)流是一個(gè)串，假設(shè)排序完成，我將它分為2部分。
- 這樣最半部分取最大值，右半部分取最小值，實(shí)現(xiàn)其平均數(shù)的結(jié)果。
- 當(dāng)N為偶數(shù)，右半邊的數(shù)要全大于左邊，所以先往左插，再插右?；鶖?shù)相反。
left.add(val);
right.add(left.poll());
字符流中第一個(gè)不重復(fù)的字符2022.7.9-3
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來找出字符流中第一個(gè)只出現(xiàn)一次的字符。例如，當(dāng)從字符流中只讀出前兩個(gè)字符 "go" 時(shí)，第一個(gè)只出現(xiàn)一次的字符是 "g"。當(dāng)從該字符流中讀出前六個(gè)字符“google" 時(shí)，第一個(gè)只出現(xiàn)一次的字符是 "l"。
- 隊(duì)列，我的第一個(gè)數(shù)字，一定是只出現(xiàn)一次的，且一定是第一次出現(xiàn)的。之后出現(xiàn)了第二次，就把它出了。
private int[] cnts = new int[128];
private Queue<Character> queue = new LinkedList<>();
public void Insert(char ch) {
cnts[ch]++;
queue.add(ch);
while (!queue.isEmpty() && cnts[queue.peek()] > 1)
queue.poll();
}
public char FirstAppearingOnce() {
return queue.isEmpty() ? '#' : queue.peek();
}
滑動(dòng)窗口的最大值2022.7.9-4
給定一個(gè)數(shù)組和滑動(dòng)窗口的大小，找出所有滑動(dòng)窗口里數(shù)值的最大值。
例如，如果輸入數(shù)組 {2, 3, 4, 2, 6, 2, 5, 1} 及滑動(dòng)窗口的大小 3，那么一共存在 6 個(gè)滑動(dòng)窗口，他們的最大值分別為 {4, 4, 6, 6, 6, 5}。
- 堆的維護(hù)，直接生成一個(gè)結(jié)果堆，然后對(duì)它進(jìn)行維護(hù)。
可以直接刪除某個(gè)數(shù)
heap.remove(num[i]);
heap.add(num[j]);
ret.add(heap.peek());
