春招杂货铺(3) 牛客面试刷题篇-某团2021

先暂存一下,有时间再排版。

#include <bits/stdc++.h>
using namespace std;

vector<int> score;

int main(){
    int n, x, y;
    cin >> n >> x >> y;
    for (int i = 0; i < n; ++i) {
        int number;
        cin>>number;
        score.push_back(number);
    }
    vector<int>  res;
    for(int i=x;i<=y;i++){
        if(n-i>=x&&n-i<=y){
            res.push_back(i);
        }
    }
    sort(score.begin(),score.end());
    cout<<score[res[0]-1];
    if(res.size()==0){
        return -1;
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
vector<int> nums;

int main(){
    int count=0;
    int n;
    cin>>n;
    int num;
    while(cin>>num){
        nums.push_back(num);
    }
    sort(nums.begin(),nums.end());
    for(int i=0;i<nums.size();i++){
        count+=abs(nums[i]-i-1);
    }
    cout<<count;
    return 0;
}

黑猩猩也可以懂的Pytorch学习过程(By Jovian.ai)(1)

1.数据的读入

由于我本人也是第一次接触Pytorch,所以就用之前帮妹妹写作业熟悉过的Jupyter Notebook进行这次的学习(Jovian官方教程也使用的Jupyter Notebook,这样就更加方便了)

# Imports
import torch
import torchvision
from torchvision.datasets import MNIST

importPytorch,没什么好说的。

Pytorch官方文档https://pytorch.org/docs/stable/index.html

MNIST是著名的数据库,存有手写的数字。将其下载下来,并命名为dataset。http://yann.lecun.com/exdb/mnist/

dataset = MNIST(root='data/', download=True)

这样就把所有的来自MNIST数据库的数据存入了根目录下的data文件夹下。

瞅一眼数据量

60000个,够用了。

而这60000个数据,应该有10000个用来验证结果。MNIST官方已经帮我们打好标签了,使用test_dataset = MNIST(root=’data/’, train=False)就可以将train值为False的数据存入test_dataset中。

如果我们取出一个,看看这个数据是什么样子。

看不懂具体是什么意思没关系,我也不懂:) 但有一些参数是能够看出来的,这是一个PIL.Image.Image类的对象,其大小为28×28个像素。

下一步使用pyplot将其画出来,看看是什么样

带有%前缀的指令叫做魔法指令,会对Jupyter Notebook本身做出一些修改,这里是为了让画的图直接在行内显示。

得到第一个数据如图,这里的image,label=dataset[0]让我困惑了一小下,不知道这是个什么种声明的方式,经过回看上文可以发现,dataset本身就是一个有两个字段的数据,前一部分是图片数据,后一部分为label,即这个数字是几。这里也放一下pyplot的官方文档的链接。

https://matplotlib.org/stable/api/pyplot_summary.html

官方文档中是这样写的。

这里我们要使用的图像是灰阶图像,因此参数选择’gray’

至此,我们已经完成图像的导入

图像的数据化

这里的图像格式为一个我们不熟悉的类,Pytorch应当使用一个tensor(译为张量对其进行处理),因此需要转换,这里Pytorch依然为我们准备好了转换的工具——torchvision.transforms

将 torchvision.transforms 导入,命名为transforms

现在再来看dataset的情况。

dataset已经被成功转换为tensor格式。

打印img_tensor的通道0(因为是灰阶图像,只有0),从图片的第十行第十列输出到第15行第15列。
输出值越大,这里越接近白色。
下面的max和min也告诉了我们最大值与最小值是多少

调用熟悉的plt.imshow指令,就可以看到这一区域的图像是什么样的了。

数据预处理与读入

通常来讲,机器学习的数据集可以分为三部分(由于没学过中文课程,可能翻译有误):

1.训练集

2.验证集

3.测试集

对于MNIST数据库而言,有60000个训练图片与10000个测试图片,但没有预设的验证集,我们需要手动将60000个训练图片打散,从而得到训练集与验证集。(至于为什么训练集和测试集要分开还不得而知,看看能否通过后续的学习理解)

这里打散的方式Pytorch也给出了(所以说是黑猩猩都可以懂的学习过程,Pytorch实在太过完善,所有所需的功能基本都已给出,照着官方文档去翻看调用即可)

导入torch.utils.data将其命名为random_split
将分散的数据存入train_ds(命名意义为:用于训练的dataset)和val_ds中
查看其长度,分别为50000与10000

DataLoader是用来载入数据的,即一次读取多少数据来训练模型

这里将batch_size设置为128
在train_loader中 将shuffle设置为True,保证每一个epoch(也许是迭代?)取出的数据都是不同的
这里有一个疑问,为什么验证数据不用shullfe,可能也得通过之后的学习解答了

建立模型

这里就可以到我们熟悉的(x)神经网络环节了。

这里使用线性回归模型,其具体含义之后有机会在讲,能看到这里的同学默认都会了吧。放上Jovian官方的说明。

其模块封装于torch.nn内,导入即可

这里的Linear后的两个参数代表了这个模型所要处理的输入输出的个数
在这里,需要对有728个维度的数据进行处理(28×28=728个像素点,即728维的数据)
而输出为10维,因为要将这些数据与各个数字的可能性输出

首先来看一下model的形状如何

可以看到这是一个10*784的矩阵
而requires_grad=True是tensor的一个属性,意为我们需要对它求导。这样的标记是有意义的,但我也仅仅是知道有意义而已,具体是应用于什么样的情况还不得而知。
bias矩阵是一个1*10的矩阵

这里直接对train_loader中的数据进行处理,看看情况如何

得到了这样的结果

发生RuntimeError,因为矩阵不可相乘

这是因为我们当前的数据还是28*28维的矩阵,再与128相乘后得到了一个奇形怪状的东西:(,函数根本不会处理它

其实解决的方法很简单,将28*28的矩阵变成1*784的向量即可。

使用reshape将images变为128*784的矩阵

这里教程中新写了一个类MnistModel(继承自nn.Module)来实现我们所需模型的功能,代码如下。

这里在构造函数(也可能不叫这个名字?)中,增加了self的属性linear,linear初始化为nn.Linear提供的矩阵,input_size和num_classes均已给出
forward函数简便的提供了输入数据的tensor化功能,这里(-1,784)中的第一个参数说明函数可以自己根据输入数量决定tensor的第一维维数。
现在model进行了再次的初始化,初始化为MnistModel类的一个对象,注意此时model不再具有.weight和.bias这两个属性(attributes)

现在查看一下model对象的linear属性

之前,属于model类的.weight和.bias转移到(或者说重新初始化为)model.linear门下。

这里的parameters()函数应该来自于Pytorch本身,因为我们的MnistModel类继承自nn.Module,自然也就有他的各种功能

这回再来将数据读入,进行处理。得到如下结果。

使用softmax函数对输出进行处理

可以看到,在上文,我们使用model对images进行处理后,每张图片输出了一个十维向量,但现在的输出是有正有负很不直观,因此要用softmax函数对其处理,使这十个输出值变为正,并且和为1。思路很简单,将得到的数值变为指数函数的指数,再除以总的数值即可,看图片可能更直观一些。

先通过指数函数的映射使各个值变为正
再使用softmax函数将输出值归一化

作为傻瓜式教程,softmax函数当然也被Pytorch提供了,直接导入torch.nn.functional模块即可

将torch.nn.functional模块导入,命名为F
查看经过处理过的output数据,发现其均为正,和为1,达到目的

得到预测结果

现在就可以得到我们的神经网络的预测结果了,当然这个预测肯定是不准确的,这里通过选择可能性最高的(即softmax函数输出的最高值认为它就代表数字几)

这可以使用torch.max函数实现

预测得到的结果

那么与数据库提供的标签对比如何呢?查看一下数据库提供的标签数据。

可以看到大部分数据都预测错误了,但没关系,毕竟这只是初始化的网络,还没有开始学习

评价指标与损失函数

Accuracy函数

神经网络的基本概念我们应该都知道,如果预测的结果错误,我们应当给他一个改动,然后继续训练,直到预测的准确度达到我们的要求为止,那么在这个过程中,就需要一个参数来评估,这就是接下来要用的accuracy指标。

accuracy指标的定义也十分简单,用预测对的结果数量比上总的结果数量即可,新定义accuracy函数进行计算。

这里的下划线是表示函数并不关心前者的取值,回看之前使用max函数的例子,我们会发现假如下划线是一个变量的话,它会被赋值为最大可能性的值,这里我们只需要预测值和标签值相比,因此使用了这样一种语句

调用后得到如下结果。

准确率0.0625,很低

Loss function 损失函数

accuracy函数是一种很好的评价的指标,但并不能作为损失函数。原因有二:

1.accuracy函数不可微,在accuracy函数中有‘torch.max’和’==’两个 运算,这两个都不是线性运算,因此无法使用accruracy函数计算weights和biases矩阵的改变量。

2.accuracy并没有“真正地”将预测的可能性(即我们得到的probability)带入计算中,只是单纯地比较了预测值与标签值的大小,因此也就无法对我们的模型改进做出指导。

因此,一般使用corss-entropy(交叉熵),公式如下

观察这个函数的形式,它会使预测概率更接近1的越来越接近1,预测概率接近0的越来越接近0
多分类情况

这里使用log函数的图片会更直观

假如我们得到的预测的概率为[0.1,x,0.2,……]而标签为1,也就是预测正确的可能性为x,那么忽略其他元素,只看x的话,假如这个值x很大,接近于1,那么logx接近于0,也就是损失很小,如果x很小,即预测正确的可能性很小,那么logx是一个很大的负数,我们再给它加一个负号,再取各个图片(输入)的平均值,就可以得到一次输入的平均损失值,越大越不好

再次扣题,PyTorch已经为我们准备好了交叉熵损失函数的计算,并且自带softmax函数,作为只有大猩猩智商的我,直接进行一个调的用。

得到损失函数的值为2.3418

训练模型

现在,我们得到了模型(weight与bias矩阵),得到了评估模型的方法(accuracy函数与以corss-entropy为基础的损失函数),以及各种读取、输入数据的小工具,我们还拥有MNIST数据库中得到的验证集,那么就可以正式开始训练模型了。

训练模型的伪代码应如下所示:

#给入迭代次数num_epochs
for epoch in range(num_epochs):
    # Training phase 训练模型
    # 对于train_loader读入的一批(batch)数据 执行如下操作
    for batch in train_loader:
        # Generate predictions 生成预测值
        # Calculate loss 评估损失
        # Compute gradients 计算梯度
        # Update weights 更新权重
        # Reset gradients 重置梯度
    
    # Validation phase 验证环节
    # 对于val_loader读入的一批数据 执行如下操作
    for batch in val_loader:
        # Generate predictions 生成预测值
        # Calculate loss 计算损失
        # Calculate metrics ( accuracy etc.) 计算accuracy函数 评估准确度

    # Calculate average validation loss &amp; metrics 计算平均损失与准确度
    
    # Log epoch, loss &amp; metrics for inspection 记录这次迭代,损失函数,准且率指标并进行检查

其真正代码如下:

def fit(epochs, lr, model, train_loader, val_loader, opt_func=torch.optim.SGD):
    optimizer = opt_func(model.parameters(), lr)
    history = [] # for recording epoch-wise results
    
    for epoch in range(epochs):
        
        # Training Phase 
        for batch in train_loader:
            loss = model.training_step(batch)
            loss.backward()
            optimizer.step()
            optimizer.zero_grad()
        
        # Validation phase
        result = evaluate(model, val_loader)
        model.epoch_end(epoch, result)
        history.append(result)

    return history

这个名为fit的函数,将各参数和数据读入后,返回一个history的值,用来记录损失函数和指标的变化。

这里还有一些我们没见过的东西,比如lr代表学习率(learning rate),opt_func=torch.optim.SGD是一种随机下降方法,可以避免学习过程中的一些问题。现阶段还不需要学那么深入(毕竟我也还不会),只要明白这段代码实现了和上面伪代码一样的功能即可。

但上面的其他东西仍然需要我们自己去定义,比如需要再次重写一遍MinistModel类,从而加入raining_step、validation_step、validation_epoch_end、
epoch_end 等类函数。代码如下

class MnistModel(nn.Module):
    def __init__(self):
        super().__init__()
        self.linear = nn.Linear(input_size, num_classes)
        
    def forward(self, xb):
        xb = xb.reshape(-1, 784)
        out = self.linear(xb)
        return out
    
    def training_step(self, batch):
        images, labels = batch 
        out = self(images)                  # Generate predictions
        loss = F.cross_entropy(out, labels) # Calculate loss
        return loss
    
    def validation_step(self, batch):
        images, labels = batch 
        out = self(images)                    # Generate predictions
        loss = F.cross_entropy(out, labels)   # Calculate loss
        acc = accuracy(out, labels)           # Calculate accuracy
        return {'val_loss': loss, 'val_acc': acc}
        
    def validation_epoch_end(self, outputs):
        batch_losses = [x['val_loss'] for x in outputs]
        epoch_loss = torch.stack(batch_losses).mean()   # Combine losses
        batch_accs = [x['val_acc'] for x in outputs]
        epoch_acc = torch.stack(batch_accs).mean()      # Combine accuracies
        return {'val_loss': epoch_loss.item(), 'val_acc': epoch_acc.item()}
    
    def epoch_end(self, epoch, result):
        print("Epoch [{}], val_loss: {:.4f}, val_acc: {:.4f}".format(epoch, result['val_loss'], result['val_acc']))
    
model = MnistModel()

定义evaluate函数用来评估

在开始训练之前,用评估函数来看一下目前默认模型的准确率与损失函数的情况

正式开始训练

至此,我们已经准备妥当,直接开始训练模型即可,对model进行训练,共训练4次,每一次训练进行5次迭代,学习率设为0.001,结果如下

将默认模型和这四次训练的准确度进行合并,并在图中画出来,得到如下图像,显示了在每一次迭代后,准确率的变化情况

可以看到,仅仅经过20次迭代,模型的准确度就已经达到了85%以上

但可以看到的是,从图上的趋势而言,这个模型即使经过非常久的训练,也很难超过90%准确度的阈值。

一种可能的解释是:学习率过高, 该模型的参数可能在以最低损失为目标的最优参数集上“跳跃” 。降低学习率也许会有一些帮助。

但更有可能的解释是:模型本身就不够强大。毕竟从本质上而言,我们的人工神经网络也只是一个有几百个维度的矩阵而已!对于这次的模型,我们一开始给出这样的假设:输出与输入之间是线性关系。但也许,输入和输出之间根本就不存在这样理想的线性关系(对于本模型来说,就是像素点的密度和灰度,也许和这个数字是几之间毫无关系,但我们知道并不是这样,所以我们的模型还是可以达到较高的准确度,但换一个场景,比如我们训练一个模型让它去寻找今天天气和我午饭要吃几碗米饭之间的关系,它就无法做出准确的判断了,因为二者之间并不存在明显的线性相关关系)。

但至少我们得到了一个结论:我们需要更加复杂的模型来对输入输出进行处理来捕捉二者之间的非线性相关关系,这样才能够对更加复杂的物体识别、图像识别的任务进行实现,但那就是下一次文章的内容了,希望我不要鸽太久!

近期公众号文章整理

由于最近开学加忙春招,实在是没空两边都顾了,这里直接贴公众号文章地址了……

[LeetCode每日一题] 面试题 10.02. 变位词组

https://mp.weixin.qq.com/s?__biz=MzAwMTgxMzU0Nw==&mid=2247483827&idx=1&sn=a9e3d3b068e4b1343be87f636c365395&chksm=9ad2bcf7ada535e11ccb8e91fff35f9499ea5f91f41d7f2e16139264444ea9aa99d7a7b88f6e&token=181491738&lang=zh_CN#rd

动态规划刷题篇(2) 416. 分割等和子集

https://mp.weixin.qq.com/s?__biz=MzAwMTgxMzU0Nw==&mid=2247483838&idx=1&sn=c14d0f5e046a459fab334619926e72aa&chksm=9ad2bcfaada535ec8a458a85de66f73718984297a395aa32fcdfbe1efb19f227153a4df743b1&token=181491738&lang=zh_CN#rd

动态规划刷题篇(3) 不同的二叉搜索树、最后一块石头的重量

https://mp.weixin.qq.com/s?__biz=MzAwMTgxMzU0Nw==&mid=2247483846&idx=1&sn=cec21b9f894840ce6ddbf7da65f3b78f&chksm=9ad2bc82ada535942ec26a54fe36ddc104ea2987720ab945be5c4dc74965e9373d5680a55818&token=181491738&lang=zh_CN#rd

[LeetCode]每日1题 303.区域和检索-数组不可变

https://mp.weixin.qq.com/s?__biz=MzAwMTgxMzU0Nw==&mid=2247483853&idx=1&sn=479bee1a13b7b20af17b6284f1ace086&chksm=9ad2bc89ada5359f235bfea792322e0d5d374caf6afa24a600039c76930d70809a4d1e03e270&token=181491738&lang=zh_CN#rd

动态规划刷题篇(4) 目标和

https://mp.weixin.qq.com/s?__biz=MzAwMTgxMzU0Nw==&mid=2247483857&idx=1&sn=3c33976ec0e30c62eb42c278d0aabb04&chksm=9ad2bc95ada535837270ca5067437b2d3ddda293eb148cbcf61ef2ca3a8b2594963e80cf97bc&token=181491738&lang=zh_CN#rd

动态规划刷题篇(5) 零和一 与 用完全背包凑零钱

https://mp.weixin.qq.com/s?__biz=MzAwMTgxMzU0Nw==&mid=2247483862&idx=1&sn=3a2e3280451d62a294336f2c3bf03c4a&chksm=9ad2bc92ada5358425372cead4726d554ded6c010a422f153d76a623f8ae5db7812a26fb2dd4&token=181491738&lang=zh_CN#rd

有空再在这边发一些吧~

CSAPP读书笔记可能会在这里发,一方面涉及到版权问题,另一方面写的不好,拿去公众号误导同学就不好了……

动态规划刷题篇(1) 斐波那契、爬楼梯、路径与最长递增子序列

芜湖,春招(暑期实习)临近,今天接到了某大厂的电话,让我开始投简历,因此做题的速度要加快了!时不我待,今天做动态规划的题!今天是动态规划六连发!

509. 斐波那契数

斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1
F(n) = F(n – 1) + F(n – 2),其中 n > 1
给你 n ,请计算 F(n) 。

https://leetcode-cn.com/problems/fibonacci-number

这题作为动态规划的入门题实在是再合适不过了,斐波那契数列其实每个同学在小学就接触过,可能厉害的同学口算都会(这就是小学二年级的知识吗)。

这题就引出了动态规划中的一个重要概念:DP数组。DP数组是用来存储当前问题的子问题的这样一个数组。

动态规划的核心就在于:当前问题可以分解为几个子问题。比如,如果我们想求这道题中的F(n),就需要知道F(n-1)与F(n-2)这两个子问题的答案,而每一个子问题,又可以按照这样的规律(通常被称为转移方程)去分解,直到最简单的子问题,即F(2)和F(1),很容易知道他们的答案是1和1,我们可以手动将这些结果输入到DP数组中。再向后推导,最终得到F(n)的结果。

动态规划是一种倒着想,正着推的题目(当然,也可以使用递归来倒着推,但这样往往会浪费额外的空间,并增加时间复杂度),本质依然是一种“不充分的遍历(不知道这样描述对不对哈哈)”,其时间复杂度往往不是题目可行的算法中最低的,但其优点在于比较好想(在比较熟练的情况下),在面试中占有很重要的地位,是算法的特色,不可不品尝(x)。

说了这么多,直接上代码,这题的代码还是非常简单的(注意本题使用的并不是DP算法,因为递归算法太简单了,直接上递归,事实上对于DP算法的讲解,@labuladong有着非常详细的入门讲解,这里就不赘述了):

https://github.com/labuladong/fucking-algorithm

@labuladong的算法小抄
class Solution {
public:
    int fib(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        return fib(n-1)+fib(n-2);
    }
};

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。

示例 1:
输入: 2 输出: 2 解释: 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶

示例 2:输入: 3输出: 3解释: 有三种方法可以爬到楼顶。1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶 2 阶 + 1 阶

https://leetcode-cn.com/problems/climbing-stairs/

在做每一道DP算法的题时,我们都需要思考一下这道题的转移方程是怎样的,然后再用代码来实现这个转移方程,只要足够细心,一般来讲这样的代码都可以顺利通过。

对于这道题而言,示例已经给出了一定的思路(或者说基准情况),即输入为2时,有两种方法爬到楼顶。那么不难想,输入为3的情况呢?它应当是输入1和输入2的情况之和。

因为从第一个台阶和第二个台阶,都可以一步到达第三阶。

所以,这道题的转移方程依然为: F(n) = F(n – 1) + F(n – 2),其中 n > 1 !

那么这道题与上一题是完全相同的题目!上代码!

class Solution {
public:
    int backtracking(int n,vector<int> &dp){
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        if(dp[n]!=0){
            return dp[n];
        }
        if(dp[n-1]!=0&&dp[n-2]!=0){
            dp[n]=dp[n-1]+dp[n-2];
        }
        return backtracking(n-1,dp)+backtracking(n-2,dp);
    }
    int climbStairs(int n) {
        if(n<=2) return n;
        vector<int> dp(n+1);
        return backtracking(n,dp);
    }
};

这个代码其实写的很烂(因为是在我刚刚学习完回溯又学习DP算法时写的,现在看来思路真的非常混乱……明明是DP却用了backtracking这样的函数名,这里放上来也算是对自己的一种……纪念?),为了让大家看得明白,这里也放一下Carl大神的代码,他这里使用的是带“备忘录”的DP算法:

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n;
        int dp[3];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            int sum = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2];
    }
};
//本代码来自公众号 代码随想录 作者为Carl

