刷题日记 | LeetCode刷题总结（C++）

2020-03-25 本文已影响0人三金姐姐

l©一颗斯特拉
【注】
1.标有❤️的是值得多做的题
2.参考书：
①C++谭浩强
②C++数据结构与算法（第4版）

01 知识点

1.vector

一、介绍

定义（是什么）：向量vector是一种对象实体, 能够容纳许多其他类型相同的元素, 因此又被称为容器。与string相同, vector同属于STL(Standard Template Library, 标准模板库)中的一种自定义的数据类型, 可以广义上认为是数组的增强版。
优点（为什么用）：vector容器与数组相比其优点在于它能够根据需要随时自动调整自身的大小以便容下所要放入的元素。此外, vector也提供了许多的方法来对自身进行操作。
用法（怎么用）：在使用它时, 需要包含头文件#include<vector>。

二、向量的基本操作
1.a.size()：获取向量中的元素个数

三、二维向量
与数组相同, 向量也可以增加维数, 例如声明一个m*n大小的二维向量方式可以像如下形式：

vector< vector<int> > b(10, vector<int>(5)); //创建一个10*5的int型二维向量，括号中前者是初始大小，后者是初始值

在这里, 实际上创建的是一个向量中元素为向量的向量。同样可以根据一维向量的相关特性对二维向量进行操作。除此之外, 还可以直接使用数组来初始化向量。

2.引用

一、定义（是什么）：对变量起另外一个名字 (外号)，这个名字称为该变量的引用。

<类型> &<引用变量名> = <原变量名>；其中原变量名必须是一个已定义过的变量

//注意：①引用并没有重新在内存中开辟单元，只是引用原变量的单元，两者在内存中占用同一地址，即同一地址两个名字。②当&a的前面有类型符时 (如int &a)，它必然是对引用的声明；如果前面无类型符(如cout<<&a), 则是取变量的地址。

二、用法（怎么用）：引用的用途主要是用来作函数的参数或函数的返回值。引用作函数的形参，实际上是在被调函数中对实参变量进行操作。
//注意：引用作为形参，实参是变量而不是地址，这与指针变量作形参不一样。

01 方法

【暴力法】

思路

枚举数组里的每个数字，遍历数组统计有多少个数字比当前小。

算法

对于第 $i$ 个数字，计算 $\sum_{j=0}^{n-1} [nums[j]<nums[i]]$ 。其中我们约定括号里会返回一个数字，为真返回1，否则返回0。

复杂度分析

时间复杂度： $O(n^2)$ 。枚举数组中的元素为 $O(n)$ ，遍历也为 $O(n)$ ，其中 $n=nums.length$ 。
空间复杂度： $O(1)$ 。这里不需要开辟新的空间。

【桶计数】^[1]

思路

注意到数字的值域范围为 $[0,100]$ ，所以可以考虑建立一个频次数组 $cnt[i]$ ，表示数字 $i$ 出现的次数，那么对于数字 $i$ 而言，它的答案就是 $\sum_{j=0}^{i-1} cnt[i]$ ，即小于它的数字出现个数之和，直接算需要遍历。仍需要线性的时间去计算，但我们注意到这个答案是一个前缀和，所以我们可以再对算答案求前缀和，那么对于数字 $i$ 而言，它的答案就是 $cnt[i-1]$ ，这样就把时间复杂度 $i$ 而言，它的答案就是 $O(n)$ 降到了 $O(1)$ ，

算法

遍历数组元素，更新 $cnt$ 数组，然后对其求前缀和，最后遍历数组元素，对于相应的数字在 $O(1)$ 时间得到答案即可。

复杂度分析

时间复杂度： $O(S+n)$ ，其中 $S$ 为值域的大小， $n=nums.length$ 。
空间复杂度： $O(S)$ ，需要开一个值域大小的数组。

比较：
【暴力法】| 1 小时前 | 通过 | 100 ms | 7 MB | Cpp |
【桶计数】| 几秒前 | 通过 | 4 ms | 7 MB | Cpp |
桶计数的执行用时明显减少，内存消耗相同。

02 知识点

1.前缀和^[2]

一、定义
一维前缀和：前缀和顾名思义就是前面数的总和。这个优化主要是用来在 $O(1)$ 时间内求出一个序列中, $a[i]+a[i+1]+……+a[j]$ 的和。具体原理十分简单：用 $sum[i]$ 表示 $(a[1]+a[2]+……+a[i])$ ，其中 $sum[0]=0$ ，则 $a[i]+a[i+1]+……+a[j]$ 即等于 $sum[j]-sum[i-1]$ 。

二、应用问题
核心就两个字：降维。
面对许多高维问题，往往前缀和是最先想到的降维方法。
这样在降维的基础上，许多更进一步的优化才能实现。

