Trluper
0%

发表于 更新于 分类于
本文字数： 36k 阅读时长 ≈ 33 分钟

1. 了解SQL

1.1 数据库基础

数据库是一个以某种有组织的方式存储的数据集合。MySQL数据库中只有一个用户，名为root，但是它可以有多个数据库，如下是与Oracle数据库的不同之处：

阅读全文 »

发表于 更新于 分类于
本文字数： 78k 阅读时长 ≈ 1:11

0. 刷题规划

读者在看到这篇文章的时候不应该以本文的讲解顺序进行刷题。正常来说，按模块刷题是最好的，我的刷题是按照数组->链表->树->dp的循环进行，然后对各模块的方法进行总结，比如遇到 - 数组一类的，其可使用的方法最多：二分查找、快慢指针、双指针、滑动窗口、前缀和数组、差分数组等。 - 遇到链表，那么快慢指针是最多的。 - 遇到树，那么递归（广度or深度）是最常用的形式、非递归遍历也要顺序，记住对称性解题方式。 - 遇到动态规划，先分类其是属于哪种形式的dp（线性dp、区间dp、背包dp和状压dp），然后确定dp含义，分析状态转移方程。 - 其他方法，比如**单调栈、单调队列的实现、拓扑排序、归并排序、KMP算法、分治、广度*等算法就就需要在刷题中不断掌握

注意：在解题中一定不要忽略暴力解，许多奇妙的解法就是从暴力解的思路上想出来的，一旦遇到一道不会优解的题，可以先想一想暴力解的思路，有什么地方可以优化暴力解，来达到降低时间复杂度的效果

1. 动态规划类

动态规划的思想就是：如果一个问题能够由子问题一步步递推得来，即当前子问题的解将由上一次子问题的解推出，利用这种特性，使用一个数据结构dp来存储上一次子问题的结果，避免重复计算。

所以动态规划最重要的有三点：

  • 确定dp的含义
  • 确定dp的初始状态
  • 确定dp间的状态转移方程

知道上述三点，问题也就迎刃而解。在算法当中，常见的dp类型有线性dp、区间dp、背包dp和状压dp。下面将对这几个进行讲解。

总结：对于是否使用DP，那么就得看你能不能确定dp数组的含义，以及能够确定状态转移方程。

tips：做了比较多的题，通常许多的字符串dp类型的题目是区间dp，像回文串、编辑距离等待，二数组类型的dp，较多的是线性dp、多状态dp（状压dp)和背包dp类型

1.1 线性DP

打家劫舍

问题：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

阅读全文 »

发表于 更新于 分类于
本文字数： 11k 阅读时长 ≈ 10 分钟

DP的思想

DP的由来是因为可以将一个问题由子问题得出：完整的问题可以由正方向得出（符合人的逻辑，自底向上），也可以由反方向得出（回溯，自顶向下），一般来说推荐正难则反，即推荐反向思考。

所以dp问题最经典的解题思路四个步骤就是：问题能否从结果往前递归回溯（即由上一个问题得到当前问题解）？-->回溯+记忆化搜索（优化时间）-->1:1翻译成递推，即dp形式-->优化空间

回溯的方式更加容易且贴合dp的子问题递归，因此这里讲的是以反向方式来解决。（不去关心到达怎么解决，只关心当前状态是按什么方程由上一个状态得来的）

记忆化搜索：通过dfs的参数来决定创建的是几维数组，它也决定可了递推式中dp的维度

  • 线性DP：一般从前缀/后缀上进行转移
  • 区间DP：从小区间转移到大区间

1 线性DP

线性DP，一般从前缀/后缀上进行转移。 ### 1.1 背包问题 本质还是选与不选 #### 0-1背包 0-1背包：有n个物品，第i个物品的体积为w[i]，价值为v[i]，每个物品至多选一个，求体积和不超过capacity时的最大价值和。

思路：

背包问题是dp的一个经典题型，涉及到一个当前元素选与不选： - 选：在剩余容量为c-w[i]时，从前i-1个物品得到的最大价值和 - 不选：在剩余容量c时，从前i-1个物品得到的最大价值和 - 取两者较大值。

边界问题： - i<0或者c<0时，需要返回0，次数代表没有其他商品可选，或者没有容量可以装了

记忆化搜索：通过dfs的参数来决定创建的是几维数组，它也决定可了递推式中dp的维度

