Leetcode刷题记录

发表于 2025-04-09 更新于 2025-04-18 阅读次数：

前言

太可恶了，我刚学完C++那些基础理论，像泛型编程，类，然后再没什么刷题经验的情况下，来了Leetcode，我就说这咋实现，感觉头都大了，怎么写怎么不对，然后一看发现，数据外部传入，我只需要补充类函数实现就行了，像int main()这些根本不用写，我只需要写个处理方法就行，气死我了！！！

学算法，刷力扣（leetcode）不知道怎么刷？来看看，我把刷题网站上线了！最强刷题攻略！_哔哩哔哩_bilibili

代码随想录

二分

第704题

704. 二分查找 - 力扣（LeetCode）

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        int mid;
        while(left<=right)
        {
            mid=left+(right-left)/2;
            if(nums[mid]==target)
            {
                return mid;
            }
            if(nums[mid]>target)
            {
                right=mid-1;/*为什么加一，因为边界条件一定不满足，可以丢弃，而且可以实现最终结束循环，left>right-1!!!*/
            }
            if(nums[mid]<target)
            {
                left=mid+1;/*为什么加一，因为边界条件一定不满足，可以丢弃，而且可以实现最终结束循环，left+1>right!!!*/
            }
        }
        return -1;
    }
};
/*这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。
第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。
while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。
while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]*/

哈希

第242题

242. 有效的字母异位词 - 力扣（LeetCode）

好家伙，这就速度能比，那个内存分布有点奇怪，提交次数不一样，内存分布大小就不一样

class Solution {
public:
    bool isAnagram(string s, string t) {
        int hash[26]={0};/*切记不要忘了化0！！！C++ 中的局部变量如果没有手动初始化，值是随机的垃圾值。你需要把 hash 初始化为全 0*/
        for(auto i:s)
        {
            hash[i-'a']++;
        }
        for(auto j:t)
        {
            hash[j-'a']--;
        }
        for(int n=0;n<26;n++)
        {
            if(hash[n]!=0)
            {
                return 0;
            }
            
        }
        return 1;
    }
};

第349题

349. 两个数组的交集 - 力扣（LeetCode）

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> u1(nums1.begin(),nums1.end());//记住vector!!!很有说法
        //他们之间相互转化很有意思，iterator
        set<int> u2;//目的是帮我去重！！！
        for(auto i:nums2)
        {
            if(u1.find(i)!=u1.end())//记住这些方法！，因为find没有则返回.end()
            {
                u2.insert(i);//vector与set，insert不一样
            }
        }
        vector<int>num;//我的返回值是vector
        for(auto i:u2)
        {
            num.push_back(i);
        }
    return num;
    }
};
/*因为题目改了，所以我也可以用数组，因为范围小了，习惯性数组都要大一点hash[1005]，因为要给hash碰撞腾出空间*/
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> s1;
        vector<int> vec;
        vec.reserve(1000);
        int hash[1005]={0};
        for(int i:nums1)
        {
            hash[i]=1;
        }
        for(int j:nums2)
        {
            if(hash[j]==1)
            {
                s1.insert(j);
            }
        }
        for(int a:s1)
        {
            vec.push_back(a);
        }
    return vec;
    }
    
};//但是数组的空间占用更多了

第202题

202. 快乐数 - 力扣（LeetCode）

class Solution {
public:
    int Sum(int n)
    {
        int m=0;
        while(n)
        {
            m+=(n%10)*(n%10);
            n=n/10;
            //这里写的好，要实现一个数每一项都进行一个操作，就用while循环判定，从最后一位向高位推进，每次丢掉最后一位就行了！！！！
        }
        return m;
    }
    //这个地方就是来验证是否出现过，判定是否是死循环，提前退出，避免时间浪费
    unordered_set<int> s1;
    bool isHappy(int n) {
        while(true)
        {
            if(n==1)
            {
                return true;
            }
            
            s1.insert(n);
            n=Sum(n);
            if(s1.find(n)!=s1.end())
            {
                return false;
            }   
        }
    }
};//判定一个元素是否在一个整体里出现过就用hash

