标志注释
* ：不会
? ：有点疑惑
√ ：过了
每日一题
| 序号题目 | 类型 | 解法思路 | 算法复杂度 | 结果 |
|---|---|---|---|---|
| 1711. 大餐计数 | 双指针、哈希表 | 1. 数组内数大小在[min, max]范围内，则满足条件的2的幂次在[min, 2max]中，这个复杂度为logC 2. 如果直接去找所有组合可能为2的幂次的数量，复杂度是O(n^2logC)以上。应该首先将所有数出现的次数存到Dict中。（可以先sort，使顺序从小到大）。然后左右flag去查相加为某个2幂次的数（两数之和）（复杂度为N），进行logC次。 |
O(NlogC) | * |
GO
| 题目序号 | 类型 | 解法思路 | 时间复杂度 | 空间复杂度 | 结果 |
|---|---|---|---|---|---|
| 1. 两数之和 | 哈希表 | 1. go的字典写法：goDict := make(map[int]int)或者 goDict := map[int] int{} 2. go的查询字典中键值是否存在的写法： if _, ok := goDict[key]; ok {}3. go遍历list的写法： for index, number := range nums {} |
O(logN) | O(logN) | √ |
| 剑指 Offer 56 - I. 数组中数字出现的次数 | 位操作 | 1. go的转换二进制字符串方法：fmt.Sprintf("%08b", number)或者strconv.FormatInt(number, 2)2. go的异或：a^b 3. go的字符转数字： rune(c)，数字转字符串：string(num) |
O(logN) | O(1) | ？ |
| 1832. 判断句子是否为全字母句 | 1. go创建固定长度列表的方法：var l[26] int更新：这样在长度是var的时候会报错，请用 l=make([]int, length)2. go快速判断元素是否在数组中：使用sort.SearchSrtings() 可将判断元素在数组中的问题降低复杂度到O(logN) |
√ | |||
| 1833. 雪糕的最大数量 | 哈希表 | 方法1：先排序，再计算，复杂度=排序的O(NlogN) go的列表排序方法： sort.Ints(targetList)方法2：因为雪糕的最大价格不超过1e5，使用列表记录每个价格的雪糕的数量。空间复杂度换时间复杂度。 |
O(N+C)，C是雪糕最大价格 | O(C) | ？ |
| 1722. 执行交换操作后的最小汉明距离 | 并查集、哈希表 | 1. 分析题目，如果[0,1],[1,2]可以交换，那么[0,2]也可以交换。因此所有可以交换的索引可以形成一个集合，其中两两可以交换 2. 使用并查集得到交换操作的集合 3. 对于每一个集合，使用哈希表记录集合内索引对应的目标数组数据出现的次数。对于输入数组的每一个数，找出其索引所在集合和目标数组集合的差集，就是结果。 |
O(N+M) N为集合长度，M为交换列表长度 |
* | |
| 930. 和相同的二元子数组 | 哈希表法、三指针法 | 1. 哈希表法：用哈希表存储hash[sum]（从最左侧到index i的累计为sum的数量），在index i，查找hash[sum-goal]，即为以index i为右边界的子数组数量。时间、空间复杂度都为O(N) 2. 三指针法：左指针left1、left2，右指针right。其中右指针不断右移，左指针中，left1停在子数组sum>=goal时（连续0的右侧），left2停在sum>goal时（连续0的左侧）。然后就能通过left1和2的索引值差得到以右指针为右边界的子数组数量。时间复杂度O(N)，空间复杂度O(1) |
* | ||
| 面试题 17.10. 主要元素 | Boyer-Moore 投票算法 | 1. 初始状态，candidate任意值，count=0。 2. 遍历输入数组nums中所有元素。当count=0时，使candidate=nums[i]。否则，当candidate!=nums[i]，count-=1，当candidate==nums[i]，count+=1。 3. 如果数组中存在主要元素，当遍历结束，candidate即为该主要元素。否则，candidate可能为任意值。因此需要再一次遍历数组，确认该数字是否为主要元素。 |
O(N) | O(1) | * |
| 91. 解码方法 | dp | string转int：n, err := strconv.Atoi(string) |
O(N) | O(1) | √ |
| 1818. 绝对差值和 | 二分查找 sort | 1. go中的二分查找：j := nums.Search(v) nums是已经排序好的数列 |
O(NlogN) | O(N) | |
| 1653. 使字符串平衡的最少删除次数 | dp | 1. go中的空语句（类似python中的pass）直接空着就可以{}2. string类型也可以使用for循环迭代，中间的元素应该是char？ |
O(N) | O(1) | √ |
| 1105. 填充书架 | dp | O(N^2) | O(N) | √ | |
| 1838. 最高频元素的频数 | 排序 滑动窗口 | 1. 先调用一个排序 2. 然后使用滑动窗口 |
O(NlogN) | O(logN) | √ |
| 138. 复制带随机指针的链表 | 递归 哈希表 | 1. go的全局变量需要在函数的外部声明：var hashMap map[*Node]*Node，然后在函数内赋值：hashMap = map[*Node]*Node {}2. 创建一个Node类型的对象，然后将对象地址赋给Node类型指针： flag := &Node {Val:0}3. 这是一个使用递归的题目，对于母链表中的节点node，检查hash表中对应的newnode有没有被创建，有创建则返回该newnode，没有被创建则创建newnode，然后将该newnode更新到hash表中，然后继续检查node的next node和random node指向的节点。 |
O(N) | O(N) | * |
| 300. 最长递增子序列 | 贪心 二分法 | 1. 目的是找到最小递增幅度 2. 建立一个空序列d，遍历目标数组。当目标数组遍历到的nums[i]>d[-1]时，直接将nums[i]插入d的最后。当nums[i]大于d[-1]时，使用二分法将其替换掉d数组中正好大于nums[i]且小于等于nums[i]的某个数。 3. 最后得到的空序列长度即为最长递增子序列长度（但是d并不是最长递增子序列，是一个工具数组） |
O(NlogN) | O(N) | * |
| 1713. 得到子序列的最少操作次数 | 哈希表 最长递增子序列 | 1. 实际上的解法：将arr中的数字转换成其在target中对应的index，寻找该index序列的最长递增子序列 2. 如果直接将arr数字转换成index序列，复杂度为O(NM)，超过题目限制。利用题目中arr中数字不重复的特性，加入哈希表Dict，key为arr中数字，value为对应index。然后再遍历target，如果如果target[i]存在于哈希表的键值中，则查找对应value是否加入该递增子序列。 |
O(M+NlogN) | O(N+M) | ? |
func in(target string, str_array []string) bool {
sort.Strings(str_array)
index := sort.SearchStrings(str_array, target)
if index < len(str_array) && str_array[index] == target {
return true
}
return false
}
