計算機基礎速通--數據結構·線性表應用

如有問題大概率是我的理解比較片面,歡迎評論區或者私信指正。

?考察線性表,核心圍繞其存儲結構特性、核心操作實現、場景應用選型三大維度,重點檢驗對基礎概念的理解、代碼實現能力及問題分析能力,通常會結合算法設計、復雜度分析和實際場景進行考察。

一、基礎概念與特性辨析

  1. 核心定義與邏輯結構

    • 問題:“什么是線性表?它與非線性結構(如樹、圖)的本質區別是什么?” (考察點:線性表 “一對一” 的邏輯關系,區別于樹的 “一對多” 和圖的 “多對多”)

  2. 兩種存儲結構的核心差異

    • 問題:“順序表和鏈表在存儲方式、訪問效率、插入刪除操作上有何本質區別?” (考察點:順序表的連續空間與隨機存取、鏈表的離散空間與指針依賴;插入刪除時 “移動元素” 與 “修改指針” 的效率差異)

  3. 總結

  • 順序表 vs 鏈表的本質區別

    • 順序表:連續內存、隨機訪問快(O(1)),增刪需移動元素(O(n)),擴容成本高。

    • 鏈表:離散內存、增刪快(O(1)),查找需遍歷(O(n)),無擴容問題但存儲密度低。

    “數組和鏈表分別適合什么場景?為什么數據庫索引常用B+樹(基于數組)而非鏈表?”
    :數組適合讀多寫少(如索引),鏈表適合頻繁增刪(如操作歷史記錄)。

二、核心操作的代碼實現(邊界處理)

(一)順序表操作

插入與刪除

問題1:“編寫函數,在順序表的第 i 個位置插入元素 x,需處理越界、表滿等異常。” (關鍵點:從后往前移動元素(避免覆蓋),表長 + 1;時間復雜度分析)

