one question per day

2022-12-29

https://leetcode.cn/problems/two-out-of-three/;
逻辑，哈希；

// 2032: https://leetcode.cn/problems/two-out-of-three/
// 9:10 - 9:16
func twoOutOfThree(nums1 []int, nums2 []int, nums3 []int) []int {
 res := []int{}
 resMap := map[int]bool{}
 countMap1 := map[int]bool{}
 for _, v := range nums1 {
  countMap1[v] = true
 }
 countMap2 := map[int]bool{}
 for _, v := range nums2 {
  countMap2[v] = true
 }
 countMap3 := map[int]bool{}
 for _, v := range nums3 {
  countMap3[v] = true
 }
 for _, v := range nums1 {
  if countMap2[v] || countMap3[v] {
   resMap[v] = true
  }
 }
 for _, v := range nums2 {
  if countMap1[v] || countMap3[v] {
   resMap[v] = true
  }
 }
 for key := range resMap {
  res = append(res, key)
 }
 return res
}

func main() {

 nums1 := []int{1, 1, 3, 2}
 nums2 := []int{2, 3}
 nums3 := []int{3}
 fmt.Println(twoOutOfThree(nums1, nums2, nums3))
}

2022-12-28

https://leetcode.cn/problems/minimum-length-of-string-after-deleting-similar-ends/;
逻辑，双指针；

package main

import "fmt"

// 1750: https://leetcode.cn/problems/minimum-length-of-string-after-deleting-similar-ends/
// 9:36 - 9:44
func minimumLength(s string) int {
 left, right := 0, len(s)-1
 for left < right {
  if s[left] != s[right] {
   return right - left + 1
  }
  leftCur := left
  for leftCur+1 < right && s[leftCur+1] == s[left] {
   leftCur++
  }
  rightCur := right
  for rightCur-1 > left && s[rightCur-1] == s[right] {
   rightCur--
  }
  if leftCur < rightCur {
   left = leftCur + 1
   right = rightCur - 1
  } else {
   return 0
  }
 }
 return right - left + 1
}

func main() {
 // s := "cabaabac"
 s := "ca"
 fmt.Println(minimumLength(s))
}

2022-12-16

package main

import "fmt"

// 1785: https://leetcode.cn/problems/minimum-elements-to-add-to-form-a-given-sum/
// 9:39- 09:46
func minElements(nums []int, limit int, goal int) int {
 sum := 0
 for _, v := range nums {
  sum += v
 }
 gap := goal - sum
 if gap < 0 {
  gap = -gap
 }
 if gap == 0 {
  return 0
 }
 // fmt.Println(gap, gap/limit)
 res := gap / limit
 if gap%limit > 0 {
  res += 1
 }
 return res
}

func main() {
 nums, limit, goal := []int{1, -1, 1}, 3, -4
 fmt.Println(minElements(nums, limit, goal))
}

2022-12-15

package main

import (
 "fmt"
 "strconv"
 "strings"
)

// 1945: https://leetcode.cn/problems/sum-of-digits-of-string-after-convert/
// 09:37- 09:53

func getLucky(s string, k int) int {
 t := []string{}
 for _, v := range s {
  t = append(t, strconv.Itoa(int(v-'a'+1)))
 }
 curStr := strings.Join(t[:], "")
 for i := 1; i <= k && len(curStr) > 1; i++ {
  sum := 0
  for _, c := range curStr {
   sum += int(c - '0')
  }
  curStr = strconv.Itoa(sum)
 }
 // fmt.Println(curStr)
 ans, _ := strconv.Atoi(curStr)
 return ans
}

func main() {
 s, k := "iiii", 1
 ans := getLucky(s, k)
 fmt.Printf("%v", ans)
}

2022-12-13

https://leetcode.cn/problems/check-if-the-sentence-is-pangram/;
逻辑，哈希；

package main

import "fmt"

// 1832: https://leetcode.cn/problems/check-if-the-sentence-is-pangram/
// 13:38 - 13:42
func checkIfPangram(sentence string) bool {
 countMap := map[rune]bool{}
 for _, v := range sentence {
  countMap[v] = true
 }
 return len(countMap) == 26

}

func main() {
 // sentence := "thequickbrownfoxjumpsoverthelazydog"
 sentence := "leetcode"
 fmt.Println(checkIfPangram(sentence))
 // fmt.Println(ans)
}

2022-12-08

package main;
func squareIsWhite(coordinates string) bool {
 d1 := byte(coordinates[0]) - byte('a')
 d2 := byte(coordinates[1]) - byte('1')
 // fmt.Println(d1, d2)
 return (d1%2 == 0 && d2%2 == 1) || (d1%2 == 1 && d2%2 == 0)
}

func main() {
 coordinates := "a1"
 ans := squareIsWhite(coordinates)
 fmt.Printf("%v", ans)
}

2022-12-07

