2022-04-11：给定一个正数数组arr，其中每个值代表砖块长度

原创

福大大架构师每日一题

发布于 2022-04-11 23:11:10

3210

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-04-11：给定一个正数数组arr，其中每个值代表砖块长度，

所有砖块等高等宽，只有长度有区别，

每一层可以用1块或者2块砖来摆，

要求每一层的长度一样，

要求必须使用所有的砖块，

请问最多摆几层。

来自华为。

答案2022-04-11：

双指针，先排序。

情况一：最大的单独一层。

情况二：最大的需要组合。

代码用golang编写。代码如下：

package main

import (
	"fmt"
	"sort"
)

func main() {
	arr := []int{50, 50, 100}
	ret := maxLevels(arr)
	fmt.Println(ret)
}

func maxLevels(arr []int) int {
	if len(arr) == 0 {
		return 0
	}
	n := len(arr)
	if n < 2 {
		return n
	}
	sort.Ints(arr)
	p1 := levels(arr, arr[n-1])
	p2 := levels(arr, arr[n-1]+arr[0])
	return getMax(p1, p2)
}

// 要求所有砖必须都使用，并且每一层最多两块砖，并且每一层长度都是len
// 返回能摆几层，如果无法做到返回-1
func levels(arr []int, len0 int) int {
	ans := 0
	L := 0
	R := len(arr) - 1
	for L <= R {
		if arr[R] == len0 {
			R--
			ans++
		} else if L < R && arr[L]+arr[R] == len0 {
			L++
			R--
			ans++
		} else {
			return -1
		}
	}
	return ans
}

func getMax(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

执行结果如下：