Segment Tree 线段树

线段树解决的是「区间和」的问题，且该「区间」会被修改

一个区间的例子是对于 nums = [1, 2, 3, 4, 5] 多次求某些区间的和，是不是首先想到了利用「前缀和」。

但是如果 nums 会被修改呢？比如：

• 把第 i 个元素修改成 x
• 把第 i 个元素增加 x
• 把区间 [i, j] 内的元素都增加 x

此时，如果我们再使用「前缀和」，就没那么高效了。因为每一次更新，前缀和数组必须也随之更新，时间复杂度为 O(n)。

股市买卖问题

故事买卖类的问题主要使用动态规划进行解决，只是复杂程度不同罢了。

递归方程的建立考虑以下问题：

• 目的：能够获得的最大利润

• 联系：一共有n天需要记录，每天有两种状态，当天有股票或没股票

  • 今天没有股票：昨天也没买今日未操作，或者卖掉股票获得钱
  • 今天有股票：昨天就已经买入股票今日未操作，或者今日买入股票

• 优化：是否需要记录每一天，还是只与上一天的结果有关。

Binary Search 二分搜索

二分搜索的关键在于：

1. 搜索 [0, len-1] 这个闭区间，还是 [0, len) 这个开区间.
2. 如果是闭区间，则循环条件使用 while(left <= right)；如果是开区间，则使用while(left < right)。很好理解，考虑列表只有一个因素的情况，闭区间是[1,1]需要等于搜索。
3. 思考返回的问题：
   • 如果元素是不重复的，可以直接if(nums[mid] == target) return mid;判断返回。
   • 如果元素是重复的，需要考虑返回第一个重复元素还是最后一个重复元素的问题。
     • 返回第一个：if (nums[mid] == target) right = mid - 1; 锁定左侧边界，返回值为：return nums[left] == target ? left : -1;
     • 返回最后一个：if (nums[mid] == target) left = mid + 1; 锁定右侧边界，返回值为：nums[right] == target ? right : -1;

Heapsort 堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

• Java 的 PriorityQueue 的实现方式就是堆排序。

Backtracking Algorithm 回溯算法

In a netshell 解题思路

In abraction, solving a backtracking problem is acutally iterating a decision tree. Every node of a tree has a valid answer and we traversing the tree to collect all the valid answers. 抽象地说，解决一个回溯问题，实际上就是遍历一棵决策树的过程，树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍，把叶子节点上的答案都收集起来，就能得到所有的合法答案。

Binary Tree Questions 二叉树问题

This article is concluded from this article in Chinese.

Cheatsheet: Steps to solve binary tree questions

1. Can we get the answer by traversing the binary tree once? 是否能通过遍历一棵树来获取结果？
2. If not, can we define a recursive function that gets the answer to the original question from the answer to the subtree? If the solution involved the information of the subtree, it is recommended to use post-order position to handle data. 如果不能，是否能通过递归的方式获取子树的结果，再根据子树的结果计算最终结果。通常而言，由于需要子树的结果，常在后序位置处理节点数据。
3. No matter which model you are using, we need to think about what and when should we do for a single node? (Pre/In/Post-order) 无论使用哪一种思维模式，都要明白二叉树的每一个节点需要做什么，需要在什么时候（前中后序）做

Data Structure Basic 数据结构基础

The storage of data

There are only two ways to storage the data, the Array and the Linked list. All the other data structures are developed based on them.

Arrays, due to their compact and contiguous storage, allow for random access, enabling quick retrieval of elements by index. Moreover, they are relatively space-efficient. However, because of their contiguous storage, memory space must be allocated all at once. This means that if you want to expand an array, you need to reallocate a larger block of memory and copy all the data to it, resulting in a time complexity of O(N). Additionally, if you want to insert or delete elements in the middle of an array, you must shift all the data behind it to maintain continuity, also resulting in a time complexity of O(N).

Dynamic Programming 动态规划

This blog records the solutions I made for the Dynamic Programming questions from Leetcode.

Fibonacci related problems

Firstly, find out the transformation function for the problem.

Then, from the starting point to calculate the results by iterating the array.