系列篇:
LeetCode 解题笔记（二）数组篇
● 建议：
1、不会的，没有头绪的，先学习答案，有些方法你脑海中都没有，如何又能想到呢？先学习答案吧
2、暴力解法也是解，先出答案再考虑时间复杂度和空间复杂度
3、选择题目，除了在难度上要循序渐进，还建议在算法上进行划分。目前先刷个100题再说
4、同一类型，批量答题，将有助于系统性的学习！
● 刷题记录
03月09日 更新
● 字符串长度或大小:
s.length();
s.size();
● 反转一个数的技巧
resverdNum = resverdNum *10 + x%10;
x/= 10;
● 指针对应的空位 nullptr
if(digits.empty()) return vector<string>();
● ++写在前面
++i:
● range-based for：
string s1 = "123456";
for (auto i : s1 ) //普通方式改变访问
i ++; //改变字符串的每个字符， 不会改变整个字符串s1（123456）
for(const auto& i : s3) //常引用方式访问元素，避免拷贝代价 s1（123456）
// i ++; //报错
for (auto& i : s2 ) //引用方式访问元素
i ++; //改变字符串的每个字符， 使用引用会改变整个字符串s1（234567）
● vector 相关，（代替数组）
int maxArea(vector<int>& height) { int n = height.size()} //取大小
vector<int> vret; //用于返回最终结果vret
vret.push_back(3); //在vret中数组最后插入3
vert.pop_back(); //在vret中最后去掉一个数
vector<int> v(201, 0); //用于存储nums数组中元素的重复次数
vector<int> b(2,-1); //初始化一个大小为2，值为-1的容器b
void threeSum(vector<int>& nums) {
vector<vector<int>> ans; //二维数组
ans.push_back( {nums[i], nums[j], nums[k]}; //二维数组添加
...
}
//没有指定 vector 的大小，不能在中间直接插入数据的！
● 普通数组
//初始化
int[] array= new int[5];
● 直接调用函数：交换、快速排序
swap(x,y); //值交换直接调用
void fun(vector<int>& nums) {
std::sort(nums.begin(), nums,end()) //快速排序
...
}
● 无穷大的数
int inf = 1e9; //1e9 表示一个大数，记为无穷大
● map、unordered_map、set、unordered_set
其中 unordered_map、unordered_set 用的太多了！
参考：map,unordered_map,set和unordered_set
● map
优点：有序性，这是map结构最大的优点（map 内部实现了一个 红黑树）
缺点：空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率（低于unorder_map），但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间（但占用的内存比unorder_map低）
适用处：对于那些数据存储有顺序要求的问题，用map会更高效一些
实例：
vector<int> list = { 5,14,34,22,39,5};
map<int, int> map;
for (int i = list.size() - 1; i >= 0; i--) {
map[i] = list[i]; //倒序插入
}
for (auto num = map.begin(); num != map.end(); num ++) {
cout << num->first << ' ' << num->second << endl; //输出的数是有序的且有两个
//打印：
//0 5
//1 14
//2 34
//3 22
//4 39
//5 5
}
//find()和count()的输入参数都是key值
cout << map.find(3)->first << "," << map.find(3)->second; //3,22
//m.count(n)计算下标为n的位置有无数据，有返回1，无返回0
cout << map.count(5); // 1
参考：https://blog.csdn.net/bryant_zhang/article/details/111600209
● unordered_map（无序的映射 ）
优点： 因为内部实现了哈希表，因此，其元素的排列顺序是无序的。因此其查找速度非常的快（运行效率快于map），时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用
缺点： 哈希表的建立比较耗费时间（unorder_map占用的内存比map要高）
适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用 unordered_map
vector<int> list = { 5,14,34,22,39,5};
unordered_map<int, int> map;
for (int i = list.size()-1; i>=0; i--) {
map[i] = list[i]; //倒序插入
}
for (unordered_map<int, int>::iterator i = map.begin(); i != map.end(); i++) { //auto 更好
cout << i->first << ' ' << i->second << endl; //输出的数是有序的且有两个
/*打印：unordered_map 是基于hash表的，因此元素是无序存储的（ 不按键 升序排列）。
5 5
4 39
3 22
2 34
1 14
0 5
*/
}
//find()和count()的输入参数都是key值
cout << map.find(3)->first << "," << map.find(3)->second; //3,22
//m.count(n)计算下标为n的位置有无数据，有返回1，无返回0
cout << map.count(5); // 1
//删除下标为 5 的位置
cout << map.erase(5);
实例2：
leetcode ：169. 多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
class Solution {
public:
int majorityElement(vector<int>& nums) {
//哈希, 不用数组因为是不知道有多大；对于乱序问题、查找问题，适用于 unordered_map
unordered_map<int,int> seen;
int n = nums.size();
int majority = 0;
for(auto const & num : nums) {
seen[num]++;
if(seen[num] > n/2) {
majority = num;
}
}
return majority;
}
};
实例3： 17. 电话号码的字母组合
unordered_map<char, string> phoneMap{
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
● set
set 实现了红黑树的平衡二叉检索树的数据结构，插入元素时，它会自动调整二叉树的排列，把元素放到适当的位置，以保证每个子树根节点键值大于左子树所有节点的键值，小于右子树所有节点的键值；另外，还得保证根节点左子树的高度与右子树高度相等。**在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。**平衡二叉检索树使用中序遍历算法，检索效率高于vector、deque和list等容器，另外使用中序遍历可将键值按照从小到大遍历出来。
实例1
vector<int> list = { 5,14,34,22,39,5 };
set<int> set1;
for (int i = list.size() - 1; i >= 0; i--) {
set1.insert(list[i]); //倒序插入
}
for (auto num = set1.begin(); num != set1.end(); num ++) {
cout << *num << endl; //输出的数是有序的且只有一个5
/*打印结果* set 是基于RBT的，因此元素是顺序存储的（默认按 键值 升序排列）。
5
14
22
34
39 */
}
cout << *set1.find(5) << endl; //5
cout << set1.count(5) << endl; //1
● STL 容器： unordered_set
unordered_set的内部实现了一个 哈希表，因此， 其元素的排列顺序是无序的。
实例1：
//#include <unordered_set>
vector<int> list = { 5,14,34,22,39,5 };
unordered_set<int> set;
for (int i = list.size() - 1; i >= 0; i--) {
set.insert(list[i]); //倒序插入
}
for (unordered_set<int>::iterator num = set.begin(); num != set.end(); num ++) {
cout << *num << endl; //输出的数是无序的且只有一个5
/*打印结果: unordered_set是基于hash表的，因此元素是无序存储的（ 不按键值 升序排列）。
5
39
14
22
34 */
}
cout << *set.find(39) << endl; //39
cout << set.count(14) << endl; //1
实例2：
//初始化一个结构体
unordered_set<ListNode *> seen;
//判断是否包含某一个元素
seen.count(head);
//添加一个元素
seen.insert(head);
实例三： 217.存在重复元素
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> s;
for (int x: nums) {
if (s.find(x) != s.end()) {
return true;
}
s.insert(x);
}
return false;
}
};
revertedNum //回收的数
merge // 合并
frequency //频率
链接：9. 回文数
标签：
思路：1. 字符串反转；2. 数字的反转（采用这个），且只需要反转一半，当然奇数需要多反转一下。
注意：1. 特殊数的判定：位数为0的、数字0、负数 2. 奇数和偶数的判定 3.while和for的抉择
class Solution {
public:
bool isPalindrome(int x) {
//负数不考虑，末尾为0不考虑
//0 的特殊性
if(x<0 || (x%10==0 && x!=0) ) {
return false;
}
int revertedNum = 0;
while(revertedNum < x) {
revertedNum = revertedNum * 10 + x%10;
x /= 10;
}
return (x==revertedNum) || (x==revertedNum/10);
}
};
链接： 11. 盛最多水的容器
题目：
关键词： 双指针
暴力解法：（会超时）
class Solution {
public:
int maxArea(vector<int>& height) {
int n = height.size();
int maxarea = 0;
for(int i=1; i<n; i++) {
for(int j=0; j<i; j++) {
maxarea = max(min(height[j], height[i]) * (i-j), maxarea);
}
}
return maxarea;
}
};
官方答案： 双指针
抛弃长的，以短的边，水只会越来越少。所以只能抛弃短的，以长的为边，水才有可能越来越大~，人生也是如此，知道已经是最差的活法呢，为什么不换一种方式重新开始呢！
class Solution {
public:
int maxArea(vector<int>& height) {
int left=0, right=height.size()-1;
int water = 0;
while(left < right) {
int tmp = min(height[left] ,height[right]) * (right - left) ;
water = max(tmp, water);
if(height[left] < height[right]) {
++ left;
}
else {
-- right;
}
}
return water;
}
};
链接：15. 三数之和
标签： 双指针、排序、数组
我的思路： 三重循环，但是没有考虑重复的，比如 -5,1,1,1,4,4,4 就有多组重复的
思路： 排序+双指针， 排序后，然后固定第一个数，另外两个数从两头加，大了话，右指针减，小了话左指针加，知道 left=right ，然后再去重！
网友简洁版答案：（好理解）
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> ret;
if(n < 3) return {}; // 特判
//快速排序
std::sort(nums.begin(), nums.end());
//固定第一个数，转化为求两数之和
for(int i=0; i<n; ++i) {
if(nums[i] >0) return ret; //第一个数为0，后续也不可能相加为0了，除开0,0,0
if(i>0 && nums[i] == nums[i-1]) continue;
int left = i+1, right =n-1; // 双指针在nums[i]后面的区间中寻找和为0-nums[i]的另外两个数
while(left < right) {
if(nums[left] + nums[right] > -nums[i]) {
--right; // 两数之和太大，右指针左移
}
else if(nums[left] + nums[right] < -nums[i]) {
++left; // 两数之和太小，左指针右移
}
else {
// 找到一个和为零的三元组，添加到结果中，左右指针内缩，继续寻找
ret.push_back( {nums[i], nums[left], nums[right]} );
--right;
++left;
// 去重：第二个数和第三个数也不重复选取
// 例如： -5,1,1,1,4,4,4 如果用if还是会重复 -5 1 4, 要用while
while (left < right && nums[left] == nums[left-1]) left++;
while (left < right && nums[right] == nums[right+1]) right--;
}
}
}
return ret;
}
};
链接： 17. 电话号码的字母组合
标签： 回溯、哈希表、字符串、广度优先搜索、树
思路： 看答案开始不懂，但用纸笔一步一步拆解跟踪后，便一目了然。主要是画出一个树的结构，树根是出发点，第一层表示第一个数字代表的字母，以此类推…
简单版：
class Solution {
public:
vector<string> letterCombinations(string digits) {
if(digits.empty()) return vector<string>();
unordered_map<char,string> phoneMap = {
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
vector<string> ans;
string str = "";
traceback(0, ans, phoneMap, digits, str);
return ans;
}
// 引用，自己始终要记录;
void traceback(int index, vector<string>& ans, unordered_map<char,string> phoneMap, string digits, string str) {
//递归，进来就是条件
if(index == digits.size()) {
ans.push_back(str);
return ; //可不加，加入好理解
}
else {
//添加过程中的字符
char digit = digits[index]; //"245" 中的 “2”
string letters = phoneMap.at(digit); //也可以直接 phoneMap[digit], 得到“abc”
for (char letter: letters) {
str.push_back(letter); //最后添加单个字符
traceback(index+1, ans, phoneMap, digits, str);
str.pop_back(); //移除最后的字符
}
}
}
};
增加引用&、const、auto 后： （要习惯这样用，更加严谨，可读可写，一目了然）
class Solution {
public:
vector<string> letterCombinations(string digits) {
if(digits.empty()) return vector<string>();
unordered_map<char,string> phoneMap = {
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
vector<string> ans;
string str = "";
traceback(0, ans, phoneMap, digits, str);
return ans;
}
// 引用，自己始终要记录;
void traceback(int index, vector<string>& ans, const unordered_map<char,string>& phoneMap, const string& digits, string& str) {
//递归，进来就是条件
if(index == digits.size()) {
ans.push_back(str);
return ; //可不加，加入好理解
}
else {
//添加过程中的字符
char digit = digits[index]; //"245" 中的 “2”
const string& letters = phoneMap.at(digit); //也可以直接 phoneMap[digit], 得到“abc”
for (const auto& letter: letters) {
str.push_back(letter); //最后添加单个字符
traceback(index+1, ans, phoneMap, digits, str);
str.pop_back(); //移除最后的字符
}
}
}
};
链接： 20. 有效的括号
标签： 栈、哈希
class Solution {
public:
bool isValid(string s) {
int n = s.size();
if (n % 2 == 1) {
return false;
}
unordered_map<char, char> pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
//C++ Stack（堆栈） 是一个容器类的改编，为程序员提供了堆栈的全部功能，——也就是说实现了一个先进后出（FILO）的数据结构。
//c++ stl栈stack的头文件为: #include <stack>
//empty() 堆栈为空则返回真
//pop() 移除栈顶元素
//push() 在栈顶增加元素
//size() 返回栈中元素数目
//top() 返回栈顶元素
stack<char> stk;
//这个和foreach的for循环一样的，也就是遍历
//这里的char ch: s就是定义一个遍历字符ch，让它分别等于字符串数组s里面的各个字符，然后执行下面的语句，当c被赋值为s里面所有字符各一次后，就会退出这个循环.
for (char ch: s) {
//如果 hash_map 包含其排序键与参数键匹配的元素，则返回 1；如果 hash_map 不包含具有匹配键的元素，则返回 0
if (pairs.count(ch)) {
//栈中本身是空， 如果匹配了右键 而此时而栈为空、或者栈顶不等于键值，则不满足条件
if (stk.empty() || stk.top() != pairs[ch]) {
return false;
}
//满足条件，移除栈顶的元素
stk.pop();
}
else {
stk.push(ch); // 增加一个值（左括号）
}
}
return stk.empty();
}
};
链接：21. 合并两个有序链表
标签：链表、迭代
思路：比较两个链表的第一个数就好，谁的小，新建的链表指向谁。
注意：指针的空为nullptr、链表的指针使用->
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
//定义头：方便返回 注意是地址
ListNode* listHead = new ListNode(-1);
//定义一个跟随的指针
ListNode* prev = listHead;
while(l1!=nullptr && l2!=nullptr) {
if(l1->val <= l2->val) {
prev->next = l1;
l1=l1->next;
}
else {
prev->next = l2;
l2=l2->next;
}
prev = prev->next;
}
if(l1==nullptr) prev->next = l2;
else prev->next = l1;
return listHead->next;
}
};
链接：53. 最大子序和
标签：动态规划、滚动数组
思路：存在最大和：
f(i) = max{f(i−1)+nums[i], nums[i]}
注意：指针的空为nullptr、链表的指针使用->
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//pre: 加上新来的后当前最大的， maxAns：历史最大的
int pre = 0, maxAns = nums[0];
//for(int i=0; i<nums; i++)
for(const auto& a: nums) {
//如果前边累加后还不如自己本身大，那就把前边的都扔掉，从此自己本身重新开始累加。
pre = max(pre + a, a);
maxAns = max(maxAns, pre);
}
return maxAns;
}
};
链接：55. 跳跃游戏
标签： 贪心算法
class Solution {
public:
bool canJump(vector<int>& nums) {
int k=0;
int num = nums.size();
for(int i=0; i<num; i++ ) {
if(k<i) return false;
//获取最大可跳的数
k = max(k, nums[i] + i);
//以下可有可无
if(k >= num-1) return true;
}
return true;
}
};
链接：70. 爬楼梯
标签： 动态规划
思路:
//f(1) = 1
//f(2) = 2
//f(3) = f(2) + f(1) = 3
//f(4) = f(3) + f(2) = 5
//再用滚动数组
class Solution {
public:
int climbStairs(int n) {
int a=1,b=2,c;
if(n==1) return c=1;
if(n==2) return c=2;
for(int i=3; i<=n; ++i) {
c = a + b;
a = b;
b = c;
}
return c;
}
};
链接：121. 买卖股票的最佳时机
标签： 动态规划、数组
题目：
我的答案：
思路： 不断的找最小值，不断计算后面的数与最小值的差值。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int min = prices[0];
int profit = 0, maxProfit = 0;
for(int i=1; i<n; i++) {
if(prices[i] <= min) {
min = prices[i];
}
else {
profit = prices[i] - min;
if(maxProfit <= profit)
maxProfit = profit;
}
}
return maxProfit;
}
};
官方：思路基本一样，但很简洁，学习学习…
class Solution {
public:
int maxProfit(vector<int>& prices) {
int inf = 1e9; //1e9 表示一个大数，记为无穷大
int minprice = inf, maxprofit = 0;
for (int price: prices) {
maxprofit = max(maxprofit, price - minprice);
minprice = min(price, minprice);
}
return maxprofit;
}
};
链接：141. 环形链表
标签： 哈希表、Floyd 判圈算法、链表、双指针
题目：
官方方法一：
使用哈希表存储所有已经访问过的节点，每次判断是否存在
（我也想到了，但是不会使用）
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode *> seen;
while (head != nullptr) {
if(seen.count(head)) {
return true;
}
seen.insert(head);
head = head->next;
}
return false;
}
};
官方方法二：
Floyd 判圈算法，采用双指针，一快一慢，快的指针每次移动两个，慢的每次移动一个，如果有环则一定相遇，如果到了链表尾没有相遇则不是有环的
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
//双指针
if( head==nullptr || head->next == nullptr) {
return false;
}
ListNode* fast = head->next;
ListNode* slow = head;
while(fast != slow) {
//不相等就开启下一轮，一定要提前判断空指针，记得从左往右的一个一个判断
//更加习惯下面的判断，因为第二个已经判断不为空了
if( fast->next == nullptr || fast->next->next == nullptr) {
return false;
}
//官方：
// if (fast == nullptr || fast->next == nullptr) {
// return false;
// }
fast = fast->next->next;
slow = slow->next;
}
return true;
}
};
链接：169. 多数元素
标签：哈希、数字
方法一：我的方法(哈希方法）
class Solution {
public:
int majorityElement(vector<int>& nums) {
//哈希, 不用数组因为是不知道有多大
unordered_map<int,int> seen;
int n = nums.size();
int majority = 0;
for(auto const & num : nums) {
seen[num]++;
if(seen[num] > n/2) {
majority = num;
}
}
return majority;
}
};
方法二：官方：哈希映射
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> counts;
int majority = 0, cnt = 0;
for (int num: nums) {
++counts[num];
if (counts[num] > cnt) {
majority = num;
cnt = counts[num];
}
}
return majority;
}
};
方法三：官方：
思路：先排序，再用哈希映射
链接：283. 移动零
标签： 数组、双指针
题目：
自答：
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int j = 0;
for(int i=0; i<n; i++) {
//核心：不是0的，往前挪
if(nums[i] != 0) {
nums[j++] = nums[i];
}
}
//后面的补0
for(; j< n; j++) {
nums[j] = 0;
}
}
};
官方： 双指针
● 使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
● 右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
● 左指针左边均为非零数；右指针左边直到左指针处均为零。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size(), left = 0, right = 0;
while(right < n) {
if(nums[right]) {
swap(nums[left], nums[right]);
left++;
}
right++;
}
}
};
链接：461. 汉明距离
标签：位运算
题目：
1）我的答案：
① 通过异或，可以获取不同位置的值
② 通过取余，求得 1 的个数
class Solution {
public:
int hammingDistance(int x, int y) {
int z = x ^ y, ret = 0;
while (z) {
if( z%2 ) {
ret ++;
}
z /= 2;
}
return ret;
}
};
2）官方：移位实现位计
① 通过异或，可以获取不同位置的值
② 通过向右移位，1就在最末位，然后与1做与运算
class Solution {
public:
int hammingDistance(int x, int y) {
int s = x ^ y, ret = 0;
while (s) {
ret += s & 1;
s >>= 1;
}
return ret;
}
};
3）官方：Brian Kernighan 算法
class Solution {
public:
int hammingDistance(int x, int y) {
int s = x ^ y, ret = 0;
while (s) {
s &= s - 1;
ret++;
}
return ret;
}
};
链接： 448. 找到所有数组中消失的数字
题目：
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
int n = nums.size();
for(auto& num: nums) {
int x = (num-1) % n;
nums[x] += n;
}
vector<int> ret;
for(int i=0; i<n; i++) {
if(nums[i] <= n) {
ret.push_back(i+1);
}
}
return ret;
}
};
链接： 1636. 按照频率将数组升序排序
标签：排序、vector 容器
思路：
① 首先创建一个大小为201的数组vn来存储nums中所有元素的出现次数（元素值-100对应v中下标为0,依次类推）
② 然后按频率低到高、数字大到小 输出下标值到vret返回即可
输入：nums = [1,1,2,2,2,3]
输出：[3,1,1,2,2,2]
解释：'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。
class Solution {
public:
vector<int> frequencySort(vector<int>& nums)
{
//定义一个数组，里面包含了-100 到 100 之间出现的个数
vector<int> vn(201,0);
//定义一个返回的数组
vector<int> vret;
//先求出-100 到 100 之间出现的个数 +100 后 求出0 到 200 之间出现的个数
for(const auto& a: nums) {
vn[a+100] ++;
}
//频率排序： 最多100， 最多nums.size
int nSize = nums.size();
for(int i=1; i<=nSize; i++) {
//从100 往下 到-100 这样是倒序 但是最大的数字 可以算出来
for(int j=200; j>=0; j--) {
//核心为： 从频率递到高，从大到小输出 频率肯定先试只出现一次的，3
if(vn[j] == i) {
for(int k=0; k<i; k++) {
vret.push_back(j-100);
}
}
}
}
return vret;
}
};