贝壳网2020笔试题解析

╰半橙微兮° 2023-06-02 09:22 45阅读 0赞

2019年8月10号我参加贝壳笔试，没想到是四道编程题，这个着实让我措手不及。下面我就来带大家看看这四道题目。首先我要吐槽下赛码网的系统，为啥非得写输入输出，能不能学学Leetcode ！

## 第一题：计算绝对值 ##

题目描述：给出n个整数，要找出相邻两个数字中差的绝对值最小的一对数字，如果差的绝对值相同的，则输出最前面的一对数。2<=n<=10，正整数都在10^16次方范围内。

输入：输入包含两行，第一行是n，第二行是n个用空格间隔的正整数。

输出：输出包含一行两个正整数，要求按照原来的顺序输出。

样例输入：9

1 3 4 7 2 6 5 12 32

样例输出：3 4

这道题应该是四道题中最简单的一道，有很多种方法。其中要注意的是对于差值相同的多对数，只输出最前面的一对数。在笔试时我用的map结构实现去重，其实是把这道题做复杂了，简单的一个数组就OK了。

下面来看看第一种做法，比较简单，大家就直接看代码吧。第一种解法的平均时间复杂度为O(n+m), 空间复杂度为O(m)。

第二种解法利用map去存储差值和数字对，时间复杂度和空间复杂度和第一种方法相同。

package main
    
    import (
        "fmt"
        "math"
    )
    
    func solution(nums []int) []int {
        minuss := make([]float64, len(nums))
        for i := 0; i < len(nums)-1; i++ {
            minuss[i] = math.Abs(float64(nums[i] - nums[i+1]))
        }
    
        min := math.MaxFloat64
        mini := 0
        for i, e := range minuss {
            if e < min {
                min = e
                mini = i
            }
        }
        res := []int{nums[mini], nums[mini+1]}
        return res
    }
    
    func solution1(nums []int) []int {
        m := make(map[int][]int)
        for i := 0; i < len(nums)-1; i++ {
            minus := int(math.Abs(float64(nums[i] - nums[i+1])))
            pair := []int{nums[i], nums[i+1]}
            if _, ok := m[minus]; !ok {
                m[minus] = pair
            }
        }
        minK := int(math.MaxInt64)
        for k, _ := range m {
            if k < minK {
                minK = k
            }
        }
        return m[minK]
    }
    
    func main() {
        var n int
        var nums []int
        fmt.Scanf("%d", &n)
        for i := 0; i < n; i++ {
            var tmp int
            fmt.Scanf("%d", &tmp)
            nums = append(nums, tmp)
        }
        res := solution1(nums)
        for _, elm := range res {
            fmt.Print(elm, " ")
        }
    }

## 第二题：月光宝盒 ##

题目描述：小希偶然得到了传说中的月光宝盒，然而打开月光宝盒需要一串密码，虽然小希并不知道具体的密码是什么，但是月光宝盒的说明书上有着一个长度为n（2<=n<=50000）的序列a(10^-9 <= a <= 10^9)。上面写着一句话：密码是这个序列的最长严格上升子序列的长度（严格上升子序列是指子序列的元素是严格递增的），请你帮小希找出这个密码。

输入：

第一行，1个数n。n为序列长度（2<=n<=50000）

第2到n+1行，每行一个数，对应序列的元素

输出：

正整数，表示严格上升子序列的长度

样例输入：

样例输出：

5，因为目标子序列为1 2 4 5 10

这道题在Leetcode上有原题，方法也很多，我在这里讲两种方法，动态规划和二分加贪心法。

方法1：动态规划法

动态规划两要素：递推方程和初始条件，我们令递推方程F(i)表示以nums\[i\]为最大值的前i-1个元素的最长上升子序列（nums\[0 ... i-1\]）的长度。我们令递推方程 F(i) = max( max( F(0), F(1), ... , F(i-1) )+1, F(i))， 初始时F中的所有元素都等于0。可以看出整个递推方程实际上是求两个最大值的过程。代码如下所示：

func max(a, b int) int {
        if a > b {
            return a
        } else {
            return b
        }
        return a
    }
    
    func lengthOfLIS(nums []int) int {
        F := make([]int, len(nums))
        var maxL int
        for i := 0; i < len(nums); i++ {
         
    　　　　　//内层循环找nums[i]之前的最长上升子序列长度，只在nums[i] > nums[j]进行计算
            for j := 0; j < i; j++ {
                if nums[i] > nums[j] {
                    F[i] = max(F[j]+1, F[i])
                }
            }
    　　　　　//外层循环求整个F[i]的最大值
            maxL = max(maxL, F[i]+1)
        }
        return maxL
        //return maxf
    }

方法2：二分加贪心算法

我们用 tail\[i\] 表示长度为 i+1 的子序列的最小的元素。比如对于序列\[4，5，6，3\]，tail数组的填充过程如下所示。

`len = 1 : [4], [5], [6], [3] => tails[0] = 3`

`　　len = 2 : [4, 5], [5, 6] => tails[1] = 5`

