tags: LeetCode 移除小写字母中重复的字母，让所有字母都只出现一次，并且结果是所有结果中按照字典序排序最小的那个。 Example 1 Input: “bcabc” Output: “abc” Example 2 Input: “cbacdcbc” Output: “acdb” 解法之一: 通过一个数组对每一个出现的字母进行计数 遍历每一个字母放入栈，并将该字母的计数减 1 查看栈底的字母有没有比当前字母大且该字母的计数不为 0 的（有比当前更小的字典序），从栈底弹出该字母 func removeDuplicateLetters(s string) string { var countOfEachLetter [26]int var visited [26]bool stack := make([]byte, 0) stackBottom := 0 bytesArr := []byte(s) for _, c := range bytesArr { countOfEachLetter[getIndex(c)]++ } for _, c := range bytesArr { index := getIndex(c) countOfEachLetter[index]-- if visited[index] { continue } // countOfEachLetter[getIndex(stack[stackBottom])] > 0 后面还有该字符 for len(stack[stackBottom:]) > 0 && stack[stackBottom] > c && countOfEachLetter[getIndex(stack[stackBottom])] > 0 { // 标记为未访问用于后面的字符加入结果 visited[getIndex(stack[stackBottom])] = false // 移动栈底 stackBottom++ } // 加入到结果栈 stack = append(stack, c) visited[index] = true } return string(stack[stackBottom:]) } func getIndex(b byte) int { return int(b - 'a') } 通过上面解法遇到如下错误： ...

tags: LeetCode 解法 1 找到中间节点依次往左右扩散： 向左边扩散，如果左边的大于当前元素，那么当前元素即为最小值 向右边扩散，如果右边的小于当前元素，那么右边元素即为最小值 如果以上不成立则第一个元素为最小元素（未旋转），以下是代码 func findMin(nums []int) int { length := len(nums) if length == 1 { return nums[0] } // 从中间开始确定方向 mid := length / 2 - 1 left, right := mid, mid for left - 1 >= 0 || right + 1 < length { if left - 1 >= 0 { if nums[left - 1] > nums[left] { return nums[left]; } left-- } if right + 1 < length { if nums[right] > nums[right + 1] { return nums[right + 1] } right++ } } return nums[0] } 优化 参考答案后可通过二分查找做如下优化，首先判断是否被旋转： 如果数组尾部的元素大于首部的元素则表示数组未被旋转，可以直接返回第一个元素。 由于是从一个有序数组旋转的，所以以上条件可以保证。 然后再判断方向： 如果所取中间元素大于数组的第一个元素则最小元素在右边 否则最小元素在左边 func findMin(nums []int) int { length := len(nums) if nums[0] <= nums[length - 1]{ return nums[0] } if length == 2 { return nums[1] } left, right := 0, length - 1 for left < right { mid := left + ((right - left) / 2) if nums[mid] > nums[mid + 1] { return nums[mid + 1] } if nums[mid - 1] > nums[mid] { return nums[mid] } if nums[mid] > nums[0] { left = mid + 1 } else { right = mid - 1 } } return -1 }

tags: LeetCode 思路 这个是 LeetCode: 153.Find Minimum in Rotated Sorted Array 扩展，增加了以下几种边界情况： ‘[2, 2, 2, 2, 1]’ ‘[3, 1, 3]’ ‘[1, 1, 1]’ ‘[10, 1, 10, 10, 10]’ 但核心依然是判断最小值是在左边还是右边。假设如下数组： ‘[3, 3, 3, 1, 3]’ left[0]=3, right[4]=3, mid[2]=3, 这时候不确定最小值在哪边但是 right– 是安全的，所以执行 right– left[0]=3, right[3]=1, mid[2]=3, 这时候 mid < right 说明最小值在 mid 的右边，所以调整 left = mid + 1 左右两边索引一致终止循环 实现 func findMin(nums []int) int { length := len(nums) left, right := 0, length - 1 for left < right { mid := (left + right) / 2 if nums[mid] > nums[right] { left = mid + 1 } else if nums[mid] < nums[right] { right = mid } else { right-- } } return nums[right] }

tags: LeetCode 准备 动态规划 实践 字符串 “abcabcbb” 根据索引有如下关系 a b c a b c b b 0 1 2 3 4 5 6 7 \(f(0,1)=f(0,0) + 1\) \(f(0,2)=f(0,1) + 2\) 在所有字符都不重复的情况下有如下公式 \(f(s,e)=f(s,e-1) + e\) 若遇到重复的情况则，3 索引于当前字串 的 0 重复则表明当前字串已经到头，需要记录并偏移 s，s=1： \(f(1,3)=f(1,2)+3\) 假设： s - 开始字符索引 e - 结束字符索引 若遇到当前字符于前面 r 字符重复则： \[ f(r,e)=f(s,e - 1) + e; s=r \] 解法 func lengthOfLongestSubstring(s string) int { if len(s) == 0 { return 0 } appearedIndexes := [256]int{} for i := 0; i < 256; i++{ appearedIndexes[i] = -1 } longest, start, end := 0, 0, 0 b := []byte(s) for cIndex, c := range b { index := int(c) appearedIndex := appearedIndexes[index] end = cIndex // 出现过需要截断 if appearedIndex != -1 { // 重置已出现的字符 for i := start; i <= appearedIndex; i++{ appearedIndexes[b[i]] = -1 } length := end - start if length > longest { longest = length } start = appearedIndex+1 } appearedIndexes[index] = cIndex } if end - start + 1 > longest { longest = end - start + 1 } return longest }

tags: LeetCode 思路 归并排序 代码 func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { nums := mergeSort(nums1, nums2) length := len(nums) if length % 2 != 0 { return float64(nums[(length - 1) / 2]) } i := length / 2 return (float64(nums[i]) + float64(nums[i - 1])) / 2 } func mergeSort(nums1 []int, nums2 []int) []int { l1 := len(nums1) l2 := len(nums2) result := make([]int, 0, l1 + l2) i, j := 0, 0 for i < l1 && j < l2 { if nums1[i] < nums2[j] { result = append(result, nums1[i]) i++ } else { result = append(result, nums2[j]) j++ } } result = append(result, nums1[i:]...) result = append(result, nums2[j:]...) return result }

tags: LeetCode > https://leetcode.com/problems/longest-palindromic-substring/description/ 思路 直接暴力往两边搜索 func longestPalindrome(s string) string { buf := []byte(s) length := len(buf) if length == 0 { return s } start, end := 0, 0 for ci, _ := range buf { i, j := ci, ci // 无法处理 "aaaa" 和 "noon" 这种情况 for i > 0 && j < length - 1 && buf[i - 1] == buf[j + 1] { i-- j++ } // 考虑 "bba" 这种情况 if i == j && ci > 0 && buf[ci] == buf[ci - 1] { i, j = ci-1, ci } // 考虑 "abb" 这种情况 if i == j && ci < length - 1 && buf[ci] == buf[ci + 1] { i, j = ci, ci + 1 } if i != j && j - i >= end - start { start, end = i, j } } return string(buf[start:end + 1]) } 上面代码无法处理 “aaaa” 和 “noon” 这种情况，只要把下面处理 “bba” 和 “abb” 情况的代码放到上面即可 ...

tags: LeetCode srouce: https://leetcode.com/problems/zigzag-conversion/description/ 先根据行数计算列数： \(column=length / (row + 2) + bool(length \mod (row + 2))\) 每一行必然有点的位置为： \(i \mod (row - 1)\) 为 0

tags: 读书笔记,Rust 语句和表达式 所有权 引用和借用 结构体 枚举 模式匹配 if let 模块化 错误处理 Traits 生命周期 闭包 迭代器 智能指针 Rust 宏 Rust 并发 函数指针 fn 区分闭包的 Fn 特性，函数指针都实现来三个闭包的特性。 fn do(f: fn(i32) -> i32, arg: i32) -> i32 { f(arg) + f(arg) }