算法基础:最大递减数问题(Golang实现)

给出一个非负整数,找到这个非负整数中包括的最大递减数。一个数字的递减数是指相邻的数位从大到小排列的数字。 如: 95345323,递减数有:953,95,53,53,532,32, 那么最大的递减数为953。 假设输入的数字为负数,返回-1。 假设找不到递减数,也返回-1.

代码实现:

package huawei

import (
	"fmt"
	"sort"
	"strconv"
)

func Test5Base() {
	num := 431492
	degressiveNums := getDegressiveNums(num)

	max := -1
	if len(degressiveNums) > 0 {
		max = getMax(degressiveNums)
	}

	fmt.Println("max:", max)
}

//获取num的全部递减数
func getDegressiveNums(num int) []int {
	if num < 0 {
		return []int{-1}
	}

	degressiveNums := make([]int, 0)
	numStr := strconv.Itoa(num)
	length := len(numStr)
	//长度为i的子串
	for i := 2; i < length; i++ {
		//从j開始截取
		for j := 0; j < length-i+1; j++ {
			//截取数字
			n, err := strconv.Atoi(numStr[j : j+i])
			checkError(err, "string to integer")

			//是否为递减数
			if isDegressive(n) {
				degressiveNums = append(degressiveNums, n)
			}
		}
	}

	return degressiveNums
}

//推断数字num是否是递减数
func isDegressive(num int) bool {
	weishu := make([]int, 0)
	for num >= 1 {
		n := num % 10
		weishu = append(weishu, n)
		num /= 10
	}

	return sort.IntsAreSorted(weishu)
}

//获取一个slice中最大的数
func getMax(nums []int) int {
	if len(nums) == 0 {
		panic("empty slice.")
	}

	max := nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i] > max {
			max = nums[i]
		}
	}

	return max
}

原文发布于微信公众号 - Golang语言社区(Golangweb)

原文发表时间:2016-03-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

UOJ#52. 【UR #4】元旦激光炮(交互)

一种很显然的$log^2n$的做法:首先在$a$中二分,然后再$b,c$中二分。这样可以得到$60$分的好成绩。

8320
来自专栏数据结构与算法

洛谷P3807 【模板】卢卡斯定理exgcd

题目背景 这是一道模板题。 题目描述 给定n 求  保证P为prime C表示组合数。 一个测试点内包含多组数据。 输入输出格式 输入格式: 第一行...

40760
来自专栏ACM算法日常

迷宫问题(BFS问题) - POJ 3984

本题是新加入我们的大虾Gabriel童鞋写的,他是一个刚入大学的大一新生,孺子如虎也,赞!

36920
来自专栏算法与数据结构

PTA 数据结构 一元多项式求导 (仅供参考)

请勿粘贴 输入格式: 以指数递降方式输入多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。 输出格式: 以与输入相同的格式输出导数多项...

240100
来自专栏Java爬坑系列

C\C++ 生成各位数不相等的随机数

  最近想写一个1A2B的小游戏来练习一下,结果在第一步生成随机数的时候就遇到了一点点问题。   游戏初始化时需要先生成一个四位随机数,且各位各不相等。于是最开...

29770
来自专栏程序员互动联盟

【编程之美】最短路径

最短路径 任意给定两个数字A和B,通过将A和6个数(7,-7,5,-5,12,-12)做加减运算,运算次数不限,每个数可以被使用多次,求从A到B最少要经过多少次...

42460
来自专栏yl 成长笔记

时间复杂度的概念以及计算

The time complexity of an algorithm quantifies the amout of time taken by an alg...

17620
来自专栏人工智能LeadAI

pytorch入门教程 | 第一章:Tensor

1 pytorch安装 安装pytorch之前,需要安装好python,还没安装过python的宝宝请先移步到廖雪峰的python教程,待安装熟悉完之后,再过来...

450100
来自专栏小樱的经验随笔

洛谷P1313 计算系数【快速幂+dp】

P1313 计算系数 题目描述 给定一个多项式(by+ax)^k,请求出多项式展开后x^n*y^m 项的系数。 输入输出格式 输入格式: 输入文件名为facto...

22850
来自专栏landv

c语言_头文件

22930

扫码关注云+社区

领取腾讯云代金券