前言
本篇博客主要分享数据结构和算法，通过分享可以梳理好散乱的知识点
稀疏数组
稀疏数组是只有少数几个元素的值不为零,大部分元素的值都是零的数组。
对于这种数组,我们可以使用稀疏数组来保存空间。稀疏数组包括:
- 数组的原始长度
- 非零元素的个数
- 非零元素的索引及值
比如,有一个数组:int arr[12] = {0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0};我们可以将它表示为稀疏数组:
int sparseArr[3][3] = { {12, 2}, // 数组长度和非零元素个数 {1, 1}, // 第一个非零元素的索引和值 {6, 2} // 第二个非零元素的索引和值 }这样我们只需要保存3个值,就可以表示原数组,从而节省空间。
稀疏数组常用于游戏开发中保存棋盘状态,图像处理中的矩阵等。运用稀疏数组可以有效压缩数据量,加速运算速度。
总的来说,对于有大量零元素的数组,使用稀疏数组可以极大地节省内存空间,这在处理大规模数据时很有意义。
循环队列
循环队列是一种特殊的队列,它的头尾指针可以循环使用。当尾指针达到数组末尾时,它自动返回到数组头部。
循环队列需要以下三个变量:
- 队列数组:array[]
- 头指针:front,指向队头元素
- 尾指针:rear,指向队尾元素的下一个位置
循环队列的enqueue和dequeue操作如下:// enqueue操作 void enqueue(int data) { // 判断队列是否已满 if ((rear + 1) % MAXSIZE == front) { printf("Queue is full!\n"); return; } // 将新元素加入队尾 array[rear] = data; // rear指针移动 rear = (rear + 1) % MAXSIZE; } // dequeue操作 void dequeue() { // 判断队列是否为空 if (front == rear) { printf("Queue is empty!\n"); return ; } // front指针移动 front = (front + 1) % MAXSIZE; }循环队列由于采用循环数组,可以充分利用数组空间,无需像普通队列那样重新分配更大的内存空间,所以空间利用率高。
但是,循环队列也存在两个问题: - 队列满时,无法继续入队,会溢出
- 队列空时,无法继续出队,会下溢
所以,循环队列适用于元素入队出队次数相近的场景。单链表
单链表是一种线性表数据结构,它的每个节点包含两个域:
- 数据域:存储数据元素
- 指针域:存储后继节点的指针
单链表的结构如下:struct Node { int val; struct Node *next; };
单链表需要一个头指针来指向第一个节点。
单链表的基本操作有:
1. 遍历:从头指针开始,沿next指针遍历每个节点
```css
void traverse(struct Node *head) {
struct Node *p = head;
while (p != NULL) {
printf("%d ", p->val);
p = p->next;
}
}- 插入:在指定节点之前/之后插入新节点
// 将新节点插入在p节点之后 void insertAfter(struct Node *p, int val) { struct Node *q = (struct Node*)malloc(sizeof(struct Node)); q->val = val; q->next = p->next; p->next = q; } - 删除:删除指定节点
// 删除p节点之后的节点 void deleteAfter(struct Node *p) { struct Node *q = p->next; p->next = q->next; free(q); } - 查找:根据值查找节点
struct Node* search(struct Node *head, int val) { struct Node *p = head; while (p != NULL && p->val != val) p = p->next; return p; }单链表相比数组的优点是:插入和删除方便,不需要移动大量元素。但是查找和访问则比较慢,需要从头指针开始遍历。
所以,单链表适用于插入和删除频繁的场景。单链表面试题
单链表常见的面试题有:
- 反转单链表:将节点的next指针反向指向前一个节点,实现链表反转。
struct Node* reverse(struct Node* head) { struct Node *prev = NULL; struct Node *cur = head; while (cur != NULL) { struct Node *next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } - 找出中间节点:使用快慢指针,慢指针一次走一步,快指针一次走两步,当快指针到达尾节点时,慢指针指向中间节点。
struct Node* middleNode(struct Node* head) { struct Node *slow = head; struct Node *fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; } - 两个单链表相交的节点:使用两个指针遍历两个链表,若遇到相同节点,则为相交节点。否则当一个链表遍历完时,指向另一个链表的头继续遍历。
struct Node* getIntersectionNode(struct Node* headA, struct Node* headB) { struct Node *pA = headA; struct Node *pB = headB; while (pA != pB) { pA = pA == NULL ? headB : pA->next; pB = pB == NULL ? headA : pB->next; } return pA; } - 删除倒数第k个节点:使用快慢指针,快指针先走k步,然后快慢指针同时走,当快指针到达尾节点时,慢指针指向倒数第k个节点。
void removeNthFromEnd(struct Node* head, int n) { struct Node *fast = head; struct Node *slow = head; while (n > 0 && fast != NULL) { fast = fast->next; n--; } while (fast != NULL) { fast = fast->next; slow = slow->next; } slow->next = slow->next->next; }环形链表解决约瑟夫问题
环形链表可以解决约瑟夫问题。约瑟夫问题为:
n个人围坐一圈,从第k个人开始报数,数到m的人出列,然后再从下一人开始报数。重复这个过程,直到所有人出列。要求出列的顺序。
使用环形链表可以这样解决: - 创建一个长度为n的环形链表,每个节点的值为1到n
- 设两个指针p和q,初始都指向头节点
- p先移动k-1步,到达第k个节点
- p和q同时移动,每m个节点,删除q所指节点
- p和q继续同时移动,直到q指向最后一个节点
- 环形链表此时剩余节点的值为出列顺序
代码实现如下:struct Node { int val; struct Node *next; }; struct Node* createCircularList(int n) { struct Node *head = (struct Node*)malloc(sizeof(struct Node)); struct Node *cur = head; for (int i = 1; i <= n; i++) { struct Node *newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->val = i; cur->next = newNode; cur = newNode; } cur->next = head; // 合成环型 return head; } int josephus(struct Node* head, int k, int m) { struct Node *p = head; struct Node *q = head; while (--k > 0) { p = p->next; // p移动k-1步 } q = p->next; // q从p的下一个节点开始 while (q != p) { // 未形成环 for (int i = 0; i < m-1; i++) { p = p->next; q = q->next; } struct Node *del = q; // 待删除节点 q = q->next; // q移到下一个节点 p->next = q; // 删除节点 printf("%d ", del->val); // 输出删除节点的值 free(del); } }栈实现综合计算器
可以使用栈实现一个简单的综合计算器。思路如下:
- 遇到数字,将数字字符转换为整数,压入栈
- 遇到运算符,弹出栈顶的两个数a和b,进行运算,并将结果压入栈
- 遇到括号,判断是左括号还是右括号
- 左括号:直接压入栈
- 右括号:弹出栈顶元素进行运算,直到遇到左括号,然后弹出左括号
- 重复上述步骤,直到表达式结束
- 最后弹出栈中唯一的元素,即为表达式结果
代码实现如下:int calculate(char *expr) { stack<int> s; // 存放数字的栈 char c; int a, b, num = 0; for (int i = 0; c = expr[i]; i++) { // 遇到数字,转换为整数,压入栈 if (isdigit(c)) { num = num * 10 + c - '0'; } else if (c == '(') { // 遇到左括号,压入栈 s.push(c); } else if (c == ')') { // 遇到右括号,弹出栈顶元素运算直到左括号 while (s.top() != '(') { b = s.top(); s.pop(); a = s.top(); s.pop(); s.push(calculate(a, b)); // 计算两个数的结果 } s.pop(); // 弹出'(' } else { // 遇到运算符,弹出两个数字运算 b = s.top(); s.pop(); a = s.top(); s.pop(); switch (c) { case '+': s.push(a+b); break; case '-': s.push(a-b); break; case '*': s.push(a*b); break; case '/': s.push(a/b); break; } } // 如果num不为0,则压入栈 if (num != 0) { s.push(num); num = 0; } } // 计算最终结果,栈中只剩一个元素 return s.top(); }中缀表达式转为后缀表达式，实现逆波兰计算器
中缀表达式转后缀表达式,可以使用栈实现。算法如下:
- 从左到右扫描中缀表达式
- 遇到操作数,直接输出
- 遇到左括号'(',直接入栈
- 遇到右括号')',弹出栈顶元素直到左括号,左括号出栈但不输出
- 遇到操作符,比较栈顶元素优先级
- 高优先级:压入栈
- 相等优先级:弹出栈顶元素,当前操作符入栈
- 低优先级:弹出栈顶元素输出,再比较栈顶元素
- 重复步骤3-5,直到表达式结束
- 将栈中所有元素弹出输出
- 最后输出的序列为后缀表达式
代码实现如下:void infixToPostfix(char *infix, char *postfix) { stack<char> s; char c; for (int i = 0; c = infix[i]; i++) { // 遇到操作数,直接输出 if (isdigit(c) || isalpha(c)) { *postfix++ = c; } else if (c == '(') { // 遇到左括号,压入栈 s.push(c); } else if (c == ')') { // 遇到右括号,弹出栈顶元素直到左括号 while (s.top() != '(') { *postfix++ = s.top(); s.pop(); } s.pop(); // 弹出'(' } else { // 遇到操作符,比较栈顶元素优先级 while (!s.empty() && precedence(c) <= precedence(s.top())) { *postfix++ = s.top(); s.pop(); } s.push(c); } } // 将栈中剩余元素弹出输出 while (!s.empty()) { *postfix++ = s.top(); s.pop(); } }使用后缀表达式可以构建逆波兰计算器。逆波兰计算器不需要括号,直接从左到右计算即可。这是因为后缀表达式的运算符总是在两个操作数的后面,所以可以直接拿来计算。
后缀表达式具有运算符在操作数后面的特点,计算简单高效,无需考虑运算符优先级和括号。递归之迷宫问题
迷宫问题是递归算法的典型例子。问题描述如下:
给定一个n*m的迷宫,入口在(0, 0)位置,出口在(n-1, m-1)位置。迷宫中可能存在障碍,用1表示,空路径用0表示。要求找出从入口到出口的路径。
思路: - 如果当前位置为出口,直接返回true
- 如果当前位置在迷宫外或者是障碍,直接返回false
- 如果当前位置已经访问过,直接返回false
- 标记当前位置已访问
- 上、右、下、左四个方向递归调用,只要有一条路径返回true,则返回true
- 如果四个方向都走不通,返回false
代码实现:bool maze(int **maze, int n, int m, int x, int y) { // 递归终止条件 if (x == n-1 && y == m-1) return true; if (x < 0 || x >= n || y < 0 || y >= m || maze[x][y] == 1) return false; if (maze[x][y] == 2) return false; // 已访问过 // 标记当前位置已访问 maze[x][y] = 2; // 上、右、下、左四个方向递归调用 if (maze(maze, n, m, x-1, y) || // 上 maze(maze, n, m, x, y+1) || // 右 maze(maze, n, m, x+1, y) || // 下 maze(maze, n, m, x, y-1)) { // 左 return true; } return false; }迷宫问题是典型的使用回溯算法解决的问题。回溯的思想是从一条路走到尽头,若是死路就返回来尝试其他路径,最终找到一条通路或所有路都试完依然没找到,此问题无解。
递归和回溯是解决这类问题的有力手段,需要对递归的机制有清晰的理解。谁发明的八皇后，本宫赐你一丈红
八皇后问题是著名的规划问题,最初由德国数学家卡尔·弗里德里希·高斯在19世纪提出。
八皇后问题是指在8*8棋盘上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处在同一行、同一列或同一斜线上,问有多少种摆法。
高斯提出这个问题的目的是为了研究数学中的排列与组合,他自己使用回溯算法给出了92种解法。
八皇后问题的基本解法思路为: - 以行为序,对每行试探所有的列,检查是否和前面已经摆放的皇后冲突。
- 如果冲突,继续试探下一列;如果不冲突, Fixed 这一行的皇后,并递归地摆放下一行。
- 递归终止条件是已经摆放完第8行的皇后。
典型的回溯解决方案代码如下:bool isValid(int row, int col) { /* ... */ } void backtrack(int row) { if (row == 8) { // 找到一个解 solutions++; return; } for (int col = 0; col < 8; col++) { if (isValid(row, col)) { // 检查这一行的皇后摆放在col列是否合适 board[row][col] = true; // 摆放皇后 backtrack(row + 1); // 递归摆放下一行 board[row][col] = false;// 撤销摆放 } } } int totalNQueens(int n) { int solutions = 0; backtrack(0); return solutions; }这就是八皇后问题的提出者、解决思路和基本实现。高斯使用这个问题深入研究了回溯算法,为后来的算法发展做出了重要贡献,对此高斯确实应该得到赞扬。
算法的时间复杂度和空间复杂度
算法的时间复杂度和空间复杂度是评估算法效率的两大关键指标。
时间复杂度:表示算法执行所需的时间量。以大O符号表示,常见的有O(1)、O(n)、O(n2)、O(nlogn)、O(n!)等。
空间复杂度:表示算法执行所需的存储空间量。也用大O符号表示,与时间复杂度相同。
我们以快排算法为例,分析时间复杂度和空间复杂度:
快排的基本思想是选择一个pivot,将数组分为两部分,左边都比pivot小,右边都比pivot大。然后递归左右两部分。public void quickSort(int[] nums, int left, int right) { if (left >= right) return; int pivot = partition(nums, left, right); quickSort(nums, left, pivot - 1); quickSort(nums, pivot + 1, right); } private int partition(int[] nums, int left, int right) { int pivot = nums[left]; int i = left, j = right; while (i < j) { while (i <= j && nums[i] <= pivot) i++; while (i <= j && nums[j] > pivot) j--; swap(nums, i, j); } swap(nums, left, j); return j; }时间复杂度:每次选取一个pivot将数组分成两部分,如果每次都最为平均分,那么递归深度为logn,partition的时间复杂度为O(n),所以总时间复杂度为O(nlogn)。
空间复杂度:由于递归调用栈,空间复杂度也是O(logn)。
对算法效率的分析需要从时间复杂度和空间复杂度两个方面考虑。在实际应用中,还需要综合考虑算法的稳定性和实现难易程度。这些都是正确选择和设计算法的关键指标。常见的7种排序算法
- 冒泡排序:交换相邻元素,使较大的元素往后移。时间复杂度O(n2),空间复杂度O(1)。
- 选择排序:从未排序的元素中找到最小的元素,放到开头。时间复杂度O(n2),空间复杂度O(1)。
- 插入排序:将未排序的元素插入到前面已排序的序列中,使之成为新的有序序列。时间复杂度O(n2),空间复杂度O(1)。
- 快速排序:选择一个pivot,左边小于等于pivot,右边大于等于pivot,然后递归左右两部分。时间复杂度O(nlogn),空间复杂度O(logn)。
- 归并排序:递归将序列一分为二,到只剩一个元素为止;然后合并两个有序序列,使之成为一个新的有序序列。时间复杂度O(nlogn),空间复杂度O(n)。
- 希尔排序:通过增量分组,将元素移动到适当位置。时间复杂度O(nlogn),空间复杂度O(1)。
- 计数排序:统计每个数出现的次数,然后依次输出。时间复杂度O(n+k),空间复杂度O(n+k),k为序列最大值。
这7种排序算法涵盖了比较排序和非比较排序,各有优缺点,需要根据实际情况选择合适的排序算法。
比较排序:通过比较判断元素间的相对顺序,如冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序。
非比较排序:不通过比较判断元素顺序,如计数排序。
非比较排序在数据范围较小时效率高,但无法应对范围较大时的排序需求。所以通常先使用非比较排序缩小数据范围,再使用比较排序完成最终排序。这是排序算法的一个重要综合运用方法。
理解不同排序算法的时间复杂度、空间复杂度及适用场景,对算法的选择至关重要。这也是面试中常考察的内容之一。二分查找、插值查找、斐波那契查找
二分查找、插值查找和斐波那契查找都是折半查找,可以在有序数组中快速查找元素。
二分查找:
特点:每次都将查找区间折半,所以间隔大小一直都是2的n次方,即logn。
实现:int binarySearch(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }时间复杂度:O(logn)
空间复杂度:O(1)
插值查找:
特点:根据查找值和数组的最大最小值,计算出一个可能的中间位置。
实现:int interpolationSearch(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right && target >= nums[left] && target <= nums[right]) { int mid = left + (right - left) * (target - nums[left]) / (nums[right] - nums[left]); if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else { return mid; } } return -1; }时间复杂度:O(log(logn)),n为数组长度,在数据均匀分布的情况下最优。
空间复杂度:O(1)
斐波那契查找:
特点:每次折半区间Fib(k)的大小,k为斐波那契数列的数值。
实现:int fibSearch(int[] nums, int target) { int left = 0, right = nums.length - 1, k = 0; int mid = 0; while (nums[left] < target) { // 找到大于target的第一个数字,用于后续的折半 left = mid + 1; k++; } int fibM = fib(k - 1); // F(k-1) while (left < right) { // 斐波那契折半 mid = left + fibM - 1; if (nums[mid] < target) { left = mid + 1; k--; fibM = fib(k - 1); } else { right = mid; } } if (nums[left] == target) return left; return -1; }时间复杂度:O(logn),n为数组长度
空间复杂度:O(1)
这三种折半查找算法各有优点,实际使用时根据需要选择合适的算法。二叉树
二叉树是非常重要的数据结构,用来表示这样的树结构:每个节点最多有两个子节点(左子节点和右子节点)。
二叉树常用来实现二叉搜索树和二叉堆。
二叉树的基本结构:public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }二叉树常用操作:
- 添加节点:找到节点应该插入的位置,插入节点。如在二叉搜索树中按值的大小插入。
- 删除节点:删除叶节点直接删除,删除有一子节点的节点直接用子节点替代,删除有两个子节点的节点用后继节点或前驱节点替代。
- 先序遍历:根-左-右。递归实现如下:
public void preorder(TreeNode root) { if (root == null) return; System.out.println(root.val); preorder(root.left); preorder(root.right); } - 中序遍历:左-根-右。递归实现如下:
public void inorder(TreeNode root) { if (root == null) return; inorder(root.left); System.out.println(root.val); inorder(root.right); } - 后序遍历:左-右-根。递归实现如下:
public void postorder(TreeNode root) { if (root == null) return; postorder(root.left); postorder(root.right); System.out.println(root.val); } - 求最大/小值:递归左子节点和右子节点,比较大小得到最大/小值。
- 求高度:递归左子节点和右子节点的高度,取最大值加1。
- 求叶子节点个数:递归终止条件,若为叶子节点则个数加1;否则分别递归左子节点和右子节点。
二叉树是非常基础的数据结构,要熟练掌握各种操作和遍历算法。这也是面试中常考察的内容。线索化二叉树与堆排序
线索化二叉树是二叉树的一种改进,能够快速访问前驱和后继节点。
实现思路: - 将所有叶子节点的left和right都指向前驱和后继节点
- 非叶子节点的left仍指向自己的左孩子,right指向前驱节点或后继节点
- 采用中序遍历对二叉树进行线索化
具体实现代码如下:public class ThreadedBinaryTree { private TreeNode pre; // 保存当前节点的前驱节点 public void inOrderThreading(TreeNode root) { if (root == null) return; inOrderThreading(root.left); // 线索化左子树 if (root.left == null) { // 没有左子节点 root.left = pre; root.leftType = 1; // 左线索 } if (pre != null && pre.right == null) { // 前驱节点right为空 pre.right = root; pre.rightType = 1; // 右线索 } pre = root; // 前驱指向当前节点 inOrderThreading(root.right); // 线索化右子树 } }线索化二叉树的好处是可以快速访问节点的前驱和后继,不需要递归遍历,时间复杂度为O(1)。这在某些应用中具有很高的优势,如树的遍历、删除等操作。
堆排序利用二叉堆的结构实现排序,具体做法为:
1.将无序序列构建成一个二叉堆,根节点为最大值。
2.每次取出二叉堆的根节点,并进行调整使其重新符合二叉堆。
3.重复步骤2,直到堆为空,则获得一个有序序列。
具体实现代码如下:public void heapSort(int[] nums) { if (nums == null || nums.length < 2) return; // 构建初始堆,i从最后一个有孩子节点的开始调整 for (int i = nums.length / 2 - 1; i >= 0; i--) { heapify(nums, i, nums.length); } // 进行n-1次调整,第i次得到i个元素的有序序列 for (int i = nums.length - 1; i > 0; i--) { swap(nums, 0, i); // 交换堆顶和最后一个元素 heapify(nums, 0, i); // 重新调整 } } // 调整使以start为根节点的子树成为一个堆 public void heapify(int[] nums, int start, int end) { int parent = start, left = 2 * start + 1, right = 2 * start + 2; int max = parent; // 默认根节点最大 // 找到最大值,交换到根节点 if (left < end && nums[left] > nums[max]) max = left; if (right < end && nums[right] > nums[max]) max = right; if (max != parent) { swap(nums, max, parent); heapify(nums, max, end); // 继续调整 } }堆排序的时间复杂度为O(nlogn),空间复杂度为O(1)。利用二叉堆的结构实现,效率很高。
数据结构和算法