https://leetcode.cn/problems/equal-sum-arrays-with-minimum-number-of-operations/description/;
贪心，哈希计数；

package main

// 1775: https://leetcode.cn/problems/equal-sum-arrays-with-minimum-number-of-operations/
// 09:42- 09:54;
func minOperations(nums1 []int, nums2 []int) int {
 if 6*len(nums1) < len(nums2) || 6*len(nums2) < len(nums1) {
  return -1
 }
 d := 0
 for _, x := range nums2 {
  d += x
 }
 for _, x := range nums1 {
  d -= x
 }
 if d < 0 {
  d = -d
  nums1, nums2 = nums2, nums1
 }
 cnt := [6]int{}
 for _, x := range nums1 {
  cnt[6-x]++
 }
 for _, x := range nums2 {
  cnt[x-1]++
 }
 ans := 0
 for i := 5; ; i-- {
  if i*cnt[i] >= d {
   return ans + (d+i-1)/i
  }
  ans += cnt[i]
  d -= i * cnt[i]
 }
 // return ans
 return ans
}

func main() {
 nums1 := []int{1, 2, 3, 4, 5, 6}
 nums2 := []int{1, 1, 2, 2, 2, 2}
 fmt.Println(minOperations(nums1, nums2))
 // fmt.Println(ans)
}

2022-11-29

package main

import "fmt"

func minOperations(s string) int {
 res := len(s)
 arr := []byte{'0', '1'}
 for i := 0; i < 2; i++ {
  temp := 0
  for j := 0; j < len(s); j++ {
   if j%2 == 0 && s[j] == arr[i%2] {
    temp++
   }
   if j%2 == 1 && s[j] == arr[(i+1)%2] {
    temp++
   }
  }
  if temp < res {
   res = temp
  }

 }

 return res
}

func main() {
 s := "0100"
 // s := "1111"
 ans := minOperations(s)
 fmt.Printf("%v", ans)
}

2022-11-28

https://leetcode.cn/problems/largest-sum-of-averages/description/
前缀和，递归，剪枝；

package main

import "fmt"

// 9:33- 10:02
func largestSumOfAverages(nums []int, k int) float64 {
 res := float64(-1)
 targetSum := make([]int, len(nums))
 for i, v := range nums {
  if i == 0 {
   targetSum[0] = v
  } else {
   targetSum[i] = v + targetSum[i-1]
  }
 }
 var getScopeSum func(left, right int) int
 getScopeSum = func(left, right int) int {
  return targetSum[right] - targetSum[left] + nums[left]
 }
 var getScopeAverage func(left, right int) float64
 getScopeAverage = func(left, right int) float64 {
  // fmt.Println(left, right, sum, right-left+1, sum/(float64((right - left + 1))))
  return float64(getScopeSum(left, right)) / (float64((right - left + 1)))
 }

 var dfs func(index, count int, sum float64)
 dfs = func(index, count int, sum float64) {
  if count == k && index == len(nums) {
   res = max(res, sum)
   return
  } else if index >= len(nums) {
   return
  } else if count >= k {
   return
  }
  if count == k-1 {
   tempSum := sum + getScopeAverage(index, len(nums)-1)
   dfs(len(nums), k, tempSum)
  } else {
   for i := index; i < len(nums)-1; i++ {
    dfs(i+1, count+1, sum+getScopeAverage(index, i))
   }
  }
 }
 dfs(0, 0, 0)
 return res
}

func max(a, b float64) float64 {
 if a < b {
  return b
 }
 return a
}

func main() {
 // nums := []int{9, 1, 2, 3, 9}
 // k := 3
 // nums := []int{1, 2, 3, 4, 5, 6, 7}
 // k := 4
 nums := []int{7769, 5973, 2106, 45, 9869, 1196, 8869}
 k := 1

 fmt.Println(largestSumOfAverages(nums, k))
 // fmt.Println(ans)
}

2022-11-27

package main

import "fmt"

func check(nums []int) bool {
 curIndex := -1
 for i := range nums {
  if i+1 < len(nums) && nums[i] > nums[i+1] {
   curIndex = i + 1
   break
  }
 }
 if curIndex == -1 {
  return true
 }
 curNums := []int{}
 curNums = append(curNums, nums[curIndex:]...)
 curNums = append(curNums, nums[0:curIndex]...)
 for i := range curNums {
  if i+1 < len(curNums) && curNums[i] > curNums[i+1] {
   return false
  }
 }
 return true
}

func main() {
 nums := []int{3, 4, 5, 1, 2}
 // nums := []int{2, 1, 3, 4}
 // nums := []int{1, 3, 4}
 // nums := []int{2, 4, 1, 3}
 fmt.Println(check(nums))
}

2022-11-25

https://leetcode.cn/problems/expressive-words/description/;
逻辑，计数；

package main

import "fmt"

type Res struct {
 char  byte
 count int
}

