leetcode刷题(001-003)

• 这个系列是为了笔试快速刷题
• 不定期、不定量、不定时，不高效
• 使用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;
}