这个就是
这道吧 关键在于理解虽然题目中限制同时进行异或操作的只能是相邻两个节点， 但实际上因为是连通图以及异或本身的性质（异或同一个数两次还是原来的数）可以通过多次异或将异或操作“传递”到远处的节点， 实际上是任意两个节点之间都能同时异或k。这样直接遍历所有节点，统计异或k后会变大的数并且把变大的数加和 ，变小的则保持不变加和。 奇数还要判断变大的增量和变小的减量，减少的多就让这个数不减少 保持原来的数， 增大的多就留增大的
1 个赞
我还是算了吧，这道题我题都看不懂。。。
没事 可以慢慢研究 多想想 你可以的
1 个赞
题解
本题如何求出所有组合并且保存以前计算过的组合的状态是关键, 考虑只有两个数的情况, 一共有三个组合, 1,2,1-2. 在此基础上考虑三个数的情况,会发现共有7种组合, 1,2,1-2,3,1-3,2-3,1-2-3. 可以注意到, 除了3自己这种情况外, 其余包含3的情况是将3和只有两个数的所有情况组合. 因此可以得出规律, 对于前n+1个数, 可以将包含前n个数的所有组合与第n+1个数组合, 再加上第n+1个数自身即为前n+1个数的所有组合. 用数组保存到当前位置的所有已经计算过的组合即可.
代码
func subsetXORSum(nums []int) int {
save_state := []int{}
result := 0
for _, value := range nums{
newstate := 0
for _, saved := range save_state{
newstate = value ^ saved
result += newstate
save_state = append(save_state, newstate)
}
result += value
save_state = append(save_state, value)
}
return result
}
1 个赞
更新
2 个赞
题解
本题在寻找全部的子数组的方法上和昨天题目的方法一致, 都是保存前n个数能构成的所有组合的集合,再与第n+1个数依次组合(空也算单独一个组合), 就得到了前n个数能构成的所有组合.
代码
func subsets(nums []int) [][]int {
result := [][]int{}
result = append(result, []int{})
for _, value := range nums{
for _, subset := range result{
newset := []int{}
newset = append(newset, subset...)
newset = append(newset, value)
result = append(result, newset)
}
}
return result
}
总结
还有一种通过dfs递归实现的方法也很有趣, 核心在于把握所有组合中原来数组中的数要么出现要么不出现, 那么就可以递归调用每次选择包含或者不包含下一个数, 通过将所有的包含与不包含组合, 就得到了所有的组合.
var res [][]int
func subsets(nums []int) [][]int {
res = nil
if len(nums) == 0 {
return res
}
var subset []int
dfs(subset, nums)
return res
}
func dfs(subset, nums []int) {
if len(nums) == 0 {
curr := make([]int, len(subset))
copy(curr, subset)
res = append(res, curr)
return
}
//include
included := append(subset, nums[0])
dfs(included, nums[1:])
//not include
dfs(subset, nums[1:])
}
2 个赞
更新
3 个赞
题解
本题需要枚举所有的子集分割并判断分割后的这些子集是否均为回文串. 这里可以使用回溯算法. 可以进行一些剪枝, 因为题目限制了所有字串都必须为回文串, 因此若产生的某个子串已经不是回文串则可以直接停止遍历其之后的串. 回溯算法可以使用递归实现. 本质上是一种深度优先搜索.
代码
func partition(s string) [][]string {
result := [][]string{}
if len(s) == 1{
return [][]string{[]string{s}}
}
for index, _ := range s[0:len(s)-1]{
head := s[0:index+1]
newtails := [][]string{}
if ispalin(head){
newtails = partition(s[index+1:])
for _, tail := range newtails{
newresult := []string{head}
newresult = append(newresult, tail...)
result = append(result, newresult)
}
}
}
if ispalin(s){
result = append(result, []string{s})
}
return result
}
func ispalin(s string) bool{
begin := 0
tail := len(s) - 1
for begin <= tail{
if s[begin] != s[tail]{
return false
}
begin++
tail--
}
return true
}
1 个赞
更新
2 个赞
佬你错过了每天+10
是新开帖可以+10嘛
1 个赞
学到了 明天试试 
1 个赞
看不懂咋办
慢慢理解 多花点时间 肯定行的 有耐心 一步步解析
4 个赞
这里也更新一下 方便日后整理 新帖太多可能不好整理
409. 最长回文串
题解
本题也是一道简单题, 最近几天的每日一题都比较简单, 因为是能组成的最长回文串, 与顺序无关, 因此只需统计字母个数即可. 遍历字符串并统计字母, 每当同一个字母有两个时就将结果加2并将字母个数重置为0. 遍历一遍后如果仍有字母剩余1个,则将结果加1表示奇数长度的回文串在中间添加的字母.
先统计全部字母的数量再最终求和会快一些, 减少了不必要的判断和加法操作.
代码
func longestPalindrome(s string) int {
charslice := make([]int,52)
for i,_ := range s{
if s[i] >= 'a'{
charslice[s[i]-'a']++
}else{
charslice[26+s[i]-'A']++
}
}
result := 0
odd := 0
for _,num := range charslice{
if num % 2 == 0{
result += num
}else{
result += num - 1
odd = 1
}
}
return result + odd
}
1 个赞
不会做啊
1 个赞
题解
本题也是一道简单题, 仍然是寻找在所有单词中都存在的字母, 重复的字母单独计算, 同样不要求顺序, 对于没有顺序要求的字符串问题, 计数往往是很好的解决方法, 因此只需依次遍历所有单词, 对单词中所有字母计数, 再与之前的字母计数比较, 取二者之间的较小值, 最后根据每个字母的计数个数输出答案即可. 注意题目限制字符串长度最多为100, 因此初始化为101保存字母个数的数组即可正常被更小的值刷新.
代码
func commonChars(words []string) []string {
beforechars := []int{101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101}
for _,word := range words{
nowchars := make([]int,26)
for i,_ := range word{
nowchars[word[i]-'a']++
}
for i,value := range nowchars{
beforechars[i] = min(beforechars[i],value)
}
}
fmt.Println(beforechars)
result := []string{}
for i,chars := range beforechars{
if chars > 0{
for chars>0{
result = append(result, string('a'+i))
chars--
}
}
}
return result
}
题解
因为要将数组中的数分为几组连续相邻的数且组内个数为groupSize大小, 显然每次都扫描整个数组寻找当前数字的下一个相邻数字效率极低, 所以可以先排序, 排序后数组中的数从小到大排列, 如果相邻的数存在应该在数组中是相邻的, 因此从头遍历排序后的数组, 依次将相邻的数放入一个groupSize大小的判别数组中并在数组中删掉放入的数, 遇到相同的数先继续向后遍历寻找下一个不同的相邻数字, 直到填满整个判别数组为止, 如果找不到相邻的数则可直接返回false. 填满判别数组后再从头遍历数组, 清空判别数组, 重复上述操作. 直到数组中没有数且判别数组刚好填满为止.
代码
func isNStraightHand(hand []int, groupSize int) bool {
sort.Ints(hand)
arrangelen := 0
current := 0
for len(hand) > 0{
arrangelen = 0
remaingroup := []int{}
current = hand[0]
for _, value := range hand{
if current == value && arrangelen < groupSize{
arrangelen++
hand = hand[1:]
current++
}else if arrangelen == groupSize{
break
}else{
if value == current - 1{
hand = hand[1:]
remaingroup = append(remaingroup, value)
}else{
return false
}
}
}
hand = append(remaingroup, hand...)
}
if arrangelen == groupSize{
return true
}else{
return false
}
}
总结
这种算法是可行的, 但由于大量的数组删除元素和数组连接操作, 使得实际耗时比较长. 本题还可以使用优先级队列(最小堆)来求解, 将元素全部放入最小堆中, 构造一个哈希表, 保存每个元素和其对应的元素个数. 每次从堆顶弹出一个元素, 即当前的最小元素, 如果弹出的元素不是相邻的数, 则返回false, 弹出后减少该元素在哈希表中对应的元素个数, 直到为0判断其前面是否还有其他更小的数, 如果有可直接返回false(这种情况下一定无法在group中再构成连续相邻的数了). 在函数开头可以先判断下数组的长度能否被groupSize整除, 不能直接返回false, 后面就可以不用再判断是否能填满最后一个group了. 开头的这个判断通过一些简单的方法过滤掉了不满足条件的解, 避免后续浪费时间对这些解进行判断, 做题时要先考虑一些这样可以通过简单判断排除不可行解的情况. 可以大大加快整体的运行效率.
type MinHeap []int
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func isNStraightHand(hand []int, groupSize int) bool {
if len(hand) % groupSize != 0 {
return false
}
h := MinHeap{}
heap.Init(&h)
hm := make(map[int]int)
for _, elem := range hand {
hm[elem]++
}
for key, _ := range hm {
heap.Push(&h,key)
}
for h.Len() > 0 {
startGroup := h[0]
for i := startGroup; i < startGroup + groupSize; i++ {
if _, ok := hm[i]; !ok {
return false
}
hm[i]--
if hm[i] == 0 {
if i != h[0] {
return false
}
heap.Pop(&h)
}
}
}
return true
}
3 个赞
牛逼牛逼这个学习力扣的方法，学习学习一下
1 个赞