func getWordCount(s string) []Res {
 res := []Res{}
 for i := 0; i < len(s); {
  tempRes := Res{
   char:  s[i],
   count: 1,
  }
  j := i + 1
  for ; j < len(s); j++ {
   if s[j] != tempRes.char {
    break
   }
   tempRes.count++
  }
  res = append(res, tempRes)
  i = j
 }
 return res
}

func judgeTwoStruct(res1 []Res, res2 []Res) bool {
 if len(res1) != len(res2) {
  return false
 }
 for i := range res1 {
  c2 := res2[i].count
  c1 := res1[i].count
  // fmt.Println(c1, c2)
  if res1[i].char != res2[i].char {
   return false
  }
  if !((c1 == c2) || (c2 < c1 && c1 >= 3)) {
   // fmt.Println("----", c2, c1, res2)
   return false
  }
 }
 return true
}

func expressiveWords(s string, words []string) int {
 initialStruc := getWordCount(s)
 // fmt.Println(initialStruc)
 res := 0
 for i := range words {
  tempStruc := getWordCount(words[i])
  // fmt.Println(tempStruc)
  if judgeTwoStruct(initialStruc, tempStruc) {
   res++
  }
 }
 return res
}

func main() {
 // S := "heeellooo"
 // fmt.Printf("%v", getWordCount(S))
 // words := []string{"hello", "hi", "helo"}
 S := "dddiiiinnssssssoooo"
 words := []string{"dinnssoo", "ddinso", "ddiinnso", "ddiinnssoo", "ddiinso", "dinsoo", "ddiinsso", "dinssoo", "dinso"}
 ans := expressiveWords(S, words)
 fmt.Printf("%v", ans)
}

2022-11-24

https://leetcode.cn/problems/number-of-subarrays-with-bounded-maximum/description/;
计数，逻辑；

package main

import "fmt"

// 9:05- 9:29

func numSubarrayBoundedMax(nums []int, left int, right int) int {
 res := 0
 last2, last1 := -1, -1
 for i, x := range nums {
  if left <= x && x <= right {
   last1 = i
  } else if x > right {
   last2 = i
   last1 = -1
  }
  if last1 != -1 {
   res += last1 - last2
  }
 }
 return res
}

func main() {
 // nums := []int{2, 1, 4, 3}
 // left := 2
 // right := 3
 nums := []int{2, 9, 2, 5, 6}
 left := 2
 right := 8
 ans := numSubarrayBoundedMax(nums, left, right)
 fmt.Printf("%v", ans)
}

2022-11-23

https://leetcode.cn/problems/maximum-number-of-balls-in-a-box/solutions/;
基本逻辑，哈希记数；

package main

import "fmt"

// 9:30- 9:36

func getNumBitSum(target int) int {
 res := 0
 cur := target
 for cur > 0 {
  res += cur % 10
  cur = cur / 10
 }
 return res
}

func countBalls(lowLimit int, highLimit int) int {
 max := 0
 countMap := map[int]int{}
 for i := lowLimit; i <= highLimit; i++ {
  temp := getNumBitSum(i)
  countMap[temp]++
  if countMap[temp] > max {
   max = countMap[temp]
  }
 }
 return max
}

func main() {
 // lowLimit := 1
 // highLimit := 10
 lowLimit := 5
 highLimit := 15
 ans := countBalls(lowLimit, highLimit)
 fmt.Printf("%v", ans)
}

2022-11-22

https://leetcode.cn/problems/nth-magical-number/description/;
数学和二分查找；

package main

import "fmt"

func min(a, b int) int {
 if a < b {
  return a
 }
 return b
}

func gcd(a, b int) int {
 if b != 0 {
  return gcd(b, a%b)
 }
 return a
}

const mod int = 1e9 + 7

func nthMagicalNumber(n int, a int, b int) int {
 l := min(a, b)
 r := n * min(a, b)
 c := a / gcd(a, b) * b
 for l <= r {
  mid := (l + r) / 2
  cnt := mid/a + mid/b - mid/c
  if cnt >= n {
   r = mid - 1
  } else {
   l = mid + 1
  }
 }
 return (r + 1) % mod
}

func main() {
 ans := nthMagicalNumber(1, 2, 3)
 fmt.Printf("%v", ans)
}

2022-11-21

https://leetcode.cn/problems/soup-servings/solutions/;
动态规划和记忆化搜索；

package main

import "fmt"

func soupServings(n int) float64 {
 n = (n + 24) / 25
 if n >= 179 {
  return 1
 }
 dp := make([][]float64, n+1)
 for i := range dp {
  dp[i] = make([]float64, n+1)
 }
 dp[0][0] = 0.5
 for i := 1; i <= n; i++ {
  dp[0][i] = 1
 }
 for i := 1; i <= n; i++ {
  for j := 1; j <= n; j++ {
   dp[i][j] = (dp[max(0, i-4)][j] + dp[max(0, i-3)][max(0, j-1)] + dp[max(0, i-2)][max(0, j-2)] + dp[max(0, i-1)][max(0, j-3)]) / 4
  }
 }
 return dp[n][n]
}

