2022.9.25 用友 笔试
之前选修过会计双学位，了解到用友这个公司，笔试投一下体验一下难度。
整体感觉 比较水。应该是 没系统学过算法的也能做出来的那种程度。
整体包括单选+多选+2编程+1编程题
1、纯暴力的
题目：一些数字 1-n，n的范围很小（1~52），先找到1，把1去掉，随后 找下一个除4余2的，除4余3的，除4余0的，除4余1的，直到最后一个
很明显数据量才50，暴力就可以的。实际实现的时候有个小优化，提前把 数字模4的结果存起来，作为info数组。为了防止手动构造一个队列，用一个valid数组，表示数字是否被选过
如果选过，那以后就不要选择这个数字。
数据量很少，最后直接暴力过一下，哪个还没有被标记，就是答案。
package yongyou.t01;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;
class Main{
public static int shrinkCircle (int[] circle) {
// write code here
int n = circle.length;
int[] info = new int[n];
boolean[] valid = new boolean[n];
for(int i = 0; i < n; i++){
info[i] = circle[i] % 4;
}
int index = 0;
while (circle[index] != 1){
index++;
}
valid[index] = true;
int num = 1;
//go
int c = 2;
while(num != n-1){
if(!valid[index] && info[index] == c){
//find！
valid[index] = true;
c = c == 3 ? 0 : c+1;
num++;
//System.out.println("num++, num="+num);
}
index = index == n-1 ? 0 : index+1;
}
//ans
for(int i = 0; i < n; i++){
if(!valid[i]){
return circle[i];
}
}
return -1;
}
public static void main(String[] args) {
int[] a = new int[]{9,8,7,6,5,4,3,2,1};
System.out.println(shrinkCircle(a));
// Scanner in = new Scanner(System.in);
}
} 2、
在一个三维直角坐标系中，有一只蚂蚁从原点 (0, 0, 0) 开始，向目标点 (l, m, n) 前进，蚂蚁的前进规则如下： 1、l, m, n >= 0，且 l + m + n > 0； 2、蚂蚁每次只能沿X/Y/Z轴的方向前进一个单位，比如，当前蚂蚁在点(x0, y0, z0)，下一步只能前进到下面三个点中的任意一个：(x0 + 1, y0, z0)，或(x0, y0 + 1, z0)，或(x0, y0, z0 + 1)。 返回所有可以从原点 (0, 0, 0) 到目标点 (l, m, n) 的可行路径数量。 * @param x int整型 目标点的X坐标 * @param y int整型 目标点的Y坐标 * @param z int整型 目标点的Z坐标 * @return long长整型 */说实话这个是高中数学题，我们可以认为，有三个商品abc，每一个又有多个，问你有多少种组合方式。相当于
1、在所有的 a+b+c 中，先选出a个位置 放a，个数为C(a+b+c, a) [不太会打上下的格式，就是排列组合中的 C，不是A]
2、在剩下的b+c个中，选出b个放b
3、c的话剩余的位置，只有1种
答案就是 第一步结果 * 第二部结果 * 1
【高中数学题，就比如从(0,0) 岛 （2，3） 有多少条路，相当于要在总共5步里面，选2个往上走，剩下自动向右了，答案就是 C(5, 2)】
注意说返回的long，应该很大，我再计算过程中用的Big Integer， 其它语言的可以看看有没有各自的函数。
有个优化点，我没有实现，就是计算C的时候，为了防止溢出，可以计算分子 、分母的过程中，同时除以他俩的最大公约数，比如 5*4*3 / 3*2*1，在分子是5*4时，分母3*2，他俩可以同时除以gcd(20, 6) = 2, 变成分子10， 分母3。
class Main {
public static long countPaths (int x, int y, int z) {
// write code here
int all = x + y + z;
BigInteger b1 = process(all, x);
BigInteger b2 = process(all - x, y);
return b1.multiply(b2).longValue();
}
public static BigInteger process(int a, int b){
//总共a个 选出b 有多少种
BigInteger top = BigInteger.valueOf(1), down = BigInteger.valueOf(1);
int time= b;
for(int i = 0; i < time; i++){
top = top.multiply(BigInteger.valueOf(a));
down = down.multiply(BigInteger.valueOf(b));
a--;b--;
}
return top.divide(down);
}
public static void main(String[] args) {
System.out.println(countPaths(1,0,0));
Scanner in = new Scanner(System.in);
}
优化点：使用info数组，info[i] 表示，最长递增子序列长度必须是 i+1的时候，最后一个数字最小是什么。比如2 3 5 这个子序列，应该 info[2] = 5，表示长度为3的子序列，最后一个最小 时 5。
对于任何一个数字，通过二分查找加速，o(nlogn ) 最优解肯定能过。暴力的方式不清楚能不能过。
package yongyou.t03;
import java.util.Arrays;
import java.util.Scanner;
class Main {
public static int lengthOfList (int[] nums) {
// write code here
//最长递增子序列
//必须以 info[i] i+1长度的递增子序列，最后一个数字 最小是什么
int n = nums.length;
int[] info = new int[n];
if(n <= 1){
return n;
}
int ans = 0;
info[0] = nums[0];
for(int i = 1; i < n; i++){
int cur = nums[i];
//二分 找到 >= 最左的位置
int left = 0, right = ans;
int curAns = -1;
while(left <= right){
int mid = left + (right - left)/2;
if(info[mid ] >= cur){
curAns = mid;
right = mid - 1;
}else{
left = mid + 1;
}
}
if(curAns == -1){
++ans;
info[ans] = cur;
}else{
info[curAns] = Math.min(info[curAns], cur);
}
}
System.out.println(Arrays.toString(info));
return ans+1;
}
public static void main(String[] args) {
System.out.println(lengthOfList(new int[]{10,9,2,5,3,7,101,18}));
Scanner in = new Scanner(System.in);
}
} 