746. 使用最小花费爬楼梯

数组的每个下标作为一个阶梯,第 i 个阶梯对应着一个非负数的体力花费值 cost[i](下标从 0 开始)。
每当你爬上一个阶梯你都要花费对应的体力值,一旦支付了相应的体力值,你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时,你可以选择从下标为 0 或 1 的元素作为初始阶梯。
输入:cost = [10, 15, 20]
输出:15
解释:最低花费是从 cost[1] 开始,然后走两步即可到阶梯顶,一共花费 15 。

https://leetcode-cn.com/problems/min-cost-climbing-stairs

由于登上每个台阶的当前花费是固定的(这不是废话吗……),那么登上这个台阶的总花费的最小值,应当是这个台阶的前两个台阶的总花费最小值+这个台阶的当前花费。

即,DP[n]=min(DP[n-1],DP[n-2])+cost[n]。

理解了这个,这道题就迎刃而解了。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        vector<int> minCost(n);
        minCost[0]=cost[0];
        minCost[1]=cost[1];
        for(int i=2;i<n;i++){
            minCost[i]=min(minCost[i-1],minCost[i-2])+cost[i];
        }
        return min(minCost[n-1],minCost[n-2]);
    }
};

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?

输入:m = 3, n = 7 输出:28

https://leetcode-cn.com/problems/unique-paths