func max(a, b int) int {
 if b > a {
  return b
 }
 return a
}

func main() {
 fmt.Println(soupServings(50))
}

2022-09-07

https://leetcode.cn/problems/rearrange-spaces-between-words/;
基础逻辑；

package main

import (
 "fmt"
 "strings"
)

// 1592: https://leetcode.cn/problems/rearrange-spaces-between-words/
// 10:50 - 10:56;
func reorderSpaces(text string) string {
 words := strings.Fields(text)
 spaceNum := strings.Count(text, " ")
 lw := len(words) - 1
 if lw == 0 {
  return words[0] + strings.Repeat(" ", spaceNum)
 }
 return strings.Join(words, strings.Repeat(" ", spaceNum/lw)) + strings.Repeat(" ", spaceNum%lw)
}

func main() {
 text := "  this   is  a sentence "
 fmt.Println(reorderSpaces(text))
 // fmt.Println(ans)
}

2022-08-05

https://leetcode.cn/problems/k-radius-subarray-averages/;
逻辑，滑动窗口；

package main

import "fmt"

// 2090: https://leetcode.cn/problems/k-radius-subarray-averages/
// 10:58 - 11:10;

func getAverages(nums []int, k int) []int {
 if k == 0 {
  return nums
 }
 if len(nums) < 2*k+1 {
  ans := []int{}
  for i := 0; i < len(nums); i++ {
   ans = append(ans, -1)
  }
  return ans
 }
 ans := []int{}

 currentSum := 0
 for i := 0; i < 2*k+1; i++ {
  currentSum += nums[i]
 }
 for i := 0; i < len(nums); i++ {
  if i < k {
   ans = append(ans, -1)
  } else if i == k {
   ans = append(ans, currentSum/(2*k+1))
  } else if len(nums)-i > k {
   currentSum = currentSum + nums[i+k] - nums[i-k-1]
   ans = append(ans, currentSum/(2*k+1))
  } else {
   ans = append(ans, -1)
  }
 }
 return ans
}

func main() {
 nums := []int{7, 4, 3, 9, 1, 8, 5, 2, 6}
 k := 3
 // nums := []int{100000}
 // k := 0
 // nums := []int{8}
 // k := 1000000
 fmt.Println(getAverages(nums, k))
 // fmt.Println(ans)
}

2022-08-04

https://leetcode.cn/problems/minimum-subsequence-in-non-increasing-order/;
逻辑，贪心，排序；

package main

import (
 "fmt"
 "sort"
)

// 1403:https://leetcode.cn/problems/minimum-subsequence-in-non-increasing-order/
// 12:03 - 12:08

func minSubsequence(nums []int) []int {
 tempNums := append([]int{}, nums...)
 sort.Ints(tempNums)
 sum := 0
 for _, v := range tempNums {
  sum += v
 }
 ans := []int{}
 tempCount := 0
 for i := len(tempNums) - 1; i >= 0; i-- {
  if tempCount > sum-tempCount {
   break
  }
  ans = append(ans, tempNums[i])
  tempCount += tempNums[i]
 }

 // fmt.Println(tempNums)
 return ans
}

func main() {
 // nums := []int{4, 3, 10, 9, 8}
 // nums := []int{4, 4, 7, 6, 7}
 nums := []int{6}
 fmt.Println(minSubsequence(nums))
 // fmt.Println(ans)
}

2022-08-03

https://leetcode.cn/problems/minimize-the-difference-between-target-and-chosen-elements/
dfs,动态规划；

package main

// 1981: https://leetcode.cn/problems/minimize-the-difference-between-target-and-chosen-elements/
// 9:39 - 9: 52

func minimizeTheDifference(mat [][]int, target int) int {
 if len(mat) == 0 {
  return target
 }
 ans := 1000000
 row := len(mat)
 col := len(mat[0])
 var dfs func(index int, current int)
 dfs = func(index int, current int) {
  if current > target && abs(current-target) > ans {
   return
  }
  if index == row {
   // fmt.Println(index, current, ans)
   if abs(current-target) < ans {
    ans = abs(current - target)
   }
   return
  }
  for i := 0; i < col; i++ {
   dfs(index+1, current+mat[index][i])
  }
 }
 dfs(0, 0)
 return ans
}

func abs(a int) int {
 if a < 0 {
  return -a
 }
 return a
}

2022-07-29

https://leetcode.cn/problems/valid-square/;
逻辑，几何知识；

package main

import (
 "fmt"
 "math"
)

// 593: https://leetcode.cn/problems/valid-square/
// 9:21 - 9:38

