- 博客(50)
- 收藏
- 关注
RSS订阅原创 2021-02-03
win10下安装kali子系统详细步骤1.打开开发者选项，可能需要加载一些必要的程序。等就好了2、打开适图中子系统服务。3、去Microsoft 商店搜索kali,下载并安装，4、设置用户名和密码初次安装时普通用户，初始时，root用户时没有的（不清楚，反正就是没有），需要重置root密码。输入：su passwd root设置密码完成后，先进入root用户，以免后面安装得sudo.切换到root用户：su输入刚那个密码5、先安装一个v...
2021-02-04 08:47:43
194
原创 python刷题之路：递归--426. 恢复IP地址
题目：426.恢复IP地址中文English给一个由数字组成的字符串。求出其可能恢复为的所有IP地址。(你的任务就是往这段字符串中添加三个点, 使它成为一个合法的IP地址. 返回所有可能的IP地址.)样例样例 1:输入: "25525511135"输出: ["255.255.11.135", "255.255.111.35"]网上最详细的解释，每一步代码都有注...
2019-09-06 22:05:28
316
原创 LeetCode51：Python--N皇后问题
看了很多人讲述的题解，都觉得不够清楚。然后自己写了一下，应该很清楚吧如果是返回解的个数，那就直接用一个全局变量在遍历退出的地方记录一下就好了或者返回len(ans)，哈哈哈class Solution(object): """ @param: n: The number of queens @return: All distinct solutions ...
2019-09-03 21:52:40
287
原创 两个队列实现一个栈
class Q_to_S(object): def __init__(self): self.queue1 = [] self.queue2 = [] def push(self,data): if len(self.queue1) == 0: self.queue2.append(data) ...
2019-08-12 22:21:37
108
原创 dp基础之坐标型Max Square
问题：给定一个全是0或1的网格，求一块全由1组成的最大的正方形的面积例：A = [[0,1,1,1,0], [0,1,1,1,1], [1,1,1,1,0], [0,0,1,0,0]]输出：9（边长是3）设:f[i][j]是以A[i][j]为右下角的最大的全1正方形的边长 f[i][j] = 0 if A[i][j]...
2018-12-25 13:12:55
364
原创 dp基础之难点解析K Edit Distance
重要的是先说三遍：先看Edit Distance，先看Edit Distance，先看Edit Distance！本文是加强版K Edit Distance：给定N个字符串A，问哪些字符串和Target的最小编辑距离不大于K.编辑操作和上面一样：增加（插入）、删、替换例：输入：A = ["abc","abd","abcd","adc,"a"](为了简单，只考虑小写字母的字符串)Tar...
2018-12-23 21:14:15
550
原创 dp基础之难点解析K Sum
问题：给定数组A,包含n个互不相等的正整数，问有多少种方式从中找出K个数，使得和为arget例：A = [1,2,3,4].K = 2,Target = 5输出：2（1,4；2,3）问题分析：考虑最后一步A[n-1]是否选入这K个数 case1:A[n-1]不选入，则需要在前n-1个数里选K个数使得和为Target case2:A[n-1]选入，则需要在前n-1个数里选...
2018-12-20 13:38:24
377
原创 dp基础之难点解析Minimum Adjustment Cost
问题：给定数组A,每个元素是不超过100的正整数，将A中每个元素修改，使得变成数组B,要求是数组B中任意两个相邻元素之间的差不超过Target,求最小的修改代价,即|A[0]-B[0]|+...+|A[n-1]_B[n-1]|的最小值例：A = [1,4,2,3],Target = 1输出：2（B = [2,3,2,3]）问题分析：首先无论怎么修改，B中的元素肯定是在1和100之间，因...
2018-12-20 13:10:53
293
原创 dp基础之Ones and Zeroes
问题：给定t个01字符串S[0],...,S[t-1],现有m个0，n个1，问最多能组成多少个给定字符串，每个字符串最多组成一次。例：输入：S = ["10","0001","111001","1","0"],m = 5,n = 3输出：4（"10","0001","1","0"）跟背包问题有点类似，我们考虑最后一个字
2018-12-04 13:16:15
169
原创 dp基础之双序列型regular expression match && wildcad match
问题：给定两个字符A,B,B是一个正则表达式，里面可能含有"."、"*"，请问A是否和B匹配？（True/False）"."可以匹配前面的任何一个字符，"*"可以匹配前面的一个字符0、1、多次A = ["aa","aa","aaa","aa","aa","ab","aab"]B = [
2018-12-03 21:22:30
166
原创 dp基础之双序列型子串出现次数
问题：给定A[0,...,m-1],B[0,...,n-1],问B在A中出现几次（可以不连续）例：A = ['r','a','b','b','b','i','t']B = ['r','a','b','i','t']输出：3问题分析：可以用类似于最长公共子串的思路。问B在A中出现的次数，考虑最后一个字符B[n-1]和A[m-1] case1:如果B[n-1] = A[m-1],则...
2018-12-03 19:30:42
165
原创 dp之空间优化理解
有关之前空间优化用了滚动数组的方法（如果可以优化的话），其实最好空间的复杂度是min{O(m),O(n)}，本质上是矩阵计算时的变化情况，即按行计算还是按列计算的问题，空间优化的本质也在于此，只要弄清楚了计算过程的变化情况，一般情况下就解决空间优化的问题。...
2018-11-28 16:32:10
382
原创 dp基础之双序列型最短编辑距离Edit Distance
问题：给定连个字符串A、B,要求把A变成B,可以进行如下操作，问最少的操作次数可以使A变成B，即最小编辑距离?操作：增加（插入）、删、替换例：A = ['m','a','r','t'],B = ['k','a','r','m','a']输出：3（m换成k,t换成m,加上a）问题分析：设m = len(A),n = len(B),我们考虑最后，操作完成后，A的长度也变成n,A[n-1] ...
2018-11-28 16:25:50
277
原创 dp基础之双序列型交错形成字符串
问题：给定三个字符串A,B,X，判断X是否是由A,B的字符交错而形成（True/False）例：A = ['a','a','b','c','c'],B = ['d','b','b','a','c']X = ["a","a",'d',"b",'b',"c",'b',"c",'a','c']输出：True(双引号是A中的字符，单引号是B中的字符)问题分析：令m = len(A),n = le...
2018-11-27 11:38:48
143
原创 dp基础之双序列型最长公共子串
问题：给定两个字符串A,B，找到两个字符互传的公共最长子串的长度。子串：在原字符串上去去掉某些字符后形成的字符串，不改变字符之间的顺序例：A = ['j', 'i', 'u', 'z', 'h', 'a', 'n', 'g']B = ['l', 'i', 'j', 'i', 'a', 'n', 'g']输出：5（ ['j', 'i', 'a', 'n', 'g']）问题分析：确定状...
2018-11-25 22:23:44
292
原创 dp基础之区间型炸气球
问题：有N个气球A[1],...A[N],扎破第i个气球所得的金币A[left]*A[i]*A[right],扎破气球i后，气球left和right就变成相邻的气球，求获得最多的金币数，A[0] = A[N+1] = 1例：A = [3,1,5,8][3,5,8]-->[3,8]-->[8]-->[]金币数3*1*5+3*5*8+1*3*8+1*8*1 = 167问...
2018-11-25 01:57:32
283
原创 dp基础之区间型scramble string
问题：给定一个字符串S,按照树的结构每次二分左右两个部分，直至到单个字符，在树的某个节点交换左右儿子，可以形成新的字符串，判断一个字符串T是否经过这样的变换而成。例：S = 'grate',T = 'rgtae'S = ['g','r','a','t','e'] ,T = ['r','g','t','a','e']输出：True如下图示意 问题分析：首先：如果T和S长度不...
2018-11-24 21:27:43
872
原创 dp基础之博弈型和区间型结合轮流取数字
问题：给定一个序列A[0],..,A[N-1]，两个人轮流从序列两头取数字（每次只取一个），双方都用最优策略，使自己的取到的数字和尽量比对手大。问先手是否必胜？当和一样大时规定先手胜。(True/False)例：A = [1,5,233,7]输出：True(,先手取1，无论后手取哪个，先手都能取到233，即先手必胜)问题分析：这是一道博弈型dp,其实质上是区间型dp,目标是让自己拿到...
2018-11-24 17:07:08
775
原创 dp基础之区间型最长回文子串
区间型dp:一般是给定一个字符串或者序列，对其进行一些操作，最后一步将它去头或者去尾，剩下会是一个区间 [ i , j ],状态定义就是f[i][j],表示子序列[i,j]具有的最优性质。问题一：给定一个字符串序列，找出其最长的子回文串序列的长度。例:输入：S = ['b','b','b','a','b']输出：4（['b','b','b','b']）问题分析：最优策略的子序列是T,...
2018-11-23 23:39:28
560
原创 dp基础之背包问题小结
可行性背包问题：最多能装多少重量，需要记录前 i 个物品能不能拼出重量W（w=0...Target）,如dp基础之背包问题里的问题一,用f[i][w]表示前i个物品能不能拼出重量w,f[i][w] = True/False 计数型背包问题：有多少种方式拼出重量，如dp基础之背包问题里的问题二,f[i][w]表示前i种物品拼出重量w的方式数，如dp基础之背包问题里的问题三，有多少种方式拼出重...
2018-11-23 16:27:11
127
原创 dp基础之背包问题
问题一：有N个物品，重量为A[0]...A[N-1],有一个容量为M(M是一个正整数)。问：最多能带走多重的物品。例：A = [2,3,5,7] M = 10输出：10（2,3,5）问题分析：要求N个物品能否拼出重量W(W = 0,1...M)，需要知道前N-1个物品能否拼出重量W(W = 0,1...M)考虑最后一个物品(A[N-1]）放不放入进入背包 情况1：如...
2018-11-19 21:31:50
294
原创 dp基础之博弈型取石子
对于博弈型dp，一般是从复杂走向简单，故不从最后一步开始分析，反而从第一部开始分析问题：一排N个硬币，两人先后从最右边取一个或两个硬币，规定取走最后石子的人为胜。 问先手是否必胜（先手必胜：True；先手必败：False）例：N = 5输出：True,先手必胜，第一个人先取两个石子，无论后手怎么取，最终都是先手拿到最后的石子问题分析： 要求面对N个石子，是否先手必...
2018-11-19 17:38:41
307
原创 dp基础之划分型小结
问题：一般时要求将一个序列或字符串划分成若干段并且满足一定的要求分析：从最优策略的最后一步开始，枚举最后一段的起点。如果题目不指定段数，则直接用f[i]表示前i个元素分段后的性质/最值，个数：完全平方数或者方式数：回文问题。如果题目指定了段数，用f[i][j]表示前i个元素段分成j段的性质，方式数：抄写书本问题 ...
2018-11-19 17:28:51
337
原创 dp基础之划分型抄写书的最短时间
问题：有N本书需要抄写，每本书的页数分别为A[0]...A[N-1]，现有K个抄写员。每个抄写员可以连续抄写若干本书，每个抄写员的抄写速度一样一分钟一页，问最少需要多长时间抄写完所有的书。例：A = [3,2,4],K = 2最少时间为：5分析：若一个抄写员抄写A[i...j]，需要时间为A[i]+...+A[j] 最后抄写时间取决于耗时最长的那个抄写员问题变成，找到一种...
2018-11-18 13:47:41
271
原创 dp基础之划分型划分最小划分次数
问题：给定一个字符串S[0,..n-1],最少划分几次使得每个子串都是回文串确定状态：最优策略中最后一段回文串是S[j...n-1] 需要知道S前j个字符[0...j-1]最少可以划分成几个回文串子问题：设：S前i个字符[0...i-1]最少可以划分成f[i]个回文串 f[i] = min{f[j]+1 | S[j...i-1]是回文串} {S前...
2018-11-17 20:57:39
346
原创 dp基础之划分型划分最少完全平方数个数
问题：给定一个正整数n,问：最少可以将n分成几个完全平方数(1 4 9 16..)之和?例：输入：n = 1313 = 4+9输出：2分析：状态确定：最优策略中最后一步，假设n的最优划分的最后一个平方数是j，则需要知道n-j^2的最优划分转移方程：设：f[i]表示i的最优划分的个数 f[i] = min{f[i-j^2]+1}(0<=j*j<i)...
2018-11-15 20:47:22
425
原创 dp基础之序列型最长上升子序列
问题 ：给定a[i](i=0...n-1),找到最长上升子序列(假设长度为k)，输出k例：a = [4,2,4,5,3,7]返回k=4（[2,4,5,7]）分析：对于最优策略：一定有最后一个元素a[j]情况1：最优策略就是{a[j]},长度k就是1情况2：最优策略子序列长度大于1，则最优策略中最后一个元素a[j]前一定有一个元素a[i],且a[i]<a[j](i&l...
2018-11-15 19:04:16
187
原创 dp基础之序列型Stock
问题：已知后N天 的股票价格为p[0],p[1]..p[N-1](N>=2)要求：可以最多买一股卖一股，求最大获利分析： 枚举第j天卖（0<j<=N-1） 保存j天之前第i天卖的最小值（i<j） 返回最大的利润（j-i）代码及注释如下：def get_proft(p): n = len(p) #初始化 ...
2018-11-13 20:41:24
170
原创 dp基础之序列型House Robber
问题：有一排房子N栋，房子i 里有金币 house[i]，现有小偷想选择而一些房子偷金币，为了防止被抓，不能偷相邻两栋房子，问最多能偷多少钱？分析;在最优策略中，偷或不偷房子N-1 1不偷，则最优策略就是前N-1栋房子的最优策略 2偷，需要知道前N-1栋房子的最优策略且房子N-2不能偷。子问题：我们用f[i][0]表示在不偷房子i-1的情况下，前i-1栋房子的最优策略（...
2018-11-13 19:04:41
237
原创 序列型dp和坐标型dp小结
一、序列型dp状态转移方程中f[i]表示前i个元素a[0],a[1],...a[i-1]的某种性质,坐标型dp状态转移方程中f[i]表示以元素a[i]结尾的某种性质。二、在初始化时，序列型dp中f[0]一般表示的是空序列一般是f[0] = 0,坐标型dp中f[0]表示以a[0]结尾的子问题具有的性质，得看具体条件 , ...
2018-11-13 16:08:06
600
原创 dp基础之位移问题
问题：求从0到N（包括N）的二进制表示里有多少个1，结果以数组返回?动态规划解决，分析：要求N的二进制里有多少个1，可以先求N去掉最后一位(N mod 2)后Y（Y = X>>1）里有多少个1子问题：f[i]表示数字i的二进制里有多少个1f[i] = f[i>>1] + i mod 2数字i的二进制里有多少个1 = i去掉最后一位里的二进制有多少个1 + i的最后...
2018-11-13 15:57:05
194
原创 dp基础之划分型数字解密
#问题：有一段A-Z组成字母信息串被加密数字串，加密方式A-1,B-2...给定加密后的数字串有多少种解密方式？代码及注释如下：def get_case(s): #f[i]表示前i个数字可以解密成的种数 n = len(s) if n==0: return 0 f = [0 for x in range(n+1)] #初始 ...
2018-11-08 16:16:05
270
原创 python列表反转
#python列表反转A = [5,1,6,3,4]#切片A0 = A[::-1]#内建函数sorted()#sorted(iterable[, cmp[, key[, reverse]]])A1 = sorted(a,reverse=True)#内建函数reversed，reversed返回的是迭代器，故需用list转换A2 = list(reversed(A))...
2018-11-08 16:11:19
2189
原创 dp基础坐标型问题之最长单调子序列
问题：最长连续上升子序列长度，或者说最长连续单调子序列 代码及注释如下：def get_length(A): #f[i]表示以A[i]结尾的最长上升子序列的长度 n = len(A) #最终结果 res = 0 if n==0: return 0 f = [0 for x in range(n)] for i ...
2018-11-08 16:08:40
177
原创 dp基础之序列型油漆房子
问题：有一排N栋房子，每栋房子要油漆成红、蓝、绿三种颜色，第i栋房子油漆成红、蓝、绿的花费分别为cost[i][0]、cost[i][1]、cost[i][2]要求：相邻的房子颜色需不同求油漆好房子的最小花费代码及注释如下：def Pint_huose(cost): #N是房子的个数，K是油漆的颜色种数 N,K = len(cost),len(cost[0])...
2018-11-07 20:52:46
284
原创 python采坑之路1
在list中有如下：列表生成式和*x = [[0]*n]*my = [[0 for x in range(n)] for y in range(m)]x[0][0] = 1y[0][0] = 1print(x)print(y)结果：[[1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]][[1, 0, 0, 0], [0, 0, ...
2018-11-07 19:11:28
183
原创 dp基础之存在性dp问题
问题：在x轴上，从0到n-1，对应一个一维数组A，要求，每次在位置i只向右跳最多A[i]的长度，问最终能不能到达位置n-1?代码及注释如下：#!/usr/bin/pythondef get_case(A): n = len(A) #创建一个列表 #f[i]表示能不能跳到位置i,1表示能，0表示不能 #先假设全部都跳不到 f = [0]*n #f[0]表示初始情况 f[0]...
2018-11-06 20:05:34
394
原创 dp基础之网格问题
问题1：在一个m*n的网格里，从左上到右下一共有多少种路径，要求，只能向右或向下走？（m,n>0）代码及注释如下：#!/usr/bin/pythondef get_case(m,n): #m,n分别为网格的行列数 #创建一个列表 #f[i][j]表示从左上开始到第i行第j列的点的路径数 f = [[0 for x in range(n)] for y in range(m...
2018-11-06 19:15:53
396
原创 dp基础之计数型硬币问题
解决DP问题的四大步骤：1.确定状态：研究最优策略的最后一步，转化为子问题 ，重点2.转移方程：根据子问题定义直接得到转移方程，难点3.初始条件和边界情况：注意点4.计算顺序：最好能利用之前计算好的结果，省得重复计算，技巧点问题：现有2,5,7三种硬币足够数量，要拼凑成m元钱，求使用最少硬币数。代买及注释如下：import sysdef get_num(coins,...
2018-11-06 18:37:25
507
原创 numpy(一)
1.基础Numpy库里最重要的数组对象，叫做narray,是一个通用的同构数据多维容器，和C语言里的多维数组类似。这个narray容器里所有类型即dtype必须保持一致，可以有int32,float64等，每一个narray容器都有一个shape(表示narray的维度)。另外还有许多关于narray的内置函数，在下面代码里意义进行解释说明。#!/usr/bin/pythonimpor...
2018-08-27 22:15:39
216
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人