public class SeqList {private int[] data;      // 存儲元素的數組private int maxSize;     // 順序表最大容量private int length;      // 當前元素個數// 初始化順序表public SeqList(int capacity) {this.maxSize = capacity;this.data = new int[maxSize];this.length = 0;}/*** 在順序表第i個位置插入元素x* @param i 插入位置(位序從1開始)* @param x 插入元素值* @return 操作是否成功*/
public boolean insert(int i, int x) {// 1. 檢查位序有效性if (i < 1 || i > length + 1) {System.err.println("插入位置越界!有效范圍:[1, " + (length + 1) + "]");return false;}// 2. 檢查表滿異常if (length >= maxSize) {System.err.println("順序表已滿!最大容量:" + maxSize);return false;}// 3. 元素后移操作(從后向前移動)for (int j = length-1; j >= i-1; j--) {data[j+1] = data[j];  // 將元素向后移動一位}// 4. 插入新元素data[i - 1] = x;  // 數組下標 = 位序 - 1length++;         // 更新表長return true;}
}

問題2:“刪除順序表中值為 x 的所有元素,要求時間復雜度O(n)、空間復雜度O(1)。” (思路:用 k 記錄有效元素個數,遍歷數組時將非 x 元素前移至 k 位置,最后更新表長)

public class OrderedList {private int[] data;      // 存儲元素的數組private int length;      // 當前元素個數private int capacity;    // 列表容量// 初始化順序表public OrderedList(int capacity) {this.capacity = capacity;this.data = new int[capacity];this.length = 0;}/*** 刪除所有值為x的元素(時間復雜度O(n),空間復雜度O(1))* @param x 要刪除的目標值* @return 刪除的元素數量*/public int removeAll(int x) {int k = 0; // 有效元素指針int count = 0; // 刪除計數// 雙指針遍歷for (int i = 0; i < length; i++) {if (data[i] != x) {// 保留非x元素data[k] = data[i];k++;} else {// 統計刪除元素count++;}}// 更新表長length = k;return count;}// 輔助方法:添加元素(測試用)public void add(int value) {if (length < capacity) {data[length] = value;length++;}}// 輔助方法:打印當前列表(測試用)public void print() {System.out.print("[");for (int i = 0; i < length; i++) {System.out.print(data[i]);if (i < length - 1) System.out.print(", ");}System.out.println("]");}
}

查找與擴容

問題1:“在有序順序表中實現折半查找,返回元素位置;若不存在,返回插入位置。” (考察點:二分法的邊界控制(low <= high)、循環結束時 low 的含義)

/*** 在有序順序表中執行折半查找* * @param arr 有序順序表(升序排列)* @param target 目標元素值* @return 元素位置(從1開始計數),若不存在則返回應插入位置*/
public static int binarySearch(int[] arr, int target) {// 邊界檢查:空表直接返回插入位置1if (arr == null || arr.length == 0) {return 1;}int low = 0;int high = arr.length - 1;// 關鍵點1:循環條件必須包含等號(單個元素)while (low <= high) {// 關鍵點2:防止整數溢出的中間值計算int mid = low + ((high - low) >> 1);if (arr[mid] == target) {// 找到目標值,返回位序(索引+1)return mid + 1;} else if (arr[mid] < target) {// 目標在右半區low = mid + 1;} else {// 目標在左半區high = mid - 1;}}// 關鍵點3:循環結束時low指向第一個大于target的元素位置return low + 1;
}

問題2:“順序表動態擴容的原理是什么?為什么擴容時通常選擇擴大為原容量的 1.5?倍?” (考察點:避免頻繁擴容導致的時間開銷, amortized 復雜度優化,懶加載策略)

public class ArrayList<E> {/*** 默認初始化空間*/private static final int DEFAULT_CAPACITY = 10;/*** 空元素*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/*** ArrayList 元素數組緩存區*/transient Object[] elementData;private int size;//實際容量// 添加元素觸發擴容public boolean add(E e) {// 步驟1:計算最小所需容量int minCapacity = size + 1;// 步驟2:處理首次添加的特殊情況if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}// 步驟3:檢查并執行擴容if (minCapacity - elementData.length > 0) {// 3.1 記錄當前容量int oldCapacity = elementData.length;// 3.2 計算新容量(1.5倍擴容)int newCapacity = oldCapacity + (oldCapacity >> 1);// 3.3 處理1.5倍不足的情況if (newCapacity - minCapacity < 0) {newCapacity = minCapacity;}// 3.4 創建新數組并復制數據elementData = Arrays.copyOf(elementData, newCapacity);}// 步驟4:安全添加元素elementData[size++] = e;return true;}

(二)鏈表操作

單鏈表基礎操作

問題1:“帶頭結點的單鏈表中,實現第 i 個位置插入元素;若 i=1,操作和其他位置有何不同?” (關鍵點:頭結點的作用 —— 統一插入邏輯,無需特殊處理 i=1;指針修改順序:先連新結點,再斷原鏈)

class LinkedListWithHead {private Node head; // 頭指針始終指向頭結點(哨兵結點)public LinkedListWithHead() {head = new Node(-1); // 創建頭結點(哨兵結點),數據域通常無效}// 在位置 i 插入元素public boolean insert(int i, int data) {if (i < 1) return false; // 位置無效檢查Node pre = head; // 從頭結點開始// 尋找第 i-1 個結點(插入位置的前驅)for (int pos = 0; pos < i - 1; pos++) {if (pre.next == null) break; // 提前到達鏈表末尾pre = pre.next;}if (pre == null) return false; // 前驅結點無效Node newNode = new Node(data); // 創建新結點newNode.next = pre.next; // 新結點指向原位置結點pre.next = newNode;     // 前驅指向新結點return true;}// 刪除位置 i 的元素public boolean delete(int i) {if (i < 1 || head.next == null) return false; // 位置無效或鏈表為空Node pre = head; // 從頭結點開始// 尋找第 i-1 個結點(刪除位置的前驅)for (int pos = 0; pos < i - 1; pos++) {if (pre.next == null) break; // 提前到達鏈表末尾pre = pre.next;}if (pre.next == null) return false; // 要刪除的結點不存在pre.next = pre.next.next; // 跳過要刪除的結點return true;}// 查找元素public int find(int data) {int position = 1;Node current = head.next; // 從第一個實際結點開始while (current != null) {if (current.data == data) {return position; // 找到元素,返回位置}current = current.next;position++;}return -1; // 未找到}// 獲取鏈表字符串表示public String getListString() {StringBuilder sb = new StringBuilder("Head → ");Node current = head.next; // 跳過頭結點while (current != null) {sb.append(current.data);if (current.next != null) sb.append(" → ");current = current.next;}sb.append(" → NULL");return sb.toString();}
}
class LinkedListWithoutHead {private Node head; // 直接指向第一個實際結點(可能為null)public LinkedListWithoutHead() {head = null; // 初始化為空鏈表}// 在位置 i 插入元素public boolean insert(int i, int data) {if (i < 1) return false; // 位置無效檢查// 特殊處理 i=1 的情況if (i == 1) {Node newNode = new Node(data);newNode.next = head; // 新結點指向原頭結點head = newNode;      // 更新頭指針return true;}Node pre = head; // 從第一個結點開始// 尋找第 i-1 個結點for (int pos = 1; pos < i - 1; pos++) {if (pre == null) break; // 提前結束pre = pre.next;}if (pre == null) return false; // 前驅結點無效Node newNode = new Node(data);newNode.next = pre.next; // 新結點指向原位置結點pre.next = newNode;     // 前驅指向新結點return true;}// 刪除位置 i 的元素public boolean delete(int i) {if (i < 1 || head == null) return false; // 位置無效或鏈表為空// 特殊處理 i=1 的情況if (i == 1) {head = head.next; // 頭指針指向第二個結點return true;}Node pre = head; // 從第一個結點開始// 尋找第 i-1 個結點for (int pos = 1; pos < i - 1; pos++) {if (pre.next == null) break; // 提前結束pre = pre.next;}if (pre.next == null) return false; // 要刪除的結點不存在pre.next = pre.next.next; // 跳過要刪除的結點return true;}// 查找元素public int find(int data) {int position = 1;Node current = head; // 從第一個實際結點開始while (current != null) {if (current.data == data) return position;current = current.next;position++;}return -1; // 未找到}// 獲取鏈表字符串表示public String getListString() {if (head == null) return "NULL"; // 空鏈表StringBuilder sb = new StringBuilder();Node current = head;while (current != null) {sb.append(current.data);if (current.next != null) sb.append(" → ");current = current.next;}sb.append(" → NULL");return sb.toString();}
}

?單鏈表有無頭節點操作細節總結:

查找:

Node current = head.next; // 從第一個實際結點開始
Node current = head; // 從第一個實際結點開始

刪除:

if (i < 1 || head.next == null) return false; // 位置無效或鏈表為空
if (i < 1 || head == null) return false; // 位置無效或鏈表為空
        Node pre = head; // 從頭結點開始// 尋找第 i-1 個結點(插入位置的前驅)for (int pos = 0; pos < i - 1; pos++) {if (pre.next == null) break; // 提前到達鏈表末尾pre = pre.next;}if (pre == null) return false; // 前驅結點無效Node pre = head; // 從第一個結點開始// 尋找第 i-1 個結點for (int pos = 1; pos < i - 1; pos++) {if (pre == null) break; // 提前結束pre = pre.next;}if (pre == null) return false; // 前驅結點無效
?pre.next = pre.next.next; // 跳過要刪除的結點// 特殊處理 i=1 的情況if (i == 1) {head = head.next; // 頭指針指向第二個結點return true;}pre.next = pre.next.next; // 跳過要刪除的結點

插入:

?    if (i < 1) return false; // 位置無效檢查Node pre = head; // 從頭結點開始// 尋找第 i-1 個結點(插入位置的前驅)for (int pos = 0; pos < i - 1; pos++) {if (pre.next == null) break; // 提前到達鏈表末尾pre = pre.next;}if (pre == null) return false; // 前驅結點無效if (i < 1) return false; // 位置無效檢查Node pre = head; // 從第一個結點開始// 尋找第 i-1 個結點for (int pos = 1; pos < i - 1; pos++) {if (pre == null) break; // 提前結束pre = pre.next;}if (pre == null) return false; // 前驅結點無效
??newNode.next = pre.next; // 新結點指向原位置結點pre.next = newNode; ? ? // 前驅指向新結點// 特殊處理 i=1 的情況if (i == 1) {Node newNode = new Node(data);newNode.next = head; // 新結點指向原頭結點head = newNode; ? ? ?// 更新頭指針return true;}newNode.next = pre.next; // 新結點指向原位置結點pre.next = newNode; ? ? // 前驅指向新結點

問題2:“刪除單鏈表中值為 x 的所有結點,如何避免內存泄漏?” (思路:用前驅指針 pre 遍歷,找到目標結點后,pre->next 指向其后繼,釋放當前結點)

// 帶頭結點鏈表中刪除所有值為 x 的結點
public void deleteAll(int x) {Node pre = head; // 前驅指針指向頭結點Node cur = head.next; // 當前指針指向第一個實際結點while (cur != null) {if (cur.data == x) {// 找到目標結點pre.next = cur.next; // 前驅指針跳過當前結點// 釋放內存(在Java中置為null幫助GC,在C++中需要delete)cur.next = null; // 斷開引用cur = pre.next; // 移動當前指針到下一個結點} else {// 非目標結點,雙指針一起移動pre = cur;cur = cur.next;}}
}
// 無頭結點鏈表中刪除所有值為 x 的結點
public void deleteAll(int x) {// 特殊情況:刪除開頭連續的目標結點while (head != null && head.data == x) {Node temp = head;head = head.next;temp.next = null; // 斷開引用}if (head == null) return; // 鏈表為空Node pre = head;Node cur = head.next;while (cur != null) {if (cur.data == x) {pre.next = cur.next; // 前驅指針跳過當前結點cur.next = null; // 斷開引用cur = pre.next; // 移動當前指針} else {pre = cur;cur = cur.next;}}
}

內存泄漏分析及避免方法

操作內存泄漏風險正確做法
未斷開引用被刪除結點仍被其他對象引用將被刪除結點的 next 置為 null
未釋放內存已刪除結點仍占用內存空間在C++中使用 delete,在Java中依賴GC
指針處理錯誤鏈表斷裂,無法訪問后續結點使用雙指針技術確保鏈表連續性
頭指針處理不當刪除頭結點后未更新頭指針單獨處理鏈表開頭連續的目標結點
雙鏈表與循環鏈表

問題1:“雙鏈表中,在 p 所指結點后插入 s 結點,需修改哪些指針?” (步驟:s->next = p->next;p->next->prior = s;s->prior = p;p->next = s)

public class DLinkedList<T> {// ... 省略其他代碼/*** 在節點 p 后插入新節點* @param p 目標節點(不能為 null)* @param data 新節點的數據* @return 插入成功返回 true,失敗返回 false*/public boolean insertAfter(DNode<T> p, T data) {if (p == null) return false;  // p 無效DNode<T> s = new DNode<>(data);  // 創建新節點 s// 核心步驟:s.next = p.next;     // 1. s 的 next 指向 p 的原后繼if (p.next != null) {p.next.prior = s;  // 2. 如果 p 有后繼,其 prior 指向 s(文檔:p->next->prior=s)}s.prior = p;         // 3. s 的 prior 指向 pp.next = s;          // 4. p 的 next 指向 sreturn true;}
}
public class DLinkedList<T> {// ... 省略其他代碼/*** 刪除節點 p* @param p 要刪除的節點(不能為 null 或頭結點)* @return 刪除成功返回 true,失敗返回 false*/public boolean deleteNode(DNode<T> p) {if (p == null || p == head) return false;  // 禁止刪除頭結點或無效節點// 核心步驟:if (p.prior != null) {p.prior.next = p.next;  // 1. 前驅節點的 next 指向 p 的后繼}if (p.next != null) {p.next.prior = p.prior;  // 2. 后繼節點的 prior 指向 p 的前驅}// 清理引用,避免內存泄漏p.prior = null;p.next = null;return true;}
}
public class DLinkedList<T> {// ... 省略其他代碼// 后向遍歷(從頭結點后的第一個節點開始)public void traverseForward() {DNode<T> p = head.next;  // 跳過頭結點while (p != null) {System.out.print(p.data + " ");  // 處理節點(如打印)p = p.next;                      // 移動到后繼}System.out.println();}// 前向遍歷(需先定位到尾節點,然后從尾到頭)public void traverseBackward() {// 先找到尾節點(需遍歷整個鏈表)DNode<T> tail = head.next;while (tail != null && tail.next != null) {tail = tail.next;}// 從尾節點開始前向遍歷(跳過頭結點)DNode<T> p = tail;while (p != null && p != head) {  System.out.print(p.data + " ");p = p.prior;                  // 移動到前驅}System.out.println();}
}

問題2:“循環單鏈表相比單鏈表有何優勢?如何判斷循環鏈表為空或滿?” (考察點:首尾相連,適合環形場景(如約瑟夫問題);判空:頭結點 next 指向自身;判滿:需額外標志或犧牲一個節點)

// 定義鏈表結點類,存儲數據和下一個結點指針
class LNode<T> {T data;          // 結點數據LNode<T> next;   // 指向下一個結點的指針public LNode(T data) {this.data = data;this.next = null;  // 初始化時next為null,在鏈表中會被設置}
}// 定義循環單鏈表類
public class CircularLinkedList<T> {private LNode<T> head;     // 頭結點(不存儲數據,用于標記鏈表起始)private int size;          // 當前鏈表大小(額外標志,用于判滿)private int maxSize;       // 鏈表最大容量(設置判滿條件)// 初始化鏈表:創建頭結點,并使其next指向自身(形成環)public CircularLinkedList(int maxSize) {this.head = new LNode<>(null);  // 頭結點data為nullthis.head.next = this.head;     // 關鍵:next指向自身,表示空表this.size = 0;this.maxSize = maxSize;         // 設置最大容量(用于判滿)}// 判斷鏈表是否為空:頭結點的next指向自身public boolean isEmpty() {return head.next == head;}// 判斷鏈表是否為滿:基于size變量(額外標志)public boolean isFull() {return size >= maxSize;  // size達到maxSize時為滿}// 添加結點到鏈表尾部(示例操作,展示環形遍歷)public void append(T data) {if (isFull()) {throw new IllegalStateException("LinkedList is full. Cannot append.");}LNode<T> newNode = new LNode<>(data);if (isEmpty()) {// 空表:新結點next指向頭結點,頭結點next指向新結點newNode.next = head;head.next = newNode;} else {// 非空表:找到尾結點(尾結點的next指向頭結點),插入新結點LNode<T> current = head.next;while (current.next != head) {  // 遍歷到尾結點current = current.next;}current.next = newNode;       // 尾結點指向新結點newNode.next = head;          // 新結點指向頭結點,維持環狀}size++;  // 更新大小}// 示例:打印鏈表(展示環形訪問)public void printList() {if (isEmpty()) {System.out.println("LinkedList is empty.");return;}LNode<T> current = head.next;System.out.print("Circular List: ");do {System.out.print(current.data + " -> ");current = current.next;} while (current != head);  // 循環直到回到頭結點System.out.println("(head)");  // 表示環閉合}// 主方法:測試判空、判滿和環形場景public static void main(String[] args) {// 初始化鏈表,設置最大容量為3(用于判滿)CircularLinkedList<Integer> list = new CircularLinkedList<>(3);// 測試判空System.out.println("Is empty? " + list.isEmpty());  // 輸出: true// 添加結點list.append(1);list.append(2);list.append(3);list.printList();  // 輸出: Circular List: 1 -> 2 -> 3 -> (head)// 測試判滿System.out.println("Is full? " + list.isFull());  // 輸出: true// 嘗試添加更多結點(會拋異常)try {list.append(4);  // 拋出 IllegalStateException} catch (IllegalStateException e) {System.out.println("Error: " + e.getMessage());}}
}

背景:約瑟夫環問題(Josephus problem)是一個著名的理論和計算機科學問題:??n個人圍成一圈,從第一個人開始報數,每數到k的人被淘汰出局,然后從下一個人重新開始報數,如此循環,直到最后剩下一個人為止??。這個幸存者在初始圓環中的位置即為約瑟夫問題的解。

?

class Node {int data;Node next;public Node(int data) {this.data = data;this.next = null;}
}public class JosephusProblem {public static int josephus(int n, int k) {if (n <= 0 || k <= 0) {throw new IllegalArgumentException("n and k must be positive integers");}// 創建循環鏈表Node head = new Node(1);Node prev = head;for (int i = 2; i <= n; i++) {prev.next = new Node(i);prev = prev.next;}prev.next = head; // 形成環Node current = head;Node previous = prev; // 前驅節點// 當鏈表中不止一個節點時while (current.next != current) {// 報數:移動k-1步(從1開始計數)for (int i = 0; i < k - 1; i++) {previous = current;current = current.next;}// 移除當前節點previous.next = current.next;current = previous.next; // 從下一個節點重新開始}return current.data; // 最后剩下的節點}public static void main(String[] args) {int n = 7;  // 總人數int k = 3;   // 報數到k的人出列int survivor = josephus(n, k);System.out.println("最后剩下的人的編號是: " + survivor);}
}

鏈表的特殊操作

問題1:“反轉單鏈表(就地逆置),要求空間復雜度O(1)。” (思路:用 prev、curr、next 三個指針迭代反轉,避免遞歸棧開銷)

206. 反轉鏈表 - 力扣(LeetCode)

class Solution {public ListNode reverseList(ListNode head) {ListNode cur=head;ListNode pre=null;ListNode next=null;while(cur!=null){next=cur.next;cur.next=pre;pre=cur;cur=next;}return pre;}
}

問題2:“判斷單鏈表是否有環?若有環,如何找到環的入口?” (快慢指針法:快指針每次 2 步,慢指針 1 步,相遇則有環;再從表頭和相遇點同步走,交點即為入口)

141. 環形鏈表 - 力扣(LeetCode)

//雙指針法
public class Solution {public boolean hasCycle(ListNode head) {ListNode slow=head;ListNode fast=head;while(fast!=null && fast.next!=null){slow=slow.next;fast=fast.next.next;if(slow==fast)return true;}return false;}
}

142. 環形鏈表 II - 力扣(LeetCode)

ListNode detectCycle(ListNode head) {if (head == null) return null;// 步驟1:判斷是否有環并記錄相遇點ListNode slow = head;ListNode fast = head;boolean hasCycle = false;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {hasCycle = true;break;}}// 無環則返回nullif (!hasCycle) return null;// 步驟2:重置慢指針到鏈表頭slow = head;// 步驟3:同步移動直至相遇while (slow != fast) {slow = slow.next;fast = fast.next; // 快指針改為每次1步}return slow; // 相遇點即環入口
}

三、場景應用與選型

1.存儲結構選型

問題:“當需要頻繁按序號訪問元素時,選順序表還是鏈表?當需要頻繁在中間位置插入刪除時,選哪種?為什么?” (考察點:順序表隨機存取O(1)適合高頻訪問;鏈表插入刪除O(1)已知前驅)適合高頻修改)

實際場景設計

問題:“設計一個通訊錄系統,支持添加、刪除、查詢聯系人,應采用順序表還是鏈表?說明理由。” (考察點:通訊錄數據量動態變化(適合鏈表)、查詢頻率(若按姓名查詢,兩種結構差異不大;若按索引,順序表更優))

2. 手寫算法實現

考察目的:考察編碼能力和邊界處理。

? 刪除鏈表中重復元素(有序鏈表)83. 刪除排序鏈表中的重復元素 - 力扣(LeetCode)

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode cur=head;while(cur!=null && cur.next!=null){if(cur.val==cur.next.val){cur.next=cur.next.next;}else{cur=cur.next;}}return head;}
}

