9.25用友笔试
题目见上。
第一题直接用链表模拟了。
就用Java的LinkedList实现，怎么实现环形呢，直接把头元素取出再加到尾，这就是环了
public int shrinkCircle (int[] circle) {
//用链表模拟
LinkedList<Integer> data = new LinkedList<>();
//原来要从1开始找
int i = 0;
for(; i < circle.length; i++){
if(circle[i] == 1){
break;
}
data.addLast(circle[i]);
}
//出来的时候i是1的位置，那再从末尾元素加到i的位置
for(int j = circle.length - 1; j >= i; j--){
data.addFirst(circle[j]);
}
//这样子出现的就是
//1到末尾元素，第一个元素到1的之前
int remainder = 1;
while(data.size() > 1){
Integer temp = data.removeFirst();
if(temp % 4 == remainder){
remainder++;
if(remainder == 4){
remainder = 0;
}
//符合条件就不要加回去了，就从环中剔除了该元素
continue;
}
data.addLast(temp);
}
//只剩最后一个了
return data.getFirst();
} 第二题，是力扣62题不同路径和牛客这题的进阶不同路径的数目(一)_牛客题霸_牛客网 (nowcoder.com)
只是难以使用递推的方式递推（反正我没想出来），直接记忆化搜索解决问题吧。
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* @param x int整型 目标点的X坐标
* @param y int整型 目标点的Y坐标
* @param z int整型 目标点的Z坐标
* @return long长整型
*/
public long countPaths (int x, int y, int z) {
long[][][] memo = new long[x + 1][y + 1][z + 1];
//base case
//从起点到起点只有一种路径，那就是站着不动，这就是唯一的base case
memo[0][0][0] = 1;
return dp(memo, x, y, z);
}
//采用记忆化搜索的办法
private long dp(long[][][] memo, int x, int y, int z){
//dp含义，从0,0,0到x,y,z的路径数量
//状态转移
//依据题意，每次都只能沿着三条坐标轴之一移动一个方向，所以到达x,y,z这个点的，只可能有这三种情况
//从x-1,y,z过来，从x,y-1,z过来，从x,y,z-1过来
//因此状态转移方程为
//dp[x][y][z] = dp[x-1][y][z] + dp[x][y-1][z] + dp[x][y][z-1]
if(x == -1 || y == -1 || z == -1){
return 0;
}
if(memo[x][y][z] != 0){
return memo[x][y][z];
}
//只能从三个方向而来
long res = dp(memo, x - 1, y, z) + dp(memo, x, y - 1, z) + dp(memo, x, y, z - 1);
memo[x][y][z] = res;
return memo[x][y][z];
} 第三题，力扣300题最长递增子序列原题。牛客上此题连接：最长上升子序列(一)_牛客题霸_牛客网 (nowcoder.com)
public int lengthOfLIS(int[] nums) {
//dp数组的含义为，dp[i]的值是以nums[i]结尾的最长递增子序列长度
//base case为dp[i] = 1，因为递增子序列最少包括自身，自然长度为1
//状态转移
//从左往右找，限定j为0到i-1之间
//当nums[i] > nums[j]
//dp[i] = MAX { dp[j] + 1 , dp[i] }
int[] dp = new int[nums.length];
int res = 1;
Arrays.fill(dp , 1);
for(int i = 1; i < dp.length; i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
dp[i] = Math.max(dp[i] , dp[j] + 1);
}
}
res = Math.max(dp[i] , res);
}
return res;
}
