2019年9月25号华为面试算法题
2019年秋招，华为面试加了两轮的手撕代码环节
一面算法题
1. 复盘第一题，可以在2019年4月10号华为春招实习机试上查看代码思路。
2. LIS问题，最长连续递增子序列问题
package huawei.interview1st;
import java.util.Arrays;
/**
* 求一个序列中，最长的一段连续子序列的长度，比如{3, 5, 2, 4, 6, 7, 1, 8}， 最长的连续子序列是{2, 4, 6, 7}长度为4。
*/
public class LongestContinuousSubsequence {
/*
考察nums每一个元素为结尾的最长子序列，记录其中最长的即为返回值
令 len[i]为以 nums[i]为结尾的最长子序列长度，则len[i] 可以由前面的 len[i - 1]决定，
若 nums[i - 1] >= nums[i]，则len[i]为1，否则，len[i]为len[i - 1] + 1
时间复杂度O(N)，空间复杂度O(N)
*/
public static int longestContinusSubsequenceDP(int[] nums) {
if (nums == null || nums.length < 1) return 0;
if (nums.length == 1) return 1;
int[] len = new int[nums.length];
Arrays.fill(len, 1);
int maxLen = 1;
for (int i = 1; i < len.length; i++) {
len[i] = nums[i] > nums[i - 1] ? len[i - 1] + 1 : 1;
maxLen = Math.max(maxLen, len[i]);
}
return maxLen;
}
/*
优化DP，其实并不需要len数组，只需要维护一个curLen和maxLen即可
*/
public static int longestContinusSubsequenceFinal(int[] nums) {
if (nums == null || nums.length < 1) return 0;
if (nums.length == 1) return 1;
int curLen = 1, maxLen = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
curLen++;
} else {
curLen = 1;
}
if (maxLen < curLen) maxLen = curLen;
}
return maxLen;
}
public static void main(String[] args) {
int[] nums;
int n = 1000;
while (n > 0) {
nums = generateNums();
if (longestContinusSubsequenceDP(nums) != longestContinusSubsequenceFinal(nums)) {
System.out.println("failed");
return;
}
n--;
}
System.out.println("succeed");
}
private static int[] generateNums() {
int len = (int) (Math.random() * 50);
int[] nums = new int[len];
for (int i = 0; i < nums.length; i++) {
nums[i] = (int) (Math.random() * 100);
}
return nums;
}
}
3. LIS，最长 递增非 连续子序列问题
改进算法参考了博客最长递增子序列LIS的O(nlogn)的求法，请支持原文作者原创内容，认真看可以看懂，且可以收获新的解题思路。
package huawei.interview1st;
import java.util.Arrays;
import static huawei.interview1st.LongestContinuousSubsequence.generateNums;
/**
* 求一个序列中，最长的一段连续子序列的长度，比如{3, 5, 2, 4, 6, 7, 1, 8}， 最长的连续子序列是{2, 4, 6, 7, 8}或{1, 4, 6, 7, 8}或{3, 5, 6, 7, 8}，长度为5。
*/
public class LongestNon_ContiguousSubsequence {
/*
考察nums每一个元素为结尾的最长子序列，记录其中最长的即为返回值
令 len[i]为以 nums[i]为结尾的最长子序列长度，则len[i] 可以由前面的 (len[i - 1], nums[i - 1]), ... (len[0], nums[0])决定，
若 nums[i] > nums[j]，则len[i]为len[j] + 1, 否则，为1，且需要比较i前面所有的j
时间复杂度O(N^2)，空间复杂度O(N)
*/
public static int longestNon_ContiguousSubsequenceDP(int[] nums) {
if (nums == null || nums.length < 1) return 0;
if (nums.length == 1) return 1;
int[] len = new int[nums.length];
Arrays.fill(len, 1);
int maxLen = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) len[i] = Math.max(len[i], len[j] + 1);
}
maxLen = Math.max(maxLen, len[i]);
}
return maxLen;
}
/*
优化算法：
辅助数组tails，tails[i]记录长度为i + 1的子序列的最小末尾数，因为在nums中遇到一个新的数，就把数据更新到tails数组中第一个比这个数大的数的位置，并不会影响后面的tails的更新
如果，经过二分查找后，发现这个数就是最大数，则，此时，比当前长度更长的最长子序列被发现。
返回size即为所求值
*/
public static int longestNon_ContiguousSubsequenceFinal(int[] nums) {
if (nums == null || nums.length < 1) return 0;
if (nums.length == 1) return 1;
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int i = 0, j = size;
while (i != j) {
int m = (j - i) / 2 + i;
if (tails[m] < x) i = m + 1;
else j = m;
}
tails[i] = x;
if (i == size) ++size;
}
return size;
}
public static void main(String[] args) {
int n = 1000;
while (n > 0) {
int[] nums = generateNums();
if (longestNon_ContiguousSubsequenceDP(nums) != longestNon_ContiguousSubsequenceFinal(nums)) {
System.out.println("failed");
System.out.println(nums.length);
return;
}
n--;
}
System.out.println("succeed");
}
}
二面算法题
1. 猴子爬楼梯问题，猴子一次只能爬一级台阶或者三级台阶，问猴子爬到n级台阶总共有多少种方法？
package huawei.interview2nd;
import java.util.Arrays;
/**
* 猴子爬楼梯问题，猴子一次只能爬一级台阶或者三级台阶，问猴子爬到n级台阶总共有多少种方法？
*/
public class MonkeyClimbStairs {
public static void main(String[] args) {
int n = 60;
while (n > 0) {
if (monKeyClimbStairsDP(n) != monkeyClimbStairsFinal(n)) {
System.out.println("failed");
System.out.println(n);
return;
}
n--;
}
System.out.println("succeed");
}
public static int monkeyClimbStairs(int n) {
if (n < 3) return 1;
if (n == 3) return 2;
return monkeyClimbStairs(n - 1) + monkeyClimbStairs(n - 3);
}
public static int monKeyClimbStairsDP(int n) {
if (n < 3) return 1;
int[] dp = new int[n + 1];
Arrays.fill(dp, 1);
for (int i = 3; i < dp.length; i++) {
dp[i] = dp[i - 1] + dp[i - 3];
}
return dp[n];
}
public static int monkeyClimbStairsFinal(int n) {
if (n < 3) return 1;
int prePrePre = 1;
int prePre = 1;
int pre = 1;
int cur = 0;
while (n >= 3) {
cur = pre + prePrePre;
prePrePre = prePre;
prePre = pre;
pre = cur;
n--;
}
return cur;
}
}
2. 顺时针旋转的矩阵,（0， 0）位置的数字是1，向右、向下分别是x轴、y轴的正方向，具体题意可以看代码中的注释，求（x, y）对应的值是多少，本题用了对数器对算法做了验证。
package huawei.interview2nd;
import java.util.Date;
/**
* 坐标(0, 0)的数字是1，规定向右由坐标轴的x轴的正方向，向下为y轴的正方向，从原点出发，按顺时针方向可以看到，矩阵的值是递增的，根据(x, y)得到矩阵中的坐标值。
* 示例：
* 21 22 23 24 25
* 20 7 8 9 10
* 19 6 1 2 11
* 18 5 4 3 12
* 17 16 15 14 13
* <p>
* (1, 1)对应的坐标是3， (2, -1)对应的坐标是10
*/
public class ClockwiseMatrixCoordinateEvaluation {
// 暴力解法，用(m, n)移动到(x, y)，记录一个递增的res，当(m, n) = (x, y)时，到达目标点
// 示例中的 值矩阵 对应的坐标矩阵是
/*
(-2, -2) (-1, -2) ( 0, -2) ( 1, -2) ( 2, -2)
(-1, -1) (-1, -1) ( 0, -1) ( 1, -1) ( 2, -1)
(-2, 0) (-1, 0) ( 0, 0) ( 1, 0) ( 2, 0)
(-2, 1) (-1, 1) ( 0, 1) ( 1, 1) ( 2, 1)
(-2, 2) (-1, 2) ( 0, 2) ( 1, 2) ( 2, 2)
*/
// 移动规律是 m++ -> 2
// n++ -> 3
// m-- -> 4
// m-- -> 5
// n-- -> 6
// n-- -> 7
// m++ m++ m++ n++ n++ n++ m-- m-- m-- m-- n-- n-- n-- n--
public static int clockwiseMatrixCoordinateEvaluation(int x, int y) {
int m = 0; // 移动点的横坐标
int n = 0; // 移动点的纵坐标
int res = 1; // 初始值，走一步自加一次，走到终点即为结果值
boolean postiveDirectMoveFlag = true; // 正方向移动标志
int steps = 1; // 朝特定方向一次移动步长
int xCurStep = 0; // 点当前沿着x轴运动的步数
int yCurStep = 0; // 点当前沿着y轴运动的步数
while (m != x || n != y) {
if (postiveDirectMoveFlag) { // 正向移动
if (xCurStep < steps) {
m++;
xCurStep++;
res++;
} else if (yCurStep < steps) { // x方向走完, 开始沿着y方向移动
n++;
yCurStep++;
res++;
} else { // y方向走完，可以设置steps自加1,，且反转方向
steps++;
xCurStep = 0;
yCurStep = 0;
postiveDirectMoveFlag = !postiveDirectMoveFlag;
}
} else {
if (xCurStep < steps) {
m--;
xCurStep++;
res++;
} else if (yCurStep < steps) { // x方向走完, 开始沿着y方向移动
n--;
yCurStep++;
res++;
} else { // y方向走完，可以设置steps自加1,，且反转方向
steps++;
xCurStep = 0;
yCurStep = 0;
postiveDirectMoveFlag = !postiveDirectMoveFlag;
}
}
}
return res;
}
/*
暴力解法的时间复杂度是O(N)，由更低时间复杂度的算法，即需要招数学规律，观察矩阵坐标和对应的矩阵值
(-2, -2) (-1, -2) ( 0, -2) ( 1, -2) ( 2, -2)
(-1, -1) (-1, -1) ( 0, -1) ( 1, -1) ( 2, -1)
(-2, 0) (-1, 0) ( 0, 0) ( 1, 0) ( 2, 0)
(-2, 1) (-1, 1) ( 0, 1) ( 1, 1) ( 2, 1)
(-2, 2) (-1, 2) ( 0, 2) ( 1, 2) ( 2, 2)
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
以原点开始给矩阵分成正方形点阵集合的数组pointSet，pointSet[i]点阵的集合为{(x, y)| |x| = i or |y| = i, |x| <= i and |y| <= i}。
根据(x, y)可以知道所求点在pointSet[Math.max(Math.abs(x), Math.abs(y))]中。
且,
坐标(t, -t)对应的值是v，有：
(2 * t + 1) ^ 2, t >= 0,
v =
(2 * t) ^ 2 + 1, t < 0
规定，每一圈的终点为(t, -t)，t >= 0, 设为 endVal
pointSet[t], t > 0，且集合元素大小为8*t
在坐标轴上的四个顶点是(t, t), (-t, t), (-t, -t), (t, -t),
对应的值分别是 endVal - 6t, endVal - 4t, endVal - 2t, endVal
对于在pointSet[t]上的坐标(x, y),
只要根据点在pointSet[t]的一条边上，就可以得到指定的值是多少
*/
public static int clockwiseMatrixCoordinateEvaluation2(int x, int y) {
int t = Math.max(Math.abs(x), Math.abs(y)); // 确定(x, y)在pointSet[t];
int endVal = 1;
endVal = (t << 1) + 1;
endVal *= endVal;
if (endVal == 1 || x == t && y == -t) return endVal;
if (Math.abs(x) == t) {
if (x > 0) {
return endVal - 7 * t + y;
} else {
return endVal - 3 * t - y;
}
} else {
if (y > 0) {
return endVal - 5 * t - x;
} else {
return endVal - t + x;
}
}
}
public static void main(String[] args) {
System.out.println(clockwiseMatrixCoordinateEvaluation2(1, 1)); // 3
System.out.println(clockwiseMatrixCoordinateEvaluation2(1, 2)); // 14
System.out.println(clockwiseMatrixCoordinateEvaluation2(2, 1)); // 12
System.out.println(clockwiseMatrixCoordinateEvaluation2(2, 2)); // 13
System.out.println(clockwiseMatrixCoordinateEvaluation2(2, -1)); // 10
int count = 100000;
long startTime = System.currentTimeMillis();
long endTime = 0L;
System.out.println(new Date().toString());
while (count > 0) {
int x = (int) (Math.random() * 100);
int y = (int) (Math.random() * 100);
int res1 = clockwiseMatrixCoordinateEvaluation(x, y);
int res2 = clockwiseMatrixCoordinateEvaluation2(x, y);
if (res1 != res2) {
System.out.println("failed");
System.out.println("x = " + x + ", y = " + y);
System.out.println("execute time: " + (endTime - startTime) + "ms");
System.out.println(new Date().getTime());
return;
}
count--;
}
endTime = System.currentTimeMillis();
System.out.println(new Date().getTime());
System.out.println("execute time: " + (endTime - startTime) + "ms");
System.out.println("succeed");
}
}
转载：https://blog.csdn.net/LingGit/article/details/101473738
查看评论