LeetCode刷题记录

Posted by kevin on July 1, 2020

1 两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

我只会用暴力解法,看了题解才知道哈希表可以这样用,屌!就,用一个表存入数据和索引,遍历这个表一次,如果 target 减去当前元素的值在哈希表里面的话可以直接返回索引,就不需要双重循环遍历了。更牛逼的做法是变将数据和索引存入哈希表边检查有没有存在,有的话可以不用将剩下的数据存完就返回了。

class Solution {	// 我写的辣鸡暴力法
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        for (int i = 0; i < nums.size(); ++i) {
            int t1 = nums[i];
            for (int j = i + 1; j < nums.size(); ++j) {
                int t2 = nums[j];
                if (t1 + t2 == target) {
                    result.push_back(i);
                    result.push_back(j);
                }
            }
        }
        return result;
    }
};

这就是更牛逼的做法,不过 C++ 的 map 中的 find 和 count 方法针对的都是 key ,并不是 value,因此如果我们想要知道索引号的话就得将索引和数据反过来存进 map 中

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> a;//提供一对一的hash
        vector<int> b(2,-1);//用来承载结果,初始化一个大小为2,值为-1的容器b
        for(int i=0;i<nums.size();i++)
        {
            if(a.count(target-nums[i])>0)   //找到了目标
            {
                b[0]=a[target-nums[i]];
                b[1]=i;
                break;
            }
            a[nums[i]]=i;//反过来放入map中,用来获取结果下标
        }
        return b;
    };
};

136 只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1] 输出: 1

示例 2:

输入: [4,1,2,1,2] 输出: 4

这题就很骚,线性复杂度,又不能用额外空间,先来几个正常点的题解。

暴力解法如下,两重 for 循环,找不到配对的数字就返回,找到的话就定义这两个位置为无效,不参与 for 循环

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret, i = 0, j = 0;
        int invalid = INT_MAX;
        for (i = 0; i < nums.size(); ++i) {
            if (nums[i] != invalid){
                for (j = i + 1; j < nums.size(); ++j) {
                    if (nums[j] != invalid && nums[i] == nums[j]){
                        nums[i] = invalid;
                        nums[j] = invalid;
                        break;
                    }                             
                }
                if (j == nums.size()){  // 说明没有找到配对的数字
                    break;
                }
            }
        }
        return nums[i];
    }
};

但是我还是喜欢哈希表的解法,将数字存为 key,次数存为 value,每次有同样的就直接次数 ++ 就行了,我爱哈希表!

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> ump;
        for (const auto &n : nums){
            ump[n]++;
        }
        int res;
        for (auto it = ump.begin(); it != ump.end(); ++it) {
            if (--(it->second) == 0){
                res = it->first;
                break;
            }
        }
        return res;
    }
};

异或满足分配律和交换律,并且题目说每个数字只出现两次,正好是异或发挥作用的时候,因为一个数异或自己就是 0, 0 和任何一个数异或都是另一个数,这题不断的异或下去就是最终答案(要是说每个数字出现 3 次或者奇数次就不能这么做了)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = nums[0];
        for (auto it = nums.begin() + 1; it < nums.end(); ++it) {
            res ^= *it;
        }
        return res;
    }
};

206 反转链表

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

有两种解法,都是利用双指针来反转,个人觉得第二种解法比较容易些(做链表题一定要在纸上画出来!)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL)
            return NULL;

        ListNode *cur = NULL, *pre = head;
        while (pre != NULL)
        {
            ListNode *t = pre->next;
            pre->next = cur;
            cur = pre;
            pre = t;
        }
        return cur;
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL)
            return NULL;

        ListNode *cur = head;
        while (head->next != NULL)
        {
            // 保护现场,不改变head
            ListNode *t = head->next->next;
            head->next->next = cur;
            cur = head->next;
            head->next = t;
        }
        return cur;
    }
};

209 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组,并返回其长度。如果不存在符合条件的连续子数组,返回 0。

示例:

输入:s = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数组 [4,3] 是该条件下的长度最小的连续子数组。

两种方法,首先可以直接用暴力法求解,也就是用两个 for 循环,

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int ans = INT_MAX;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= s) {
                    ans = min(ans, j - i + 1);
                    break;
                }
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int ans = INT_MAX;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

204. 计数质数

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

吗的,这题就是计算质数的个数啊,大一 C 语言经典考题,但是我第一遍竟然没写出来……,然后说一下,暴力法不行……会超时,所以可以优化一下暴力法,比如 2 的倍数不可能是质数之类的。当然,还有一种解题思路就是将当前数字的倍数全都除掉,然后最后剩下的就是质数,这个牛逼!

