3.29日百度笔试编程题前两题答案

╰+哭是因爲堅強的太久メ 2023-07-19 05:56 53阅读 0赞

# 第一题： #

Java中没有long long类型，只有long类型。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

// // 解法1：（超时）
    // import java.util.*;
    
    // public class Main_1 { 
    
    // // 辗转相除法求最大公约数 gcd
    // public static int gcd(int a, int b)
    // { 
    // return b == 0 ? a : gcd(b, a % b);
    // }
    
    // // 最大公约数 = (a * b) / 最小公倍数
    // public static int lcm(int a, int b)
    // { 
    // return (a * b) / gcd(a, b);
    // }
    
    // public static void main(String[] args) { 
    // Scanner sc = new Scanner(System.in);
    // while(sc.hasNextInt())
    // { 
    // int n = sc.nextInt();
    // int max = -1;
    // int min = 1000000001;
    // for(int i = 1; i <= n; i++)
    // { 
    // for(int j = 1; j <= n; j++)
    // { 
    // if(lcm(i , j) > max)
    // { 
    // max = lcm(i, j);
    // }
    // else if(gcd(i, j) < min)
    // { 
    // min = gcd(i, j);
    // }
    // }
    // }
    // int res = max - min;
    // System.out.println(res);
    // }
    // }
    // }
    
    // 解法2：（数学方法）
    import java.util.*;
    
    public class Main_1 { 
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            while(sc.hasNextLong())
            { 
                long n = sc.nextLong();
                long res = n * (n - 1) - 1;
                System.out.println(res);
            }
        }
    }
    // 输入：
    // 5
    // 输出：
    // 19

# 第二题： #

第二题的主要思路是，因为数最大为10^18，所以如果用减法的话则会复杂度过高，重复的减法便是除法，然后先算一个最大的数，这里我用了排序，减去n多少次后，会小于n，便是除法的结果，然后再将结果加到其他n-1个数，继续循环即可。  
**注：**  
此题最优解应该是：最大堆 + 除法

例如：在1000个数中找到最大的那个数。如果用快速排序对所有数字进行排序，时间复杂度是O(NlogN)；而用优先队列（用队实现）存储数据，然后取出最大元素（此处为优先权最大的元素），这种数据结构时间复杂度为O(logN)。  
即在时间复杂度上，优先队列 > Arrays.sort().  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]  
最快的排序算法的时间复杂度为：O(NlogN).

// 解法1：（超时）
    // import java.util.*;
    
    // public class Main_2 { 
    
    // public static void main(String[] args) { 
    // Scanner sc = new Scanner(System.in);
    // while(sc.hasNextInt())
    // { 
    // int n = sc.nextInt();
    // long a[] = new long[n];
    // for(int i = 0; i < n; i++)
    // { 
    // a[i] = sc.nextLong();
    // }
    // int count = 0;
    // while(a[n - 1] >= n)
    // { 
    // int flag = 0;
    // for(int i = 0; i < n - 1; i++)
    // { 
    // if(a[i] > a[n - 1])
    // { 
    // flag = 1;
    // }
    // }
    // if(flag == 1)
    // { 
    // Arrays.sort(a);
    // a[n - 1] -= n;
    // for(int i = 0; i < n - 1; i++)
    // { 
    // a[i] += 1;
    // }
    // count++; 
    // }
    // else if(flag == 0)
    // { 
    // a[n - 1] -= n;
    // for(int i = 0; i < n - 1; i++)
    // { 
    // a[i] += 1;
    // }
    // count++;
    // }
    // }
    // System.out.println(count);
    // }
    // }
    // }
    
    // 解法2：
    import java.util.*;
    
    public class Main_2 { 
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            while(sc.hasNextInt())
            { 
                int n = sc.nextInt();
                long a[] = new long[n];
                for(int i = 0; i < n; i++)
                { 
                    a[i] = sc.nextLong();
                }
                Arrays.sort(a);
                if(a[n - 1] < n)
                { 
                    System.out.println(0);
                    continue;
                }
                long num = n;
                long count = 0;
                while(a[n - 1] >= n)
                { 
                    count = count + a[n - 1] / num;
                    for(int i = 0; i < n - 1; i++)
                    { 
                        a[i] = a[i] + a[n - 1] / num;
                    }
                    a[n - 1] = a[n - 1] % num;
                    Arrays.sort(a);
                }
                System.out.println(count);
            }
        }    
    }
    // 输入：
    // 3
    // 1 0 3
    // 输出：
    // 1

# 参考： #

1.  [3.29百度笔试编程题前两题答案][3.29]
2.  [3-29 百度 笔试 java后台开发，三道题AC答案][3-29 _ _ java_AC]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: /images/20230528/eb00b78afe1747dd9170184fdb7ca689.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/3c76beb07d5649118a2b4f0b8fb7b844.png
[3.29]: https://www.nowcoder.com/discuss/395140
[3-29 _ _ java_AC]: https://www.nowcoder.com/discuss/395175