公众号merlinsea
- leetcode链接
- 题目描述
- 给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
- 思路
- 假设给出的数字是43215，移除其中的一位使其变得更小，可以发现如果我们已出3、2、1、5中的任意一位，剩下的都是4开头的千位数，但如果移掉4可以使得剩下的是3开头的千位数，因此可以得到的结论是尽可能移调靠左边度数后使得下一位顶上来的数字小于被移除的数字
- 答案
func removeKdigits(num string, k int) string { if k == len(num) { return "0" } for k>0 { // 注意这里不能写出r,num := remove(num) // 因为 := 是会创建一个新地址的num变量，导致结果不正确！！ r,numStr := remove(num) if r{ k-- }else{ numStr = num[0:len(num)-k] k=0 } num = numStr } for len(num)>1 && num[0]=='0' { num = num[1:] } return num } func remove(num string) (bool,string){ var idx = -1 for i:=1;i<len(num);i++ { if num[i] < num[i-1]{ idx = i-1 break } } if idx == -1 { return false,num } var numStr = num[:idx] + num[idx+1:] return true,numStr }
- 面试题目
- 假设有一种36进制的加法，有效字符是0-9，a-z，请计算这种进制下的加法。
- 思路：参考10进制的加法，36进制的加法就是逢36进1，但需要我们设置一种转换规则可以把a-z对应到十进制，然后再进行计算。
package main import "fmt" var mp map[byte]int = make(map[byte]int) var mpr map[int]byte = make(map[int]byte) func main() { initMap() var r = cal("10a", "2xx") fmt.Println(r) } func initMap() { var k int = 0 for c := '0'; c <= '9'; c++ { mp[byte(c)] = k mpr[k] = byte(c) k++ } for c := 'a'; c <= 'z'; c++ { mp[byte(c)] = k mpr[k] = byte(c) k++ } } func cal(n string, m string) string { var r string = "" var i = len(n) - 1 var j = len(m) - 1 var bit byte = '0' for i >= 0 && j >= 0 { var res = add(n[i], m[j], bit) if len(res) == 2 { r = string(res[1]) + r bit = res[0] } else { r = string(res[0]) + r bit = '0' } i-- j-- } for i >= 0 { var res = add(n[i], '0', bit) r = string(res[1]) + r bit = res[0] i-- } for j >= 0 { var res = add(0, m[j], bit) r = string(res[1]) + r bit = res[0] j-- } if bit != '0' { r = string(bit) + r } return r } func add(x byte, y byte, bit byte) string { var str string = "" var res int = mp[x] + mp[y] + mp[bit] // 注意这里的res是大于0，而不是大于36！！！ for res > 0 { str = str + string(mpr[res%36]) res = res / 36 } return str }