原始暴力法(超时)

class Solution {
public:
    int countPrimes(int n) {
        int res = 1;
        int i = 0, j = 0;

        if (n < 3) {
            return 0;
        }
        for (i = 3; i < n; ++i) {
            int flag = true;
            for (j = 2; j <= std::sqrt(i); ++j) {
                if (i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                res++;
            }
        }
        return res;
    }
};

改进版暴力法(偶数非质数)

class Solution {
public:
    int countPrimes(int n) {
        int res = 1;
        int i = 0, j = 0;

        if (n < 3) {
            return 0;
        }
        for (i = 3; i < n; ++i) {
            if (i % 2 == 0) {
                continue;
            }
            int flag = true;
            for (j = 3; j <= std::sqrt(i); j+=2) {
                if (i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                res++;
            }
        }
        return res;
    }
};

牛逼的方法(厄拉多塞筛法)

sort

class Solution {
public:
    int countPrimes(int n) {
        int res = 0;
        int array[n] = {0};
        for (int i = 2; i < n; ++i) {
            if (array[i] != -1){
                res++;
                // 这句是精髓!
                for (int j = i + i; j < n; j += i) {
                    array[j] = -1;        
                }
            }
        }
        return res;
    }
};

215 数组中的第K个最大元素

##

二叉树的三种遍历(前序144,中序94,后序145)

451 根据字符出现频率排序

示例 1:

输入: “tree”

输出: “eert”

解释: ‘e’出现两次,’r’和’t’都只出现一次。 因此’e’必须出现在’r’和’t’之前。此外,”eetr”也是一个有效的答案。

还是用一个哈希表储存每个字符出现的次数,然后再将表里面的 key 和 value 储存进一个 vector 向量,对其进行排序,然后再输出即可

大佬的题解 (unordered_map 内部实现了一个哈希表,是无序的,map 的话内部是实现了一个红黑树,所以里面的数据全都是有序的)

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> ump;
        for (const auto &c : s) {
            ++ump[c];
        }
        vector<pair<char, int>> vec;
        for (const auto &m : ump) {
            vec.push_back(m);
        }
        sort(vec.begin(), vec.end(), [](const pair<char, int> &p1, const pair<char, int> &p2) { return p1.second > p2.second; });
        string ret;
        for (const auto &v : vec) {
            ret += string(v.second, v.first);
        }
        return ret;
    }
};

我仿照的题解(所以说还是得学一下 stl,大佬这个 for 循环就很实用,不用管迭代器数据是什么类型,直接 auto 一把梭)

class Solution {
    public:
        string frequencySort(string s) {
            map<char, int> mp;
            for (int i = 0; i < s.length(); ++i) {
                mp[s[i]] += 1;
            }
            vector<pair<char, int>> vec;
            for (const auto &m : mp) {
                vec.push_back(m);
            }
            sort(vec.begin(), vec.end(), [](const pair<char, int> &p1, const pair<char, int> &p2) { return p1.second > p2.second; });
            string ret;
            for (int i = 0; i < vec.size(); ++i) {
                ret += string(vec[i].second, vec[i].first);
            }
            return ret;
        }
};

961. 重复 N 次的元素

在大小为 2N 的数组 A 中有 N+1 个不同的元素,其中有一个元素重复了 N 次。

返回重复了 N 次的那个元素。

示例 1:

输入:[1,2,3,3] 输出:3

示例 2:

输入:[2,1,2,5,3,2] 输出:2

我想到了中规中矩的哈希表,存储数字和他出现的次数,边存的时候便检查有没有大于1 ,大于 1 就说明是这个数字

class Solution {
public:
    int repeatedNTimes(vector<int>& A) {
        int res = -1;
        unordered_map<int, int> ump;
        for (auto it = A.begin(); it != A.end(); it++) {
            ump[*it]++;
            if (ump[*it] > 1) {
                res = *it;
            }
        }
        return res;
    }
};

下面一种方法就比较巧妙,直接猜测排列,2N 个元素,如果有两个相同的元素是相邻的,那么直接相邻元素异或为 0 就找到答案了。如果没有两个元素相邻的话,那么前面四个元素的排列一定是 ABAC 或者 ABCA 或者 BABC 这三种,逐一判断一下就知道答案了

class Solution {
public:
    int repeatedNTimes(vector<int>& A) {
        int res = -1;
        for (auto it = A.begin(); it != A.end() - 1;) {
            if(!*it ^ *(it++)) {
                res = *it;
            }
        }
        if (A[0] == A[2] || A[0] == A[3]) {
            res = A[0];
        }
        if (A[1] == A[3]) {
            res = A[1];
        }
        return res;
    }
};