/leetcode-prectice

Primary LanguageC++

关键知识点

0、多种类型数据结构的创建

链表

02 链表按位相加 整体翻转 取map元素+链表尾插
19 快慢指针 删除第n个点
21 swap交换两链表 链表的拼接
24 三个指针进行node两两交换
61 整体翻转 使用map或者暴力破解
141 环形链表检测 快慢指针

位操作

89 格雷码

树

17 排列组合
46 排列组合
48 排列组合
78 排列组合
22 递归创建括号 回溯
39 vector递归组合 回溯
120 vector递归组合 回溯
437 相互调用 耦合度高
637 BFS求平均值 已经有一维 二维结果存储
94 144 145 894 递归实现深度遍历 以及使用栈实现深度遍历

排序

56 stl-sort 二维数组
75 双指针 vector-swap交换
347 451 为stl-sort排序(hashmap+2dvector)
215 快排 冒泡 stl-sort 数值大小排序
179 stl-sort 数值逐位排序 按照字符串大小排序
45 string-sort 1011 33 二分法求解

map-hash-set

45 用于保存同型异构题 first为排序后的结果 second为排序前
347 字符统计 first为字母 second为出现次数
451 字符统计 first为字母 second为出现次数
17 查map表 排列组合 递归
36 用来统计字符出现次数 map.clear()
01 hashmap基本用法 常用操作
03 hashmap配合deque实现统计个数
128 hashset基本用法 常用操作
205 复杂度为n map索引 string替换
242 复杂度为n map索引计数
409 复杂度为n map统计
697 两个hash组pair 分别统计位置与次数 进行判断

递归

17 46 48 排列组合递归 回溯
78 90 DFS 93
22 递归创建括号 回溯
39 40 216 377 vector递归组合 回溯
120 递归 动态
424 string递归 93 遍历
89 位操作+递归

递归创建树

贪心

53 717依次遍历 寻找最优值 不考虑耗时
135
466

动态规划

53 依次遍历 注重有效贡献
413 等差数列满足状态转移方程 遍历比较即可
198 与70 64相似 都是有将之前数值进行累计的** 通过判断抢不抢来取max
70 爬楼梯 经典题型 通过计算第n>2 层左右可能的爬楼方法 向上累加即可
64 二维最小路径 明确状态转移方法为从上或者左最小值移动而来 取min
516 序列类题目 通过二维数组存储 若无新回文字符串添加则取max当前最长回文

dp[i,j] = dp[i+1][j-1]+2 
or max(dp[i][j-1],dp[i+1][j])```<br>
300 序列类题目 外循环快于内循环 ```dp[i] = max(dp[t]+1,dp[i])

91 一维dp 字符解码组合 较复杂
542 二维dp 仅通过左上右下两次遍历即可完成计算距离最近点的距离
62 二维路径搜索
121 122 二维dp
121 122 123 188 offer63 股票问题 322 416 装满书包问题

组合问题： 377. 组合总和 Ⅳ(涉及排序) 494. 目标和 518. 零钱兑换 II

True、False问题： 139. 单词拆分 416. 分割等和子集(或实现的bool判断)

最大最小问题： 474. 一和零 322. 零钱兑换(最少要多少个硬币)

//组合问题公式
dp[i] += dp[i-num]
//True、False问题公式
dp[i] = dp[i] or dp[i-num]
//最大最小问题公式
dp[i] = min(dp[i], dp[i-num]+1)或者dp[i] = max(dp[i], dp[i-num]+1)


1.如果是0-1背包，即数组中的元素不可重复使用，nums放在外循环，target在内循环，且内循环倒序；
for num in nums:
for i in range(target, nums-1, -1):
2.如果是完全背包，即数组中的元素可重复使用，nums放在外循环，target在内循环。且内循环正序。
for num in nums:
for i in range(nums, target+1):
3.如果组合问题需考虑元素之间的顺序，需将target放在外循环，将nums放在内循环。
for i in range(1, target+1):
for num in nums:

cpp 相关知识点

1、const的使用
    // 引用只是为提高程序执行效率
    // 函数中首先选择引用传递 & 直接对传入参数进行修改
    void sortVector(vector<int>&nums)
    { quickSort(nums);}

    // 如果不想在原来基础上进行修改 加个const即可 
    vector<int> sortVector(const vector<int>&nums)
    {
        vector<int>fakenums = nums;
        quickSort(fakenums);
        return fakenums;
    }
    // the variable is constant and prevent to modifying it 
    // it's a way to replace the #define
    const int i = 5;

    // 声明常量成员函数 const在声明和定义中都要使用
    // 获取当前id 不做修改
    int  getId() const {return id;};

    // ※定义常量指针 地址不可修改 所指向的数值可以修改
    int value_1 = 0;
    int*const intValuePtr_1= &value_1;
    *intValuePtr_1 = 10;
    cout<<intValuePtr_1<<" "<<value_1<<" "<<&value_1<<endl;
    
    // ※定义常量数值指针 地址可修改 所指向的数值不可以修改
    int value_2 = 10;
    int value_22 = 11;
    const int* intValueptr_2  = &value_2;
    intValueptr_2 = &value_22;
2、添加enum 条件运算符进行状态切换
  • enum
    state.h
        // 这里可以加当前是否允许攻击
        enum {attack,noattack};
        int state;
        void setAttackMode(){state = (state==attack)?noattack:attack};
3、添加vactor容器
  • 创建容器
    Agents.h
        // 创建智能指针类型容器
        vector<std::shared_ptr<AgentAbstract>> all_agents;
        vector<shared_ptr<int>> sharePtr;
        
        // 创建类指针容器
        vector<AgentAbstract*> ally;
        
        // 创建int容器
        std::vector<int> intCounter;
        vector<int*> intPointer;
        vector<string> stringList;
