第5章第10节动态规划_vlambda技术博客

vlambda
2020-09-25

第5章第10节动态规划

● 算法题，单链表判断是否有环(leetcode easy)，以及判断环入口

参考回答：

是否有环：

while (faster.next != null && faster.next.next != null) {faster = faster.next.next;slower = slower.next;if (faster == slower) {return true;}}return false;

判断环入口：

复制代码

Node meet = null;

while (faster.next != null && faster.next.next != null) {

faster = faster.next.next;

slower = slower.next;

if (faster == slower) {

meet = faster;

}

if (meet != null) {

newSlower = head;

while (newSlower != slower) {

newSlower = newSlower.next;

slower = slower.next;

}

return newSlower;

}

return null;

● 找出数组中只出现1次的数，其余数均出现2次，扩展，其余数出现2次以上

参考回答：

位运算题目，

位运算中异或的性质：两个相同数字异或=0，一个数和0异或还是它本身。当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。

public static int find1From2(int[] a){int len = a.length, res = 0;for(int i = 0; i < len; i++){res = res ^ a[i];}return res;}

扩展：

复制代码

public static int find1From3(int[] a){

int[] bits = new int[32];

int len = a.length;

for(int i = 0; i < len; i++){

for(int j = 0; j < 32; j++){

bits[j] = bits[j] + ( (a[i]>>>j) & 1);

}

int res = 0;

for(int i = 0; i < 32; i++){

if(bits[i] % 3 !=0){

res = res | (1 << i);

}

return res;

}

● 最短描述数，10的最短描述数是3^2+1^2所以是2，求一个数的最短描述数

参考回答：

动态规划问题，参考牛客网“拼凑面额”题解

● 跳台阶问题，每次只能跳1个台阶或者2个台阶，n个台阶共有多少种方式

参考回答：

最基础的动态规划问题

复制代码

public class Solution {

public int JumpFloor(int target) {

if(target<=1) return target;

int[] a = new int[target+1];

a[1]=1; a[2]=2;

for(int i=3;i<=target;i++){

a[i] = a[i-1] + a[i-2];

}

return a[target];

}

● 动态规划和带记忆递归的区别

参考回答：

自顶而下和自底而上

● 手撕代码：0-1矩阵的最大正方形

参考回答：

public int maxSquare(int[][] matrix) {

int row = matrix.length; //行大小

int line = matrix[0].length; //列大小

//一个与matrix相同大小的辅助数组

int[][] tmp = new int[row][line];

//将matrix的第一行和第一列元素直接存放到

for(int i=0;i<row;i++){tmp[i][0] = matrix[i][0];}for(int i=0;i<line;i++){tmp[0][i] = matrix[0][i];}for(int i=1;i<row;i++){for(int j=1;j<line;j++){if(matrix[i][j] == 1){tmp[i][j] =Math.min(Math.min(tmp[i-1][j],tmp[i][j-1]),tmp[i-1][j-1]) + 1;}if(matrix[i][j] == 0){tmp[i][j] = 0;}}}

int max=0; //记录tmp中最大元素的值（tmp中元素值表示正方形的边长)

复制代码

for(int i=0;i<row;i++){

for(int j=0;j<line;j++){

if(tmp[i][j] > max){

max = tmp[i][j];

}

return max*max;

}

vlambda博客
学习文章列表