LeetCode C++ 笔记
|
128
|
0
|
笔记-编程语言

2504 字
|
13 分钟

1. 二分查找避免死循环

在二分查找中，通常会有两个主要操作：

  1. 更新左边界 (left = mid 或 left = mid + 1)。
  2. 更新右边界 (right = mid - 1 或 right = mid)。

二分查找通过不断缩小 [left, right] 的区间，最终使得 left == right 或者区间变得不可再缩小，从而退出循环。

假设我们使用经典的二分查找方法来计算 mid：

mid = (left + right) >> 1;

如果在某些情况下，更新区间时没有正确地缩小区间，就会导致死循环。例如：

  • 假设 left = 2，right = 3。
  • 计算 mid = (2 + 3) >> 1 = 2。
  • 如果条件导致 left = mid，那么 left 的值仍然是 2，而 right 的值仍然是 3。
  • 在下一次迭代中，mid 的值仍然是 2，区间没有缩小，导致死循环。

为了避免这种情况，通常需要在某些场景下通过 +1 或其他方法来确保区间能够正确缩小。

在这段代码中，mid = (left + right + 1) >> 1 的作用是使 mid 向上取整（更偏向右边界）：

  • 当 left + right 是奇数时，+1 的效果是使得 mid 更靠近右边界。
  • 这可以确保当更新区间时，left 或 right 都会发生变化，从而避免死循环。

2. 前缀和（Prefix Sum）

定义：

前缀和是一种用于快速求解数组区间和的预处理方法。通过构造一个前缀和数组，使得在进行区间和查询时可以通过简单的加减操作快速得到结果。

前缀和的构造：

给定一个数组 nums，其前缀和数组 prefix 的定义如下：

  • prefix[i] 表示从数组起点 nums[0] 到 nums[i-1] 的元素和。
  • 构造公式为：prefix[i] = prefix[i-1] + nums[i-1] （i >= 1） prefix[0] = 0

作用：

前缀和的主要作用是快速求解任意区间 [l, r] 的元素和。通过前缀和数组，可以将区间和的计算复杂度从 O(n) 降低到 O(1)。

区间和计算公式：

对于区间 [l, r] 的和，可以通过前缀和数组直接计算：

sum[l, r] = prefix[r+1] - prefix[l]

应用场景：

  1. 快速区间和查询： 在多次查询区间和的情况下，前缀和可以显著提高效率。
  2. 子数组问题： 前缀和常用于解决子数组和相关问题，例如寻找符合条件的子数组。
  3. 动态规划优化： 在一些动态规划问题中，前缀和可以减少重复计算。

代码示例：

int main() {
    // 构造前缀和数组
    vector<int> nums = {1, 2, 3, 4, 5};
    int n = nums.size();
    vector<int> prefix(n + 1, 0);  // 初始化前缀和数组，大小为 n + 1

    // 计算前缀和
    for (int i = 1; i <= n; ++i) {
        prefix[i] = prefix[i - 1] + nums[i - 1];
    }

    // 查询区间 [1, 3] 的和
    int l = 1, r = 3;
    int result = prefix[r + 1] - prefix[l];
    cout << "区间和: " << result << endl;  // 输出 9（2+3+4）

    return 0;
}

优势：

  1. 预处理后查询快速： 查询复杂度为 O(1)。
  2. 简单易实现： 构造前缀和数组的复杂度为 O(n)。

注意事项：

  • 前缀和适用于静态数组。如果数组频繁更新，可能需要其他数据结构（如树状数组或线段树）。
  • 前缀和数组通常比原数组多一个元素，用于表示空区间的和（prefix[0] = 0）。

3. 线段树（Segment Tree）

线段树是一种高级的数据结构，主要用于处理区间查询和区间更新的问题。它是一棵二叉树，能够高效地解决一维数组上的操作，比如求区间和、区间最大值、区间最小值等。线段树的构建、查询和更新操作时间复杂度均为 O(log⁡n)，适合处理动态数据。

线段树的特点

  1. 树的结构：
    • 每个节点存储数组某个区间的信息（如区间和、区间最大值等）。
    • 根节点表示整个区间，叶节点表示单个元素。
    • 每个非叶节点的值根据其子节点值计算而来。
  2. 区间划分：
    • 每次将数组区间分为两部分（左右区间），递归构建。
    • 左子节点表示区间的左半部分，右子节点表示区间的右半部分。
  3. 操作时间复杂度：
    • 构建线段树： O(n)。
    • 单次区间查询： O(log⁡n)。
    • 单次区间更新： O(log⁡n)。

