网站建设基础书本wordpress大图模板

当前位置： 首页 > news >正文

网站建设基础书本,wordpress大图模板,景观设计案例网站,深圳定制家具厂layout: post title: leetcode重点题目分类别记录#xff08;二#xff09;基本算法#xff1a;二分#xff0c;位图#xff0c;回溯#xff0c;动态规划#xff0c;拓扑排序 description: leetcode重点题目分类别记录#xff08;二#xff09;基本算法#xff1a;二… layout: post title: leetcode重点题目分类别记录二基本算法二分位图回溯动态规划拓扑排序 description: leetcode重点题目分类别记录二基本算法二分位图回溯动态规划拓扑排序 tag: 数据结构与算法 基本算法二分位图回溯动态规划图搜索拓扑排序二分查找搜索插入位置搜索旋转数组前缀和一维二维差分数组题目应用回溯组合排列分割问题分割回文串复原ip地址子集问题子集2递增子序列子集2的另一种去重方法暴力搜索动态规划背包问题01背包完全背包打家劫舍股票系列子序列类数位dp图搜索广度优先搜索bfs迷宫最近的出口解开密码锁的最少次数双向bfs优化深度优先搜素dfs图论基础及其遍历算法基本概念邻接表和邻接矩阵度加权图无向图图的遍历题目应用可能的路径二分图判断算法概念二分图判断思路题目应用拓扑排序部分内容来自拉不拉东的算法小抄 二分查找 搜索插入位置 二分查找本质上是排除法的思路不断将搜索空间缩减为原来的一半因此整体的时间复杂度为O(LogN)不同的题目需要注意ans的候选位置。 例如本题搜索插入位置返回插入位置的索引 如果mid处等于目标值那么直接返回mid 如果mid处大于目标值说明目标值应该插在mid左边那么ans候选位置就是mid 如果mid处小于目标值说明目标值应该插入mid右边那么ans候选位置就是mid1 int searchInsert(vectorint nums, int target) {int left 0, right nums.size() - 1, ans left;while (left right) {int mid left ((right - left) 1);if (nums[mid] target) return mid;if (nums[mid] target) {// target在左边更新右边界mid处为可能的插入位置ans mid;right mid - 1;} else {// target 在右边更新左边界mid 1处为可能的插入位置left mid 1;ans left;}}return ans;}搜索旋转数组 基础版没有重复元素 int search(vectorint nums, int target) {int left 0, n nums.size(), right n - 1;while (left right) {int mid left ((right - left) 1);if (nums[mid] target) return mid;if (nums[mid] nums[0]) { // 通过与nums[0]比较判断nums[mid]的落点在断点左边或右边// 在断点左边这部分有序区间二分if (target nums[0] target nums[mid]) right mid - 1; // 如果目标值与中间值在同一部分有序区间可以排除一半并进入有序空间的排序else left mid 1; // 即使不在同一部分也可以缩减搜索整个区间的范围} else {// 在断点右边这部分有序区间二分if (target nums[mid] target nums[right]) left mid 1;else right mid - 1;}}return -1;}前缀和 前缀和适用于很快的求解某个区间的累计和 一维 preSum[i]记录前i个数的累计和i从0开始那么 preSum[right] - preSum[left] 就是左闭右开区间[left, right)的nums子数组和。 二维 仿照一维的思路用pre[i 1][j 1]表示从左上角到下标(ij)位置表示的右下角位置间区域的累计和。 那么任意一个矩形区间的累计和可标记为 注意在下边的代码中在计算累加时的方法为 presum[i 1][j 1] presum[i 1][j] presum[i][j 1] matrix[i][j] - presum[i][j]; 左上角部分加了两次要减去 而计算区间时左上角部分减了两次要加回来 presum[row2 1][col2 1] presum[row1][col1] - presum[row1][col2 1] - presum[row2 1][col1];
class NumMatrix { public:vectorvectorint presum;NumMatrix(vectorvectorint matrix) {int m matrix.size(), n matrix[0].size();presum vectorvectorint(m 1, vectorint(n 1));for (int i 0; i m; i) {for (int j 0; j n; j) {presum[i 1][j 1] presum[i 1][j] presum[i][j 1] matrix[i][j] - presum[i][j];}}}int sumRegion(int row1, int col1, int row2, int col2) {return presum[row2 1][col2 1] presum[row1][col1] - presum[row1][col2 1] - presum[row2 1][col1]; } };差分数组 差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。 差分数组的求法 第一个数与nums[0]后边每个数等于该处下标 减去 前一个下标。 后减去前第一个位置前面没有故是本身 diff[0] nums[0]; diff[i] nums[i] - nums[i - 1]; 可以发现根据差分数组diff可以还原出nums数组具体做法就是对差分数组diff求累计和 因为是求累计和所以假定我们给diff数组i位置处增减一个元素值那么它后边位置处都会增减该元素值。 具体的假定你要让左闭右开区间[left, right)上的元素都加上k 那么只需令差分数组diff[left] kdiff[right] - k; 我们可以将上述过程写成一个封装的类输入一个nums数组设置increament方法。 特别需要注意的是 构建差分数组diff[]时需要右减左而恢复时是需要累加。 class Difference {public:vectorint diff;Difference(const vectorint nums){diff nums;for (int i 1; i nums.size(); i) {diff[i] - nums[i - 1]; }}// 给左闭右开区间[i, j) 增加valval可以是负数void increment(int i, int j, int val) {diff[i] val;if (j diff.size()) diff[j] - val;}vectorint getResult() {vectorint res(diff);for (int i 1; i res.size(); i) {res[i] res[i - 1];}return res;} };题目应用 分析题意其实就是初始answer都是0根据bookings将对应区间都加上座位数。 可以直接利用上边写的差分数组类 注意我们写的时候是对左必右开区间同时增加。 而题目的意思是左右闭区间此外航班序号比索引号大1. vectorint corpFlightBookings(vectorvectorint bookings, int n) {vectorint nums(n);Difference d(nums);for (int i 0; i bookings.size(); i) {int x bookings[i][0] - 1, y bookings[i][1], val bookings[i][2];d.increment(x, y, val);}return d.getResult();}回溯 组合 注意剪枝 当前可选的数据范围为[i, n] 有 n - i 1个 还需要的数据个数为 k - path.size(); 可选范围必须大于等于所需的元素。 vectorvectorint combine(int n, int k) {vectorvectorint ans;vectorint path;functionvoid(int) backtracking {if (path.size() k) {ans.push_back(path);return;}for (int i index; i n path.size() n - i 1 k; i) {path.push_back(i);backtracking(i 1);path.pop_back();}};backtracking(1);return ans;}排列 排序问题与组合问题最大的区别在于前边的选择是否影响后边的选择 比如123 如果第一步选择了2那么后边可选的只剩下3 而排列中第一步选择了2后边还是可以选择1或3 对应在代码中组合问题一般回溯到下一层传递的是 i 1i是当前选择的位置而排序则是index 1按照 index即层序来更新而非当前选择的位置i。 vectorvectorint permute(vectorint nums) {vectorvectorint ans;functionvoid(int) dfs {if (index nums.size()) {ans.push_back(nums);return;}for (int i index; i nums.size(); i) {swap(nums[i], nums[index]);dfs(index 1);swap(nums[i], nums[index]);}};dfs(0);return ans;}有重复情况下的排列去重逻辑与组合一样。与组合不同的地方在于每个位置都有可能添加到当前path的末尾因此需要一个used数组然后每次遍历整个nums。 vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(), nums.end());vectorvectorint ans;vectorint path;vectorbool used(nums.size(), false);functionvoid() dfs {if (path.size() nums.size()) {ans.push_back(path);return;}for (int i 0; i nums.size(); i) {if (i 0 nums[i] nums[i - 1] used[i - 1] false) continue;if (used[i] false) {path.push_back(nums[i]);used[i] true;dfs();path.pop_back();used[i] false;}}};dfs();return ans;}分割问题 分割回文串 分割问题的本质为确定分割线的位置可能 根据一个起始的分割点枚举所有可能的下一个分割点如果当前分割出了回文串进入更深层次的搜索。 class Solution { public:vectorvectorstring partition(string s) {vectorvectorstring ans;vectorstring path;functionvoid(int) dfs {if (index s.size()) {ans.push_back(path);return;}for (int i index; i s.size(); i) {string str s.substr(index, i - index 1);if (isValid(str)) {path.push_back(str);dfs(i 1);path.pop_back();}}};dfs(0);return ans;}bool isValid(const string str) {for (int i 0, j str.size() - 1; i j; i, –j) {if (str[i] ! str[j]) return false;}return true;} };复原ip地址 复原ip地址问题同样是确定分割点这里比较复杂的地方在于剪枝。 class Solution { public:vectorstring restoreIpAddresses(string s) {vectorstring ans;vectorstring path;if (s.size() 4 || s.size() 12) return ans;functionvoid(int) dfs {// 根据当前位置和剩余的字符确定剩余部分是否能够构成一个有效的部分int leftPart 4 - path.size(), leftChar s.size() - index;if (leftChar leftPart || leftChar 3 * leftPart) return;if (path.size() 3) {string leftStr s.substr(index, leftChar);if (isValid(leftStr)) {string res;for (string str : path) res str .;res leftStr;ans.push_back(res);}return;}// i index 3 保证了分割出的子串长度小于等于3for (int i index; i s.size() i index 3; i) {string str s.substr(index, i - index 1);if (isValid(str)) {path.push_back(str);dfs(i 1);path.pop_back();}}};dfs(0);return ans;}bool isValid(const string str) {if (str.size() 1) return true;if (str[0] 0) return false;int num 0;for (char c : str) num num * 10 (c - 0);return num 255;} };子集问题 子集2 子集问题与回溯中其他问题最大的区别在于不需要设置回溯的终点因为回溯路径上每一个节点都是最终所需的一个path因此上来就需要将当前path加入到ans中且不能return选或者不选都是一种子集可能的情况。 vectorvectorint subsetsWithDup(vectorint nums) {vectorvectorint ans;vectorint path;sort(nums.begin(), nums.end());vectorbool used(nums.size(), false);functionvoid(int) dfs {ans.push_back(path);for (int i index; i nums.size(); i) {if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue;path.push_back(nums[i]);used[i] true;dfs(i 1);path.pop_back();used[i] false;}};dfs(0);return ans;}递增子序列 该题与子集2有相似的地方每次需要取路径树上的节点即选或者不选都是一种可能回溯开始就考虑是否将path添加到ans中 另一个相似的地方在于需要去重。 这一题去重的逻辑比子集稍微复杂一些首先它也是在当前层去重当前层如果已经选择了某个元素当前层的后边节点就不可以在使用。 但是子集2中不要求输出顺序因此可以对其进行排序把重复元素堆在一块儿。 这里则不行需要使用一个单独的hash表来记录当前层使用了哪些元素。注意这里的hash表只对当前回溯过程中当前层使用与used数组不同 vectorvectorint findSubsequences(vectorint nums) {vectorvectorint ans;vectorint path;int n nums.size();functionvoid(int) dfs {if (path.size() 1) ans.push_back(path);int hash[201] {0};for (int i index; i n; i) {if ((!path.empty() path.back() nums[i]) || hash[nums[i] 100] 1) continue;path.push_back(nums[i]);hash[nums[i] 100] 1;dfs(i 1);path.pop_back();}};dfs(0);return ans;}子集2的另一种去重方法 子集问题实际上也可以使用上边这种在单层使用hash表记录的形式。 并且我认为这种形式实际上更加直观易懂 vectorvectorint subsetsWithDup(vectorint nums) {vectorvectorint ans;vectorint path;sort(nums.begin(), nums.end());functionvoid(int) dfs {ans.push_back(path);int hash[21] {0};for (int i index; i nums.size(); i) {if (hash[nums[i] 10] 1) continue;path.push_back(nums[i]);hash[nums[i] 10] 1;dfs(i 1);path.pop_back();}};dfs(0);return ans;}暴力搜索 动态规划 背包问题 01背包 完全背包 打家劫舍 股票系列 子序列类 数位dp 图搜索 广度优先搜索bfs 广度优先搜索最经典的题目就是二叉树的层序遍历。 广度优先搜索的问题的本质就是让你在一幅图中找到从起点start到终点target的最近距离。 迷宫最近的出口 思路每次有四个方向可以选择使用bfs搜索将非墙的位置加入到队列中。为了避免走重复的路在加入队列后将相应位置标记为墙。当来到边界位置处边是最近的出口。为了记录距离可以把位置距离起点的距离同时记录到队列中的节点。 int nearestExit(vectorvectorchar maze, vectorint entrance) {int m maze.size(), n maze[0].size();const int dx[4] {1, -1, 0 , 0}, dy[4] {0, 0, 1, -1}; // 偏移量数组queuetupleint, int, int que; // 包含位置xy和距离起点距离的节点队列que.emplace(entrance[0], entrance[1], 0); maze[entrance[0]][entrance[1]] ; // 每次加入队列后将位置改为墙避免重复while (!que.empty()) {auto [x, y, d] que.front();que.pop();for (int i 0; i 4; i) {int cx x dx[i], cy y dy[i];if (cx 0 cx m cy 0 cy n maze[cx][cy] .) { // 只有相邻位置可走才进行判断与加入队列的操作if (cx 0 || cx m - 1 || cy 0 || cy n - 1) return d 1; // 如果其中一个有效相邻位置为边缘处说明找到出口了que.emplace(cx, cy, d 1);maze[cx][cy] ; // 每次加入队列后将位置改为墙避免重复}}}return -1;}解开密码锁的最少次数 class Solution { public:// 将i位置数字加一string plusone(string s, int i) {if (s[i] 9) {s[i] 0;return s;}s[i];return s;}// 将i位置数字减一string minusone(string s, int i) {if (s[i] 0) {s[i] 9;return s;}–s[i];return s;}int openLock(vectorstring deadends, string target) {const string root 0000;if (target root) return 0; // 如果目标值就是当前值直接返回unordered_setstring visited;for (string str : deadends) visited.insert(str); // 死亡数字相当于已经访问过不能再访问queuestring que;if (!visited.count(root)) { // 只有非访问过的节点才能加入队列入队即访问que.push(root);visited.insert(root);}int ans 0;while (!que.empty()) {int sz que.size();for (int i 0; i sz; i) {string cur que.front();que.pop();for (int j 0; j 4; j) { // 四个数字轮流上下转动string plus plusone(cur, j);if (plus target) return ans 1; // 如果转到target返回ans 1if (!visited.count(plus)) { // 只有非访问过的节点才能加入队列入队即访问que.push(plus);visited.insert(plus);}string minus minusone(cur, j);if (minus target) return ans 1;if (!visited.count(minus)) { // 只有非访问过的节点才能加入队列入队即访问que.push(minus);visited.insert(minus);}}}ans;}return -1;} };双向bfs优化 传统的 BFS 框架就是从起点开始向四周扩散遇到终点时停止而双向 BFS 则是从起点和终点同时开始扩散当两边有交集的时候停止。 因为双向bfs需要从两头开始扩散因此必须指定目标点位置 传统bfs是从起点位置不断向周围扩散直至扩散至目标处。 双向bfs从起点和终点两头扩散看最终是否能够有交集。
深度优先搜素dfs 图论基础及其遍历算法 基本概念 邻接表和邻接矩阵 邻接表和邻接矩阵是存储图结构的两种主要的方式方式 邻接表很直观把每个节点x的邻居都存到一个列表里然后把x和这个列表关联起来这样就可以通过一个节点x找到它的所有相邻节点。 邻接矩阵则是一个二维布尔数组我们权且称为matrix如果节点x和y是相连的那么就把matrix[x][y]设为true如果想找节点x的邻居那么遍历一遍matrix[x][…]就够了。 代码形式如下 // 邻接表 // graph[x] 存储 x 的所有邻居节点 vectorint graph[];// 邻接矩阵 // matrix[x][y] 记录 x 是否有一条指向 y 的边 bool matrix[][]; 邻接表的优点在于占用空间少因为邻接矩阵有很多空余空间浪费。但是邻接表无法快速判断两个节点是否相邻而临界矩阵却可以。因此两种形式各有利弊使用时需结合具体情况。 度 在无向图中度就是每个节点相连的边的条数由于有向图的边是有方向的因此每个节点的度又被细分为出度和入度。 加权图 有时图中还需要存储每个节点与相邻节点间的权重距离对于这种加权图 如果采用邻接表的形式存储在储存邻居点标号的同时还需记录对应的权重 如果采用邻接矩阵那么matrix[x][y]不再是布尔值而是一个int值0表示没有连接其他值表示权重。 代码形式如下 vectorpairint, int graph[];// 邻接矩阵 // matrix[x][y] 记录 x 指向 y 的边的权重0 表示不相邻 vectorvectorint matrix;无向图 如果是无向图其实等同于每个相邻节点是双向的。 如果连接无向图中的节点 x 和 y把 matrix[x][y] 和 matrix[y][x] 都变成 true 不就行了邻接表也是类似的操作在 x 的邻居列表里添加 y同时在 y 的邻居列表里添加 x。 把上面的技巧合起来就变成了无向加权图。 图的遍历 图的遍历与多叉树是类似的使用dfs遍历图可能是包含环的为了避免重复遍历需要一个visited数组进行辅助如果题目告诉了不包含环那么可以去掉visited数组 void traverse(TreeNode root) {if (root null) return;for (TreeNode child : root.children) {printf(进入节点 %s, child);traverse(child);printf(离开节点 %s, child);} }如果执行上边的遍历算法会发现这种方式会把根节点遗漏为了避免遗漏我们应该将打印时机放在for循环外部 void traverse(TreeNode root) {if (root null) return;printf(进入节点 %s, root);for (TreeNode child : root.children) {traverse(child);}printf(离开节点 %s, root); }题目应用 可能的路径 vectorvectorint allPathsSourceTarget(vectorvectorint graph) {vectorvectorint ans;vectorint path;int n graph.size();// 根据遍历起始点搜索下一步可以到达的位置functionvoid(int) traverse {// 记录path.push_back(cur);if (cur n - 1) {ans.push_back(path);}for (int c : graph[cur]) traverse©;// 撤销当前的记录path.pop_back();};traverse(0);return ans;}二分图判断算法 概念 二分图的定义 二分图的顶点集可分割为两个互不相交的子集图中每条边依附的两个顶点都分属于这两个子集且两个子集内的顶点不相邻。 从定义上不太好理解但可以用双色问题来等同于二分图问题。 给你一幅「图」请你用两种颜色将图中的所有顶点着色且使得任意一条边的两个端点的颜色都不相同你能做到吗 如果能那么这幅图就是二分图反之则不是。 从简单实用的角度来看二分图结构在某些场景可以更高效地存储数据。 比如说我们需要一种数据结构来储存电影和演员之间的关系某一部电影肯定是由多位演员出演的且某一位演员可能会出演多部电影。 既然是存储映射关系最简单的不就是使用哈希表嘛我们可以使用一个 HashMapString, List 来存储电影到演员列表的映射如果给一部电影的名字就能快速得到出演该电影的演员。 但是如果给出一个演员的名字我们想快速得到该演员演出的所有电影怎么办呢这就需要「反向索引」对之前的哈希表进行一些操作新建另一个哈希表把演员作为键把电影列表作为值。 显然如果用哈希表存储需要两个哈希表分别存储「每个演员到电影列表」的映射和「每部电影到演员列表」的映射。但如果用「图」结构存储将电影和参演的演员连接很自然地就成为了一幅二分图 每个电影节点的相邻节点就是参演该电影的所有演员每个演员的相邻节点就是该演员参演过的所有电影非常方便直观。 其实生活中不少实体的关系都能自然地形成二分图结构所以在某些场景下图结构也可以作为存储键值对的数据结构符号表。 二分图判断思路 判定二分图的算法很简单就是用代码解决「双色问题」。 说白了就是遍历一遍图一边遍历一边染色看看能不能用两种颜色给所有节点染色且相邻节点的颜色都不相同。 // 二叉树遍历框架 void traverse(TreeNode* root) {if (root nullptr) return;traverse(root-left);traverse(root-right); }// 多叉树遍历框架 void traverse(Node* root) {if (root nullptr) return;for (Node* child : root-children)traverse(child); }// 图遍历框架 vectorbool visited; void traverse(Graph* graph, int v) {// 防止走回头路进入死循环if (visited[v]) return;// 前序遍历位置标记节点 v 已访问visited[v] true;for (Vertex neighbor : graph-neighbors(v))traverse(graph, neighbor); } 因为图中可能存在环所以用 visited 数组防止走回头路。 这里可以看到我习惯把 return 语句都放在函数开头因为一般 return 语句都是 base case集中放在一起可以让算法结构更清晰。 回顾一下二分图怎么判断其实就是让 traverse 函数一边遍历节点一边给节点染色尝试让每对相邻节点的颜色都不一样。 所以判定二分图的代码逻辑可以这样写 // 图遍历框架 void traverse(Graph graph, bool visited[], int v) {visited[v] true;// 遍历节点 v 的所有相邻节点 neighborfor (int neighbor : graph.neighbors(v)) {if (!visited[neighbor]) {// 相邻节点 neighbor 没有被访问过// 那么应该给节点 neighbor 涂上和节点 v 不同的颜色traverse(graph, visited, neighbor);} else {// 相邻节点 neighbor 已经被访问过// 那么应该比较节点 neighbor 和节点 v 的颜色// 若相同则此图不是二分图}} } 题目应用 bool isBipartite(vectorvectorint graph) {int n graph.size();vectorbool visit(n, false), color(n, false);bool ans true;functionvoid(int) dfs {if (!ans) return; // 如果已经非二分图了直接返回不需要再遍历了if (visit[cur]) return; // 遍历过的跳过避免环路重复遍历visit[cur] true;for (int nb : graph[cur]) {if (!visit[nb]) {// 如果相邻节点没有被访问过那么给neighbor涂上与cur不一样的颜色color[nb] !color[cur];dfs(nb); // 接着遍历} else {// 如果相邻节点访问过了判断它与cur是否颜色不一样如果一样说明不是二分图if (color[cur] color[nb]) {ans false;return;}}}};// 因为图不一定是连通的可能存在多个子图所以要把每个节点都作为起点进行一次遍历如果任意一个子图不是二分图整个图都不算是二分图for (int v 0; v n; v) {if (!visit[v]) {dfs(v);}if (!ans) return false; // 如果从某个节点处开始遍历发现已经出现非二分图了直接返回false}return true;}拓扑排序