關鍵點:雙指針遍歷。

3. 復雜問題與優化

考察目的:考察算法設計思維和優化能力。

(1) 合并兩個有序鏈表(LeetCode 21)21. 合并兩個有序鏈表 - 力扣(LeetCode)

思路:虛擬頭節點簡化邊界處理。

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {//虛擬頭節點ListNode head=new ListNode(-1);ListNode cur=head;while(list1!=null && list2!=null){if(list1.val<=list2.val){cur.next=list1;list1=list1.next;}else{cur.next=list2;list2=list2.next;}cur=cur.next;}cur.next=(list1==null)?list2:list1;return head.next;}
}



4. 場景應用題
考察目的
:將線性表應用于實際問題。

Q:設計一個支持高效插入、刪除和隨機訪問的數據結構(LeetCode 380)。

A:使用?哈希表 + 動態數組

數組存儲元素,支持O(1)隨機訪問。

哈希表存儲元素到數組下標的映射,支持O(1)插入/刪除。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/91505.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/91505.shtml
英文地址,請注明出處:http://en.pswp.cn/web/91505.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

LeetCode Hot 100:42. 接雨水

題目 給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖&#xff0c;計算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 解析 和題目 盛水最多的容器 類似&#xff0c; LeetCode Hot 100&#xff1a;11. 盛最多水的容器-CSDN博客 只是這里將每一個柱子視為一個寬度為…

