斐波那契数列 C_C++
用三种方法实现:
带备忘录的递归
dp迭代
迭代优化,空间复杂度为O(1)
#include <cstdio>#include <iostream>#include <vector>using namespace std;#define _for(i,a,b) for(int i=(a);i<=(b);i++)//备忘录int helper(vector<int>& memo, int n) { //base case if (n == 2 || n == 3) { return 1; } if (memo[n] != 0) { return memo[n]; } else { memo[n] = helper(memo, n - 1) + helper(memo, n - 2); return memo[n]; }}//带备忘录法int fib_1(int N) { if (N <= 1) { retur ...
算法期末复习
用思维导图整理了一下算法的基本知识
算法概述
递归与分治策略
动态规划
贪心算法
回溯法
分支限界法
PDF文件(内有超链接)
参考资料:
算法中的P问题、NP问题、NP完全问题和NP难问题
分治法之棋盘覆盖问题
排序之归并排序
教你彻底学会动态规划——入门篇
矩阵连乘
最小生成树的两种方法(Kruskal算法和Prim算法)
循环赛日程表(分治法)
最后推荐一个算法可视化的网站VisuAlgo
软件体系结构基本知识——期末复习
根据老师画的重点做了一些思维导图,希望可以帮到需要的人
第一章
第二章
第三章
第四章
第六章
第七章
第八-九章
PDF文件
做得如有不足,敬请谅解~
图的邻接表表示转换成邻接矩阵
算法思想:先初始化邻接矩阵。依次遍历各个顶点的边表,根据边表中记录的“改弧所指向的顶点的位置”修改邻接矩阵arc[i][j]的值。例如遍历第 i 行的时候(当前的顶点所在行数为 i ),依次遍历该顶点的边表结点,若当前顶点的弧顶点的位置为j,则arc[i][j] = 1
创建如下的图:
全部代码如下:
#include <iostream>using namespace std;#pragma region 创建邻接表存储的无向图#define MaxVertexNum 100 //图中顶点数目最大值#define VertexType char#define _for(i,a,b) for(int i=(a);i<(b);i++)typedef struct ArcNode { //边表结点 int adjvex; //该弧所指向的顶点的位置 ArcNode* next; //指向下一条弧的指针}ArcNode;typedef struct VNode { / ...
LeetCode 131. Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: “aab”Output:[ [“aa”,”b”], [“a”,”a”,”b”]]
题目链接
可以回溯法切割出来字串,然后判断是否为回文串
由于要找出来全部的字串,所有回溯的范围应该是全部遍历一遍。使用for循环进行横向的遍历,for循环结束的条件就是本层集合的个数(也就是树中孩子的数量),cur代表当前要切割的位置
for(int i=cur;i<s.length();i++)
然后进行纵向的遍历,每当切割出来一个回文串,就把其放入tmp中,然后进行回溯。否则跳过。
if(Ispalindrome(s,cur,i)){ string item=s.substr(cur,i-cur+1); tmp.pu ...
LeetCode 47 Permutations II
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.Example 1:
Input: nums = [1,1,2]Output:[[1,1,2], [1,2,1], [2,1,1]]Example 2:
Input: nums = [1,2,3]Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints:
1 <= nums.length <= 8-10 <= nums[i] <= 10
题目链接
这道题在全排列1上添加了重复的元素,所以剪枝的情况要多考虑一种。比如1,2,2’2,2’与2’,2其实是一种情况,所以要舍去。而对于重复的元素,一开始先排序是一个不错的选择。再排序完之后,如果当前元素和上一个元素相等并且上一个元素还没有被用过(但是后面一定会被用到造成重复),这样的时候就要考虑剪枝
i ...
LeetCode 46. Permutations
Given a collection of distinct integers, return all possible permutations.Example:
Input: [1,2,3]Output:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
题目链接
看了看大佬们的讲解,终于自己做出来一道回溯的题。回溯大致分为三步:
终止条件:回溯到什么情况就可以加入答案列表
剪枝条件:什么情况下就可以停止回溯直接continue
回溯范围:如何将当前层和下一层联系起来继续递归下去
对于这道全排列的题,我们需要一个res保存答案,一个temp参与回溯,当达到终于条件也就是temp的大小与nums的相等时便把temp加入res中;然后需要一个check数组来标记使用过的元素,当一个数已经被使用过便把对应的位置的值设为1,这样避免了一个数重复使用多次。由于这道题是要列出所有的排列结果,所以需要全部遍历
代码如下:
class Solution {public: vector<vector&l ...
Java实现鲜花销售系统
描述项目环境
IDE:IDEA
数据库:Mysql 8.0.22
JDK:1.8
界面设计插件:JFormDesigner
登录界面顾客界面
后代管理界面
代码结构
源码链接
C_C++用宏定义简化for循环
记录一下for循环简化#define _for(i,a,b) for( int i=(a); i<(b); ++i)这样for(int i=0;i<10;i++)就简化为了
_for(i, 0, 10)
2021版王道数据结构课后代码题全部实现
历时2个多月,把21版王道数据结构的课后代码题全部实现了一遍,一共96道题
文件目录结构:
编程环境:Visual Studio 2019
编程语言:C/C++
其中,每道题都是一个独立的cpp文件,可以独立运行。在树和图的章节,会有输入样例和对应的示例图。
cpp文件结构
建立要求的数据结构
题目说明
题目要求的代码
运行示例
以树章节的题目示例:
#include <iostream>#include <stack>#include <queue>using namespace std;#pragma region 构造链式存储的表达式二叉树#define MaxSize 100#define ElemType char#define _for(i,a,b) for(int i=(a);i<(b);i++)typedef struct node { //树的结点 ElemType data[10]; node* left; node* right;}Node, * BiTree;void ...