6. 從尾到頭列印鏈表
題意：面試題06. 從尾到頭列印鏈表
思路：首先遍歷一遍鏈表得到鏈表的長度，使用此長度初始化陣列，然后再從頭到尾遍歷一遍鏈表，并將遍歷得到的數字從后往前插入陣列，
class Solution {
public int[] reversePrint(ListNode head) {
int len = 0;
ListNode p = head;
while (p != null) {
p = p.next;
len ++;
}
int[] res = new int[len];
p = head;
while (p != null) {
res[--len] = p.val;
p = p.next;
}
return res;
}
}
9. 用兩個堆疊實作佇列
題意：面試題09. 用兩個堆疊實作佇列
思路：“出隊”操作，將一個堆疊的資料全部倒入到另一個空堆疊中，之后另一個堆疊的操作順序即為佇列的出堆疊順序，
class CQueue {
Stack<Integer> in;
Stack<Integer> out;
public CQueue() {
in = new Stack<>();
out = new Stack<>();
}
public void appendTail(int value) {
in.push(value);
}
public int deleteHead() {
if (out.isEmpty()) {
while (!in.isEmpty()) {
out.push(in.pop());
}
}
return out.isEmpty() ? -1 : out.pop();
}
}
18. 洗掉鏈表的節點
題意：面試題18. 洗掉鏈表的節點
思路1：要洗掉單鏈表中的某一個節點node，首先需要找到node的前一個節點pre，然后把pre的next指標指向node的下一個節點即可，
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head == null) {
return head;
}
if (head.val == val) {
return head.next;
}
ListNode p = head;
while (p.next != null) {
if (p.next.val == val) {
p.next = p.next.next;
break;
}
p = p.next;
}
return head;
}
}
思路2：上述思路1是在不能修改鏈表節點值的情況下的操作，如果可以修改鏈表的值，或者題目中沒有給出鏈表頭節點，只給出了要被洗掉的節點，
這時我們可以使用后面的節點值覆寫前面節點的值來完成洗掉節點操作，參照面試題 02.03. 洗掉中間節點
class Solution {
public void deleteNode(ListNode node) {
ListNode p = node;
ListNode q = node.next;
while (q.next != null) {
p.val = q.val;
p = p.next;
q = q.next;
}
p.val = q.val;
p.next = null;
}
}
22. 鏈表中倒數第k個節點
題意：面試題22. 鏈表中倒數第k個節點
思路：快慢雙指標法，讓快指標先走k步，然后快慢指標一起走，當快指標走到鏈表結尾的時候，慢指標就指向倒數第k個節點
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode p = head;
while (p != null && k > 0) {
p = p.next;
k --;
}
if (p == null && k > 0) {
return null;
}
ListNode q = head;
while (p != null) {
p = p.next;
q = q.next;
}
return q;
}
}
24. 反轉鏈表
題意：面試題24. 反轉鏈表
思路：遞回，先反轉當前節點的后面節點，reverseList(head.next)，這個函式回傳的是反轉之后的鏈表頭，即最后一個節點，進行這步操作之后，當前節點下一個節點指向的是反轉之后鏈表的尾部節點，即head.next，這時將head.next的下一個節點指向當前節點即可完成反轉，
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
ListNode next = reverseList(head.next);
head.next.next = head;
head.next = null;
return next;
}
}
25. 合并兩個排序的鏈表
題意：面試題25. 合并兩個排序的鏈表
思路：雙指標法，使用兩個指標分別指向l1和l2的頭結點，如果l1.val < l2.val，那么將l1指向的結點加入新的鏈表中，否則將l2指向的結點加入新的鏈表，
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(-1);
ListNode r = head;
while (l1 != null && l2 != null) {
if (l1.val > l2.val) {
r.next = l2;
l2 = l2.next;
} else {
r.next = l1;
l1 = l1.next;
}
r = r.next;
}
r.next = (l1 == null) ? l2 : l1;
return head.next;
}
}
30. 包含min函式的堆疊
題意：面試題30. 包含min函式的堆疊
思路：使用兩個堆疊，一個堆疊data用來保存資料，另一個堆疊min用來存data中最小值的資訊，
1）入堆疊時，若當前入堆疊的元素x小于min堆疊中堆疊頂元素，那么將當前元素x同時壓入data堆疊和min堆疊，
2）出堆疊時，若出堆疊元素x等于min的堆疊頂元素，那么將x也從min堆疊中彈出，
class MinStack {
Stack<Integer> data;
Stack<Integer> min;
/** initialize your data structure here. */
public MinStack() {
data = https://www.cnblogs.com/yzihan/p/new Stack<>();
min = new Stack<>();
}
public void push(int x) {
data.push(x);
if (min.isEmpty() || x <= min.peek()) {
min.push(x);
}
}
public void pop() {
if (data.isEmpty()) {
return;
}
int num = data.pop();
if (num == min.peek()) {
min.pop();
}
}
public int top() {
if (data.isEmpty()) {
return -1;
}
return data.peek();
}
public int min() {
if (min.isEmpty()) {
return -1;
}
return min.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.min();
*/
31. 堆疊的壓入、彈出序列
題意：面試題31. 堆疊的壓入、彈出序列
思路：建一個堆疊來模擬題目中的壓入、彈出操作，由于彈出序列中的第一個數字，一定是出現在堆疊頂時彈出的，如
pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
中，彈出序列中的第一個元素4出堆疊時，壓堆疊序列中一定是將4以及之前的元素壓入堆疊內了，這時模擬彈出堆疊頂的元素4，然后接著比較彈出序列的下一個元素是否還與堆疊頂相同，
即每次將彈出序列的元素，與堆疊頂元素比較，相同則彈出，不同則繼續入堆疊元素，最后判斷堆疊是否為空即可判斷是否為合法的彈出序列，
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int pushIndex = 0;
int popIndex = 0;
while (pushIndex < pushed.length) {
stack.push(pushed[pushIndex]);
while (popIndex < popped.length
&& !stack.isEmpty()
&& popped[popIndex] == stack.peek()) {
stack.pop();
popIndex ++;
}
pushIndex ++;
}
return stack.isEmpty();
}
}
35. 復雜鏈表的復制
題意：面試題35. 復雜鏈表的復制
思路：鏈表除了next指標，還包含random指標，使用一個Map記錄下已經創建的新結點，并將舊結點與新結點建立映射關系，在遍歷程序中對于已經創建過的結點直接從Map中取即可，
class Solution {
Map<Node, Node> map = new HashMap<>();
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
if (map.get(head) != null) {
return map.get(head);
}
Node newNode = new Node(head.val);
map.put(head, newNode);
newNode.next = copyRandomList(head.next);
newNode.random = copyRandomList(head.random);
return newNode;
}
}
41. 資料流中的中位數
題意：面試題41. 資料流中的中位數
思路：構造兩個堆，一個大根堆，一個小根堆，使大根堆中記錄資料流中較小部分的元素，小根堆中記錄資料流中較大部分的元素，
使得小根堆中元素的值都大于大根堆中元素的值，即使小根堆的根結點值比大根堆的根結點值要大，
并且保證，在資料流的個數為偶數時，兩個堆中的資料個數一樣（此時中位數為兩個堆堆頂元素的平均值），資料流個數為奇數時，大根堆個數比小根堆多一個（此時中位數為大根堆的堆頂元素），
class MedianFinder {
PriorityQueue<Integer> min;
PriorityQueue<Integer> max;
/** initialize your data structure here. */
public MedianFinder() {
min = new PriorityQueue();
max = new PriorityQueue(Collections.reverseOrder());
}
public void addNum(int num) {
if (max.size() == min.size()) {
min.add(num);
max.add(min.poll());
} else {
max.add(num);
min.add(max.poll());
}
}
public double findMedian() {
return max.size() == min.size() ? (max.peek() + min.peek()) / 2.0 : max.peek();
}
}
52. 兩個鏈表的第一個公共結點
題意：面試題52. 兩個鏈表的第一個公共節點
思路：先計算兩個鏈表的長度，算出兩個鏈表長度之差diff，較長的鏈表先走diff步之后，兩個鏈表同時向后遍歷，直到找到公共結點，或者到達兩個鏈表結尾，
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
int lenA = len(headA);
int lenB = len(headB);
ListNode p = lenA > lenB ? headA : headB;
ListNode q = p == headA ? headB : headA;
int diff = Math.abs(lenA - lenB);
while (diff > 0) {
p = p.next;
diff--;
}
while (p != null && q != null) {
if (p == q) {
return p;
}
p = p.next;
q = q.next;
}
return null;
}
private int len(ListNode head) {
ListNode tmp = head;
int len = 0;
while (tmp != null) {
tmp = tmp.next;
len ++;
}
return len;
}
}
59-II. 佇列的最大值
題意：面試題59 - II. 佇列的最大值
思路：單調堆疊，除了使用一個資料佇列記錄入隊的元素，還要使用一個雙端佇列（單調的），維護一個從頭到尾遞減的序列，雙端佇列的隊頭元素即為佇列的最大值，入資料佇列時，如果元素大于雙端佇列的隊尾元素，就要把隊尾元素依次出隊，然后把當前元素插入佇列中，
當資料佇列出隊的元素等于雙端佇列的頭元素時，雙端佇列的隊頭元素也要出隊，
class MaxQueue {
Queue<Integer> queue;
Deque<Integer> maxValue;
public MaxQueue() {
queue = new LinkedList<>();
maxValue = https://www.cnblogs.com/yzihan/p/new LinkedList<>();
}
public int max_value() {
if (maxValue.isEmpty()) {
return -1;
}
return maxValue.peek();
}
public void push_back(int value) {
queue.add(value);
while (!maxValue.isEmpty() && maxValue.getLast() < value) {
maxValue.removeLast();
}
maxValue.add(value);
}
public int pop_front() {
if (maxValue.isEmpty()) {
return -1;
}
int val = queue.poll();
if (val == maxValue.peek()) {
maxValue.removeFirst();
}
return val;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/140453.html
標籤：Java
上一篇：技術小菜比入坑 LinkedList，i 了 i 了
下一篇：Redis中的Scan命令踩坑記