先从小到大选一波,再从大到小选一波,重复上述步骤,直到选完。
直接模拟一下。(数据量大的话不要直接用 +
拼接,效率太低,而且浪费内存)
func sortString (s string ) string { m := [26 ]uint8 {} for i := range s { m展开 收缩
-97 ]++ } var ans strings.Builder for i := 0 ; i < len (s); { for j := 0 ; j < 26 ; j++ { if m[j] > 0 { ans.WriteString(string (j+97 )) m[j]-- i++ } } for j := 25 ; j >= 0 ; j-- { if m[j] > 0 { ans.WriteString(string (j+97 )) m[j]-- i++ } } } return ans.String() }
给你一个字符串 s
,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 ‘a’,’e’,’i’,’o’,’u’ ,在子字符串中都恰好出现了偶数次(含 0 次)。
这题卡了很久,如果暴力做的话肯定会超时,这个状态表示太妙了。
每个元音字母出现次数是否为偶数次可用 0、1 来表示,那么 5 个元音字母就 32 个状态,其中题目要求的全为偶数次的状态——00000
。
如果 s[0…i]
与 s[0…j]
状态相同,那么 s[i+1...j]
的状态一定是 00000
。
由于求的是最长子串,那么记录一下每个状态出现的第一次位置,再次出现该状态时做差取最大值即可。
func findTheLongestSubstring (s string ) int { first := make ([]int , 32 ) for i := range first { first[i] = math.MinInt32 } first[0 ] = -1 ans, cur := 0 , 0 for i := range s { switch s[i] { case 'a' : cur ^= 1 case 'e' : cur ^= 2 case 'i' : cur ^= 4 case 'o' : cur ^= 8 case 'u' : cur ^= 16 } if first[cur] == math.MinInt32 { first[cur] = i } else { if i-first[cur] > ans { ans = i - first[cur] } } } return ans }
记录一下来源方向,交错路径加一,相同方向置零。
var maxLen int func longestZigZag (root *TreeNode) int { maxLen = 0 helper (root.Right, 0 , false ) helper (root.Left, 0 , true ) return maxLen } func helper (root *TreeNode, cnt int , dir bool ) { if root == nil { return } cnt++ if cnt > maxLen { maxLen = cnt } if dir { helper(root.Right, cnt, false ) helper(root.Left, 0 , true ) } else { helper(root.Left, cnt, true ) helper(root.Right, 0 , false ) } }
给你一棵树的根结点,请在符合二叉搜索树要求的子树中求出其最大键值和。
首先得判断该子树是否为二叉搜索树,记录下键值和,还要尽可能减少重复计算。
回顾一下,如何验证二叉搜索树。
func isValidBST (root *TreeNode) bool { return helper(root, nil , nil ) } func helper (root, min, max *TreeNode) bool { if root == nil { return true } if (min != nil && root.Val <= min.Val) || (max != nil && root.Val >= max.Val) { return false } return helper(root.Left, min, root) && helper(root.Right, root, max) }
改改代码就行了。
var ans int func maxSumBST (root *TreeNode) int { ans = 0 helper(root) return ans } func helper (root *TreeNode) (int , int , int , bool ) { if root == nil { return math.MinInt32, math.MaxInt32, 0 , true } lMax, lMin, lSum, lValid := helper(root.Left) rMax, rMin, rSum, rValid := helper(root.Right) sum, valid := 0 , false if lValid && rValid && lMax < root.Val && root.Val < rMin { sum = lSum + root.Val + rSum ans = max(ans, sum) valid = true } return max(rMax, root.Val), min(lMin, root.Val), sum, valid } func max (x, y int ) int { if x > y { return x } return y } func min (x, y int ) int { if x < y { return x } return y }
- By:wywwzjj.top
评论