2020shopee春招第一次的在线编程题及AC解答

刺骨的言语ヽ痛彻心扉 2023-07-05 13:26 3阅读 0赞

时间2020年2月15日14：00~16：00

Let the code speak!

## 第一题 ##

版本号比较大小  
@return 0代表相等，1代表左边大，-1代表右边大  
输入两个版本号，中间逗号隔开，比较大小。

package algorithm.test;
    
    import java.util.Scanner;
    public class Main { 
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            String string = scanner.nextLine();
            String[] str = string.split(",");
            System.out.println(compareVersion(str[0],str[1]));
        }
        public static int compareVersion(String version1, String version2) { 
            String[] v1 = version1.split("\\.");
            String[] v2 = version2.split("\\.");
            for (int i = 0, j = 0; i < v1.length || j < v2.length; i++, j++) { 
                int one = i < v1.length ? Integer.parseInt(v1[i]) : 0;
                int two = j < v2.length ? Integer.parseInt(v2[j]) : 0;
                if (one == two) { 
                    continue;
                } else { 
                    return one > two ? 1 : -1;
                }
            }
            return 0;
        }
    }

三元运算符可以很明显的提升效率。

## 第二题 ##

题目描述：  
已知正整数数组删除数组中重复的数字使数组满足以下条件，使1出现一次，2出现2次，3出现3次。。。。。。输出最后的数组长度。

package algorithm.test;
    
    import java.util.Scanner;
    public class Main { 
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            String str = scanner.nextLine();
            String[] s = str.split(" ");
            int[] a = new int[s.length];
            for (int i = 0; i < s.length; i++){ 
                a[i] = Integer.valueOf(s[i]);
            }
            int result = 0;
            int len = a.length;
            int tmp;
            for (int i = 0 ; i < len - 1; i += tmp) { 
                tmp = 0;
                for (int j = i + 1; j < len; j++) { 
                    if (a[i] == a[j]){ 
                        tmp++;
                    }
                }
                tmp += 1;
                if (tmp != 0){ 
                    if (tmp <= a[i]){ 
                        result += tmp;
                    }else { 
                        result +=a[i];
                    }
                }
            }
            System.out.println(result);
        }
    }

## 第三题 ##

题目描述：经典问题：对于一个m\*n的网格，从左上角的方格到右下角的方格，共有多少条路径（只允许向右和向下）

import java.util.Scanner;
    import java.util.*;
    public class Main { 
        public static void main(String[] args) { 
            Solution s = new Solution();
            Scanner sc = new Scanner(System.in);
            int m = sc.nextInt();
            int n = sc.nextInt();
            System.out.println(s.uniquePaths(m,n));
        }
    }
     
    class Solution { 
        public int uniquePaths(int m, int n) { 
            int[] memo = new int[n];
    
            Arrays.fill(memo, 1);
    
            for (int i = 1; i < m; i++) { 
                for (int j = 1; j < n; j++) { 
                    memo[j] += memo[j - 1];
                }
            }
    
            return memo[n - 1];
        }
    }