func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
 var getTwoPointRatio func([]int, []int) float64
 getTwoPointRatio = func(p1 []int, p2 []int) float64 {
  if p1[0] == p2[0] {
   return -1

  }
  return float64(p1[1]-p2[1]) / float64(p1[0]-p2[0])
 }
 var getTwoPointDistance func([]int, []int) float64
 getTwoPointDistance = func(p1 []int, p2 []int) float64 {
  return math.Sqrt(float64(p1[0]-p2[0])*float64(p1[0]-p2[0]) + float64(p1[1]-p2[1])*float64(p1[1]-p2[1]))
 }

 // fmt.Println(getTwoPointRatio(p1, p2), getTwoPointRatio(p3, p4), getTwoPointRatio(p1, p3), getTwoPointRatio(p2, p4))
 // p1 和 p2 是邻边；
 if getTwoPointRatio(p1, p2) == getTwoPointRatio(p3, p4) && getTwoPointDistance(p1, p2) == getTwoPointDistance(p3, p4) {
  edge := getTwoPointDistance(p1, p2)
  possible1 := getTwoPointDistance(p1, p3)
  possible2 := getTwoPointDistance(p1, p4)
  if edge == possible1 || edge == possible2 {
   return true
  }
 }
 // p1 和 p3 是邻边；
 if getTwoPointRatio(p1, p3) == getTwoPointRatio(p2, p4) && getTwoPointDistance(p1, p3) == getTwoPointDistance(p2, p4) {
  edge := getTwoPointDistance(p1, p3)
  possible1 := getTwoPointDistance(p1, p2)
  possible2 := getTwoPointDistance(p1, p4)
  if edge == possible1 || edge == possible2 {
   return true
  }
 }
 return false
}

func main() {
 p1 := []int{0, 0}
 p2 := []int{1, 1}
 p3 := []int{1, 0}
 p4 := []int{0, 1}
 // two
 // p1 := []int{0, 0}
 // p2 := []int{1, 1}
 // p3 := []int{1, 0}
 // p4 := []int{0, 12}
 // // three
 // p1 := []int{1, 0}
 // p2 := []int{-1, 0}
 // p3 := []int{0, 1}
 // p4 := []int{0, -1}
 // three
 // p1 := []int{0, 0}
 // p2 := []int{5, 0}
 // p3 := []int{5, 4}
 // p4 := []int{0, 4}
 fmt.Println(validSquare(p1, p2, p3, p4))
 // fmt.Println(ans)
}

2022-07-28

https://leetcode.cn/problems/rank-transform-of-an-array/;
逻辑，哈希，排序；

package main

import (
 "fmt"
 "sort"
)

// 1331: https://leetcode.cn/problems/rank-transform-of-an-array/
// 9:37 - 9:46

func arrayRankTransform(arr []int) []int {
 tempArr := []int{}
 tempMap := map[int]int{}
 for _, v := range arr {
  if _, ok := tempMap[v]; !ok {
   tempMap[v] = 1
   tempArr = append(tempArr, v)
  }
 }
 // fmt.Println(tempArr)
 sort.Slice(tempArr, func(a, b int) bool {
  return tempArr[a] < tempArr[b]
 })
 // fmt.Println(tempArr)
 for i, v := range tempArr {
  tempMap[v] = i + 1
 }
 result := []int{}
 for _, v := range arr {
  result = append(result, tempMap[v])
 }
 return result
 // return []int{1}
}

func main() {
 arr := []int{40, 10, 20, 30, 10}
 fmt.Println(arrayRankTransform(arr))
 // fmt.Println(ans)
}

2022-07-27

https://leetcode.cn/problems/fraction-addition-and-subtraction/;
逻辑，求最大公约数；

package main

import (
 "fmt"
 "unicode"
)

// 592: https://leetcode.cn/problems/fraction-addition-and-subtraction/
// 9:32 - 9:49

func fractionAddition(expression string) string {
 denominator, numberator := 0, 1
 for i, n := 0, len(expression); i < n; {
  // 读取分子
  denominator1, sign := 0, 1
  if expression[i] == '-' || expression[i] == '+' {
   if expression[i] == '-' {
    sign = -1
   }
   i++
  }
  for i < n && unicode.IsDigit(rune(expression[i])) {
   denominator1 = denominator1*10 + int(expression[i]-'0')
   i++
  }
  denominator1 = sign * denominator1
  // 读取分母
  i++
  numberator1 := 0
  for i < n && unicode.IsDigit(rune(expression[i])) {
   numberator1 = numberator1*10 + int(expression[i]-'0')
   i++
  }
  denominator = denominator*numberator1 + denominator1*numberator
  numberator = numberator * numberator1
 }
 if denominator == 0 {
  return "0/1"
 }
 g := gcd(abs(denominator), numberator)
 // fmt.Println(denominator, numberator, g)
 return fmt.Sprintf("%d/%d", denominator/g, numberator/g)
 // return ""
}

func gcd(a, b int) int {
 if a >= b {
  a, b = b, a
 }
 if a != 0 {
  a, b = b%a, a
 }
 return b
}

