数据结构与算法做题笔记

Live the life you want to live

数据结构篇

 数据结构是算法的基础，在初学语言时我们对数据结构的了解多为数组，数组只是一种连续的存储方式，它占用一篇连续的内存空间。除了连续存储方式，还存在一种非连续性存储方式，链表和树是其中典型的代表。这种存储有其优点，在增加和删除元素时较为便捷，同时缺点也比较明显，在查找和删除时较为困难。

 对于数据结构中，数组，字符串，二叉树，链表，栈，队列等其操作方法总体可以分为两类，一类是线性访问，一种是非线性的访问。线性方式通常为：for循环，while循环。非线性访问通常为使用递归方法（递归，函数调用自身的方法就称作为递归）

//线性操作
for(int i=;i<;i++){}
while(condition){}

//非线性操作
dfs()
{
    ...
    dfs()
}

1、链表

2、二叉树

2.1 二叉树层序遍历的结果力扣102

给定一颗二叉树，利用二维数组返回其层序遍历的结果。

• 题目描述与思路

我刚拿到这个题目，没有思路，我很明白二叉树的层序遍历结果，但是你要是让我通过代码来实现，我们肯定能想到，每一层都需要使用一个vector进行从左到右存储，那就是想办法要把每一层存下来，同时呢，当前层操作完还能往下一层去操作，每一层操作完后放入到返回数组中

这里给出题目解析

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
//此题不解，我誓不为人
//最核心的要素是根据一层一层的顺序来搞，你以为你会了cout<<"Hello World!"就OK了?,想的太美！！！！，辣鸡！！！！

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        //如果为空则返回
        vector<vector<int>> ans;
        if(!root) return ans;
        queue<TreeNode*> queNode;
        queNode.push(root);
        while(!queNode.empty())
        {
            int size=queNode.size();
            vector<int>temp;
            for(int i=0;i<size;i++)
            {
                TreeNode *node=queNode.front();
                temp.push(node->val);
                queNode.pop();
                if(root->left!=nullptr) queNode.push_back(root->left->val);
                if(root->right!=nullptr) queNode.push_back(root->right->val);
            }
            ans.push_back(temp);
        }
};

算法篇

1、动态规划（递归暴力解自顶向下；迭代解法自底向上）

1.1 基础知识准备

动态规划的最核心关键在于对递推公式的发掘，初始边界条件的判断和分析。动态规划的入门题目有青蛙跳台问题。这种题目最为直接的解答方式就是寻找当前节点与前面节点之间的计算关系。

A. 动态规划特点：

1. 重叠子问题
2. 状态转移方程（最关键）
3. 最优子结构

B. 动态规划套路：

1. 明确状态
2. 明确选择
3. 明确dp函数/数组的定义
4. 明确 base case

C.动态规划解法代码框架

#初始化，basecase
dp[0][0][...]=base
#进行状态转移
for 状态1 in 状态1所有取值：
    for 状态2 in 状态2所有取值：
        for ...
            dp[状态1][状态2][...]=求最值(选择1，选择2...)

D.动态规划经常要求出的答案特点：

A.求方法数目

B.求最大最小值（这个概率真的很高）

C.是或者否

1.2例题分析

①斐波拿数列

 它并不是典型的动态规划，因为它不涉及到求最值得问题。也可以说它是一个可以利用递归和迭代举例题目。

