算法练习——力扣随笔【LeetCode】【C++】

来杯Sherry

发布于 2023-07-24 19:26:36

2650

发布于 2023-07-24 19:26:36

文章被收录于专栏：第一专栏

LeetCode 练习随笔

做题环境 C++ 中等题很值，收获挺多的不会的题看题解，一道题卡1 h +，多来几道，时间上耗不起。

力扣上的题目和 OJ题目相比不同之处？

一开始上手力扣不习惯，OJ 的题目提交的是完整代码，力扣上的C++只提交目标函数代码，比如某个题目你只需要完成topKFrequent(nums,k)这个函数。

class Solution {
    vector<int> topKFrequent(vector<int>& nums, int k) {

    }
};

这也就意味着程序设计的输入不需要自己额外设计了，同时限制了你数据的输入和返回内容的格式。多亏了oj许多来自力扣的题并补全了完整代码（目标函数部分空缺），渐渐习惯了编写目标函数的答题习惯。

定义问题

在哪定义结构体？

有两个位置可写：

1）类里面，讲究的话写在private中，这里就不讲究了。

class Solution {
public:
    struct node
    {
      int data;  
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {

    }
};

2）顶部区域

 struct node
    {
      int data;  
    };

class Solution {
public:
    struct node
    {
      int data;  
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {

    }
};

在哪定义全局变量？

1）顶部区域

#include<algorithm>
int a =3;
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        
        vector<int>v;
        v.push_back(a);
return v;
    }
};

2）换个方式，传参方式改为引用

很多全局变量是可以被替代的，比如希望值被修改并返回到原来作用域，但返回值位置紧张。

暴力时，全局变量开大数组还是有点用处的。

在哪定义头文件？

一般是全面的，多虑了。

下面这种做题区域顶部写头文件试过，编译通过。

#include<algorithm>

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {

    }
};

排序问题

vector 存入结构体怎么自定义比较规则？

1）自定义规则为结构体形式（优先队列也可用）

class Solution
{

public:
    typedef struct node
    {
        int data;
        int sum;
    } ll;
//    static bool cmp(ll a, ll b)
//    {
//        return a.sum > b.sum;
//    }

    struct CompareBySumDesc
    {
        bool operator()( ll a,  ll b) 
        {
           return a.sum > b.sum;
        }
    };


    vector<int> topKFrequent(vector <int> &nums,int k)
    {
       
        vector<ll>v;
        //...
        
		//vector排序
        sort(v.begin(),v.end(),CompareBySumDesc());
//        sort(v.begin(),v.end(),cmp);
        //...
        return res;


    }


};

2）自定义规则为静态函数（简单）

class Solution
{

public:
    typedef struct node
    {
        int data;
        int sum;
    } ll;
    static bool cmp(ll a, ll b)
    {
        return a.sum > b.sum;
    }

//    struct CompareBySumDesc
//    {
//        bool operator()(const ll a, const ll b) const
//        {
//           return a.sum > b.sum;
//        }
//    };


    vector<int> topKFrequent(vector <int> &nums,int k)
    {
       
        vector<ll>v;
        //...
        
		//vector排序
//        sort(v.begin(),v.end(),CompareBySumDesc());
        sort(v.begin(),v.end(),cmp);
        //...
        return res;


    }


};

vector 存入结构体怎么逆置？

用 stack。

存入结构体的 priority_queue 怎么自定义比较规则？

给 ll 按照 sum 排序

class Solution
{
public:
    typedef struct node
    {
        int data;
        int sum;
    } ll;
  //试过了，static 函数行不通，只能 
    struct cmp
    {
        bool operator()( ll a,  ll b)
        {
            return a.sum > b.sum;
        }
    };
    
    void f()
    {
        priority_queue<ll, vector<ll>, cmp> pq;

      
};
int main()
{
    Solution().f();

    return 0;
}

//默认降序

//没有结构体，升序
priority_queue <int,vector<int>,greater<int> > q;

使用 priority_queue 实现堆排序？

优先队列本身是堆实现的。只需维护好优先队列的容量 k，超过pop掉。

统计问题

map 统计的神。遍历别忘了迭代器初始化。

其他

删除 vector 任意位置元素？

vector<int>v;
//删除 v[i]
swap( v[i],v[v.size()-1]);
v.pop_back();

其实只是 v.size()减少，内存不释放。

 vector<int >v;
    v.push_back(11);
    v.push_back(22);
    v.push_back(33);

    v.pop_back();
    v.pop_back();
    v.pop_back();
    
    cout<<v.size()<<endl;
	v.push_back(44);

    cout<<v[0]<<endl;
    cout<<v[1]<<endl;
    cout<<v[2]<<endl;