这一题被力扣归为medium题,但实际上其DP算法的转移方程及实现都依然非常简单,只不过从一维换成了二维。

每个格子的路径,等于其右边的格子的路径与下面的格子的路径之和,而最靠近右下角的那两行/列格子,其路径都是1(只有一种方法到达finish,只能横着走或者竖着走)。

即:DP[i][j]=DP[i-1][j]+DP[i][j-1](i<m,j<n)。且DP[m][i]=DP[i][n]=1。

代码如下:

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i=n;i>0;i--){
            dp[m][i]=1;
        }
        for(int i=m;i>0;i--){
            dp[i][n]=1;
        }
        for(int i=m-1;i>0;i--){
            for(int j=n-1;j>-0;j--){
                dp[i][j]=dp[i+1][j]+dp[i][j+1];
            }
        }
        return dp[1][1];
    }
};

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。

https://leetcode-cn.com/problems/unique-paths-ii

上一道题会了的话,这一题就不难解出,只需要加一条规则:如果当前位置的格子有石头,这个格子的路径值变为0(或者什么都不做也可以)。就这么简单,上代码:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<long int>> dp(m+1,vector<long int>(n+1,0));
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                if(obstacleGrid[i][j]==1){
                    dp[i][j]=0;
                }
                else if(i==m-1&&j==n-1){
                    dp[i][j]=1;
                }
                else{
                    dp[i][j]=dp[i+1][j]+dp[i][j+1];
                }
            }
        }
        return dp[0][0];
    }
};