func abs(x int) int {
 if x < 0 {
  return -x
 }
 return x
}

func main() {
 // expression := "-1/2+1/2"
 // expression := "-1/2+1/2+1/3"
 // expression := "1/3-1/2"
 expression := "5/3+1/3"
 ans := fractionAddition(expression)
 fmt.Println(ans)
}

2022-07-18

https://leetcode.cn/problems/design-linked-list/;
链表；

package main

import "fmt"

// 707: https://leetcode.cn/problems/design-linked-list/
// 10:24 - 10:48

type Node struct {
 val  int
 next *Node
}

type MyLinkedList struct {
 head *Node
 size int
}

func Constructor() MyLinkedList {
 dummyHead := &Node{
  val:  -1,
  next: nil,
 }
 return MyLinkedList{head: dummyHead, size: 0}

}

func (this *MyLinkedList) Get(index int) int {
 if index < 0 || index >= (this.size-1) {
  return -1
 }
 var cur *Node = this.head
 for i := 0; i <= index; i++ {
  cur = cur.next
 }
 return cur.val
}

func (this *MyLinkedList) AddAtHead(val int) {
 newNode := &Node{val: val, next: nil}
 newNode.next = this.head.next
 this.head.next = newNode
 this.size++
}

func (this *MyLinkedList) AddAtTail(val int) {
 newNode := &Node{val: val, next: nil}
 cur := this.head
 for cur.next != nil {
  cur = cur.next
 }
 cur.next = newNode
 this.size++

}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
 if index > this.size {
  return
 }
 if index == this.size {
  this.AddAtTail(val)
  return
 }
 newNode := &Node{val: val, next: nil}
 cur := this.head
 for i := 0; i < index; i++ {
  cur = cur.next
 }
 newNode.next = cur.next
 cur.next = newNode
 this.size++
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
 if index > this.size-1 || index < 0 {
  return
 }
 cur := this.head
 for i := 0; i < index; i++ {
  cur = cur.next
 }
 cur.next = cur.next.next
 this.size--

}

func main() {
 obj := Constructor()
 obj.AddAtHead(1)
 obj.AddAtTail(3)
 obj.AddAtIndex(1, 2)
 fmt.Println(obj.head, obj.head.next, obj.head.next.next, obj.head.next.next.next)
 fmt.Println(obj.Get(1))
}

2022-07-01

https://leetcode.cn/problems/cells-with-odd-values-in-a-matrix/;
基础逻辑；

package main

import "fmt"

// 1252: https://leetcode.cn/problems/cells-with-odd-values-in-a-matrix/
// 10:38- 10:48
func oddCells(m int, n int, indices [][]int) int {
 xMap := map[int]int{}
 yMap := map[int]int{}
 for _, v := range indices {
  xMap[v[0]]++
  yMap[v[1]]++
 }
 // fmt.Println(xMap, yMap)
 ans := 0
 for i := 0; i < m; i++ {
  for j := 0; j < n; j++ {
   count := xMap[i] + yMap[j]
   if count%2 == 1 {
    ans++
   }
  }

 }
 return ans
}

func main() {
 m := 2
 n := 3
 indices := [][]int{{0, 1}, {1, 1}}
 ans := oddCells(m, n, indices)
 fmt.Println(ans)
 // fmt.Println(ans)
}

2022-06-22

package main

import "fmt"

type TreeNode struct {
 Val   int
 Left  *TreeNode
 Right *TreeNode
}

// 513: https://leetcode.cn/problems/find-bottom-left-tree-value/
// 11:35 - 11:40
func findBottomLeftValue(root *TreeNode) int {
 if root == nil {
  return 0
 }
 queue := []*TreeNode{root}
 ans := 0
 for len(queue) > 0 {
  tempQueue := []*TreeNode{}
  ans = queue[0].Val
  for _, node := range queue {
   if node.Left != nil {
    tempQueue = append(tempQueue, node.Left)
   }
   if node.Right != nil {
    tempQueue = append(tempQueue, node.Right)
   }
  }
  queue = tempQueue
 }
 return ans
}

func main() {
 root := &TreeNode{
  Val:   1,
  Left:  &TreeNode{Val: 2},
  Right: &TreeNode{Val: 3},
 }
 ans := findBottomLeftValue(root)
 fmt.Println(ans)
 // fmt.Println(ans)
}

2022-06-19

https://leetcode.cn/problems/most-frequent-subtree-sum/;
递归，后序遍历；

package main

import "fmt"

// 508: https://leetcode.cn/problems/most-frequent-subtree-sum/
// 11:21 - 11:32

type TreeNode struct {
 Val   int
 Left  *TreeNode
 Right *TreeNode
}

