经典算法四题速解攻略

一、今日学习目标承接上节基础题拿下 4 道中等高频经典题爬楼梯简单 DP 入门最大子数组和经典 DP无重复字符的最长子串滑动窗口二叉树层序遍历迭代通用模板一、爬楼梯 —— 动态规划入门题意每次爬 1 阶或 2 阶爬到第 n 阶共有多少种方法。核心思路dp[i]dp[i−1]dp[i−2]最后一步走 1 阶 / 最后一步走 2 阶。#include stdio.h int climbStairs(int n) { if (n 2) return n; int a 1, b 2, c; for (int i 3; i n; i) { c a b; a b; b c; } return b; } int main() { printf(%d\n, climbStairs(5)); return 0; }二、最大子数组和 —— 经典 DPKadane 算法题意找出整数数组中连续子数组的最大和。思路选当前数单独开局 / 接上前面子数组dp[i]max(nums[i], dp[i−1]nums[i])int maxSubArray(int* nums, int n) { int pre nums[0]; int maxSum nums[0]; for (int i 1; i n; i) { pre pre nums[i] nums[i] ? pre nums[i] : nums[i]; maxSum pre maxSum ? pre : maxSum; } return maxSum; }三、无重复字符最长子串 —— 滑动窗口核心双指针维护窗口记录字符是否出现遇重复左指针右移。#include string.h int lengthOfLongestSubstring(char *s) { int exist[128] {0}; int l 0, maxLen 0; int len strlen(s); for (int r 0; r len; r) { while (exist[s[r]]) { exist[s[l]] 0; l; } exist[s[r]] 1; int curLen r - l 1; maxLen curLen maxLen ? curLen : maxLen; } return maxLen; }四、二叉树层序遍历 —— 队列迭代通用模板复用队列 BFS按层输出面试手写高频。#include stdlib.h typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }TreeNode; #define MAXSIZE 1000 void levelOrder(TreeNode* root) { if (!root) return; TreeNode* q[MAXSIZE]; int front 0, rear 0; q[rear] root; while (front rear) { int size rear - front; for (int i 0; i size; i) { TreeNode* cur q[front]; printf(%d , cur-val); if (cur-left) q[rear] cur-left; if (cur-right) q[rear] cur-right; } printf(\n); } }五、核心算法思想总结爬楼梯线性 DP空间压缩最简递推最大子数组贪心 DP 结合大厂笔试原题最长无重复子串滑动窗口字符串通用解法层序遍历BFS 队列模板所有二叉树层次题通用六、今日小练习爬楼梯 n6输出答案数组[-2,1,-3,4,-1,2,1,-5,4]求最大子数组和字符串abcabcbb求最长无重复子串长度