这里使用long int避免输出溢出的问题,力扣官方给的答案有一个超出了int类型值,这样就规避了这个问题。

300. 最长递增子序列

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

https://leetcode-cn.com/problems/longest-increasing-subsequence

这一题实际上转移方程就比较难了!用语言描述一下:

如果想求DP[3](代表着[0,3,1,6]这个子数组的最长递增子序列的结果),就需要知道DP[0]、DP[1]、DP[2]这三个结果,其中DP[0]我们可以轻易地得到1这个结果,那么,对于DP[3]而言,我们需要先知道nums[3]与nums[0]、nums[1]、nums[2]的大小,如果,nums[3]大于其中某一个,那么,DP[3]就等于那个数所在的DP数组值+1。

即,一个最简单的例子,0123,因为3大于2,所以到3这里,最长递增子序列的长度要加1!

总之这么描述可能依然会有些同学不明白,可以多想一想,或者干脆去看更详细的教程(x),依然推荐labuladong的算法小抄,毕竟我也是照着人家学得嘛~

上代码,结束今天的学习!

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n,1);
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=max(dp[i],dp[j]+1);
                }
                else if(nums[i]==nums[j]){
                    dp[i]=dp[j];
                }
            }
        }
        int maxLength=0;
        for(auto i =0; i<n; i++){
            maxLength=max(maxLength,dp[i]);
        }
        return maxLength;
    }
};

