前言

前言

作为一名视觉方向零基础的研究生，每天的学习内容主要包括leetcode刷题、跟李沐学pytorch、相关文献阅读。leetcode水平目前只有周赛前两题，欢迎各位有相同学习计划的来相互探讨交流，也欢迎各路大神提出宝贵的意见。

一、leetcode 1619与947

1.1619

        1619是今天的每日一题，难度easy。题目描述为删除前5%和后5%的元素后取平均值，思路较为简单清晰。首先对数组nums进行排序，然后遍历中间90%的元素进行求和，最终返回平均值。

        唯一需要注意的一个点，一般来说习惯性定义sum为int类型，而题目返回值为double类型，所以需要在返回时进行转化，将sum * 1.0 。

class Solution {
public:
    double trimMean(vector<int>& arr) {
        int fro = (int)arr.size() * 0.05;
        sort(arr.begin(), arr.end());
        int sum = 0;
        for(int i = fro; i < arr.size() - fro; ++i) {
            sum += arr[i];
        }
        return sum * 1.0/(0.9 * arr.size());
    }
};

 2.947

 题目描述：n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。

如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。

给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。

题目分析：根据题意，二维平面，求移除的最大数量，而移除的条件是二者同行或者同列。由此我们可以联想到连通图概念，连通图中最后只剩下一个元素。因此考虑使用并查集解决该问题，并查集主要作用就是求连通分支数。

class Solution {
    private:
        int father[20005];
        int n = 20005;
    //首先使用初始化函数，将每一个点的根节点都设置为自己
    void init() {
        for(int i = 0; i < n; ++i) {
            father[i] = i;
        }
    }
    //find函数作用是寻找根，使用两层树结构优化find函数，减少不必要的深度
    int find(int u) {
        //return u == father[u] ? u : father[u] = find[father[u]];
        if(u == father[u])
            return u;           //如果他就是根节点，结束
        else
            return father[u] = find(father[u]);   //找到最浅层的根节点
    }

    //join函数，将两个u、v合并
    void join(int u, int v) {
        int findu = find(u);        //首先利用find函数寻找根，如果同一个根则返回，如果不是同一个
        int findv = find(v);        //则随便指定u、v的根为对方的根，因为此处uv本就应该同根
        if(findu == findv) return ;
        father[findu] = findv;
    }

public:
    int removeStones(vector<vector<int>>& stones) {
        init();
        for(int i = 0; i < stones.size(); ++i) {
            join(stones[i][0], stones[i][1] + 10001); //所有石头计算根节点
        }
        unordered_map<int, bool> umap;                 //计算最后剩下的根节点，赋值为true
        for(int i = 0; i < stones.size(); ++i) {
            umap[find(stones[i][0])] = true;
            umap[find(stones[i][1] + 10001)] = true;
        }
        return stones.size() - umap.size();
    }
};

 具体并查集可以参考这篇博客，非常详细和生动。

【算法与数据结构】—— 并查集_酱懵静的博客-CSDN博客_并查集

二、跟李沐学pytorch

今日学习内容为线性回归与基础优化算法。

本节用梯度下降法求解权重问题，此处需要注意梯度下降方向实际为反梯度方向。针对线性问题，主要有学习率和batch_size两个超参需要调整，但是本节没有详细讲解。代码方面主要实现了不调用API和调用API两种方式。两种方式中均采用小批量随机梯度下降，小批量如何选择是一个未解答的问题。

torch.normal(means, std, size(m*n)) 正态分布随机取值函数

torch.matmul() 矩阵相乘

yield函数 python中yield的用法详解——最简单，最清晰的解释_冯爽朗的博客-CSDN博客_python yield

1.不使用API

import random
import torch
from d2l import torch as d2l

def synthetic_data(w, b, num_examples):
    x = torch.normal(0, 1, (num_examples, len(w)))
    y = torch.matmul(x, w) + b
    y += torch.normal(0, 0.01, y.shape)         #噪声
    return x, y.reshape((-1, 1))

true_w = torch.tensor([2, -3.4])
true_b = 4.2
features, labels = synthetic_data(true_w, true_b, 1000)

#print(features[1], labels[0])

d2l.set_figsize()
d2l.plt.scatter(features[:, 1].detach().numpy(),      #detach为分离
                labels.detach().numpy(), 1)
#d2l.plt.show()

#实现一个函数小批量读取
def data_iter(batch_size, features, labels):
    num_examples = len(features)
    indices = list(range(num_examples))
    random.shuffle(indices)  #随机打乱下标
    for i in range(0, num_examples, batch_size):
        batch_indices = torch.tensor(
            indices[i:min(i + batch_size, num_examples)]
        )
        yield features[batch_indices], labels[batch_indices]

batch_size = 10

"""
for x, y in data_iter(batch_size, features, labels):
    print(x, '\n', y)
    break

"""

#定义初始化模型参数
w = torch.normal(0, 0.01, size=(2, 1), requires_grad=True)
b = torch.zeros(1, requires_grad=True)

#定义模型
def linreg(x, w, b):
    """线性回归模型"""
    return torch.matmul(x, w) + b

#定义损失函数
def squared_loss(y_hat, y):
    """均方损失"""
    return (y_hat - y.reshape(y_hat.shape))**2 / 2

#定义优化算法
def sgd(params, lr, batch_size):
    """小批量随机梯度下降"""
    with torch.no_grad():
        for param in params:
            param -= lr * param.grad / batch_size
            param.grad.zero_()


lr = 0.03
num_epochs = 3
net = linreg
loss = squared_loss

for epoch in range(num_epochs):
    for x, y in data_iter(batch_size, features, labels):
        l = loss(net(x, w, b), y)

        l.sum().backward()
        sgd([w, b], lr, batch_size)
    with torch.no_grad():
        train_l = loss(net(features, w, b), labels)
        print(f'epoch {epoch + 1}, loss {float(train_l.mean()):f}')

print(f'w的估计误差: {true_w - w.reshape(true_w.shape)}')
print(f'b的估计误差：{true_b - b}')

2.使用API

import numpy as np
import torch
from torch.utils import data
from d2l import torch as d2l
from torch import nn

#使用现有框架中的API来读取数据

true_w = torch.tensor([2, -3.4])
true_b = 4.2
features, labels = d2l.synthetic_data(true_w, true_b, 1000)

def load_array(data_arrays, batch_size, is_train = True):
    """构造一个pytorch迭代器"""
    dataset = data.TensorDataset(*data_arrays) #*表示解开入参
    return data.DataLoader(dataset, batch_size, shuffle=is_train)   #随机抽取样本

batch_size = 10
data_iter = load_array((features, labels), batch_size)

#print(next(iter(data_iter)))

net = nn.Sequential(nn.Linear(2, 1))
net[0].weight.data.normal_(0, 0.01)
net[0].bias.data.fill_(0)

loss = nn.MSELoss()  #均方误差

trainer = torch.optim.SGD(net.parameters(), lr = 0.03)

num_epochs = 3
for epoch in range(num_epochs):
    for x, y in data_iter:
        l = loss(net(x), y)
        trainer.zero_grad()
        l.backward()
        trainer.step()
    l = loss(net(features), labels)
    print(f'epoch {epoch + 1}, loss {l:f}')

上面两段代码是李沐老师课堂讲解内容，我只是将他搬运到vscode上运行，增加了一点注释。

总结

路漫漫其修远兮，吾将上下而求索。

今天从李沐老师那里学到一个词，深度人生。希望有朝一日能创造出属于自己的深度人生。