class Solution
{
public:
    //画树结构，这个解法是自顶向下的递归解法,每一个Fib函数，只有判断和加法，复杂度为1,但是树上有2^N个节点。
    int Fib(int n)
    {
        if(n==1) return 1;
        if(n==0) return 0;
        return Fib[n-1]+Fib[n-2];
    }
    //定义一个迭代数组，从最底部自底向上解法，一个for循环，一个数组，时间和空间都为N,空间可只用三个变量进行优化到1.
    int DFib(int n)
    {
        vector<int> dp(n+1);
        dp[0]=0;
        dp[1]=1
        for(int i=2;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
    
};

②硬币的面额（非常经典）

给定硬币总类数组coins和目标总额，求解最小硬币数目。

• 这道题我拿到最先想到的是硬币数组要遍历每一个面额（状态），这是关键点，但是并没有立刻想到每一次遍历的下一层的最小值加一就为目标答案。
• 循环遍历最小值：可以通过一次for循环进行找到
• base case是什么，一种为正好分配到0，一种分配到小于0，正好分配到0说明刚好刚好，返回零就OK前面的次数每次加了1；小于0说明那个面额不可以选，前面的都是无效，返回答案-1.

建议：画一个树结构来帮助自己理解。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
      //使用迭代的解法自底向上进行求解
      //先定义一个dp数组
        vector<int> dp(amount+1,amount+1);
        dp[0]=0;
        for(int i=0;i<dp.size();i++)
        {
            for(auto c:coins)
            {
                if(i<c) continue;
                dp[i]=min(dp[i],dp[i-c]+1);
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];
    }
};

③最长公共子序列

这是一道典型的动态规划思维的题目，它是一个二维类型的题目，他的核心在于迭代求解，迭代的推进需要状态转移矩阵来搞。

最长公共子序列，两个数组连线，这种类型的题目都是一个意思，总体过程都是定义dp数组，初始化basecase，然后是明确状态转移的方法。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        const int lengtha=text1.size();
        const int lengthb=text2.size();
        vector<vector<int>>dp(lengtha+1,vector<int>(lengthb+1,0));
        text1=" "+text1;
        text2=" "+text2;
        for(int i=0;i<=lengtha;i++) dp[i][0]=1;
        for(int j=0;j<=lengthb;j++) dp[0][j]=1;
        for(int i=1;i<=lengtha;i++)
        {
            for(int j=1;j<=lengthb;j++)
            {
                //这是一个自底向上的方法
                //一定要记住状态转移的明确，
                if(text1[i]==text2[j]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[lengtha][lengthb]-1;
    }
};

④硬币的面额改题：直接灵感来自于爬楼梯问题

2.背包问题（一种动态规划）

引子：给你一个可装载容量为W的背包和N个物品，每个物品有重量和价值两个属性。第i个物品有重量wt[i]的属性和v[i]的价值，现在让你在这个背包里面装物品，最多能装物品的最大价值是多少？

• step1：明确状态和选择

  状态 背包的空余容量剩多少，可以选择的物品还有那些

  选择：把这个物品装进背包；不把这个物品装进背包

  #初始化basecase
  dp[0][0][0]=base
  #进行状态转移
  for 状态1 in 状态1所有取值：
      for 状态2 in 状态2所有取值：
          for ...
              dp[状态1][状态2][...]=求最值(选择1，选择2...)

• step2:明确dp数组的定义

  *dp[i] [j] *的含义为对于前i个物品，当背包容量为W时，可以装的最大价值为dp[i] [j]；

  base case: base[0] […]=0，没有物品，各种容量下价值均为0，dp[…] [0] =0背包没有剩余容量，那个物品也放不进去

• 代码框架

  vector<vector<int>> dp(N+1,vector<int>(W+1,0));
  dp[0][...]=0;
  dp[...][0]=0;
  for i in [1..N]:
  	for w in [1..M]:
  		dp[i][w]=max(
          	把物品i放进背包； dp[i][w]=dp[i-1][w-wt[i]]+wt[i]
              不把物品i放进背包；dp[i][w]=dp[i-1][w]
          )
   return dp[N][M];

• 关于放与不放物品

  一般会加入一个边界条件：if(w-wt[i]<0) dp[i] [w]=dp[i-1] [w];

  贴一个自己写的C++代码

  int bagproblems(vector<int> &wt,vector<int> val,int N,int W)
  {
      vector<vector<int>> dp(N+1,vector<int>(W+1,0));
      for(int i=1;i<=N;i++)
      {
          for(int w=1;w<=W;j++)
          {
              if(w-wt[i-1]<0) dp[i][w]=dp[i-1][w];
              else{
               dp[i][w]=max(dp[i-1][w],dp[i-1][w-wt[i-1]]+val[i-1])
              }
          }
      }
      return dp[N][M];
  }

3 回溯算法

1. 回溯算法就是暴力穷举算法
2. 穷举过程就是遍历一颗多叉树的过程
3. 回溯算法的代码框架和多叉树遍历的代码框架类似

//回溯算法框架
void backtrack(路径，选择列表){
    if(满足结束条件){
        result.add(路径)；
        return;
    }
    for(选择：选择列表)
    {
        做选择；
        backtrack(路径，选择列表)；
        撤销选择；
    }
}
//多叉树遍历框架
void traverse(TreeNode root)
{
    if(root==nullptr)
    {
        return ;
    }
    for(TreeNode child:root.children) 
        traverse(child);
}

题1：解码方法**

4、双指针+滑动窗口

双指针技巧主要包括两大类部分：一类是快慢指针，一类是左右指针。快慢指针主要用来解决链表中的问题，比如典型的判断链表中是否存在环，左右指针主要用来解决数组（或字符串）中的问题，比如二分查找。

PART01快慢指针

如果链表中不存在环形，那么通过不断地去next,那么链表中一定会指向空

![][https://gblobscdn.gitbook.com/assets%2F-MaSogHyTrHQAjcG_ejV%2Fsync%2Fb4c6f201066b0a410e8ab6d59360abc1bba219ce.jpeg?alt=media]

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast=head;
        ListNode *slow=head;
        while(fast!=nullptr&&fast->next!=nullptr)
        {
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow) return true;
        }
        return true;
        
    }
};