看看近期能不能进行一个简历的写,然后针对性地去分析下各公司职位的需求,看看能否冲刺一波,挑战一下这些岗位,也许对于我和很多同学来讲,这些才是真正需要的“知识”,毕竟我们的目的主要还是为了就业,不能盲目地刷题,那么明天见!

贪心算法刷题篇(1) 分发饼干与摆动序列

455. 分发饼干

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

https://leetcode-cn.com/problems/assign-cookies

作为贪心算法的第一题,这题着实不难。

贪心算法其实说是一种算法,其实非常接近人类的思想,许多时候还没想到用贪心算法的时候,实际上已经想出来贪心算法了。

贪心算法的核心就在于可以通过局部最优解得到全局最优解,那么什么样的情况下才能够通过局部最优解得到全局最优解呢?一般来讲,在搜索局部最优解时可以利用全局信息,那么最终的解就是全局最优解。(比如二叉树,你在一个节点只能看到其左右节点的信息,那么使用贪心算法,每次遍历更大值节点就可能无法得到全局最优解,但二叉搜索树却可以得到,这是因为二叉搜索树本身的结构已知,可以认为是一种隐含的信息,因此贪心算法最终可以得到全局最优解)当然,这里的说法我自己也没有验证过对错,只好在之后的刷题过程中验证了。

