蚂蚁笔试9.15（Golang）
T1
T2
T3
#蚂蚁笔试#
一个b可以分裂为2个a，一个c可以分裂为两个b，以此类推
输入n（1<n<1000），表示a的个数，求最短可以分裂为n个a的字符串 AC
func Test1() {
m := 0
fmt.Scan(&m)
count:= []int{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024}
res := make([]byte, 0)
index := len(xy) - 1
for m > 0 {
for j := 0; j < m/count[index]; j++ {
res = append(res, byte('a'+index))
}
m %= count[index]
index--
}
fmt.Println(string(res))
} 编号为1的根节点，所有节点的权值默认为1，每次操作可以将以某个节点为根节点的子树全部节点权值+1，求让每个节点权值等于其编号的最小操作数
这个题目感觉如果树是1-3-2就无解，思考许久，不知道是不是我理解错了
func Test2() {
m := 0
fmt.Scan(&m)
edgs := make([][]int, m)
for i := 0; i < len(edgs); i++ {
edgs[i] = make([]int, 0)
}
for i := 0; i < m-1; i++ {
f, t := 0, 0
fmt.Scan(&f)
fmt.Scan(&t)
f--
t--
edgs[f] = append(edgs[f], t)
edgs[t] = append(edgs[t], f)
}
queue := make([]int, 0)
flags := make([]bool, m)
flags[0] = true
queue = append(queue, 0)
var res int64 = 0
for len(queue) != 0 {
size := len(queue)
for i := 0; i < size; i++ {
poll := queue[0]
for j := 0; j < len(edgs[poll]); j++ {
if !flags[edgs[poll][j]] {
if edgs[poll][j] > poll {
res += int64(edgs[poll][j] - poll)
}
flags[edgs[poll][j]] = true
queue = append(queue, edgs[poll][j])
}
}
queue = queue[1:]
}
}
fmt.Println(res)
} 题目：输入一个字符串，求其中只有一个字母出现奇数次的子串数目，比较经典的hashmap以及前缀应用题了，AC。
思路：以整数count（表示从0-i子串的前缀）的每一个二进制位标识在该字串中a-z每个字母出现的次数是奇数还是偶数，如果当前位为0，表示出现偶数次（包括0次），如果为1，表示出现奇数次。
例如count=6：110 表示a出现偶数次，b出现奇数次，c出现奇数次。
后续通过翻转count的每一位，来计算有多少个该位所表示的字母出现奇数的情况。
例如count=6：110，翻转第一位 111，此时110对比111的子串来说，就相当于多了一个a，表示a出现了奇数次，其他的字母出现偶数次（包括0次）
func Test3() {
str := ""
fmt.Scan(&str)
hash := make(map[int]int, 0)
count := 0
var res int64 = 0
hash[0] = 1
for i := 0; i < len(str); i++ {
count = count ^ (1 << (str[i] - 'a'))
for j := 0; j < 26; j++ {
temp := count ^ (1 << j)
if v, ok := hash[temp]; ok {
res += int64(v)
}
}
hash[count]++
}
fmt.Println(res)
} 
字节跳动公司氛围 556人发布