首页 > 奇安信 2021.08.07 代码题 Go 实现
头像
Little_ma
发布于 2021-08-07 17:19
+ 关注

奇安信 2021.08.07 代码题 Go 实现

#奇安信笔试# 
奇安信 2021.08.07 代码题 Go 实现
1. 三重循环 100% 居然没超时
package main

// TeamNums 相当于求递增、递减序列的个数
func TeamNums( height []int ) int {
	// 暴力应该会超时
    // 居然没超时
	res := 0
	for i := 0; i < len(height); i++ {
		for j := i + 1; j < len(height); j++ {
			for k := j + 1; k < len(height); k++ {
				if isOrder(height[i], height[j], height[k]) {
					res++
				}
			}
		}
	}
	return res
}

func isOrder(a, b, c int) bool {
	if a > b && b > c {
		return true
	}
	if a < b && b < c {
		return true
	}
	return false
}

2. 四个方向dfs  通过了百分之八十几,在选择路径时有问题,欢迎大佬指正。
package main

import "fmt"


func getMaximumResource( grid [][]int ) int {
	// 应该是dfs
	M := -1 << 10
	var dfs  func(i, j int) int
	dfs = func(i, j int) int {
		res := 0
		// 边界
		if i < 0 || j < 0 || i >= len(grid)  || j >= len(grid[0]){
			return 0
		}
		if grid[i][j] == 0 {
			return 0
		} else {
			// 四个方向
			res += grid[i][j]
			grid[i][j] = 0
			tmp := res 
            // 这里的选择有问题
			res = max(res, tmp + dfs(i-1, j))
			res = max(res, tmp + dfs(i+1, j))
			res = max(res, tmp + dfs(i, j-1))
			res = max(res, tmp + dfs(i, j+1))
		}
		return res
	}

	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			M = max(M, dfs(i, j))
		}
	}
	return M
}

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

func main() {
	grid := [][]int{{0,6,0},{5,8,7},{0,9,0}}
	fmt.Println(getMaximumResource(grid))
}



全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