那么上这题的代码,非常简单。

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int i=0,j=0;
        for(;i<g.size()||j<s.size();i++){
            while(i<g.size()&&j<s.size()&&g[i]>s[j]){
                j++;
            }
            if(j>=s.size()||i>=g.size()) break;
            if(g[i]<=s[j]) j++;
        }
        return i;
    }
};

376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。
例如, [1,7,4,9,2,5] 是一个摆动序列,因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。
给定一个整数序列,返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。

https://leetcode-cn.com/problems/wiggle-subsequence

这题同样不难想到用贪心算法,在每次搜索到可能成为局部最大值的点时使count+1,要注意这里的代码是可能成为局部最大值的点而不是真正的局部最大值。

因此这题也说明了贪心算法(包括回溯算法甚至是其他算法)一个重要的问题,即这种“边边角角”的问题不好处理,但没有办法,就是得硬着头皮去写,除了训练没有什么好的办法。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size()<=1) return nums.size();
        int count=1;
        int preDiff=0;
        int curDiff=0;
        int index=1;
        //ture为上升 false为下降,看完答案后发现用diff差值计算更加方便,弃用此方法
        //bool mark=nums[1]-nums[0];
        while(index<nums.size()){
            curDiff=nums[index]-nums[index-1];
//          if(curDiff*preDiff<0){
//              count++;
//          }
            if ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {
                count++;
//preDiff=curDiff要放在这个条件内,如果放在if外会损失preDiff的正负信息(如00112实际上是2,但如果放在外面会得到3)
                preDiff=curDiff;
            }
            index++;
        }
        return count;
    }
};

本题结束,今天就写这两道吧。

回溯算法刷题篇(3) 分割回文串

131. 分割回文串

给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: “aab”
输出:
[
[“aa”,”b”],
[“a”,”a”,”b”]
]

https://leetcode-cn.com/problems/palindrome-partitioning

还是,先从人类的思维思考一下(x)。现在每做一道题,都会先从人类的角度思考这道题该如何做,然后再“翻译”成编程语言,这样也许不是最好的方式,但每个初学者应该都会经历这一步吧……

这题一个比较好想的办法是从第一个元素开始遍历,找到其最长的回文串,然后递归,不断分割,将每一次分割的结果都存入ans之中。

先写一下试试发现这种算法有点过难了,换个思路。

操……写了半天,终于尼玛写出来了。终于明白啥叫尼玛回溯了,回溯就是POP!

class Solution {
public:
    bool isValid(string str,int start,int end){
        for(int i=start,j=end;i<j;i++,j--){
            if(str[i]!=str[j]) return false;
        }
        return true;
    }

    vector<string> path;
    vector<vector<string>> ans;

    void backtracking(string &s,int start){
        if(start>=s.size()){
            ans.push_back(path);
            return;
        }
        for(int end=start;end<s.size();end++){
            if(isValid(s,start,end)){
        //注意substr用法
                string str=s.substr(start, end-start+1);
                path.push_back(str);
                backtracking(s, end+1);
                path.pop_back();
            }
            else {  
                continue;
            }

        }

    }


    vector<vector<string>> partition(string s) {
        backtracking(s, 0);
        return ans;
    }
};

回溯算法刷题篇(2)

今天是回溯算法刷题的第二天,回溯算法这里定一个小目标:解决N皇后问题。

今天的推荐歌曲是来自泽野弘之与Gemie的ΛSHES。

39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。

https://leetcode-cn.com/problems/combination-sum

直接上代码,此题与昨天做过的组合总和III是类似的。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> ans;
    void backtracking(int &sum,vector<int>& candidates,int target,int &index){
        if(sum==target){
            ans.push_back(path);
            return;
        }
        if(sum>target) return;
        for(int i=index;i<candidates.size();i++){
            path.push_back(candidates[i]);
            sum+=candidates[i];
            backtracking(sum,candidates,target,i);
            path.pop_back();
            sum-=candidates[i];
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int sum=0;
        int index=0;
        backtracking(sum, candidates, target, index);
        return ans;
    }
};

