惠州做棋牌网站建设哪家好,建设一个普通的网站需要多少钱,房产备案查询,搜狗推广下架本文目录 算法的基本框架思想一、二叉树的基本框架1、二叉树的前序遍历2、二叉树的前序遍历优化2、二叉树的遍历基本框架 二、回溯算法的基本框架1、基本框架2、核心框架3、全排列的核心框架4、核心思想 三、动态规划的基本框架1、自顶向下递归的动态规划2、自顶向下递归的动态… 本文目录 算法的基本框架思想一、二叉树的基本框架1、二叉树的前序遍历2、二叉树的前序遍历优化2、二叉树的遍历基本框架 二、回溯算法的基本框架1、基本框架2、核心框架3、全排列的核心框架4、核心思想 三、动态规划的基本框架1、自顶向下递归的动态规划2、自顶向下递归的动态规划0-1 背包的解题框架 四、链表的基本框架1、迭代遍历单链表2、递归遍历单链表 五、数组的基本框架1、迭代遍历数组2、递归遍历数组 六、双指针的基本框架1、快慢指针框架1、左右指针框架 七、滑动窗口的基本框架1、滑动窗口算法框架 八、分治算法九、递归算法十、涉及字符串算法十一、Rabin-Karp 算法基础十二、二分算法基础 提示
我想说算法的本质就是穷举。 穷举有两个关键难点无遗漏、无冗余。
算法的基本框架思想
一、二叉树的基本框架
二叉树题目的重要性我提到二叉树算法是所有递归算法的根本动态规划、回溯算法、图论算法等高级算法底层都是二叉树算法的思想。
1、很多动态规划问题就是在遍历一棵树你如果对树的遍历操作烂熟于心起码知道怎么把思路转化成代码也知道如何提取别人解法的核心思路。
2、再看看回溯算法后文 回溯算法详解 干脆直接说了回溯算法就是个 N 叉树的前后序遍历问题没有例外。
3、比如全排列问题吧本质上全排列就是在遍历下面这棵树到叶子节点的路径就是一个全排列
1、二叉树的前序遍历
ListInteger res new LinkedList();// 返回前序遍历结果
ListInteger preorder(TreeNode root) {traverse(root);return res;
}// 二叉树遍历函数
void traverse(TreeNode root) {if (root null) {return;}// 前序遍历位置res.add(root.val);traverse(root.left);traverse(root.right);
}2、二叉树的前序遍历优化
// 定义输入一棵二叉树的根节点返回这棵树的前序遍历结果
ListInteger preorder(TreeNode root) {ListInteger res new LinkedList();if (root null) {return res;}// 前序遍历的结果root.val 在第一个res.add(root.val);// 后面接着左子树的前序遍历结果res.addAll(preorder(root.left));// 最后接着右子树的前序遍历结果res.addAll(preorder(root.right));return res;
}2、二叉树的遍历基本框架
void traverse(TreeNode root) {if (root null) {return;}// 前序位置traverse(root.left);// 中序位置traverse(root.right);// 后序位置
}1、二叉树模型几乎是所有高级算法的基础尤其是那么多人说对递归的理解不到位更应该好好刷二叉树相关题目。
2、二叉树题目的递归解法可以分两类思路第一类是遍历一遍二叉树得出答案第二类是通过分解问题计算出答案这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。
二、回溯算法的基本框架
1、路径也就是已经做出的选择。
2、选择列表也就是你当前可以做的选择。
3、结束条件也就是到达决策树底层无法再做选择的条件
1、基本框架
result []
def backtrack(路径, 选择列表):if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:做选择backtrack(路径, 选择列表)撤销选择2、核心框架
### 回溯算法核心框架 // 记录所有全排列
ListListInteger res new LinkedList();
LinkedListInteger track new LinkedList();/* 主函数输入一组不重复的数字返回它们的全排列 */
ListListInteger permute(int[] nums) {backtrack(nums);return res;
}// 回溯算法框架
void backtrack(int[] nums) {if (track.size() nums.length) {// 穷举完一个全排列res.add(new LinkedList(track));return;}for (int i 0; i nums.length; i) {if (track.contains(nums[i]))continue;// 前序遍历位置做选择track.add(nums[i]);backtrack(nums);// 后序遍历位置取消选择track.removeLast();}
}3、全排列的核心框架
## 全排序的主要算法
void backtrack(int[] nums, LinkedListInteger track) {if (track.size() nums.length) {res.add(new LinkedList(track));return;}for (int i 0; i nums.length; i) {if (track.contains(nums[i]))continue;track.add(nums[i]);// 进入下一层决策树backtrack(nums, track);track.removeLast();}
}
4、核心思想
1、回溯算法是对树形或者图形结构执行一次深度优先遍历实际上类似枚举的搜索尝试过程在遍历的过程中寻找问题的解。
2、深度优先遍历有个特点当发现已不满足求解条件时就返回尝试别的路径。此时对象类型变量就需要重置成为和之前一样称为「状态重置」。
3、许多复杂的规模较大的问题都可以使用回溯法有「通用解题方法」的美称。实际上回溯算法就是暴力搜索算法它是早期的人工智能里使用的算法借助计算机强大的计算能力帮助我们找到问题的解。
三、动态规划的基本框架
1、动态规划常常适用于有重叠子问题和最优子结构性质的问题并且记录所有子问题的结果因此动态规划方法所耗时间往往远少于朴素解法。
2、动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归自底向上就是递推。
3、使用动态规划解决的问题有个明显的特点一旦一个子问题的求解得到结果以后的计算过程就不会修改它这样的特点叫做无后效性求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次具有天然剪枝的功能从而减少计算量。
4、动态规划系列问题的核心原理无非就是先写出暴力穷举解法状态转移方程加个备忘录就成自顶向下的递归解法了再改一改就成自底向上的递推迭代解法了 动态规划的降维打击 里也讲过如何分析优化动态规划算法的空间复杂度。
1、自顶向下递归的动态规划
def dp(状态1, 状态2, ...):for 选择 in 所有可能的选择:# 此时的状态已经因为做了选择而改变result 求最值(result, dp(状态1, 状态2, ...))return result2、自顶向下递归的动态规划
# 初始化 base case
dp[0][0][...] base case
# 进行状态转移
for 状态1 in 状态1的所有取值for 状态2 in 状态2的所有取值for ...dp[状态1][状态2][...] 求最值(选择1选择2...0-1 背包的解题框架
int knapsack(int W, int N, int[] wt, int[] val) {assert N wt.length;// base case 已初始化int[][] dp new int[N 1][W 1];for (int i 1; i N; i) {for (int w 1; w W; w) {if (w - wt[i - 1] 0) {// 这种情况下只能选择不装入背包dp[i][w] dp[i - 1][w];} else {// 装入或者不装入背包择优dp[i][w] Math.max(dp[i - 1][w - wt[i-1]] val[i-1], dp[i - 1][w]);}}}return dp[N][W];
}四、链表的基本框架
1、单链表常考的技巧就是双指针
## 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {ListNode p1 head;// p1 先走 k 步for (int i 0; i k; i) {p1 p1.next;}ListNode p2 head;// p1 和 p2 同时走 n - k 步while (p1 ! null) {p2 p2.next;p1 p1.next;}// p2 现在指向第 n - k 1 个节点即倒数第 k 个节点return p2;
}head-1-2-3-4-5-6-7-8-9-10-null 一共10个节点
1、迭代遍历单链表
void traverse(ListNode head) {for (ListNode p head; p ! null; p p.next) {}
}x
2、递归遍历单链表 void traverse(ListNode head) {if (head null) {return;}// 前序位置traverse(head.next);// 后序位置
}五、数组的基本框架
1、数组常用的技巧有很大一部分还是双指针相关的技巧说白了是教你如何聪明地进行穷举。
2、数字组合的和等于目标和嘛。比较聪明的方式是先排序利用双指针技巧快速计算结果。
1、迭代遍历数组
void traverse(int[] arr) {for (int i 0; i arr.length; i) {}
}2、递归遍历数组 void traverse(int[] arr, int i) {if (i arr.length) {return;}// 前序位置traverse(arr, i 1);// 后序位置
}六、双指针的基本框架
1、双指针从广义上来说是指用两个变量在线性结构上遍历而解决的问题。
2、对于数组指两个变量在数组上相向移动解决的问题。
3、对于链表指两个变量在链表上同向移动解决的问题也称为「快慢指针」问题。
4、在处理数组和链表相关问题时双指针技巧是经常用到的
5、双指针技巧主要分为两类左右指针和快慢指针。
6、所谓左右指针就是两个指针相向而行或者相背而行。
7、而所谓快慢指针就是两个指针同向而行一快一慢。
8、只要数组有序就应该想到双指针技巧。这道题的解法有点类似二分查找通过调节 left 和 right 就可以调整 sum 的大小。
1、快慢指针框架
Node slow head.next;Node fast head.next;while(fast ! null fast.next ! null) {// 快指针走两步fast fast.next.next;// 慢指针走一步slow slow.next;
}1、左右指针框架
int left 0, right 0;while (right s.size()) {// 增大窗口window.add(s[right]);right;while (window needs shrink) {// 缩小窗口window.remove(s[left]);left;}
}七、滑动窗口的基本框架
1、滑动窗口算法技巧典型的快慢双指针快慢指针中间就是滑动的「窗口」主要用于解决子串问题。
2、滑动窗口也是有其限制的就是你必须明确的知道什么时候应该扩大窗口什么时候该收缩窗口。
3、滑动窗口指的是这样一类问题的求解方法在数组上通过双指针同向移动而解决的一类问题。
4、使用滑动窗口解决的问题通常是暴力解法的优化掌握这一类问题最好的办法就是练习然后思考清楚为什么可以使用滑动窗口。
1、滑动窗口算法框架
## 其中两处 ... 表示的更新窗口数据的地方到时候你直接往里面填就行了。
## 这两个 ... 处的操作分别是扩大和缩小窗口的更新操作等会你会发现它们操作是完全对称的
void slidingWindow(string s) {unordered_mapchar, int window;int left 0, right 0;while (right s.size()) {// c 是将移入窗口的字符char c s[right];// 增大窗口right;// 进行窗口内数据的一系列更新.../*** debug 输出的位置 ***/// 注意在最终的解法代码中不要 print// 因为 IO 操作很耗时可能导致超时printf(window: [%d, %d)\n, left, right);/********************/// 判断左侧窗口是否要收缩while (window needs shrink) {// d 是将移出窗口的字符char d s[left];// 缩小窗口left;// 进行窗口内数据的一系列更新...}}
}
八、分治算法
1、分治法是构建基于多项分支递归的一种很重要的算法范式。字面上的解释是「分而治之」就是把一个复杂的问题分成两个或更多的相同或相似的子问题直到最后子问题可以简单的直接求解原问题的解即子问题的解的合并。
2、这个技巧是很多高效算法的基础如排序算法快速排序、归并排序、傅立叶变换快速傅立叶变换。
九、递归算法
1、递归是计算机科学中的一个重要概念。它是许多其他算法和数据结构的基础。
2、每当递归函数调用自身时它都会将给定的问题拆解为子问题。递归调用继续进行直到到子问题成为一个不可以拆分的、可以直接求解的最简单问题。
3、为了确保递归函数不会导致无限循环它需要包含 一个简单的基本案例basic case或一些案例 能够不使用递归来产生答案的终止方案。 一组规则也称作递推关系recurrence relation可将所有其他情况拆分到基本案例。 注意函数可能会有多个位置进行自我调用这是分治算法。
十、涉及字符串算法
字符串往往由特定字符集内有限的字符组合而成根据其特点对字符串的 操作 可以归结为以下几类
1、字符串的比较、连接操作不同编程语言实现方式有所不同 2、涉及子串的操作比如前缀后缀等 3、字符串间的匹配操作如 KMP 算法、BM 算法等。
字符串排序按字典排列字符串可以调用Arrays.sort API也可以使用PriorityQueue还可以自己实现Comparator
十一、Rabin-Karp 算法基础
1、算法的核心思路就是不断向最低位个位添加数字
2、删除数字的最高位
用 R 表示数字的进制数用 L 表示数字的位数就可以总结出如下公式
/* 在最低位添加一个数字 */
int number 8264;
// number 的进制
int R 10;
// 想在 number 的最低位添加的数字
int appendVal 3;
// 运算在最低位添加一位
number R * number appendVal;
// 此时 number 82643/* 在最高位删除一个数字 */
int number 8264;
// number 的进制
int R 10;
// number 最高位的数字
int removeVal 8;
// 此时 number 的位数
int L 4;
// 运算删除最高位数字
number number - removeVal * R^(L-1);
// 此时 number 264十二、二分算法基础
int binarySearch(int[] nums, int target) {int left 0; int 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 if (nums[mid] target)right mid - 1; // 注意}return -1;
}1、初始化 right 的赋值是 nums.length - 1即最后一个元素的索引而不是 nums.length。
2、这二者可能出现在不同功能的二分查找中区别是前者相当于两端都闭区间 [left, right]后者相当于左闭右开区间 [left, right)因为索引大小为 nums.length 是越界的。
3、这个算法中使用的是前者 [left, right] 两端都闭的区间。这个区间其实就是每次进行搜索的区间。