回溯+记忆化搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxValue(vector<int>&w,vector<int>&v,int capacity){
	int n = w.size();
	//数组存储已经得到过的dfs{i,c)
	vector<vector<int>> cache(n,vector<int>(capacity+1,-1));
	function<int(int,int)> dfs = [&](int i,int c){
		if(i < 0||c < 0) return 0;
		int& res = cache[i][c];
		if(res!=-1) return res;
		if(c>=w[i]){
			res = dfs(i-1,c-w[i])+v[i];
		}
		res = max(res,dfs(i-1,c));
		return res;
	};
	return dfs(n-1,capacity);
}
递推

讲上述的“回溯+记忆化搜索”进行1：1翻译可以得到递推，注意翻译过程中的边界条件如何实现（一般通过增加1个开额外的dp数组即可）

上述中，用dp数组得到的递推式如下： dp[i][c] = max(dp[i-1][c],dp[i-1][c-w[i]]+v[i])

1
2
3
4
5
6
7
8
9
10
11
int maxValue(vector<int>&w,vector<int>&v,int capacity){
	int n = w.size();
	vector<vector<int>> dp(n+1,vector<int>(capacity+1,0));	//对边界条件和cache的翻译,i=0作为边界
	for(int i = 0; i < n; ++i){
		for(int j = 1; j <= capacity; ++j){
			if(j>=w[i]) dp[i+1][j] = dp[i][j-w[i]]+v[i];
			dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
		}
	}
	return dp[n][capacity];
}

变体题目：

494.目标和

完全背包

完全背包与01背包的不同点，只在于可以重复选择：

回溯+记忆化搜索

只需要更改res = dfs(i-1,c-w[i])+v[i];为res = dfs(i,c-w[i])+v[i];即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxValue(vector<int>&w,vector<int>&v,int capacity){
	int n = w.size();
	//数组存储已经得到过的dfs{i,c)
	vector<vector<int>> cache(n,vector<int>(capacity+1,-1));
	function<int(int,int)> dfs = [&](int i,int c){
		if(i < 0||c < 0) return 0;
		int& res = cache[i][c];
		if(res!=-1) return res;
		if(c>=w[i]){
			res = dfs(i,c-w[i])+v[i];
		}
		res = max(res,dfs(i-1,c));
		return res;
	};
	return dfs(n-1,capacity);
}

变体题目： 332.零钱兑换

1.2 股票问题(状态DP)

leetcode内由许多股票问题，这类成为状态机DP 121.买卖股票的最佳时机 122.买卖股票的最佳时机Ⅱ 123.买卖股票的最佳时机Ⅲ 188.买卖股票的最佳时机Ⅳ 714.买卖股票的最佳时机含手续费 309.买卖股票的最佳时机含冷冻期

上面的题目均可由回溯+记忆化搜索的一个模板解决。

买卖股票的最佳时机Ⅱ

其题意就是就是至少交易0次，即可以交易无穷次。

回溯+记忆化搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxProfit(vector<int>& prices) {
       int n = prices.size();
       vector<vector<int>>cache(n,vector<int>(2,-1));
       function<int(int,bool)>dfs = [&](int i,bool hold){
           if(i<0) return hold?INT_MIN/2:0; 
           int& res = cache[i][hold];
           if(res!=-1) return res;
           if(hold)
               res = max(dfs(i-1,true),dfs(i-1,false)-prices[i]);
           else 
               res = max(dfs(i-1,false),dfs(i-1,true)+prices[i]);
           cache[i][hold] = res;
           return res;
       };
       return dfs(n-1,false);
   }
递推

