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);
    }

3、最长递增子序列

优化点：使用info数组，info[i] 表示，最长递增子序列长度必须是 i+1的时候，最后一个数字最小是什么。比如2 3 5 这个子序列，应该 info[2] = 5，表示长度为3的子序列，最后一个最小时 5。

2022.9.25 用友 笔试

全站热榜

2022.9.25 用友笔试