1370. 上升下降字符串（3月25日）

01 方法^[3]

【桶计数】

思路

桶计数的思路是建立一个长度为 26 的数组表示 26 个桶，按顺序存放26个英文字母。实现本题目标，需要分两步走:
①先用 $O(|s|)$ 的时间扫描一遍字符串（其中 $|s|$ 代表字符串的长度），统计每个字母出现的次数。
②然后不停地扫描这里的这个桶序列，先从小到大扫，再从大到小扫，每次发现一个桶当中计数值不为 0 的时候，就把这个桶对应的字母添加到结果字符串的最后方，然后对计数值减一。

算法

①建立一个长度为 26 的数组h[]，作为用来计数的「桶」。
②引入内联的返回布尔型值得函数haveChar()，它的功能是在每次循环开始执行之前判断是否还有未使用的字符。
③引入函数appendChar(int i)，它的功能是检测i位置的桶是否计数值为 0，如果不为 0 则修改目标串和计数值。

复杂度分析

时间复杂度： $O(|s|)$
空间复杂度：这里使用了长度为 26 的数组作为辅助空间，故渐进空间复杂度为
$O(26)$ 。

02 知识点

1.内联函数

一、定义（是什么）：将被调函数体的代码直接插到调用处的函数。

二、优点（为什么）：内联函数的实质是用存储空间(使用更多的存储空间)来换取时间(减少执行时间)。

三、用法（怎么用）：内联函数的定义方法是，在函数定义时，在函数的类型前增加修饰词inline。

2.auto^[4]

auto是c++程序设计语言的关键字。用于两种情况：
①声明变量时根据初始化表达式自动推断该变量的类型（不建议使用）
例如，

auto f = 3.14;  //double
auto s("hello");  //const char*
auto z = new auto(9);  //int *
auto x1 = 5, x2 = 5.0, x3 = 'r';   //错误，必须是初始化为同一类型

②声明函数时函数返回值的占位符
auto关键字更适用于类型冗长复杂、变量使用范围专一时，使程序更清晰易读。如：

std::vector<int> vect; 
 for(auto it = vect.begin(); it != vect.end(); ++it)
 {  //it的类型是std::vector<int>::iterator
    std::cin >> *it;
  }

或者保存lambda表达式类型的变量声明：

  auto ptr = [](double x){return x*x;};//类型为std::function<double(double)>函数对象

3.Lambda表达式

一、定义（是什么）：Lambda 表达式（lambda expression）是一个匿名函数，Lambda表达式基于数学中的λ演算得名，直接对应于其中的lambda抽象（lambda abstraction），是一个匿名函数，即没有函数名的函数。Lambda表达式可以表示闭包（注意和数学传统意义上的不同）。

二、用法（怎么用）：

[capture list] (parameter list) -> return type { function body }

其中除了“[ ]”（其中捕获列表可以为空）和“复合语句”（相当于具名函数定义的函数体），其它都是可选的。它的类型是单一的具有成员operator()的非联合的类类型，称为闭包类型（closure type）。
C++中，一个lambda表达式表示一个可调用的代码单元。我们可以将其理解为一个未命名的内联函数。它与普通函数不同的是，lambda必须使用尾置返回来指定返回类型。
由于Lambda的类型是单一的，不能通过类型名来显式声明对应的对象，但可以利用auto关键字和类型推导：

auto f=[](int a,int b){return a>b;};

因为参数类型和函数模板参数一样可以被推导而无需和具体参数类型耦合，有利于重构代码；和使用auto声明变量的作用类似，它也允许避免书写过于复杂的参数类型。特别地，不需要显式指出参数类型时使用高阶函数变得更加容易。

4.STL（Standard Template Library）^[5]

一、STL是什么
STL标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。
STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但这种分离确实使得STL变得非常通用。例如，由于STL的sort()函数是完全通用的，你可以用它来操作几乎任何数据集合，包括链表，容器和数组。
STL另一个重要特性是它不是面向对象的。为了具有足够通用性，STL主要依赖于模板而不是封装，继承和虚函数（多态性）——OOP的三个要素。你在STL中找不到任何明显的类继承关系。这好像是一种倒退，但这正好是使得STL的组件具有广泛通用性的底层特征。另外，由于STL是基于模板，内联函数的使用使得生成的代码短小高效。
从逻辑层次来看，在STL中体现了泛型化程序设计的思想，引入了诸多新的名词，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。与OOP（object-oriented programming）中的多态（polymorphism）一样，泛型也是一种软件的复用技术。
从实现层次看，整个STL是以一种类型参数化的方式实现的，这种方式基于一个在早先C++标准中没有出现的语言特性--模板（template）。

