functwoSum(nums []int, target int) []int { length := len(nums) for i := 0; i < length; i++ { for j := 1; j < length; j++ { if i == j { continue } if nums[i]+nums[j] == target { return []int{i, j} } } } returnnil }
主要就是靠暴力，因为是两数之和，所以两层循环解决
官方暴力解法
1 2 3 4 5 6 7 8 9 10 11
functwoSum(nums []int, target int) []int { length := len(nums) for k, v := range nums { for j := k + 1; j < length; j++ { if v+nums[j] == target { return []int{k, j} } } } returnnil }
官方的更优解法
直接使用哈希表
1 2 3 4 5 6 7 8
思路及算法
注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
1 2 3 4 5 6 7 8 9 10
functwoSum(nums []int, target int) []int { hashTable := map[int]int{} for i, x := range nums { if p, ok := hashTable[target-x]; ok { return []int{p, i} } hashTable[x] = i } returnnil }
定义两个指针 left 和 right，表示当前子串的左右边界。 用一个哈希表（map）来存储当前窗口中每个字符及其出现的位置。 不断移动 right 指针，将字符加入窗口，并更新哈希表。 当窗口中出现重复字符时，移动 left 指针，缩小窗口，直到窗口中没有重复字符为止。 在整个过程中，记录窗口的最大长度即可。
for right := 0; right < len(s); right++ { if index, found := charMap[s[right]]; found { // 如果字符在窗口中已经出现过，则更新 left 指针，移动到重复字符的下一个位置 left = max(left, index+1) } // 更新字符的最新位置 charMap[s[right]] = right // 计算当前窗口的长度并更新最大长度 maxLength = max(maxLength, right-left+1) }
return maxLength }
funcmax(a, b int)int { if a > b { return a } return b }
funcexpandAroundCenter(s string, left int, right int)string { for left >= 0 && right < len(s) && s[left] == s[right] { left-- right++ } return s[left+1 : right] }
funclongestPalindrome(s string)string { n := len(s) if n <= 1 { return s }
result := ""
for i := 0; i < n; i++ { // 以当前字符为中心的奇数长度回文子串 oddPalin := expandAroundCenter(s, i, i) // 以当前字符和下一个字符的中间为中心的偶数长度回文子串 evenPalin := expandAroundCenter(s, i, i+1)
iflen(oddPalin) > len(result) { result = oddPalin } iflen(evenPalin) > len(result) { result = evenPalin } }
funcrev(str string)int { bytes := []byte(str) n := len(bytes) for i := 0; i < n/2; i++ { tmp := bytes[n-i-1] bytes[n-i-1] = bytes[i] bytes[i] = tmp } str = string(bytes) num, _ := strconv.Atoi(str) return num }
funcreverse(x int)int { str := strconv.Itoa(x) if x >= 0 { num := rev(str) if num > math.MaxInt32 { return0 } return num } else { // 去掉符号 str = str[1:] num := rev(str) if num > math.MaxInt32 { return0 } return -num } }
官方给的答案：
妙，直接用循环逆序了
1 2 3 4 5 6 7 8 9 10 11 12
funcreverse(x int) (rev int) { for x != 0 { if rev < math.MinInt32/10 || rev > math.MaxInt32/10 { return0 } digit := x % 10 x /= 10 rev = rev*10 + digit } return }
funcmax(a, b int)int { if a < b { return b } return a } funcmin(a, b int)int { if a < b { return a } return b }
funcmaxArea(height []int)int { ans := 0 l, r := 0, len(height)-1 for l < r { ans = max(ans, min(height[l], height[r])*(r-l)) if height[l] < height[r] { l++ } else { r-- } } return ans }
day12
12.整数转罗马数字
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
1 2 3 4 5 6 7 8
字符 数值 I1 V5 X10 L50 C100 D500 M1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
var valueSymbols = []struct { value int symbol string }{ {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"}, {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"}, {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}, }
funcintToRoman(num int)string { roman := []byte{} for _, vs := range valueSymbols { for num >= vs.value { num -= vs.value roman = append(roman, vs.symbol...) } if num == 0 { break } } returnstring(roman) }
官方解法之二：
因为题目已经告诉了1 <= num <= 3999这个条件，所以这里直接把每一位会出现的情况全部枚举出来，然后利用运算得到每一位的数字对应的符号，然后拼接起来
输入：word1 = "abc", word2 = "pqr" 输出："apbqcr" 解释：字符串合并情况如下所示： word1： ab c word2： pq r 合并后： apbq c r
示例 2：
1 2 3 4 5 6
输入：word1 = "ab", word2 = "pqrs" 输出："apbqrs" 解释：注意，word2 比 word1 长，"rs" 需要追加到合并后字符串的末尾。 word1： ab word2： pq r s 合并后： apbq r s
示例 3：
1 2 3 4 5 6
输入：word1 = "abcd", word2 = "pq" 输出："apbqcd" 解释：注意，word1 比 word2 长，"cd" 需要追加到合并后字符串的末尾。 word1： ab c d word2： pq 合并后： apbq c d
提示：
1 <= word1.length, word2.length <= 100
word1 和 word2 由小写英文字母组成
非常简单的题，可以直接用下标代替append， 加快时间
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
funcmergeAlternately(word1 string, word2 string)string { n, m := len(word1), len(word2) res := make([]byte, n+m) i, l := 0, 0 for i < n || i < m { if i < n { res[l] = word1[i] l++ } if i < m { res[l] = word2[i] l++ } i++ } returnstring(res) }
funckidsWithCandies(candies []int, extraCandies int) []bool { max, n := 0, len(candies) res := make([]bool, n) for _, v := range candies { if v >= max { max = v } } for k, v := range candies { if v+extraCandies >= max { res[k] = true } } return res }
funckidsWithCandies(candies []int, extraCandies int) []bool { maxCandies, n := 0, len(candies) res := make([]bool, n) for _, v := range candies { if v >= maxCandies { maxCandies = v } } for k, v := range candies { res[k] = v+extraCandies >= maxCandies } return res }
funcreverseVowels(s string)string { res := []byte(s) n := len(s) i, j := 0, n-1 for i < j { for i < n && !strings.Contains("aeiouAEIOU", string(res[i])) { i++ } for j > 0 && !strings.Contains("aeiouAEIOU", string(res[j])) { j-- } if i < j { res[i], res[j] = res[j], res[i] i++ j-- } } returnstring(res) }
input: "a good example" output: [a good example]// fmt.Println() a// for range 读取出 good example
1 2 3 4 5 6 7 8 9 10
funcreverseWords(s string)string { t := strings.Fields(s) n := len(t) for i := 0; i < n/2; i++ { //遍历数组的前半段直接交换 t[i], t[n-1-i] = t[n-1-i], t[i] } res := strings.Join(t, " ") //重新使用空格连接多个单词 return res }
funcproductExceptSelf(nums []int) []int { n := len(nums) res := make([]int, n) j, mul := 0, 1 for i := 0; i < n; i++ { for k := 0; k < n; k++{ if k == i { continue } if nums[k] == 0{ mul = 0 break } mul *= nums[k] } res[j] = mul mul = 1 j++ } return res }
funcincreasingTriplet(nums []int)bool { n := len(nums) if n < 3 { returnfalse } first, second := nums[0], 1 << 32 - 1 for i := 1; i < n; i++ { num := nums[i] if num > second { returntrue } elseif num > first { second = num } else { first = num } } returnfalse }
funccompress(chars []byte)int { n := len(chars) if n < 2 { return n } s := "" Len, j := 0, 0 for i := 0; i < n-1; i += Len { ch := chars[i] j = i + 1 Len = 1 for j < n && ch == chars[j] { Len++ j++ } if Len == 1 { s += string(chars[i]) } else { s += string(chars[i]) + strconv.Itoa(Len) } }
funcfindMaxAverage(nums []int, k int)float64 { n := len(nums) sum := 0 if n < 2 { returnfloat64(nums[0]) } if k == n { for i := 0; i < n; i++ { sum += nums[i] } returnfloat64(sum) / float64(k) }
for i := 0; i <= n-k; i++ { tmp := 0 for j := 0; j < k; j++ { tmp += nums[i+j]
} if tmp > sum { sum = tmp } } returnfloat64(sum) / float64(k) }
funcfindMaxAverage(nums []int, k int)float64 { sum := 0 for _, v := range nums[:k] { sum += v } maxSum := sum for i := k; i < len(nums); i++ { sum = sum - nums[i-k] + nums[i] maxSum = max(maxSum, sum) } returnfloat64(maxSum) / float64(k) }
funcmax(a, b int)int { if a > b { return a } return b }
funcmaxVowels(s string, k int)int { Max := 0 i, j := 0, k-1 for j < len(s) { count := Calc(s[i:j+1], k) if Max < count { Max = count } i++ j++ } return Max }
funcCalc(res string, k int) (count int) { count = 0 for i := 0; i < k; i++ { if strings.Contains("aeiou", string(res[i])) { count++ } } return }
funcmaxVowels(s string, k int)int { count := 0 for i := 0; i < k; i++ { if strings.Contains("aeiou", string(s[i])) { count++ } } Max := count for i := k; i < len(s); i++ { if strings.Contains("aeiou", string(s[i])) { count++ } if strings.Contains("aeiou", string(s[i-k])) { count-- } if count > Max { Max = count } } return Max } /* 时间 24ms 击败 28.44%使用 Go 的用户
funclargestAltitude(gain []int)int { real := make([]int, len(gain)+1) n, m := len(real), len(gain) real[0] = 0 k := 1 for i:= 0; i < m; i++ { if k < n { real[k] = gain[i] + real[k-1] k++ } } maxGain := 0 for i := 0; i < n; i++ { ifreal[i] > maxGain { maxGain = real[i] } } return maxGain }
空间复杂度为O(1)的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
funclargestAltitude(gain []int) (ans int) { total := 0 for _, x := range gain { total += x ans = max(ans, total) } return }
funcmax(a, b int)int { if a > b { return a } return b }
times := map[int]struct{}{}：创建一个空的整数到空结构体的映射，这个映射将用于记录不同的出现次数。times 的键是不同的出现次数，而值是空结构体。这种技巧通常用于检查集合中的唯一性，因为 Go 语言中的映射不能包含重复的键，所以通过这种方式来判断不同的出现次数是否唯一。
使用循环遍历 hash 中的值（即不同元素的出现次数），并将这些值作为键添加到 times 映射中，对应的值是一个空结构体。由于 Go 语言的映射不能包含重复的键，因此如果相同的出现次数出现多次，只有一个会被记录在 times 中。这意味着最终 times 中的键是不同的出现次数。
1 2 3 4 5 6 7 8 9 10 11
funcuniqueOccurrences(arr []int)bool { hash := map[int]int{} for _, v := range arr { hash[v]++ } times := map[int]struct{}{} for _, c := range hash { times[c] = struct{}{} } returnlen(times) == len(hash) }
用hash记录
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
funcuniqueOccurrences(arr []int)bool { hash := map[int]int{} for _, v := range arr { hash[v]++ } res := make(map[int]int) for k, v := range hash { if res[v] == 0 { res[v] = k } else { returnfalse } } returntrue
funcequalPairs(grid [][]int)int { n := len(grid) cnt := make(map[string]int) for _, row := range grid { cnt[fmt.Sprint(row)]++ } res := 0 for j := 0; j < n; j++ { var arr []int for i := 0; i < n; i++ { arr = append(arr, grid[i][j]) } if val, ok := cnt[fmt.Sprint(arr)]; ok { res += val } } return res }
We are given an array asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.
Example 1:
1 2 3
Input: asteroids = [5,10,-5] Output: [5,10] Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
Example 2:
1 2 3
Input: asteroids = [8,-8] Output: [] Explanation: The 8 and -8 collide exploding each other.
Example 3:
1 2 3
Input: asteroids = [10,2,-5] Output: [10] Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
Constraints:
2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
funcasteroidCollision(asteroids []int) (st []int) { for _, aster := range asteroids { alive := true for alive && aster < 0 && len(st) > 0 && st[len(st)-1] > 0 { alive = st[len(st)-1] < -aster if st[len(st)-1] <= -aster { st = st[:len(st)-1] } } if alive { st = append(st, aster) } } return }
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].
The test cases are generated so that the length of the output will never exceed 105.
Example 1:
1 2
Input: s = "3[a]2[bc]" Output:"aaabcbc"
Example 2:
1 2
Input: s = "3[a2[c]]" Output:"accaccacc"
Example 3:
1 2
Input: s = "2[abc]3[cd]ef" Output:"abcabccdcdcdef"
Constraints:
1 <= s.length <= 30
s consists of lowercase English letters, digits, and square brackets '[]'.
You have a RecentCounter class which counts the number of recent requests within a certain time frame.
Implement the RecentCounter class:
RecentCounter() Initializes the counter with zero recent requests.
int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].
It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.
