首先：你要知道，你的‘适应度函数’，作为一个好久没科研的人，看到这个一脸的懵逼，没听说过啊。看了半天，我理解了。就是一个函数求极值的问题。譬如，你有一个函数让你去找最值问题，那么f(x,y)和g(x,y,z) 就是‘适应度函数’；然后你需要找的x、y、z就是蝙蝠的位置xi的分量。这就理解了xi的‘维度’问题。2维=(x,y)；3维=(x,y,z)；4维=(x,y,z,k)；换个马甲，xi的‘维度’问题。2维=(xi-1, xi-2)；3维=( xi-1, xi-2, xi-3)；4维=( xi-1, xi-2, xi-3, xi-4)；那么，由n只蝙蝠，i=1~n;好吧，数学不好，一起撂倒！理解了上面再去看论文或者其它就好了；上面的图片里面的内容来源于论文《光电防御系统作战效能评估方法研究》：d搜索维空间——就是我的‘适应度函数’里面由d个未知数；n只蝙蝠（可能解）——就是x=/y=/z=，由n种组合；每个解，就是一个确切值；整体翻译成RH就是：我的函数由d个未知数，我尝试了n种组合从则n种组合种找到了最大或最小的那个，就是最优解；代码流程图：具体算法：clear
clc
tic
%% 20220716-以下内容我整体给注释掉了，原因是这是xx之前的程序，我这边没有数据
% 我这边将使用鸢尾花数据集代替掉，先抛弃了；
%{
load
data
load label
%% 划分数据
% 1. 随机产生训练集和测试集
n = randperm(size(data,1));
%n随机序列 106个样本，生成106个106个随机数
% 2. 训练集——80个样本
train_matrix = data(n(1:150),:);
%前80个随机数据做训练集
train_label = label(n(1:150),:);
% 3. 测试集——26个样本
test_matrix = data(n(151:end),:);
%后26个做测试集
test_label = label(n(151:end),:);
%% 数据归一化
[train_matrix,PS] = mapminmax(train_matrix');
train_matrix = train_matrix'; %保证训练集数据始终是样本数为行数，变量数为列数
test_matrix = mapminmax('apply',test_matrix',PS); %apply是指对test用和train同样的方式进行规范化
test_matrix = test_matrix';
%}
%% 以下是鸢尾花数据集的代替，数据的导入
% 鸢尾花数据集有3种，每种
load fisheriris
inds = ~strcmp(species,'setosa');
data = meas(inds,2:4); % 训训练特征的个数（2:4）表示3个，
% 这里如果使用libsvmtrain程序报错，label vector and instance matrix must be
% double；然后我搜索了下，说cell不行，需要改为double; 为了简便，直接赋值了；
label=ones(100,1);
label(51:100,:)=2;
n = randperm(size(data,1));
% 2. 训练集——80个样本
train_matrix = data(n(1:80),:);
%前80个随机数据做训练集
train_label = label(n(1:80),:);
% 3. 测试集——26个样本
test_matrix = data(n(81:end),:);
%后20个做测试集
test_label = label(n(81:end),:);
%% 数据归一化
[train_matrix,PS] = mapminmax(train_matrix');
train_matrix = train_matrix'; %保证训练集数据始终是样本数为行数，变量数为列数
test_matrix = mapminmax('apply',test_matrix',PS); % apply是指对test用和train同样的方式进行规范化(这是关键)
test_matrix = test_matrix';
%% BA参数设置
t = 1;
%用于迭代使用的
maxT = 100; %最大迭代次数
dim = 2; % 问题的维度，或者叫做蝙蝠位置的坐标；可以是多维的；
% jhc-我是根据下面的推测的，就是我需要找2个参数的最优解，所以我这里是dim=2
sizep = 50; % 种群大小，蝙蝠有几只
xmin = [1,1]; % 限制在那个地方寻找，不要跑偏了
xmax = [100,100]; %位置向量的范围
v = 5; % 这是svm的参数
A = 0.6.*ones(sizep,1);
% 响度 (不变或者减小)，在110附近会更新；问题是，一直不变？
r = zeros(sizep,1);
% 脉冲率 (不变或增加))
r0 = 0.7; % [0,1]之间的随机数都可以；
alpha_for_A = 0.9; % 论文《新型元启发式蝙蝠算法》里面说，是定值，但是需调试；
gamma_for_R = 0.9;
frequency_min = 0;
% 最小频率
frequency_max = 1;
% 最大频率
%% 初始化，并求解第一次的最优值
Lb = xmin.*ones(1,dim); % .* 代表按元素乘法
Ub = xmax.*ones(1,dim);
pop = Lb+(Ub-Lb).*rand(sizep,dim); %种群位置初始化，在范围内产生随机值；
popv = zeros(sizep,dim);
% 速度
frequency = zeros(sizep,1);
% 频率
for i = 1:sizep
cmd = ['-v ',num2str(v),' -c ',num2str( pop(i,1)),' -g ',num2str( pop(i,2))];
fitness(i) = libsvmtrain(train_label,train_matrix,cmd);
pfitness(i) = -fitness(i);
end
[bestMin, bestID]=min(pfitness);
bestS = pop(bestID, :); % 蝙蝠的最优位置，此时可以得到最小值；
bestArchive = zeros(maxT,1); %对应程序第123行出，每个t 时刻，存储一下当前 t 这个时段最小值；
%% 具体迭代过程
while t <= maxT
for i = 1:sizep
frequency(i)=frequency_min+(frequency_max-frequency_min)*rand(); %更新频率
popv(i,:)=popv(i,:)+(pop(i,:)-bestS)*frequency(i); % 更新篇幅的速度
Stemp = pop(i,:)+popv(i,:);
% 提醒：pop(i,:)——当前蝙蝠位置的值；就是要搜索的；
% 调试的时候看了下，stemp是一个1x1的矩阵；
% 看了BA的流程图，stemp在这里的一个位置中间量；
% 之后产生一个随机的新位置；Stemp=bestS+rand(1)*A(i)
% 如果Stemp=bestS+rand(1)*A(i)产生的结果好，则替换掉当前的位置的值；
% 如果Stemp=bestS+rand(1)*A(i)，则保留当前的位置的值；
% 脉冲率
if rand>r(i) % rand-产生一个随机数,看这个随机数与 ri-脉冲发射速率之间的关系；
Stemp=bestS-1+2*rand(1,dim); % 新位置由当前最佳扰动产生，这里是产生[-1,1]的随机数
% Stemp=bestS+rand(1)*A(i); % 新位置由当前最佳扰动产生；这里是产生[0,1]的随机数
end
cmd = ['-v ',num2str(v),' -c ',num2str( Stemp(1) ),' -g ',num2str( Stemp(2) )];
fitness = libsvmtrain(train_label,train_matrix,cmd);
fitTemp = -fitness;
if (fitTemp<=pfitness(i)) && (rand()<A(i))
pop(i,:) = Stemp; % 满足条件则更新，对应95行的；
pfitness(i) = fitTemp;
A(i) = alpha_for_A*A(i);
r(i) = r0*(1-exp(-gamma_for_R*t));
end
% 下面这个判断的意思是，如果我现在这个位置找到的值比最小的还要小，就说明是好的；
% 我这边更新最小值，同时更新最小值所对应的蝙蝠的位置；
% 提醒：stemp是蝙蝠的位置；
if fitTemp <= bestMin
bestMin = fitTemp;
bestS = Stemp;
end
end
bestArchive(t) = bestMin; % 存储一下当前 t 这个时段最小值；
t = t +1;
end
% 这里对应程序119行，bestS是蝙蝠最优位置，在每次迭代 时刻t 都会更新为最优的；
bestc = bestS(1);
bestg = bestS(2); %取出最优c,g核参数
cmd = [' -v ',num2str(v), ' -c ',num2str(bestc),
' -g ',num2str(bestg)];
model = libsvmtrain(train_label,train_matrix,cmd);
[predict_label,accuracy,prob_estimates] = libsvmpredict(test_label,test_matrix,model);
toc
参考论文：《新型元启发式蝙蝠算法》黎成《光电防御系统作战效能评估方法研究》李卉

作者：旅途~链接：https://www.nowcoder.com/discuss/150061来源：牛客网从暴力尝试到动态规划动态规划不是玄学，也无需去记那些所谓的刻板的“公式”（例如状态转换表达式等），其实动态规划是从暴力递归而来。并不是说一个可以动态规划的题一上来就可以写出动态规划的求解步骤，我们只需要能够写出暴力递归版本，然后对重复计算的子过程结果做一个缓存，最后分析状态依赖寻求最优解，即衍生成了动态规划。本节将以多个例题示例，展示求解过程是如何从暴力尝试，一步步到动态规划的。换钱的方法数题目：给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求换钱有多少种方法。举例：arr=[5,10,25,1]，aim=0：成0元的方法有1种，就是所有面值的货币都不用。所以返回1。arr=[5,10,25,1]，aim=15：组成15元的方法有6种，分别为3张5元、1张10元+1张5元、1张10元+5张1元、10张1元+1张5元、2张5元+5张1元和15张1元。所以返回6。arr=[3,5]，aim=2：任何方法都无法组成2元。所以返回0。暴力尝试我们可以将该题要求解的问题定义成一个过程：对于下标index，arr中在index及其之后的所有面值不限张数任意组合，该过程最终返回所有有效的组合方案。因此该过程可以描述为int process(int arr[],int index,int aim)，题目的解就是调用process(arr,0,aim)。那么函数内部具体该如何解决此问题呢？其实所有面值不限张数的任意组合就是对每一个面值需要多少张的一个决策，那我们不妨从碰到的第一个面值开始决策，比如arr=[5,10,25,1]，aim=15时，（ 选0张5元之后剩下的面值不限张数组合成15元的方法数 + 选1张5元之后剩下的面值不限张数组合成10元方法数 + 选2张5元之后剩下的面值不限张数组合成5元方法数 + 选3张5元之后剩下的面值不限张数组合成0元方法数 ）就是所给参数对应的解，其中“剩下的面值不限张数组合成一定的钱数”又是同类问题，可以使用相同的过程求解，因此有了如下的暴力递归：/**
* arr中的每个元素代表一个货币面值，使用数组index及其之后的面值（不限张数）
* 拼凑成钱数为aim的方法有多少种，返回种数
* @param arr
* @param index
* @param aim
* @return */
public static int process(int arr[], int index, int aim) {
if (index == arr.length) {
return aim == 0 ? 1 : 0;
}
int res = 0;
//index位置面值的决策，从0张开始
for (int zhangshu = 0; arr[index] * zhangshu <= aim; zhangshu++) {
res += process(arr, index + 1, aim - (arr[index] * zhangshu));
}
return res;
}
public static int swapMoneyMethods(int arr[], int aim) {
if (arr == null) {
return 0;
}
return process(arr, 0, aim);
}
public static void main(String[] args) {
int arr[] = {5, 10, 25, 1};
System.out.println(swapMoneyMethods(arr, 15));
}缓存每个状态的结果，以免重复计算上述的暴力递归是极其暴力的，比如对于参数arr=[5，3，1，30，15，20，10]，aim=100来说，如果已经决策了3张5元+0张3元+0张1元的接着会调子过程process(arr, 3, 85)；如果已经决策了0张5元+5张3元+0张1元接着也会调子过程process(arr, 3, 85)；如果已经决策了0张5元+0张3元+15张1元接着还是会调子过程process(arr, 3, 85)。你会发现，这个已知面额种类和要凑的钱数，求凑钱的方法的解是固定的。也就是说不管之前的决策是3张5元的，还是5张3元的，又或是15张1元的，对后续子过程的[30，15，20，10]凑成85这个问题的解是不影响的，这个解该是多少还是多少。这也是无后效性问题。无后效性问题就是某一状态的求解不依赖其他状态，比如著名的N皇后问题就是有后效性问题。因此，我们不妨再求解一个状态之后，将该状态对应的解做个缓存，在后续的状态求解时先到缓存中找是否有该状态的解，有则直接使用，没有再求解并放入缓存，这样就不会有重复计算的情况了：public static int swapMoneyMethods(int arr[], int aim) {
if (arr == null) {
return 0;
}
return process2(arr, 0, aim);
}
/**
* 使用哈希表左缓存容器
* key是某个状态的代号，value是该状态对应的解
*/
static HashMap map = new HashMap();
public static int process2(int arr[], int index, int aim) {
if (index == arr.length) {
return aim == 0 ? 1 : 0;
}
int res = 0;
for (int zhangshu = 0; arr[index] * zhangshu <= aim; zhangshu++) {
//使用index及其之后的面值拼凑成aim的方法数这个状态的代号：index_aim
String key = String.valueOf(index) + "_" + String.valueOf(aim);
if (map.containsKey(key)) {
res += map.get(key);
} else {
int value = process(arr, index + 1, aim - (arr[index] * zhangshu));
key = String.valueOf(index + 1) + "_" + String.valueOf(aim - (arr[index] * zhangshu));
map.put(key, value);
res += value;
}
}
return res;
}
public static void main(String[] args) {
int arr[] = {5, 10, 25, 1};
System.out.println(swapMoneyMethods(arr, 15));
}确定依赖关系，寻找最优解当然，借助缓存已经将暴力递归的时间复杂度拉低了很多，但这还不是最优解。下面我们将以寻求最优解为引导，挖掘出动态规划中的状态转换。从暴力尝试到动态规划，我们只需观察暴力尝试版本的代码，甚至可以忘却题目，按照下面高度套路化的步骤，就可以轻易改出动态规划：1. 首先每个状态都有两个参数index和aim（arr作为输入参数是不变的），因此可以对应两个变量的变化范围建立一张二维表：2. 从base case中找出特殊位置的解。比如if(index==arr.length) return aim==0?1:0，那么上述二维表的最后一行对应的所有状态可以直接求解：3. 从暴力递归中找出普遍位置对应的状态所依赖的其他状态。比如：for (int zhangshu = 0; arr[index] * zhangshu <= aim; zhangshu++) {
res += process(arr, index + 1, aim - (arr[index] * zhangshu));
}那么对于二维表中的一个普遍位置(i,j)，它所依赖的状态如下所示：也就是说一个普遍位置的状态依赖它的下一行的几个位置上的状态。那么我们已经知道了最后一行所有位置上的状态，当然可以根据这个依赖关系推出倒数第二行的，继而推出倒数第三行的……整个二维表的所有位置上的状态都能推出来。4. 找出主问题对应二维表的哪个状态（(0,maxAim)），那个状态的值就是问题的解。示例代码：public static int maxMethodsDp(int arr[], int aim) {
//二维表
int dp[][] = new int[arr.length + 1][aim + 1];
//base case
dp[arr.length][0] = 1;
//从倒数第二行开始推，推出整个二维表每个位置的状态
for (int i = arr.length - 1; i >= 0; i--) {
for (int j = 0; j <= aim; j++) {
//i对应的面值取0张
dp[i][j] = dp[i + 1][j];
//i对应的面值取1张、2张、3张……
for (int subAim = j - arr[i]; subAim >= 0; subAim = subAim - arr[i]) {
dp[i][j] += dp[i + 1][subAim];
}
}
}
return dp[0][aim];
}
public static void main(String[] args) {
int arr[] = {5, 10, 25, 1};
System.out.println(maxMethodsDp(arr, 15));
}到这里也许你会送一口气，终于找到了最优解，其实不然，因为如果你再分析一下每个状态的求解过程，仍然存在瑕疵：比如你在求解状态A时，可能会将其依赖的状态M,N,P的值累加起来；然后在求解状态B时，有需要将其依赖的状态M,N,P,Q累加起来，你会发现在这个过程中M+N+P的计算是重复的，因此还可以有如下优化：for (int i = arr.length - 1; i >= 0; i--) {
for (int j = 0; j <= aim; j++) {
dp[i][j] = dp[i + 1][j];
if (j - arr[i] >= 0) {
dp[i][j] += dp[i][j - arr[i]];
}
}
}至此，此题最优解的求解完毕。排成一条线的纸牌博弈问题题目：给定一个整型数组arr，代表分数不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。举例：arr=[1,2,100,4]。开始时玩家A只能拿走1或4。如果玩家A拿走1，则排列变为[2,100,4]，接下来玩家B可以拿走2或4，然后继续轮到玩家A。如果开始时玩家A拿走4，则排列变为[1,2,100]，接下来玩家B可以拿走1或100，然后继续轮到玩家A。玩家A作为绝顶聪明的人不会先拿4，因为拿4之后，玩家B将拿走100。所以玩家A会先拿1，让排列变为[2,100,4]，接下来玩家B不管怎么选，100都会被玩家A拿走。玩家A会获胜，分数为101。所以返回101。arr=[1,100,2]。开始时玩家A不管拿1还是2，玩家B作为绝顶聪明的人，都会把100拿走。玩家B会获胜，分数为100。所以返回100。动态规划的题难就难在暴力尝试这个“试”法，只要能够试出了暴力版本，那改为动态规划就是高度套路的。暴力尝试public static int maxScoreOfWinner(int arr[]) {
if (arr == null) {
return 0;
}
return Math.max(
f(arr, 0, arr.length-1),
s(arr, 0, arr.length-1));
}
public static int f(int arr[], int beginIndex, int endIndex) {
if (beginIndex == endIndex) {
return arr[beginIndex];
}
return Math.max(
arr[beginIndex] + s(arr, beginIndex + 1, endIndex),
arr[endIndex] + s(arr, beginIndex, endIndex - 1));
}
public static int s(int arr[], int beginIndex, int endIndex) {
if (beginIndex == endIndex) {
return 0;
}
return Math.min(
f(arr, beginIndex + 1, endIndex),
f(arr, beginIndex, endIndex - 1));
}
public static void main(String[] args) {
int arr[] = {1, 2, 100, 4};
System.out.println(maxScoreOfWinner(arr));//101
}这个题的试法其实很不容易，笔者直接看别人写出的暴力尝试版本表示根本看不懂，最后还是搜了博文才弄懂。其中f()和s()就是整个尝试中的思路，与以往穷举法的暴力递归不同，这里是两个函数相互递归调用。f(int arr[],int begin,int end)表示如果纸牌只剩下标在begin~end之间的几个了，那么作为先拿者，纸牌被拿完后，先拿者能达到的最大分数；而s(int arr[],int begin,int end)表示如果纸牌只剩下标在begin~end之间的几个了，那么作为后拿者，纸牌被拿完后，后拿者能达到的最大分数。在f()中，如果只有一张纸牌，那么该纸牌分数就是先拿者能达到的最大分数，直接返回，无需决策。否则先拿者A的第一次决策只有两种情况：先拿最左边的arr[beginIndex]，那么在A拿完这一张之后就会作为后拿者参与到剩下的(begin+1)~end之间的纸牌的决策了，这一过程可以交给s()来做。先拿最右边的arr[endIndex]，那么在A拿完这一张之后就会作为后拿者参与到剩下的begin~(end-1)之间的纸牌的决策了，这一过程可以交给s()来做。最后返回两种情况中，结果较大的那种。在s()中，如果只有一张纸牌，那么作为后拿者没有纸牌可拿，分数为0，直接返回。否则以假设的方式巧妙的将问题递归了下去：假设先拿者A拿到了arr[beginIndex]，那么去掉该纸牌后，对于剩下的(begin+1)~end之间的纸牌，后拿者B就转变身份成了先拿者，这一过程可以交给f()来处理。假设先拿者A拿到了arr[endIndex]，那么去掉该纸牌后，对于剩下的begin~(end-1)之间的纸牌，后拿者B就转变身份成了先拿者，这一过程可以交给f()来处理。这里取两种情况中结果较小的一种，是因为这两种情况是我们假设的，但先拿者A绝顶聪明，他的选择肯定会让后拿者尽可能拿到更小的分数。比如arr=[1,2,100,4]，虽然我们的假设有先拿者拿1和拿4两种情况，对应f(arr,1,3)和f(arr,0,2)，但实际上先拿者不会让后拿者拿到100，因此取两种情况中结果较小的一种。改动态规划这里是两个函数相互递归，每个函数的参数列表又都是beginIndex和endIndex是可变的，因此需要两张二维表保存(begin,end)确定时，f()和s()的状态值。1. 确定base case对应的特殊位置上的状态值：可以发现两张表的对角线位置上的状态值都是可以确定的，begin<=end，因此对角线左下方的区域不用管。2. 由递归调用逻辑找出状态依赖。f()依赖的状态：return Math.max(
arr[beginIndex] + s(arr, beginIndex + 1, endIndex),
arr[endIndex] + s(arr, beginIndex, endIndex - 1));F表的(begin,end)依赖S表(begin+1,end)和(begin,end-1)。s()依赖的状态：return Math.min(
f(arr, beginIndex + 1, endIndex),
f(arr, beginIndex, endIndex - 1));S表的(begin,end)依赖F表的(begin+1,end)和(begin,end-1)。如此的话，对于对角线的右上区域，对角线位置上的状态能推出倒数第二长对角线位置上的状态，进而推出倒数第三长位置上的状态……右上区域每个位置的状态都能推出。3. 确定主问题对应的状态：return Math.max(
f(arr, 0, arr.length-1),
s(arr, 0, arr.length-1));示例代码：public static int maxScoreOfWinnerDp(int arr[]) {
if (arr == null
arr.length == 0) {
return 0;
}
int F[][] = new int[arr.length][arr.length];
int S[][] = new int[arr.length][arr.length];
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
if (i == j) {
F[i][i] = arr[i];
}
}
}
//依次推出每条对角线，一共n-1条
for (int i = 1; i < arr.length; i++) {
for (int row = 0; row < arr.length - i; row++) {
int col = row + i;
F[row][col] = Math.max(arr[row] + S[row + 1][col], arr[col] + S[row][col - 1]);
S[row][col] = Math.min(F[row + 1][col], F[row][col - 1]);
}
}
return Math.max(F[0][arr.length - 1], S[0][arr.length - 1]);
}
public static void main(String[] args) {
int arr[] = {1, 2, 100, 4};
System.out.println(maxScoreOfWinnerDp(arr));
}代码优化：if (arr == null
arr.length == 0) {
return 0;
}
int[][] f = new int[arr.length][arr.length];
int[][] s = new int[arr.length][arr.length];
for (int j = 0; j < arr.length; j++) {
f[j][j] = arr[j];
for (int i = j - 1; i >= 0; i--) {
f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
}
}
return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);机器人走路问题给你标号为1、2、3、……、N的N个位置，机器人初始停在M位置上，走P步后停在K位置上的走法有多少种。注：机器人在1位置上时只能向右走，在N位置上时只能向左走，其它位置既可向右又可向左。public static int process(int N, int M, int P, int K) {
if (P == 0) {
return M == K ? 1 : 0;
}
if (M == 1) {
return process(N, M + 1, P - 1, K);
} else if (M == N) {
return process(N, M - 1, P - 1, K);
}
return process(N, M + 1, P - 1, K) + process(N, M - 1, P - 1, K);
}
public static void main(String[] args) {
System.out.println(process(5, 2, 3, 3));
}这里暴力递归参数列表的可变变量有M和P，根据base case和其它特殊情况画出二维表：动态规划示例代码：public static int robotWalkWaysDp(int N, int M, int P, int K) {
int dp[][] = new int[N + 1][P + 1];
dp[K][0] = 1;
for (int j = 1; j <= P; j++) {
for (int i = 1; i <= N; i++) {
if (i - 1 < 1) {
dp[i][j] = dp[i + 1][j - 1];
} else if (i + 1 > N) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = dp[i + 1][j - 1] + dp[i - 1][j - 1];
}
}
}
return dp[M][P];
}
public static void main(String[] args) {
System.out.println(robotWalkWaysDp(5, 2, 3, 3));
}字符串正则匹配问题给定字符串str，其中绝对不含有字符'.'和'*'。再给定字符串exp，其中可以含有'.'或'*'，'*'字符不能是exp的首字符，并且任意两个'*'字符不相邻。exp中的'.'代表任何一个字符，exp中的'*'表示'*'的前一个字符可以有0个或者多个。请写一个函数，判断str是否能被exp匹配。举例：str="abc"，exp="abc"，返回true。str="abc"，exp="a.c"，exp中单个'.'可以代表任意字符，所以返回true。str="abcd"，exp=".*"。exp中'*'的前一个字符是'.'，所以可表示任意数量的'.'字符，当exp是"...."时与"abcd"匹配，返回true。str=""，exp="..*"。exp中'*'的前一个字符是'.'，可表示任意数量的'.'字符，但是".*"之前还有一个'.'字符，该字符不受'*'的影响，所以str起码有一个字符才能被exp匹配。所以返回false。暴力尝试定义一个方法bool match(char[] str, int i, char[] exp, int j)，表示str的下标i ~ str.length部分能否和exp的下标j ~ exp.length部分匹配，分情况讨论如下：1. 如果j到了exp.length而i还没到str.length，返回false，否则返回true2. 如果i和j都没到右边界，并且j的后一个字符不是*或者越界，那么只有当str[i]=exp[j]或exp[j]='.'时，i和j才同时右移继续比较match(str, i+1, exp, j+1)，否则返回false3. 如果i和j都没到右边界，并且j后一个字符是*，这时右有两种情况：1.str[i] = exp[j]或exp[j]='.'。比如a*可以匹配空串也可以匹配一个a，如果str[i]之后还有连续的相同字符，那么a*还可以匹配多个，不管是哪种情况，将匹配后右移的i和j交给子过程match2.str[i] != exp[j]且exp[j] != ‘.’，那么exp[j]*只能选择匹配空串。4. 如果i到了str.length而j还没到exp.length，那么j之后的字符只能是a*b*c*.*的形式，也就是一个字符后必须跟一个*的形式，这个检验过程同样可以交给match来做示例代码：public static boolean match(char[] s, int i, char[] e, int j) {
if (j == e.length) {
return i == s.length;
}
//j下一个越界或者j下一个不是*
if (j + 1 == e.length
e[j + 1] != '*') {
if (i != s.length && s[i] == e[j]
e[j] == '.') {
return match(s, i + 1, e, j + 1);
}
return false;
}
//j下一个不越界并且j下一个是*
while (i != s.length && s[i] == e[j]
e[j] == '.') {
if (match(s, i, e, j + 2)) {
return true;
}
i++;
}
//如果上面的while是因为 s[i]!=e[j] 而停止的
return match(s, i, e, j + 2);
}
public static boolean isMatch(String str, String exp) {
if (str == null
exp == null) {
return false;
}
char[] s = str.toCharArray();
char[] e = exp.toCharArray();
return match(s, 0, e, 0);
}
public static void main(String[] args) {
System.out.println(isMatch("abbbbc","a.*b*c"));//T
System.out.println(isMatch("abbbbc","a.*bbc"));//T
System.out.println(isMatch("abbbbc","a.bbc"));//F
System.out.println(isMatch("abbbbc","a.bbbc"));//T
}动态规划match的参数列表中只有i和j是变化的，也就是说只要确定了i和j就能对应确定一个match的状态，画出二维表并将base case对应位置状态值标注出来：再看普遍位置(i,j)的依赖，第6行的if表明(i,j)可能依赖(i+1, j+1)，第13行的while表明(i,j)可能依赖(i, j+2)、(i+1, j+2)、(i+2, j+2)、……、(s.length-1, j+2)：你会发现(i,j)依赖它下面一行和右边相邻两列的状态，也就是说要想推出普遍位置的状态值，起码需要最后一行、最后一列和倒数第二列上的状态值。而base case仅为我们提供了最后一列的状态值，主过程match(e, 0, s, 0)对应(0,0)位置的状态值，我们需要推出整张表所有位置的状态值才行。这时就要回归题意了，看倒数第二列和最后一行上的状态有什么特殊含义。首先最后一行表示i到了str.length，此时如果j还没走完exp的话，从j开始到末尾的字符必须满足字符*字符*字符*的范式才返回true。因此最后一行状态值易求：而对于倒数第二列，表示j来到了exp的末尾字符，此时如果i如果在str末尾字符之前，那么也是直接返回false的：那么接下来就只剩下(str.length-1, exp.length-1)这个位置的状态值了，该位置标明i来到了str的末尾字符，j来到了exp的末尾字符，只有当这两个字符相等或exp的末尾字符为.才返回true否则false，也就是说该状态可以直接通过输入参数str和exp计算，它不依赖其他状态。二维表的初始化至此全部完成。示例代码：public static boolean isMatch(String str, String exp) {
if (str == null
exp == null) {
return false;
}
return matchDp(str, exp);
}
public static boolean matchDp(String str, String exp) {
if (str == null
exp == null) {
return false;
}
char s[] = str.toCharArray();
char e[] = exp.toCharArray();
boolean[][] dpMap = initDpMap(s, e);
//从倒数第二行开始推，每一行从右向左推
for (int i = s.length - 1; i > -1; i--) {
for (int j = e.length - 2; j > -1; j--) {
if (e[j + 1] != '*') {
dpMap[i][j] = (s[i] == e[j]
e[j] == '.') && dpMap[i + 1][j + 1];
} else {
int tmp = i;
while (tmp != s.length && (s[tmp] == e[j]
e[j] == '.')) {
if (dpMap[tmp][j + 2]) {
dpMap[i][j] = true;
break;
}
tmp++;
}
if (dpMap[i][j] != true) {
dpMap[i][j] = dpMap[i][j + 2];
}
}
}
}
return dpMap[0][0];
}
public static boolean[][] initDpMap(char[] s, char[] e) {
boolean[][] dpMap = new boolean[s.length + 1][e.length + 1];
//last column
dpMap[s.length][e.length] = true;
//last row -> i=s.length-1
for (int j = e.length - 2; j >= 0; j = j - 2) {
if (e[j] != '*' && e[j + 1] == '*') {
dpMap[s.length - 1][j] = true;
} else {
break;
}
}
//(str.length-1, e.length-1)
if (s[s.length - 1] == e[e.length - 1]
e[e.length - 1] == '.') {
dpMap[s.length - 1][e.length - 1] = true;
}
return dpMap;
}缓存结构的设计设计可以变更的缓存结构（LRU）设计一种缓存结构，该结构在构造时确定大小，假设大小为K，并有两个功能：set(key,value)：将记录(key,value)插入该结构。get(key)：返回key对应的value值。【要求】set和get方法的时间复杂度为O(1)。某个key的set或get操作一旦发生，认为这个key的记录成了最经常使用的。当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。【举例】假设缓存结构的实例是cache，大小为3，并依次发生如下行为：1. cache.set("A",1)。最经常使用的记录为("A",1)。 2. cache.set("B",2)。最经常使用的记录为("B",2)，("A",1)变为最不经常的。 3. cache.set("C",3)。最经常使用的记录为("C",2)，("A",1)还是最不经常的。 4. cache.get("A")。最经常使用的记录为("A",1)，("B",2)变为最不经常的。 5. cache.set("D",4)。大小超过了3，所以移除此时最不经常使用的记录("B",2)，加入记录 ("D",4)，并且为最经常使用的记录，然后("C",2)变为最不经常使用的记录设计思路：使用一个哈希表和双向链表示例代码：package top.zhenganwen.structure;
import java.util.HashMap;
public class LRU {
public static class Node{
K key;
V value;
Node prev;
Node next;
public Node(K key, V value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
/**
* the head is the oldest record and the tail is the newest record
*
* the add() will append the record to tail
*
* @param
key
* @param
value
*/
public static class DoubleLinkedList{
Node head;
Node tail;
public DoubleLinkedList() {
this.head = null;
this.tail = null;
}
public void add(Node node){
if (node == null) {
return;
}
if (this.head == null) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}
}
public void moveToTail(Node node){
if (node == this.tail) {
return;
}
if (node == this.head) {
Node newHead = node.next;
newHead.prev = null;
this.head = newHead;
node.next = null;
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
} else {
node.prev.next = node.next;
node.next.prev = node.prev;
node.next=null;
node.prev=this.tail;
this.tail.next = node;
this.tail = node;
}
}
public K removeHead() {
if (this.head != null) {
K deletedK = this.head.key;
if (this.head == this.tail) {
this.head = null;
this.tail = null;
} else {
Node newHead = this.head.next;
newHead.prev = null;
this.head = newHead;
}
return deletedK;
}
return null;
}
}
public static class MyCache{
HashMap> map = new HashMap();
DoubleLinkedList list = new DoubleLinkedList();
int capacity;
public MyCache(int capacity) {
this.capacity = capacity;
}
public void set(K key, V value) {
if (map.containsKey(key)) {
//swap value
//update map
Node node = map.get(key);
node.value = value;
map.put(key, node);
//update list
list.moveToTail(node);
} else {
//save record
//if full,remove the oldest first and then save
if (map.size() == this.capacity) {
K deletedK = (K) list.removeHead();
map.remove(deletedK);
}
Node record = new Node(key, value);
map.put(key, record);
list.add(record);
}
}
public V get(K key) {
if (map.containsKey(key)) {
Node target = map.get(key);
list.moveToTail(target);
return target.value;
} else {
return null;
}
}
}
public static void main(String[] args) {
MyCache myCache = new MyCache(3);
myCache.set("A", 1);
myCache.set("B", 2);
myCache.set("C", 3);
System.out.println(myCache.get("A"));
myCache.set("D", 4);
System.out.println(myCache.get("B"));
}
}面试技巧： 在刷题时，如果感觉这个题明显在30分钟内解不出来就放弃，因为面试给出的题目一般会让你在30分内解出。 在面试时如果碰到自己遇到过的题也要装作没遇到过，假装一番苦思冥想、和面试官沟通细节，然后突然想通了的样子。LFULFU也是一种经典的缓存结构，只不过它是以key的访问频度作为缓存替换依据的。举例：set("A",Data)将会在LFU结构中放入一条key为“A”的记录，并将该记录的使用频度置为1，后续的set("A",newData)或get("A")都会将该key对应的记录的使用频度加1；当该结构容量已满还尝试往里添加记录时，会先将结构中使用频度最少的记录删除，再将新的记录添加进去。设计思路：使用一个哈希表和一个二维双向链表（链表中包含链表）示例代码：import java.util.HashMap;
public class LFUCache{
/**
* Save all record
*/
private HashMap> recordMap;
/**
* The reference of the FrequencyList whose frequency is the lowest
*/
private FrequencyList headList;
/**
* Save what FrequencyList a record belongs to
*/
private HashMap listOfRecord;
/**
* How many recordMap the LFUCache can contain
*/
private int capacity;
/**
* how many recordMap has been saved
*/
private int size;
public LFUCache(int capacity) {
this.recordMap = new HashMap();
this.listOfRecord = new HashMap();
this.headList = null;
this.capacity = capacity;
this.size = 0;
}
/**
* add or update a record
* @param key
* @param value
*/
public void set(K key, V value) {
//update
if (this.recordMap.containsKey(key)) {
//update value and frequency
Record record = recordMap.get(key);
record.value = value;
record.frequency++;
//adjust the record's position in FrequencyList
adjust(record, listOfRecord.get(record));
} else {
//add
if (size == capacity) {
//delete
recordMap.remove(headList.tail.key);
headList.deleteRecord(headList.tail);
size--;
modifyFrequencyList(headList);
}
Record newRecord = new Record(key, value);
recordMap.put(key, newRecord);
size++;
if (headList == null) {
headList = new FrequencyList(newRecord);
} else if (headList.head.frequency != 1) {
FrequencyList frequencyList = new FrequencyList(newRecord);
headList.prev = frequencyList;
frequencyList.next = headList;
frequencyList.prev = null;
headList = frequencyList;
} else {
headList.addRecordToHead(newRecord);
}
listOfRecord.put(newRecord, headList);
}
}
/**
* get a record by a key,return null if not exists
* @param key
* @return */
public V get(K key) {
if (!recordMap.containsKey(key)) {
return null;
}
Record record = recordMap.get(key);
record.frequency++;
adjust(record, listOfRecord.get(record));
return record.value;
}
/**
* When the record's frequency changed,split it from its current
* FrequencyList and insert to another one
*
* @param record
* @param frequencyList
*/
private void adjust(Record record, FrequencyList frequencyList) {
//split
frequencyList.deleteRecord(record);
boolean deleted = modifyFrequencyList(frequencyList);
//insert to anther one
FrequencyList prevList = frequencyList.prev;
FrequencyList nextList = frequencyList.next;
if (nextList != null && record.frequency == nextList.head.frequency) {
nextList.addRecordToHead(record);
listOfRecord.put(record, nextList);
} else {
FrequencyList newList = new FrequencyList(record);
if (prevList == null) {
if (nextList != null) {
nextList.prev = newList;
}
newList.next = nextList;
newList.prev = null;
headList = newList;
} else if (nextList == null) {
prevList.next = newList;
newList.prev = prevList;
newList.next = null;
} else {
prevList.next = newList;
newList.prev = prevList;
newList.next = nextList;
nextList.prev = newList;
}
listOfRecord.put(record, newList);
}
}
/**
* return whether the frequencyList is deleted
* @param frequencyList
* @return */
private boolean modifyFrequencyList(FrequencyList frequencyList) {
if (!frequencyList.isEmpty()) {
return false;
}
if (frequencyList.prev == null) {
headList = frequencyList.next;
if (headList != null) {
headList.prev = null;
}
} else if (frequencyList.next == null) {
frequencyList.prev.next = null;
} else {
frequencyList.prev.next = frequencyList.next;
frequencyList.next.prev = frequencyList.prev;
}
return true;
}
/**
* The Record can be design to Record or Record used
* to encapsulate data
* @param
key
* @param
value
*/
private class Record {
K key;
V value;
/**
* up->the predecessor pointer
* down->the successor pointer
*/
Record up;
Record down;
/**
* the frequency of use
*/
int frequency;
/**
* when the record was created , set the frequency to 1
*
* @param key
* @param value
*/
public Record(K key, V value) {
this.key = key;
this.value = value;
this.frequency = 1;
}
}
/**
* The FrequencyList save a series of Records that
* has the same frequency
*/
private class FrequencyList {
/**
* prev->the predecessor pointer
* next->the successor pointer
*/
FrequencyList prev;
FrequencyList next;
/**
* The reference of the internal RecordList's head and tail
*/
Record head;
Record tail;
public FrequencyList(Record record) {
this.head = record;
this.tail = record;
}
public void addRecordToHead(Record record) {
head.up = record;
record.down = head;
head = record;
}
public boolean isEmpty() {
return head == null;
}
public void deleteRecord(Record record) {
if (head == tail) {
head = null;
tail = null;
} else if (record == head) {
head=head.down;
head.up = null;
} else if (record == tail) {
tail = tail.up;
tail.down = null;
} else {
record.up.down = record.down;
record.down.up = record.up;
}
}
}
public static void main(String[] args) {
LFUCache cache = new LFUCache(3);
cache.set("A", 1);
cache.set("A", 1);
cache.set("A", 1);
cache.set("B", 2);
cache.set("B", 2);
cache.set("C", 3);
cache.set("D", 4);
System.out.println("break point");
}
}更多名企笔试真题解析、面试经验交流、招聘信息内推，尽在牛客！求职之前，先上牛客！快快下载拿offer！与作者交流：https://www.nowcoder.com/discuss/150061更多笔经面经：https://www.nowcoder.com/discuss?order=0&type=2