将回溯+记忆化搜索进行1：1翻译成递推（自底向上），则递推式：dp(i,0)表示前i个股票中当前未持有股票时的最大利润，dp(i,1)`表示前i个股票中当前持有股票时的最大利润，有：

  • dp(i,0) = max(dp(i-1,0),dp(i-1,1)+prices[i])
  • dp(i,1) = max(dp(i-1,1),dp(i-1,0)-prices[i])

边界条件-->即递推的初始状态: 只需要将if(i<0) return hold?INT_MIN/2:0;这句话转换，因此我们为dp多开辟一个空间作为出发临界状态，即dp大小为dp[n+1][2]

  • dp[0][0] = 0
  • dp[0][1] = INT_MIN/2
1
2
3
4
5
6
7
8
9
10
11
int maxProfit(vector<int>& prices) {
	int n = prices.size();
	vector<vector<int>> dp(n+1,vector<int>(2,-1));
	dp[0][0] = 0;
	dp[0][1] = INT_MIN/2;
	for(int i = 0;i < n; ++i){
		dp[i+1][0] = max(dp[i][0],dp[i][1]+prices[i]);
		dp[i+1][1] = max(dp[i][1],dp[i][0] - prices[i]);
	}
	return dp[n][0];
}

买卖股票的最佳时机Ⅳ

最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。只需要将上面的代码dfs添加一个参数j即可 ##### 回溯+记忆化搜索 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxProfit(int k, vector<int>& prices) {
    int n = prices.size();
    int cache[n][k+1][2];
    memset(cache,-1,sizeof(cache));
    function<int(int,int,bool)> dfs = [&](int i,int j,bool hold){
         if(j<0) return INT_MIN/2;
         if(i<0) return hold?INT_MIN/2:0;
         int& res = cache[i][j][hold];
         if(res!=-1) return res;
         if(hold) res = max(dfs(i-1,j,true),dfs(i-1,j,false)-prices[i]);
         else res = max(dfs(i-1,j,false),dfs(i-1,j-1,true)+prices[i]);
         return res;
    };
    return dfs(n-1,k,false);
}

递推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 int maxProfit(int k, vector<int>& prices) {
     int n = prices.size();
     int dp[n+1][k+2][2];
     memset(dp,INT_MIN+100000,sizeof(dp));//①这句话就是边界条件返回的翻译
     for(int j = 1;j<=k+1;++j){
         dp[0][j][0] = 0;    //②，①②这两句话就是边界条件返回的翻译
     }
     for(int i = 0; i < n; ++i){
         for(int j = 1; j <= k+1; ++j){
             dp[i+1][j][1] = max(dp[i][j][1],dp[i][j][0]-prices[i]);
             dp[i+1][j][0] = max(dp[i][j][0],dp[i][j-1][1]+prices[i]);
         }
     }
     return dp[n][k+1][0];
}

思考：恰好k次交易如何做，那就需要保证初始状态正好是从恰好0次交易出发，而不会由其他状态，因此只有dp[0][1][0]=0 ，其他均为INT_MIN+100000

买卖股票的最佳时机含冷冻期

直接秒 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxProfit(vector<int>& prices) {
    int n =prices.size();
    vector<vector<int>> cache(n,vector<int>(2,-1));
    function<int(int,bool)> dfs = [&](int i,bool hold){
       if(i<0) return hold?INT_MIN/2:0;
        int& res = cache[i][hold];
        if(res!=-1) return res;
        //买入的前一天不能卖出,卖出的前一天没有限制
        if(hold) res = max(dfs(i-1,true),dfs(i-2,false)-prices[i]);
        else res = max(dfs(i-1,false),dfs(i-1,true)+prices[i]);
        return res;
    };
    return dfs(n-1,false);
}

1.3 最长公共子序列

从后缀转移进行转移，即：

回溯+记忆搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(),m = text2.size();
        vector<vector<int>> cache(n,vector<int>(m,-1));
        function<int(int,int)> dfs = [&](int i,int j){
            if(i<0) return 0;
            if(j<0) return 0;
            int& res = cache[i][j];
            if(res!=-1) return res;
            if(text1[i]==text2[j]) res = dfs(i-1,j-1)+1;
            res = max(res,max(dfs(i-1,j),dfs(i,j-1)));
            return res;
        };
        return dfs(n-1,m-1);
    }
};

递推

将上面的回溯+记忆搜索进行1:1翻译， 

1
2
3
4
5
6
7
8
9
10
11
12
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(),n=text2.size();
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));
    for(int i=0;i<m;++i){
        for(int j=0;j<n;++j){
            if(text1[i]==text2[j]) dp[i+1][j+1] = dp[i][j]+1;
            else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
        }
    }
    return dp[m][n];
}

2 区间DP

  • 区间DP：从小区间转移到大区间，可为两类
    • 选与不选：从两侧向内缩小文体规模--->如最长回文子序列(回文串系列)
    • 枚举选哪个：分割成多个规模更小的子问题--->如多边形三角部分的最低得分

2. 动态规划

我们遇到的问题中，有很大一部分可以用动态规划Dynamic Programming来解。 解决这类问题可以很大地提升你的能力与技巧，我会试着帮助你理解如何使用DP来解题

阅读全文 »

发表于 更新于 分类于
本文字数： 11k 阅读时长 ≈ 10 分钟

1. 算法总览

常见的排序算法有插入排序、选择排序、希尔排序、堆排序、冒泡排序、快速排序、归并排序和基数排序。常见排序算法可以分为两大类：

  • 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
  • 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。排序算法的时间复杂度如下：
阅读全文 »

发表于 更新于 分类于
本文字数： 4.8k 阅读时长 ≈ 4 分钟

1. make

1.1 make是什么

make是一个命令，是管理文件的自动编译管理器，这里的自动是指能根据文件时间戳自动发现更新过的文件而减少编译的工作量，同时通过读取makefile的文件的内容来进行预期的编译工作，make将只编译有改动的文件，而不用完全编译。

阅读全文 »

发表于 更新于 分类于
本文字数： 35k 阅读时长 ≈ 32 分钟

1. shell

shell是Linux系统中运行的一种特殊程序。在用户和内核之间之间充当“翻译官”，用户登陆Linux系统时，自动加载一个Shell程序，Bash是Linux系统中默认使用的Shell程序。

  • 内核：用于调用计算机硬件资源
  • shell：将用户指令转换成计算机语言让内核去调用计算机硬件资源
阅读全文 »

发表于 更新于 分类于
本文字数： 4.9k 阅读时长 ≈ 4 分钟

1. Ubuntu常用快捷键

1
2
3
4
5
6
7
8
9
1、打开终端：Ctr+Alt+T
2、关闭终端：Ctrl + Shift + Q
3、复制：Ctrl + Shift + C
4、粘贴：Ctrl + Shift + V
5、跳转回主机操作:ctr+alt
6、跳回虚拟机：Ctr+G
7、新建终端窗口：Ctrl + Shift + N
8、运行命令：Alt + F2
9、全屏切换：F11
阅读全文 »

发表于 更新于 分类于
本文字数： 88k 阅读时长 ≈ 1:20

1.STL概述

1.1 六大组件
  • 容器：各种数据结构,如vector、list、deque、set、map等,用来存放数据
  • 算法：各种常用的算法（冒泡，排序）,如sort、find、copy、for_each、search、erase
  • 迭代器：扮演了容器与算法之间的胶合剂，是所谓的泛型指针
  • 仿函数：行为类似函数，可作为算法的某种策略
  • 适配器：一种用来修饰容器或者仿函数或迭代器接口的东西
  • 空间配置器：负责空间的配置与管理。注意一般都伴随着重新分配空间，那么原来的迭代器就会失效

六大组件的交互关系是Container通过Allocator获得数据存储空间，Alogrithm通过Iterator存取Container的内容，Functor可以协助Algorithm完成不同的策略变化，Adapter可以修饰或套接Functor。本笔记将会以此对这六大组件进行介绍。

++说在前面：STL的实现版本由HP版本、PJ版本、RW版本、STLport版本和SGISTL版本等五个主要版本++

阅读全文 »

发表于 更新于 分类于
本文字数： 56k 阅读时长 ≈ 50 分钟

1.说在前面

c++支持两种类--抽象类和具体类。一个抽象类包含着没有实现代码的成员函数（纯虚函数）。具体了类没有纯虚函数。只有具体类才可以实例化（但抽象类实例化指针和引用是运行的），即只能对具体类建立实例或对象。

在这里主要讲解各种数据结构的思想，列举抽象类接口和实现一部分具体类的接口功能。

阅读全文 »

发表于 更新于 分类于
本文字数： 29k 阅读时长 ≈ 26 分钟

1. 面向对象程序设计

面向对象程序设计的核心思想是数据抽象、继承和动态绑定。通过数据抽象，我们可以将类的接口与实现相分离；使用继承。可以使用相似的类型对其关系建模；使用动态绑定，可以在一定程度上忽略相似类型的区别。

  • 1）继承：根部类为基类（相似于java的父类），其他继承于基类的类为派生类。
  • 2）虚函数：某些函数，基类希望它的派生类各自定义适合其自生的函数
  • 3）动态绑定：能使用同一代码分别处理基类和派生类。如虚函数运行版本由实参决定。

1.1 定义基类

  • 作为继承关系中根结点的类通常有定义了一个虚析构函数。
  • 基类中的成员函数分为两种：一是派生类要进行重写覆盖的函数，称为虚函数；二是希望直接继承而不改变的函数。当我们使用指针或引用调用虚函数时，该调用将被动态绑定。
  • 基类通过在其成员函数的声明语句之前加上关键字virtual使得函数执行动态绑定。其只能出现在类内部声明或定义中。
  • 派生类可以继承定义在基类中的成员，但是派生类的的成员函数不一定有权访问从基类继承而来的成员。派生类能访问公有成员，但不能访问私有成员。为解决这一问题，引入了新访问运算符：protected(派生类有权访问，禁止用户访问）
阅读全文 »