func findFrequentTreeSum(root *TreeNode) []int {
 countMap := map[int]int{}
 var dfs func(node *TreeNode) int
 dfs = func(root *TreeNode) int {
  if root == nil {
   return 0
  }
  leftTreeSum := dfs(root.Left)
  rightTreeSum := dfs(root.Right)
  sum := leftTreeSum + rightTreeSum + root.Val
  countMap[sum]++
  return sum
 }
 dfs(root)
 // fmt.Println(countMap)
 maxCount := 0
 ans := []int{}
 for key, count := range countMap {
  if count > maxCount {
   maxCount = count
   ans = []int{key}
  } else if count == maxCount {
   ans = append(ans, key)
  }
 }

 return ans
}

func main() {

 tree := &TreeNode{Val: 5, Left: &TreeNode{Val: 2}, Right: &TreeNode{Val: -3}}
 fmt.Println(findFrequentTreeSum(tree))
 // fmt.Println(ans)
}

2022-06-16

https://leetcode.cn/problems/k-diff-pairs-in-an-array/;
哈希；

package main

import (
 "fmt"
 "sort"
)

// 532: https://leetcode.cn/problems/k-diff-pairs-in-an-array/
// 8:18 - 8:25

func findPairs(nums []int, k int) int {
 valueMap := make(map[int]int)
 for _, v := range nums {
  valueMap[v]++
 }
 keyArr := []int{}
 for k := range valueMap {
  keyArr = append(keyArr, k)
 }
 sort.Ints(keyArr)
 // fmt.Printf("%v", keyArr)
 ans := 0
 for _, v := range keyArr {
  nextValue := v + k
  if nextValue != v && valueMap[nextValue] > 0 {
   ans += 1
  }
  if nextValue == v && valueMap[nextValue] > 1 {
   // fmt.Print(nextValue, valueMap[nextValue], ans)
   ans += 1
  }
 }
 return ans
}

func main() {
 // nums := []int{3, 1, 4, 1, 5}
 // k := 2

 nums := []int{1, 2, 3, 4, 5}
 k := 1

 // nums := []int{1, 1, 3, 4, 5}
 // k := 0

 ans := findPairs(nums, k)
 fmt.Println(ans)
}

2022-06-14

https://leetcode.cn/problems/diagonal-traverse/;
基本逻辑，这个很好；

package main

import "fmt"

// 498: https://leetcode.cn/problems/diagonal-traverse/
// 10:46 - 11:07

func findDiagonalOrder(mat [][]int) []int {
 ans := []int{}
 row := len(mat)
 col := len(mat[0])
 // fmt.Println(row, col)
 for i := 0; i < row+col-1; i++ {
  if i%2 == 1 {
   x := max(i-col+1, 0)
   y := min(i, col-1)
   for x < row && y >= 0 {
    ans = append(ans, mat[x][y])
    x++
    y--
   }
  } else {
   x := min(i, row-1)
   y := max(i-row+1, 0)
   for x >= 0 && y < col {
    ans = append(ans, mat[x][y])
    x--
    y++
   }
  }
 }
 return ans
}

func min(a, b int) int {
 if a > b {
  return b
 }
 return a
}

func max(a, b int) int {
 if b > a {
  return b
 }
 return a
}

func main() {
 mat := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
 ans := findDiagonalOrder(mat)
 fmt.Println(ans)
}

2022-06-13

https://leetcode.cn/problems/height-checker/;
基本逻辑；

package main

import (
 "fmt"
 "sort"
)

// 1051: https://leetcode.cn/problems/height-checker/
// 11:17- 11:24

func heightChecker(heights []int) int {
 arr := []int{}
 arr = append(arr, heights...)
 sort.Ints(arr)
 // fmt.Println(arr, heights)
 ans := 0
 for i := 0; i < len(arr); i++ {
  // fmt.Println(heights[i], arr[i])
  if heights[i] != arr[i] {
   ans++
  }
 }
 return ans
}

func main() {
 // matchsticks := []int{1, 1, 2, 2, 2}
 heights := []int{1, 1, 4, 2, 1, 3}
 ans := heightChecker(heights)
 fmt.Println(ans)
}

2022-06-09

https://leetcode.cn/problems/random-point-in-non-overlapping-rectangles/
前缀和+二分法；

package main

import (
 "fmt"
 "math/rand"
 "sort"
)

// 497: https://leetcode.cn/problems/random-point-in-non-overlapping-rectangles/
// 11:05- 11:27

type Solution struct {
 rects [][]int
 sum   []int
}

func Constructor(rects [][]int) Solution {
 sum := make([]int, len(rects)+1)
 for i, r := range rects {
  a, b, x, y := r[0], r[1], r[2], r[3]
  sum[i+1] = sum[i] + (y-b+1)*(x-a+1)
 }
 return Solution{rects, sum}
}

func (s *Solution) Pick() []int {
 k := rand.Intn(s.sum[len(s.sum)-1])
 rectIndex := sort.SearchInts(s.sum, k+1) - 1
 r := s.rects[rectIndex]
 a, b, y := r[0], r[1], r[3]
 da := (k - s.sum[rectIndex]) / (y - b + 1)
 db := (k - s.sum[rectIndex]) % (y - b + 1)
 return []int{a + da, b + db}
}

