Leetcode 刷题笔记
文章的部分内容被密码保护： --- DON'T MODIFY THIS LINE --- @Aiken 2021; 汇总LeetCode刷题以及刷《剑指offer》过程中遇到的一些不会做的题或者启发性很强的题目等等；内容主要以以下几个方面为主： 题目-题解-相关注释； 相关难点分析； 相关知识点索引 同时copy到数据结构或者c++的文档中） 《Fuck Algorithm》 针对各个专题指向性的去刷一些Leetcode中的题目，通过对这些题目进行分析整合来对巩固各个知识点，这一部分的代码整合到/leecode文件夹中，但是主要可能整合在md中； 这里可以顺便把git的内容整理一下，本地的git操作流程 最近先把数据结构刷了，变刷变看后面的搜索等等的内容，一部分一部分的往后看 第一课中回溯和其他规划的题还没看，后续再看看 思考C++中多返回值的设计 数据结构的存储方式 数据结构的存储方式 （物理层面的存储方式）：数组（顺序存储）和链表（链式存储）。 最底层的存储架构上基本上只有这两种实现的方式，更高维的才是：栈、队列、堆、树、图这些高层结构； 而这些实现的高层实现上，分别使用量中架构有啥优缺点： 综上，数据结构种类很多，甚至你也可以发明自己的数据结构，但是底层存储无非数组或者链表，二者的优缺点如下： 数组由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。 链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。 二分查找专题 由于我经常写错二分查找的边界判断条件，所以这里进行一个整理操作： 二分查找总结专题 后续整理的时候在进行阅读一下，加深一下理解 其中需要注意的是： 我们使用 left+(right-left) /2 来代替 (l+r)/2 ,因为这样的话可以防止right和left太大溢出的操作； mid +- 1 以及最终的返回条件 <= 还是小于 我们分情况来讨论： 求的是特定值，求的是左右的边界值的时候， cpp int binary_search(int[] nums, int target) { int left = 0, right = nums.length - 1; while(left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if(nums[mid] == target) { // 直接返回 return mid; } } // 直接返回 return -1; } int left_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 别返回，锁定左侧边界 right = mid - 1; } } // 最后要检查 left 越界的情况 if (left >= nums.length || nums[left] != target) return -1; return left; } int right_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 别返回，锁定右侧边界 left = mid + 1; } } // 最后要检查 right 越界的情况 if (right < 0 || nums[right] != target) return -1; return right; } 数据结构的基本操作 所有数据结构的基本操作一般都局限在 遍历+访问，更具体一点就是：增删改查； ...