这里有一个问题,即在回溯时需要传入参数index,而在再次递归时又要将本次的i作为参数传入,这样才能避免重复得到[2,2,3][2,3,2]这样的结果。

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明:
所有数字(包括目标数)都是正整数。
解集不能包含重复的组合。 

https://leetcode-cn.com/problems/combination-sum-ii

这题与上一题的不同在于,要避免同样的结果。(即如下情况,使用上面的代码,[1,2,5]会作为结果出现两次,因为有两个1)

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

因此要使用used数组存放元素的使用情况,代码如下。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> ans;
    void backtracking(int &sum,vector<int>& candidates,int target,int index, vector<bool> used){
        if(sum==target){
            ans.push_back(path);
            return;
        }
        if(sum>target) return;
        for(int i=index;i<candidates.size();i++){
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            path.push_back(candidates[i]);
            sum+=candidates[i];
            used[i]=true;
            backtracking(sum,candidates,target,i+1 , used);
            used[i]=false;
            path.pop_back();
            sum-=candidates[i];
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        int sum=0;
        vector<bool> used(candidates.size(), false);
        sort(candidates.begin(),candidates.end());
        backtracking(sum, candidates, target, 0 ,used);
        return ans;
    }
};

效率有点低……但总算是过了。

二叉树刷题篇(12) 二叉树的最近公共祖先

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree

先看我是如何写出一个完美的错误的。

class Solution {
private:
    TreeNode* ans;
    int leftMark=0;
    int rightMark=0;
public:
    void traversal(TreeNode *cur,TreeNode* p,TreeNode* q){
        if(cur==NULL) return;
        traversal(cur->left,p,q);
        if(cur==p) {
            leftMark=1;
        }
        traversal(cur->right,p,q);
        if(cur==q){
            rightMark=1;
        }
        if(rightMark==1&&leftMark==1){
            ans=cur; leftMark=0; rightMark=0;
        }

    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        traversal(root,p,q);
        return ans;
    }
};

实际上,如果从思路上弄明白什么样的节点是p与q的公共祖先,这个代码的错误也就显然易见了。

只有当一个节点的左孩子、右孩子均有p、q节点中的一个 或 左、右孩子其中一个有p或q节点,而节点本身有剩下的那个,这样的节点就是pq节点的公共祖先。

语言描述其实是有点不清晰的,看力扣官方给出的表达式。

这样是不是更明了一些?

在此也贴出官方代码:

class Solution {
public:
    TreeNode* ans;
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return false;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
            ans = root;
        } 
        return lson || rson || (root->val == p->val || root->val == q->val);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }
};

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2/
来源:力扣(LeetCode)

在我的代码中,虽然也用leftMark和rightMark这样的变量去标记左右孩子是否出现了p和q,但很显然这样会使得一些情况被错误标记。


即这种情况,会错误地返回1作为结果。这是因为在1的左右孩子判断结束时,又判断了自身是否是p或q节点,发现是,满足pq标记皆为1,1被标记。但实际上满足标记的是3,还差一层递归没有返回。

显然使用全局变量leftMark和rightMark是不对的,而是应该用函数返回值给节点一个“标记”,如同官方答案中的方法那样。

二叉树刷题篇(11) 二叉搜索树

700. 二叉搜索树中的搜索

给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。

https://leetcode-cn.com/problems/search-in-a-binary-search-tree/

……这题看来是来拜年的,直接放代码。

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root==NULL) return NULL;
        if(root->val==val) return root;
        if(root->val<val){
            return searchBST(root->right,val);
        }
        if(root->val>val){
            return searchBST(root->left,val);
        }
        return NULL;

    }
};

98.验证二叉搜索树

给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

https://leetcode-cn.com/problems/validate-binary-search-tree

不得不说这题一眼看上去太适合递归了……先试一试吧。

果然不对!这道题有一个陷阱,直接上图吧。

这种情况应该返回false,如果在递归逻辑中只判断左右节点,就会错判这种情况。

方法首先是将二叉树进行中序遍历存到数组中,判断数组是否递增。

今天有点累就不自己写代码了,直接上参考答案,代码如下:

class Solution {
private:
    vector<int> vec;
    void traversal(TreeNode* root) {
        if (root == NULL) return;
        traversal(root->left);
        vec.push_back(root->val); // 将二叉搜索树转换为有序数组
        traversal(root->right);
    }
public:
    bool isValidBST(TreeNode* root) {
        vec.clear(); // 不加这句在leetcode上也可以过,但最好加上
        traversal(root);
        for (int i = 1; i < vec.size(); i++) {
            // 注意要小于等于,搜索树里不能有相同元素
            if (vec[i] <= vec[i - 1]) return false;
        }
        return true;
    }
};
//代码来自公众号代码随想录 作者为Carl

迭代法一样,也是将二叉搜索树转换为有序数组并判断。

class Solution {
public:
    TreeNode* pre = NULL; // 用来记录前一个节点 
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;
        bool left = isValidBST(root->left);

        if (pre != NULL && pre->val >= root->val) return false;
        pre = root; // 记录前一个节点

        bool right = isValidBST(root->right);
        return left && right;
    }
};

二叉树刷题篇(10) 最大二叉树 and 合并二叉树

654.最大二叉树

给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下:
二叉树的根是数组 nums 中的最大元素。
左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
返回有给定数组 nums 构建的 最大二叉树 。