线段树的常见操作

  1. 构建线段树：
    • 通过递归方式，将数组区间分割成子区间。
    • 每个节点存储对应区间的值。
  2. 区间查询：
    • 查询某个区间的值（如区间和、区间最值等）。
    • 根据当前区间和目标区间的关系，递归访问子节点。
  3. 区间更新：
    • 更新某个区间的值（如单点更新或整个区间加某个值）。
    • 递归修改相关节点的值。

应用场景

线段树适用于需要频繁查询和更新数组区间的数据问题，例如：

  • 求数组的区间和。
  • 求数组的区间最大值或最小值。
  • 动态修改数组某个区间的值。

示例（基于 LeetCode 3479）

class SegmentTree {
    vector<int> nodes;

    void maintain(int i) {
        nodes[i] = max(nodes[i * 2], nodes[i * 2 + 1]);
    }

    void build(const vector<int> &input, int i, int l, int r) {
        if (l == r) {
            nodes[i] = input[l];
            return;
        }
        int m = (l + r) / 2;
        build(input, i * 2, l, m);
        build(input, i * 2 + 1, m + 1, r);
        maintain(i);
    }

public:
    SegmentTree(const vector<int> &input) {
        size_t n = input.size();
        nodes.resize(2 << bit_width(n - 1));
        build(input, 1, 0, n - 1);
    }

    // 找区间内的第一个 >= x 的数，并更新为 -1，返回这个数的下标（没有则返回 -1）
    int findFirstAndUpdate(int i, int l, int r, int x) {
        if (nodes[i] < x) { // 区间没有 >= x 的数
            return -1;
        }

        if (l == r) {
            nodes[i] = -1; // 更新为 -1，表示不能放水果
            return l;
        }

        int m = (l + r) / 2;
        int idx = findFirstAndUpdate(i * 2, l, m, x); // 先递归左子树
        if (idx < 0) { // 左子树没找到
            idx = findFirstAndUpdate(i * 2 + 1, m + 1, r, x); // 再递归右子树
        }
        maintain(i);
        return idx;
    }
};

A. C++ STL 容器

STL 中的容器有序列容器和关联容器，容器适配器 (congtainer adapters: stack,queue, priority queue)，位集(bit set)，串包(string package)等等。

  1. 序列式容器（Sequence containers），每个元素都有固定位置——取决于插入时机和地点，和元素值无关，vector、deque、list。
    • Vector：将元素置于一个动态数组中加以管理，可以随机存取元素（用索引直接存取），数组尾部添加或移除元素非常快速。但是在中部或头部安插元素比较费时。
    • Deque：是 double-ended queue 的缩写，可以随机存取元素（用索引直接存取），数织头部和尾部添加或移除元素都非常快速，但是在中部或头部安插元素比较费时。
    • List：双向链表，不提供随机存取（按顺序走到需存取的元素，O（n）），在任何位置上执行插入或删除动作都非常迅速，内部只需调整一下指针。
  2. 关联式容器（Associated containers），元素位置取决于特定的排序准则，和插入顺序无关，set、multiset、map、multimap等。
    • Set/Multiset：内部的元素依据其值自动排序，Set内的相同数值的元素只能出现一次，Mulisets内可包含多个数值相同的元素，内部由二叉树实现，便于查找。
    • Map/Multimap：Map的元素是成对的键值/实值，内部的元素依据其值自动排序，Map内的相同数值的元素只能出现一次，Multimaps内可包含多个数值相同的元素，内部由二叉树实现，便于查找。

容器类自动申请和释放内存，无需new和delete操作。

A.1. std::string（严格意义非容器但类似）

容量管理

  • size_t size() const noexcept：返回字符串长度。
  • size_t length() const noexcept：返回字符串长度（等价于 size()）。
  • size_t max_size() const noexcept：返回字符串的最大大小。
  • void resize(size_t n)：调整字符串大小。
  • void resize(size_t n, char c)：调整大小并填充字符 c。
  • size_t capacity() const noexcept：返回当前分配的容量。
  • void reserve(size_t new_cap = 0)：调整容量大小。
  • void shrink_to_fit()：释放多余的容量。
  • bool empty() const noexcept：检查字符串是否为空。

访问操作

  • char& front()：返回第一个字符（可修改）。
  • const char& front() const：返回第一个字符（只读）。
  • char& back()：返回最后一个字符（可修改）。
  • const char& back() const：返回最后一个字符（只读）。
  • const char* c_str() const noexcept：返回 C 字符串格式的内容。
  • const char* data() const noexcept：返回数据指针（不可修改）。
  • char* data() noexcept：返回数据指针（可修改，从 C++17 开始）。
  • std::string substr(size_t pos = 0, size_t n = npos) const：提取子字符串。