4、添加智能指针(keyword:smart ptr)
  • 方法一： 类中声明，作用域在类全局 在构造函数中初始化
game.h:
	std::shared_ptr<Agents> agents; // 先声明
	
game.cpp
    agents.reset(new Agents(policyChoice)); // 智能指针声明后初始化
  • 方法二：直接初始化完毕
agents.cpp
        std::shared_ptr<DPPolicyAgent> DPPointer(new DPPolicyAgent);
  • 测试程序
#include <iostream>
#include <memory>

using namespace std;

/**************************************
 *  int ptr 
 *====================================*/
void intFunctionTest(shared_ptr<int>(pointer) )
{
   *pointer = 10;
}

/**************************************
 *  double ptr 
 *====================================*/
void doubleFunctionTest(shared_ptr<double>(pointer) )
{
    *pointer = 10.12;
}

/**************************************
 *  return smart ptr
 *====================================*/
shared_ptr<int> intFunctionReturn(shared_ptr<int>(pointer))
{
   return pointer;
}

int main()
{
    // way1
    shared_ptr<int> pointerInt (new int);
    // way2
    shared_ptr<double> pointerDouble;
    pointerDouble.reset(new double);

    intFunctionTest(pointerInt);
    doubleFunctionTest(pointerDouble);

    cout<<"address of heaps is dynamic: "<<pointerInt<<endl;
    cout<<"address of stack is static: "<<&pointerInt<<endl;
    cout<<"value is: "<<*pointerInt<<endl;

    cout<<"address of heaps is dynamic: "<<pointerDouble<<endl;
    cout<<"address of stack is static: "<<&pointerDouble<<endl;
    cout<<"value is: "<<*pointerDouble<<endl;

    // 两个指针都指向同一块内容
    shared_ptr<int> pointerInt_r (new int);
    pointerInt_r = intFunctionReturn(pointerInt);

    cout<<"address of heaps is dynamic: "<<pointerInt_r<<endl;
    cout<<"address of stack is static: "<<&pointerInt_r<<endl;
    cout<<"value is: "<<*pointerInt_r<<endl;

    return 0;
}
5、stl-sort的使用(不能在原数组调整)
  • 在 include 中
    TODO:本质是对从选择范围内的所有数值进行两两比较后排序
    基本用法： 可以结合以下仿函数进行使用
  • less(小于)
  • greater(大于)
  • equal_to(等于)
  • not_equal_to(不相等)
  • less_equal(小于等于)
  • greater_equal(大于等于)
    // 从小到大默认排序 可以用于数组 vector 给好起止就好
    sort(nums.begin(),nums.end());
    // 若要从大到小排序 需要配合下面的函数进行修改 同时也可以用于二维数组
    sort(nums.begin(),nums.end(),sortCmp);
    // lambda
    sort(nums.begin(),nums.end(),[](int a,int b){return a>b;});
    // 仿函数
    sort(nums.begin(),nums.end(),less<int>();


当前适用情况：

    // 二维数组按照其中某一维度排序 56
    bool sortCmp(const vector<int>&a,const vector<int>&b)
    {
        return a[0] < b[0]; // 升序 < 降序
    }
    // 数值大小排序 215
    bool sortCmp(int a,int b)
    {
        return a < b; // 升序 < 降序
    }
    // 按照字符串大小排序
    // 数值逐位排序 179
    bool sortCmp(int a,int b)
    {
        return to_string(a) < to_string(b); 
    }
6、reverse-vector内容翻转的使用
  • include <vector>
  • include <algorithm>
    // 对于vector类型的数据reverse很好用
    // 对于顺序有比较高要求的情况来说很好用
    reverse(smallNumber.begin(),smallNumber.end());
    string s;
    reverse(s.begin(),s.end());
7、accumulate-vector中元素求和的使用
  • include <numeric>
  • include <vector>
    vector<int>a;
    int aSum = accumulate(a.begin(),a.end(),0);
8、erase-vector-map-set清空的使用

// 这里有坑 erase删除后原迭代器失效的问题

  • include <vector>
  • include <unordered_map>
  • include <unordered_set>
  • include <set>
    hashmap.erase(hashmap.begin(),hashmap.end());
    hashmap.erase(hashmap.find('A')); //实现精准擦除
    vector.erase(hashmap.begin(),hashmap.end());
    hashset.erase(hashmap.begin(),hashmap.end());
    ite = vector.erase(ite);// 防止删除当前位置内容迭代器失效
    
    // set初始化
    unordered_set<int> hashSet(nums.begin(),nums.end());
    set<int> Set(nums.begin(),nums.end());
9、map-find查找 set-count计数
    if(hash.find(number) != hash.end()); // number存在
    if(set.count(number)); //number存在
10、字符串截取
  • leetcode 93
    string sub = s.substr(position,length);
11、数据查找 find 复杂度较高
    hash.find() != hash.end(); //找到后可直接进行操作 精准
    string.find() --> position/-1
	// 通用格式：
	find(ite.begin(),ite.end(),n);
12、math 求幂运算
    pow(10,2) == 100
13、string 截取处理(linux 简化路径)

能够将下一个'/'之前对字符串截取出来 好用！

#include <sstream>
string path = "/../s/.//../sdf//";
stringstream is(path);
string temp = "";
while(getline(is,temp,'/'))();

复习时间

  • 1.24 114 108 树有关内容有点遗忘
  • 1.25 整理链表 hashmap pair