【C語言入門級教學】字符指針變量

文章目錄1.字符指針變量2. 數組指針變量2.1 數組指針變量初始化3.?維數組傳參的本質1.字符指針變量 在指針的類型中我們知道有?種指針類型為字符指針 char* ; ?般使?: int main() { char ch w; char* pc &ch;//pc的類型是char**pcw;//對pc解引用 修改ch存放的內容…

【Shell腳本自動化編寫——報警郵件,檢查磁盤,web服務檢測】

Shell腳本自動化編寫Shell腳本自動化編寫一、判斷當前磁盤剩余空間是否有20G&#xff0c;如果小于20G&#xff0c;則將報警郵件發送給管理員&#xff0c;每天檢查一次磁盤剩余空間。第一步&#xff1a;準備工作第二步&#xff1a;配置郵件信息第三步&#xff1a;檢查磁盤的自動…

Java 接口(下)

三、接口的繼承性【基礎重點】 1. Java中的接口之間的繼承關系是多繼承&#xff0c;一個接口可以有多個父接口(1) 語法&#xff1a;interface 接口名 extends 父接口1,父接口2{} 2. 類和接口之間是多實現的關系&#xff1a;一個類可以同時實現多個接口(1) 語法&#xff1a;clas…

學習游戲制作記錄(各種水晶能力以及多晶體)8.1

1.實現創建水晶并且能與水晶進行交換位置的能力創建好水晶的預制體&#xff0c;添加動畫控制器&#xff0c;傳入待機和爆炸的動畫創建Crystal_Skill_Control腳本&#xff1a;掛載在水晶預制體上private float crystalExstTime;//水晶存在時間public void SetupCrystal(float _c…

在vscode 如何運行a.nut 程序(Squirrel語言)

在 VS Code 中運行 Squirrel 語言編寫的 .nut 程序&#xff0c;需要先配置 Squirrel 運行環境并安裝相關插件&#xff0c;具體步驟如下&#xff1a; 一、安裝 Squirrel 解釋器 Squirrel 程序需要通過其官方解釋器 squirrel 或 sq 執行&#xff0c;首先需要安裝解釋器&#xf…

【數據結構】生活中的數據結構:從吃飯與編程看棧與隊列思維

生活中的數據結構&#xff1a;從吃飯與編程看棧與隊列思維 在軟件開發的世界里&#xff0c;棧&#xff08;Stack&#xff09;和隊列&#xff08;Queue&#xff09;是兩種基礎的數據結構&#xff0c;它們以不同的順序管理數據&#xff1a;棧遵循后進先出&#xff08;LIFO&#x…

牛客——接頭密匙

題目鏈接&#xff1a;牛客--接頭密匙 該題是一個很顯然的前綴樹問題&#xff0c;只需要構建a中所有數組對應的前綴樹&#xff0c;之后求b所處前綴個數即可。關于前綴樹的構建&#xff0c;可以觀看左老師算法講解045的視頻&#xff0c;簡單來講就是用特殊字符將實際數據隔開&…

【Linux基礎知識系列】第六十三篇 - 文件編輯器基礎:vim

在 Linux 系統中&#xff0c;文本編輯器是系統管理員和開發人員不可或缺的工具。vim 是一個功能強大的文本編輯器&#xff0c;廣泛應用于 Linux 系統中。它支持多種編輯模式&#xff0c;提供了豐富的文本編輯功能&#xff0c;適用于編寫代碼、配置文件和文檔。掌握 vim 的基本使…

音頻驅動的視覺特效:粒子、動畫與Shader的融合技術

音頻驅動視覺效果的實現與應用1. 引言在互動媒體、游戲和數字藝術領域&#xff0c;音頻數據實時控制視覺元素已成為核心技術&#xff0c;它能創造沉浸式體驗&#xff0c;增強用戶參與感。例如&#xff0c;音樂會可視化或VR游戲中&#xff0c;音頻信號驅動粒子流動、動畫變化和S…

機器學習環境配置

【終極指南】吃透機器學習環境配置&#xff1a;從Conda、CUDA到Docker容器化 大家好&#xff01;在機器學習的旅程中&#xff0c;一個穩定、可復現的環境是成功的基石。 第一部分&#xff1a;核心理念——為何環境配置如此重要&#xff1f; 任何機器學習模型的運行&#xff0c;…

【14】大恒相機SDK C#開發 ——Bitmap.UnlockBits()什么意思?有什么用?bmpData.Scan0;什么意思?有什么用?

文章目錄1 Bitmap.UnlockBits()2 bmpData.Scan01 Bitmap.UnlockBits() 在 C# 中&#xff0c;Bitmap.UnlockBits() 方法的作用是解鎖通過 Bitmap.LockBits() 方法鎖定的位圖數據&#xff0c;并釋放相關的位圖數據結構。 當你使用 Bitmap.LockBits() 方法鎖定位圖數據時&#x…

什么是doris

文章目錄簡介使用場景Apache Doris 主要應用于以下場景&#xff1a;實時數據分析&#xff1a;湖倉融合分析&#xff1a;半結構化數據分析&#xff1a;Apache Doris 的核心特性詳細請看官方文檔&#xff1a; Apache Doris介紹簡介 Apache Doris 是一款基于 MPP 架構的高性能、實…

python+pyside6的簡易畫板

十分簡單的一個畫板程序&#xff0c;用QLabel控件作為畫布&#xff0c;在畫布上可以畫出直線、矩形、填充矩形、園&#xff0c;橢園、隨手畫、文本等內容。將原先發布的畫板程序中的畫文本方法修改成了原位創建一編輯框&#xff0c;編輯框失去焦點后&#xff0c;即將文本畫在畫…

【數據可視化-76】從釋永信被查,探索少林寺客流量深度分析:Python + Pyecharts 炫酷大屏可視化(含完整數據和代碼)

&#x1f9d1; 博主簡介&#xff1a;曾任某智慧城市類企業算法總監&#xff0c;目前在美國市場的物流公司從事高級算法工程師一職&#xff0c;深耕人工智能領域&#xff0c;精通python數據挖掘、可視化、機器學習等&#xff0c;發表過AI相關的專利并多次在AI類比賽中獲獎。CSDN…

WPF TreeView自帶自定義滾動條

放在TreeView.Resources中&#xff1a;<Style TargetType"ScrollBar"><Setter Property"Stylus.IsPressAndHoldEnabled" Value"false"/><Setter Property"Stylus.IsFlicksEnabled" Value"false"/><Set…

MongoDB 詳細用法與 Java 集成完整指南

MongoDB 詳細用法與 Java 集成完整指南 目錄 MongoDB 基礎概念MongoDB 安裝與配置MongoDB Shell 基本操作Java 環境準備Java MongoDB 驅動集成連接配置基本 CRUD 操作高級查詢操作索引操作聚合管道事務處理Spring Boot 集成最佳實踐 1. MongoDB 基礎概念 1.1 核心概念對比 …

【Flutter3.8x】flutter從入門到實戰基礎教程(四):自定義實現一個自增的StatefulWidget組件

fluttet中實現一個自定義的StatefulWidget組件&#xff0c;可以在數據變化后&#xff0c;把最新的頁面效果展示給客戶 實現效果實現代碼 pages文件夾下新加一個counter_page.dart文件 class CounterPage extends StatefulWidget {const CounterPage({super.key});overrideState…

[AI8051U入門第十三步]W5500實現MQTT通信

前言 學習目標: 1、學習MQTT協議 2、了解MQTT數據幀格式 3、自己編寫MQTT程序 4、調試MQTT程序一、MQTT協議介紹 MQTT(Message Queuing Telemetry Transport) 是一種輕量級的 發布/訂閱(Pub/Sub) 消息傳輸協議,專為 低帶寬、高延遲或不可靠網絡 環境設計,廣泛應用于 物…

四、基于SpringBoot,MVC后端開發筆記

整合第三方技術&#xff1a; 1、整合Junit (1)名稱&#xff1a;SpringBootTest (2)類型&#xff1b;測試類注解 (3)位置&#xff1a;測試類定義上方 (4)作用&#xff1a;設置Junit加載的SpringBoot啟動類 (5)相關屬性&#xff1a;classes&#xff1a;設置SpringBoot啟動類 2、整…