func main() {
 // matchsticks := []int{1, 1, 2, 2, 2}
 s := Constructor([][]int{{-2, -2, 1, 1}, {2, 2, 4, 6}})
 fmt.Println(s)
 fmt.Println(s.Pick())
 // fmt.Println(s)
}

2022-06-01

https://leetcode.cn/problems/matchsticks-to-square/
技巧:回溯法；

package main

import (
 "fmt"
 "sort"
)

// 473:https://leetcode.cn/problems/matchsticks-to-square/
// 9:57 - 10:25

func makesquare(matchsticks []int) bool {
 sum := 0
 for _, i := range matchsticks {
  sum += i
 }
 if sum%4 != 0 {
  return false
 }
 edge := sum / 4
 for _, i := range matchsticks {
  if i > edge {
   return false
  }
 }
 // fmt.Println(sum)
 nums := append([]int{}, matchsticks...)
 sort.Sort(sort.Reverse(sort.IntSlice(nums)))
 edges := [4]int{}
 var dfs func(index int) bool
 dfs = func(index int) bool {
  if index == len(nums) {
   return true
  }
  for i := range edges {
   edges[i] += nums[index]
   if edges[i] <= edge && dfs(index+1) {
    return true
   }
   edges[i] -= nums[index]
  }
  // fmt.Println(index, edges, edge)
  return false
 }
 return dfs(0)
}

func main() {
 // matchsticks := []int{1, 1, 2, 2, 2}
 matchsticks := []int{3, 3, 3, 3, 4}
 ans := makesquare(matchsticks)
 fmt.Println(ans)
}

2022-05-31

https://leetcode.cn/problems/water-bottles/
技巧：基础逻辑；

// 1518: https://leetcode.cn/problems/water-bottles/
// 10:42 - 10:48

func numWaterBottles(numBottles int, numExchange int) int {
 ans := numBottles
 temp := numBottles
 for temp >= numExchange {
  temp1 := temp / numExchange
  ans += temp1
  temp = temp%numExchange + temp1
  // fmt.Println(ans, temp)
 }
 return ans
}

func main() {
 // numBottles := 9
 // numExchange := 3

 // numBottles := 15
 // numExchange := 4

 numBottles := 5
 numExchange := 5

 ans := numWaterBottles(numBottles, numExchange)
 fmt.Printf("%d", ans)
}

2022-05-30

https://leetcode.cn/problems/z1R5dt/
技巧：字典树，前缀和，哈希；

type MapSum struct {
 m, pre map[string]int
}

/** Initialize your data structure here. */
func Constructor() MapSum {
 return MapSum{
  m:   make(map[string]int),
  pre: make(map[string]int),
 }
}

func (this *MapSum) Insert(key string, val int) {
 changeNum := val
 if this.m[key] > 0 {
  changeNum -= this.m[key]
 }
 this.m[key] = val
 for i := range key {
  this.pre[key[:i+1]] += changeNum
 }
}

func (this *MapSum) Sum(prefix string) int {
 return this.pre[prefix]
}

func main() {
 ans := 1
 fmt.Printf("%v", ans)
 obj := Constructor()
 obj.Insert("insert", 1)
 fmt.Printf("%v", obj)
 fmt.Printf("%d", obj.Sum("in"))

}

one question per day ​

2022-12-29 ​

2022-12-28 ​

2022-12-16 ​

2022-12-15 ​

2022-12-13 ​

2022-12-08 ​

2022-12-07 ​

2022-11-29 ​

2022-11-28 ​

2022-11-27 ​

2022-11-25 ​

2022-11-24 ​

2022-11-23 ​

2022-11-22 ​

2022-11-21 ​

2022-09-07 ​

2022-08-05 ​

2022-08-04 ​

2022-08-03 ​

2022-07-29 ​

2022-07-28 ​

2022-07-27 ​

2022-07-18 ​

2022-07-01 ​

2022-06-22 ​

2022-06-19 ​

2022-06-16 ​

2022-06-14 ​

2022-06-13 ​

2022-06-09 ​

2022-06-01 ​

2022-05-31 ​

2022-05-30 ​

one question per day

2022-12-29

2022-12-28

2022-12-16

2022-12-15

2022-12-13

2022-12-08

2022-12-07

2022-11-29

2022-11-28

2022-11-27

2022-11-25

2022-11-24

2022-11-23

2022-11-22

2022-11-21

2022-09-07

2022-08-05

2022-08-04

2022-08-03

2022-07-29

2022-07-28

2022-07-27

2022-07-18

2022-07-01

2022-06-22

2022-06-19

2022-06-16

2022-06-14

2022-06-13

2022-06-09

2022-06-01

2022-05-31

2022-05-30