记录力扣-数据结构入门学习计划的做题记录。
第1天 数组#
217. 存在重复元素#
思路#
定义一个std::set<int>，每次插入数组元素前，检查set中是否已有整数。若已存在，则返回true；否则，继续执行，并在最后返回false。
代码#
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
set<int> check;
for (int num : nums) {
if (check.find(num) != check.end())
return true;
check.insert(num);
}
return false;
}
};笔记#
遍历 vector 可使用C++11提供的 range based for loop 特性
vector<int> vi; ... for(int i : vi) cout << "i = " << i << endl;set.find()方法返回指向该值的iterator，若 set 中不存在，则返回set.end()(iterator)Return value
Iterator to an element with key equivalent to key. If no such element is found, past-the-end (see end()) iterator is returned.
53. 最大子数组和#
思路#
定义一个dp[]用于保存以第i个数字结尾的子数组的最大连续子数组和，用ans记录当前最大子数组和。
代码#
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int l = nums.size();
int ans = nums[0];
int dp[l];
dp[0] = nums[0];
for (int i = 1; i < l; i++) {
dp[i] = max(nums[i], dp[i - 1] + nums[i]);
ans = max(ans, dp[i]);
}
return ans;
}
};笔记#
解决动态规划问题的核心在于写出正确的状态转移方程。这道题看似是编程题，实际是数学题。
dp[]数组用于维护状态，顾名思义，状态转移方程用于描述dp[n]和dp[n-1]的关系（类似数学里的数列）。找出dp[n]和dp[n-1]的关系，编程解决剩下的问题。
第2天 数组#
1. 两数之和#
思路#
定义一个std::unordered<int, int>，key 表示nums[]中的数，val 表示该数对应的索引。
遍历nums[]，若已存在，则返回true；否则，在mp中保存该数和它在nums[]中的索引。
代码#
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); i++) {
if (mp.find(target - nums[i]) != mp.end())
return {i, mp[target - nums[i]]};
mp[nums[i]] = i;
}
return {-1, -1};
}
};笔记#
注意
std::unordered<int, int>.find()的返回类型为iterator，若未找到则返回mp.end()。C++ 11 中可通过
std::vector<int> v = {1, 2, 3, 4};初始化一个vector。
88. 合并两个有序数组#
思路#
代码#
笔记#
第3天 数组#
350. 两个数组的交集 II#
350. 两个数组的交集 II - 力扣（LeetCode）
121. 买卖股票的最佳时机#
第4天 数组#
566. 重塑矩阵#
118. 杨辉三角#
第5天 数组#
36. 有效的数独#
73. 矩阵置零#
第6天 字符串#
387. 字符串中的第一个唯一字符#
387. 字符串中的第一个唯一字符 - 力扣（LeetCode）
383. 赎金信#
242. 有效的字母异位词#
第7天 链表#
141. 环形链表#
21. 合并两个有序链表#
203. 移除链表元素#
第8天 链表#
206. 反转链表#
83. 删除排序链表中的重复元素#
83. 删除排序链表中的重复元素 - 力扣（LeetCode）
第9天 栈/队列#
20. 有效的括号#
232. 用栈实现队列#
第10天 树#
144. 二叉树的前序遍历#
94. 二叉树的中序遍历#
145. 二叉树的后序遍历#
第11天 树#
102. 二叉树的层序遍历#
104. 二叉树的最大深度#
101. 对称二叉树#
第12天 树#
226. 翻转二叉树#
112. 路径总和#
第13天 树#
700. 二叉搜索树中的搜索#
701. 二叉搜索树中的插入操作#
701. 二叉搜索树中的插入操作 - 力扣（LeetCode）
第14天 树#
98. 验证二叉搜索树#
653. 两数之和 IV - 输入 BST#
653. 两数之和 IV - 输入 BST - 力扣（LeetCode）