二、常见用法
1.push_back：push_back是编程语言里面的一个函数名。如c++中的vector头文件里面就有这个push_back函数，在vector类中作用为在vector尾部加入一个数据。string中也有这个函数，作用是字符串之后插入一个字符。

void push_back(value _type _Ch);
_Ch --> The character to be added to the end of the string.

string a="123";

a.push_back('3'); //在字符串末尾添加一个字符，结果为 a="1233";

a.pop_back(); //在字符串末尾删除一个字符，结果为 a="12";

5.bool函数^[6]

一、定义：BOOL是布尔型变量，也就是逻辑型变量的定义符，类似于float、double等，只不过float定义浮点型，double定义双精度浮点型。在objective-c中提供了相似的类型BOOL，它具有YES值和NO值。布尔型变量的值只有真（true）和假（false），可用于逻辑表达式，也就是“或”“与”“非”之类的逻辑运算和大于小于之类的关系运算，逻辑表达式运算结果为真或为假。（百科）

二、优点：C++中如果值非0就为True,为0就是False。比如：bool b;b=(1>2) //此时b为false。b=(2>1) //此时b为true
比如讲你在写数据结构的时候，有时候需要判断一下链表是不是为空，这时候需要用到bool函数，再者，你看到bool就知道这个函数返回值只是用于判断真假。
比如你写一个比较两个字符是否相等的函数，如果不相等就返回真，否则返回··假，你可以写:

int function(char a,char b)
{
return a-b;
}

但是bool函数返回的只有true和false。而int会返回各种数字，但是你关心的不是数字的多少，而是这个数字为不为0.所以这种情况用bool会更加简洁，规范，你看到bool就知道这是一个判断真假函数，但是你看到是int型呢？你可能会以为返回的数字有用，又要重新看看程序。
当你写一个程序，要调用100多个自定义函数，其中又有几十个判断真假的函数时，你全用int结果可想而知！

6.for (auto &c : s)

这是特殊的for循环语句。for循环中的每个迭代初始化一个新的引用。
如果要更改字符串中的字符值，我们必须将循环变量定义为引用类型。请记住，引用只是给定对象的另一个名称。当我们使用引用作为我们的控制变量时，该变量依次绑定到序列中的每个元素。使用引用，我们可以更改引用所绑定的字符。

for (auto &c : s)   
c = toupper(c);

相当于：

for (auto it = s.begin(); it != s.end(); ++it)
{
    auto &c = *it;
    c = toupper(c);
}

本题解中，

for(const auto &c:s) ++h[c-'a'];

是利用编码相减的偏移量，做了一个hash表随时存取。

【参考资料】
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number/solution/you-duo-shao-xiao-yu-dang-qian-shu-zi-de-shu-zi--2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 ↩
【参考资料】
版权声明：本文为CSDN博主「K_rew」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/K_rew/article/details/50527287 ↩
【参考资料】
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/increasing-decreasing-string/solution/shang-sheng-xia-jiang-zi-fu-chuan-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 ↩
【参考资料】
版权声明：本文为CSDN博主「小拳头」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/xiaoquantouer/article/details/51647865 ↩
【参考资料】
版权声明：本文为CSDN博主「HUST_Miao」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/u010183728/article/details/81913729 ↩
【参考资料】
版权声明：本文为CSDN博主「Single-minded T」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_40638006/article/details/80736559 ↩

刷题日记 | LeetCode刷题总结（C++）

892. 三维形体的表面积（3月25日）

01 知识点

1.vector

2.引用

1365. 有多少小于当前数字的数字（3月26日）

01 方法

【暴力法】

思路

算法

复杂度分析

【桶计数】^[1]

思路

算法

复杂度分析

02 知识点

1.前缀和^[2]

1370. 上升下降字符串（3月25日）

01 方法^[3]

思路

算法

复杂度分析

02 知识点

1.内联函数

2.auto^[4]

3.Lambda表达式

4.STL（Standard Template Library）^[5]

5.bool函数^[6]

6.for (auto &c : s)

猜你喜欢

热点阅读

刷题日记 | LeetCode刷题总结（C++）

892. 三维形体的表面积（3月25日）

01 知识点

1.vector

2.引用

1365. 有多少小于当前数字的数字（3月26日）

01 方法

【暴力法】

思路

算法

复杂度分析

【桶计数】[1]

思路

算法

复杂度分析

02 知识点

1.前缀和[2]

1370. 上升下降字符串（3月25日）

01 方法[3]

思路

算法

复杂度分析

02 知识点

1.内联函数

2.auto[4]

3.Lambda表达式

4.STL（Standard Template Library）[5]

5.bool函数[6]

6.for (auto &c : s)

猜你喜欢

热点阅读

【桶计数】^[1]

1.前缀和^[2]

01 方法^[3]

2.auto^[4]

4.STL（Standard Template Library）^[5]

5.bool函数^[6]