- 这个系列是为了笔试快速刷题
- 不定期、不定量、不定时，不高效
- 使用C++
1.两数之和
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
代码：
利用关联容器
unorder_map做中间变量，因为此容器查找速度很快，提升时间复杂度。<u>学习到了map容器的使用</u>
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution{
public:
vector<int> twoSum(vector<int>& nums, int target) {
//利用关联容器寻找，其实用其它数据结构都可以，只不过速度快而已
unordered_map<int, int> lookup;
for (int i = 0; i < nums.size(); ++i) {
//目标值减去当前值，剩下的值再去寻找
if (lookup.count(target - nums[i])) {
return {lookup[target - nums[i]], i};
}
lookup[nums[i]] = i;//数值和下标关联
}
return {};
}
};
int main(int argc, char *argv[])
{
Solution test;
int data[8] = {2, 1, 11, 15,3,4,6,7};
vector<int> input(data , data+8);
vector<int> result = test.twoSum(input,9);
return 0;
}
2.两数相加
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
代码：
主要利用一个进位标志位去做
<u>多使用
auto自动获取数据类型</u><u>等号的优先级低于问号的优先级</u>
#include <iostream>
using namespace std;
//定义一个链表节点
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL)
{}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy{0};
auto curr = &dummy;//自动判断类型
auto carry = 0;
//两个链表和进位标志位只要有一个不为空都可以计算
while (l1 || l2 || carry) {
auto a = l1? l1->val : 0, b = l2? l2->val : 0;
auto val = carry + a + b;
curr->next = new ListNode(val % 10);
carry = val / 10;
l1 = l1 ? l1->next : nullptr;//等号优先级比问号优先级低！！！
l2 = l2 ? l2->next : nullptr;
curr = curr->next;
}
return dummy.next;
}
};
int main(int argc, char *argv[])
{
ListNode t10(2),t11(4),t12(3),t20(5),t21(6),t22(7);
t10.next=&t11;
t11.next=&t12;
t20.next=&t21;
t21.next=&t22;
Solution test;
ListNode* result = test.addTwoNumbers(&t10,&t20);
return 0;
}
3.无重复字符的最长子串
给定一个字符串，找出不含有重复字符的最长子串的长度。
示例：
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。
代码：
利用
unorder_map加快速度，再用一个位置标志位（重复的位置）+一个长度标志位<u>换位思考</u>
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// Record the last occurrence of each char.
unordered_map<char, size_t> last_occurrence;
size_t starting_idx = 0, ans = 0;
for (size_t i = 0; i < s.size(); ++i) {
auto it = last_occurrence.find(s[i]);//返回迭代器
if (it == last_occurrence.cend()) {//如果字符不重复
last_occurrence.emplace_hint(it, s[i], i);
//last_occurrence.emplace(s[i],i);
} else { // s[i] appeared before. Check its validity.
if (it->second >= starting_idx) {
ans = max(ans, i - starting_idx);
starting_idx = it->second + 1;
}
it->second = i;
}
}
ans = max(ans, s.size() - starting_idx);
return ans;
}
};
int main(int argc, char *argv[])
{
string a = "bfadajkbplx";
Solution test;
size_t result = test.lengthOfLongestSubstring(a);
return 0;
}