https://leetcode-cn.com/problems/maximum-binary-tree/

这题与昨天做的根据中序与后序遍历数组构造二叉树思路基本一样,做题的确也是有套路的,会一道就是会十道(x)。

递归法即可完美解决。这里注意要判断maxValueIndex的值,保证切割出来的左右数组大小大于0。比如[3,2,1]这个数组再去切分,会出现[]的左数组,再对这个左数组进行构造,会进入死循环。如果想解除这个死循环需要在函数前面进行判断,处理nums.size()==0的情况,就很麻烦,因此在迭代时先进行判断排除这种情况是比较方便的。

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.size()==1){
            return new TreeNode(nums[0]);
        }
        int maxValue=0;
        int maxValueIndex=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]>maxValue){
                maxValue=nums[i];
                maxValueIndex=i;
            }
        }
        TreeNode* root=new TreeNode(maxValue);
        if (maxValueIndex > 0) {
            vector<int> leftnums(nums.begin(),nums.begin()+maxValueIndex);
            root->left=constructMaximumBinaryTree(leftnums);
        }
        if (maxValueIndex < (nums.size() - 1)){
            vector<int> rightnums(nums.begin()+maxValueIndex+1,nums.end());
            root->right=constructMaximumBinaryTree(rightnums);
        }
        return root;

    }
};

仿照昨天的思路,不在每次递归中创造新的vector,而是用数组的起始结束位置作为参数传入,代码如下。

class Solution {
private:
    // 在左闭右开区间[left, right),构造二叉树
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left >= right) return nullptr;
        // 这里的判断条件可以改成left == right
        // 分割点下表:maxValueIndex
        int maxValueIndex = left;
        for (int i = left + 1; i < right; ++i) {
            if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;
        }

        TreeNode* root = new TreeNode(nums[maxValueIndex]);

        // 左闭右开:[left, maxValueIndex)
        root->left = traversal(nums, left, maxValueIndex);

        // 左闭右开:[maxValueIndex + 1, right)
        root->right = traversal(nums, maxValueIndex + 1, right);

        return root;
    }
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return traversal(nums, 0, nums.size());
    }
};

617.合并二叉树

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

https://leetcode-cn.com/problems/merge-two-binary-trees/

这题乍一看不难,似乎层序遍历+节点数值合并就可以解决,但这样面临一个严重问题,就是在这种情况下必须让空节点也能够入栈(队列),那么就无法使用while(!que.empty())这个条件让循环停止,会陷入死循环。

思来想去,还是先使用递归法吧,看代码:

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1==NULL&&root2==NULL) return NULL;
        if(root1!=NULL&&root2==NULL){
            TreeNode* node= new TreeNode(root1->val);
            node->left=mergeTrees(root1->left,NULL);
            node->right=mergeTrees(root1->right,NULL);
            return node;
        }
        if(root1==NULL&&root2!=NULL){
            TreeNode* node= new TreeNode(root2->val);
            node->left=mergeTrees(NULL,root2->left);
            node->right=mergeTrees(NULL,root2->right);
            return node;
        }
        else{
            TreeNode* node=new TreeNode(root1->val+root2->val);
            node->left=mergeTrees(root1->left,root2->left);
            node->right=mergeTrees(root1->right,root2->right);
            return node;
        }
        TreeNode* node= new TreeNode(root1->val+root2->val);
        node->left=mergeTrees(root1->left,root2->left);
        node->right=mergeTrees(root1->right,root2->right);
        return node;
    }
};

这个代码写得,emmmm……很显然内存消耗会比较大,看看Carl大神怎么写的,学习一下。

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        // 重新定义新的节点,不修改原有两个树的结构
        TreeNode* root = new TreeNode(0);
        root->val = t1->val + t2->val;
        root->left = mergeTrees(t1->left, t2->left);
        root->right = mergeTrees(t1->right, t2->right);
        return root;
    }
};

看完的确让人眼前一亮(当然也可能是我太蠢哈哈哈),其实简单地阐述一下就是,假如t1==NULL,那么t1就可以=t2(比我们一个一个节点去判断要好得多)。

当然,这里也提供一下迭代法的代码,和我们最一开始的思路一样,使用两个queue去存储节点,然后一直层序遍历,合并节点。

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        queue<TreeNode*> que;
        que.push(t1);
        que.push(t2);
        while(!que.empty()) {
            TreeNode* node1 = que.front(); que.pop();
            TreeNode* node2 = que.front(); que.pop();
            // 此时两个节点一定不为空,val相加
            node1->val += node2->val;

            // 如果两棵树左节点都不为空,加入队列
            if (node1->left != NULL && node2->left != NULL) {
                que.push(node1->left);
                que.push(node2->left);
            }
            // 如果两棵树右节点都不为空,加入队列
            if (node1->right != NULL && node2->right != NULL) {
                que.push(node1->right);
                que.push(node2->right);
            }

            // 当t1的左节点 为空 t2左节点不为空,就赋值过去
            if (node1->left == NULL && node2->left != NULL) {
                node1->left = node2->left;
            }
            // 当t1的右节点 为空 t2右节点不为空,就赋值过去
            if (node1->right == NULL && node2->right != NULL) {
                node1->right = node2->right;
            }
        }
        return t1;
    }
};

好,今天是除夕夜,就做到这里,也祝大家除夕快乐!