修改操作

  • void clear() noexcept：清空字符串。
  • std::string& insert(size_t pos, const std::string& str)：插入字符串。
  • std::string& insert(size_t pos, const char* s)：插入 C 字符串。
  • std::string& insert(size_t pos, size_t n, char c)：插入 n 个字符 c。
  • std::string& erase(size_t pos = 0, size_t n = npos)：删除子字符串。
  • std::string& replace(size_t pos, size_t len, const std::string& str)：替换子字符串。
  • void push_back(char c)：在字符串末尾添加字符。
  • void pop_back()：移除字符串末尾的字符。
  • void swap(std::string& str) noexcept：交换两个字符串内容。

查找操作

  • size_t find(const std::string& str, size_t pos = 0) const noexcept：查找子字符串。
  • size_t find(const char* s, size_t pos = 0) const：查找 C 字符串。
  • size_t find(char c, size_t pos = 0) const noexcept：查找字符。
  • size_t rfind(const std::string& str, size_t pos = npos) const noexcept：从右查找子字符串。
  • size_t find_first_of(const std::string& str, size_t pos = 0) const noexcept：查找第一个匹配的字符。
  • size_t find_last_of(const std::string& str, size_t pos = npos) const noexcept：查找最后一个匹配的字符。
  • size_t find_first_not_of(const std::string& str, size_t pos = 0) const noexcept：查找第一个不匹配的字符。
  • size_t find_last_not_of(const std::string& str, size_t pos = npos) const noexcept：查找最后一个不匹配的字符。

比较操作

  • int compare(const std::string& str) const noexcept：比较两个字符串。
  • int compare(size_t pos, size_t len, const std::string& str) const：比较子字符串。

运算符重载

  • std::string& operator=(const std::string& str)：拷贝赋值运算符。
  • std::string& operator=(std::string&& str) noexcept：移动赋值运算符。
  • std::string& operator=(const char* s)：从 C 字符串赋值。
  • std::string& operator=(char c)：赋值单个字符。
  • std::string& operator=(std::initializer_list<char> ilist)：从初始化列表赋值。
  • char& operator[](size_t pos)：获取指定位置的字符（可修改）。
  • const char& operator[](size_t pos) const：获取指定位置的字符（只读）。
  • char& at(size_t pos)：获取指定位置的字符（带边界检查，可修改）。
  • const char& at(size_t pos) const：获取指定位置的字符（带边界检查，只读）。
  • std::string& operator+=(const std::string& str)：拼接字符串。
  • std::string& operator+=(const char* s)：拼接 C 字符串。
  • std::string& operator+=(char c)：拼接单个字符。
  • bool operator==(const std::string& lhs, const std::string& rhs)：比较相等。
  • bool operator!=(const std::string& lhs, const std::string& rhs)：比较不相等。
  • bool operator<(const std::string& lhs, const std::string& rhs)：小于比较。
  • bool operator>(const std::string& lhs, const std::string& rhs)：大于比较。
  • bool operator<=(const std::string& lhs, const std::string& rhs)：小于等于比较。
  • bool operator>=(const std::string& lhs, const std::string& rhs)：大于等于比较。
  • std::string operator+(const std::string& lhs, const std::string& rhs)：拼接两个字符串。
  • std::string operator+(const std::string& lhs, const char* rhs)：拼接字符串和 C 字符串。
  • std::string operator+(const char* lhs, const std::string& rhs)：拼接 C 字符串和字符串。
  • std::string operator+(const std::string& lhs, char rhs)：拼接字符串和单个字符。
  • std::ostream& operator<<(std::ostream& os, const std::string& str)：输出流支持。
  • std::istream& operator>>(std::istream& is, std::string& str)：输入流支持。

构造函数

  • std::string()：默认构造函数，创建一个空字符串。
  • std::string(const std::string& str)：拷贝构造函数。
  • std::string(std::string&& str) noexcept：移动构造函数。
  • std::string(const char* s)：从 C 字符串构造。
  • std::string(const char* s, size_t n)：从 C 字符数组的前 n 个字符构造。
  • std::string(size_t n, char c)：构造一个包含 n 个字符 c 的字符串。
  • std::string(std::initializer_list<char> ilist)：从初始化列表构造。

A.2. std::vector

A.3. std::unordered_map

B. C++ STL 迭代器

C. C++ STL 算法

笔记编程语言
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇CUDA 学习笔记
下一篇 Nsight 学习笔记