第1题

1. 两数之和 - 力扣（LeetCode）

class Solution {
    public://当时学了STL，但不了解咋做题，直接给我弄红温了
        vector<int> twoSum(vector<int>& nums, int target) {
            for(int i = 0; i < nums.size(); i++){
                for(int j = i + 1; j < nums.size(); j++){
                    if(nums[i] + nums[j] == target){
                        return {i,j};
                    }
                }
            }
            return {0,0};
        }
    };/*这一次写出来，是因为要蓝桥杯了，所以临时抱佛脚，赶紧来做题，所有耐下心慢慢看我的问题，然后给我说int main有问题，我就知道了，所以稍加修改*/
//当然，看这个题还有个原因是刚好看了hash，来试试，显然没有头绪，所以我决定看看代码随想录了。
/*因为本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。*/
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>mp;//map就是遇到有下标保存输出的情况
        for(int i=0;i<nums.size();i++)
        {
            auto iter=mp.find(target-nums[i]);/*明确自己的目标哦，因为find返回的地址，所以用迭代器去接收*/
            if(iter!=mp.end())
        {
            return {iter->second,i};
        }
            mp.insert(pair<int,int>(nums[i],i));
        }
        return {};/*根据题目，虽然我们知道一定会有结果，但一定还是写上如果找不到的情况，增加代码的健壮性，return接相当于break，只不过return更强，代表直接结束，break只能循环里用！！！*/
    }
};//切记我们要查找什么，要得到什么，查的放key（因为可以用find(key)返回），要得到的什么，得到的用value，可以iter->second()来查找!

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
std::map 和std::multimap 的key也是有序的有序才用红黑树为底层的，无序直接用哈希表为底层的
map用来做什么
map中key和value分别表示什么

map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）

接下来是map中key和value分别表示什么。

这道题我们需要给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。

那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。

所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

过程一

动态规划

第509题

509. 斐波那契数 - 力扣（LeetCode）

class Solution {
public:
    int fib(int n) {
        if(n==0||n==1)
        {
            return n;
        }
        return fib(n-1)+fib(n-2);
        
    }
};//暴力，从后向前推
//这样是根据函数来感觉，还可以自定义一个数组，向里面存放数据，这样更有感觉，从前向后推
//还可以采用动态规划，剪枝，避免重复运算，使时间复杂度变大
//用的dp[]数组保留来实现
#include<iostream>
using namespace std;
int dp(int n);//这是动态规划
int iteration(int n);//这是迭代
int main()
{
	int n;
	while(1)
	{
		cout << "输入你想知道的斐波拉契第几项：";
		cin >> n;
		cout << dp(n) <<" --动态规划"<< endl;
		cout << iteration(n) <<" --迭代"<< endl;
	}
}
int dp(int n)
{
	int dp[1000] = { 0,1 };
	for (int i = 0; i < n; i++)
	{
		dp[i + 2] = dp[i] + dp[i + 1];
	}
	return dp[n];
}
int iteration(int n)
{
	if (n == 1 || n == 2)
	{
		return 1;
	}
	int a = 1, b = 1;
	for (int i = 0; i < n - 2; i++)
	{
		int temp = a + b;
		a = b;
		b = temp;
	}
	return b;
}

第70题

70. 爬楼梯 - 力扣（LeetCode）

class Solution {
public:
    int climbStairs(int n) {
        if(n==1||n==2)
        {
            return n;
        }
        return climbStairs(n-1)+climbStairs(n-2);
        //考虑所有可能实现的，然后加上去，这就是马尔科夫链那种呀
        //切记这里是俩，所以我们至少得有俩终止条件，否则会无限递归停不下来！！！！
    }
};
//暴力，但是已经超出时间了，因为同Fibonacci一样，越是后面越是指数级增长，所以我们需要动态规划减枝

前言

二分

第704题

第35题

第34题

第69题

第367题

哈希