`　　len = 3 : [4, 5, 6] => tails[2] = 6`

求解的过程就是不断向tail中加入合适的元素的过程，我们遍历所有长度的子序列并找到一个序列结尾最小的元素加入到tail中。为什么要找结尾最小的元素呢？

因为对于一个上升序列，当前的元素越小越有利于后续的元素的加入。这就是贪心的所在。每次循环我们只做两件事：

1. 如果nums\[i\]比当前的所有tail\[i\]元素都大，直接将其增加到尾部。

2. 如果nums\[i\]比tails\[i\]小那么更新tails\[i\]。

/*func lengthOfLIS(nums []int) int {
        tails := make([]int, len(nums))
        pos := 0
        for i := 0; i < len(nums); i++ {
            low, high := 0, pos
            for(low != high) {
                mid := (low + high)/2
                if tails[mid] < nums[i] {
                    low = mid + 1
                } else {
                    high = mid
                }
            } 
            tails[low] = nums[i]
            if low == pos {
                pos++
            }
        }
        return pos
    }*/

## 第三题：举重大赛 ##

题目描述：举重大赛开始了，为了保证公平，要求比赛双发体重较小值要大于等于较大值的90%。那么对于N个人最多能进行多少场比赛呢。任意两人只能进行一场比赛。

输入：

第一行N,表示参赛人数

第二行N个正整数，表示体重。

输出：

一个数，表示最多进行的比赛次数。

这道题，最简单的想法就是遍历每一个组合然后判断整个组合是否满足条件。但是暴力法虽然简单，但是却没有超时了。所以还是不行。其实暴力法是存在大量重复计算的，因此有很大的

优化的空间。比如如果 a >= b \* 0.9， 那么任何大于a的元素和b都可以进行比赛。

package main
    
    import (
        "fmt"
        "sort"
    )
    
    func satisfy(a, b int) bool {
        if float64(a) >= float64(b)*0.9 {
            return true
        }
        return false
    }
    
    func solution(nums []int) int {
        sort.Ints(nums)
        count := 0
        for i := 0; i < len(nums); i++ {
            for j := i + 1; j < len(nums); j++ {
                if satisfy(nums[i], nums[j]) {
                    count += len(nums) - j
                    break
                }
            }
        }
        return count
    }
    
    func main() {
        var n int
        var nums []int
        fmt.Scanf("%d", &n)
        for i := 0; i < n; i++ {
            var tmp int
            fmt.Scanf("%d", &tmp)
            nums = append(nums, tmp)
        }
        res := solution(nums)
        fmt.Println(res)
    }

## 第四题：特殊的测试 ##

题目描述：小C在做一种特殊的服务器负载测试，对于一个请求队列中的请求，每个请求都有一个负荷值。为了保证服务器稳定，请求队列中的请求负荷必须按照先增后减，或者递增或者递减的规律。比如

\[1，2，8，4，3\]，\[1，3，5\]，\[10\]是符合规律的。还有一些不满足的，比如\[1，2，2，1\]，\[2，1，2\]，\[10，10\]。现在给你一个请求队列，你可以对请求的负荷值进行增加，要求你调整队列中请求的

负荷值，最后输出使得队列满足条件的最小增加总和。

输入：输入两行，第一行N表示请求的个数，第二行表示每个请求的符合值。

输出：输出这个最小增加总和

样例输入：

1 4 3 2 5

样例输出：

6 （此时合法队列是1 4 5 6 5），最小增加总和=2+4 = 6

package main
    
    import (
        "fmt"
    )
    
    func solution(nums []int) int {
        n := len(nums)
        if n == 1 {
            return 0
        }
    
        if n == 2 && nums[0] == nums[1] {
            return 1
        }
    
        if n == 2 && nums[0] != nums[1] {
            return 0
        }
    
        cp := make([]int, n)
        copy(cp, nums)
    
        var i, j int
        for i = 0; i < n-1 && nums[i] < nums[i+1]; i++ {
        }
    
        for j = n - 1; j > 0 && nums[j] < nums[j-1]; j-- {
        }
    
        for i < j {
            if nums[i] < nums[j] {
                if (nums[i+1] - nums[i]) < 1 {
                    nums[i+1] = nums[i] + 1
                }
                i++
            } else {
                if (nums[j-1] - nums[j]) < 1 {
                    nums[j-1] = nums[j] + 1
                }
                j--
            }
        }
        return sum(nums) - sum(cp)
    }
    
    func sum(nums []int) int {
        s := 0
        for _, elm := range nums {
            s += elm
        }
        return s
    }
    func main() {
        var n int
        var nums []int
        fmt.Scanf("%d", &n)
        for i := 0; i < n; i++ {
            var tmp int
            fmt.Scanf("%d", &tmp)
            nums = append(nums, tmp)
        }
        res := solution(nums)
        fmt.Println(res)
    }

## 参考： ##

https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation

https://blog.csdn.net/wbin233/article/details/77570070

https://www.cnblogs.com/haimishasha/p/11333201.html

转载于:https://www.cnblogs.com/dennis-wong/p/11334475.html