我的个人博客

What past is prolgue.

0%

发表于 分类于

sequence

列表(lists)

[1,2,3]

odds=[3,5,7,9,11]

list(range(1,3))

​ [1,2]

[odds[i] for i in range(1,3)]

​ [5,7]

sum([1,2,3])=6

sum([[1,2],[3]],[])=[1,2,3]

  1. 函数参数加*号，代表将多个参数组装成列表

  2. 数组前面加参数，代表把数组拆分成多个逗号分割的变量，类似js中的展开符号.

def add(x,y):
    return x+y
ls=[10,12]
add(*ls)

range

tuple

immutable sequences

发表于

分治法

分治(divide-conquer)，将原问题分解为容易求解的子问题，再对子问题合并，实现对原问题求解。

自上而下分治+记忆化搜索

自下而上（动态规划）

241. 为运算表达式设计优先级

方法一：记忆化搜索
class Solution {
public:
    vector<int> operand;
    vector<char> ops;
    vector<int> diffWaysToCompute(string expression) {
        int n=expression.size();
        int i=0;
        while(i<n){
            if(isdigit(expression[i])){
                int val=0;
                while(i<n&&isdigit(expression[i])){
                    val=val*10+expression[i]-'0';
                    i++;
                }
                operand.push_back(val);
                // cout<<val<<endl;
            }else{
                ops.push_back(expression[i]);
                // cout<<expression[i]<<endl;
                i++;
            }
        }
        vector<vector<vector<int>>> dp(operand.size(),vector<vector<int>>(operand.size()));
        return backtrack(dp,0,dp.size()-1);
    }

    vector<int> backtrack(vector<vector<vector<int>>> &dp,int l,int r){
        if(l==r){
            return {operand[l]};
        }

        if(!dp[l][r].empty())
            return dp[l][r];

        for(int i=l;i<r;i++){
            auto left=backtrack(dp,l,i);
            auto right=backtrack(dp,i+1,r);
            for(int l_val:left){
                for(int r_val:right){
                    if(ops[i]=='+') dp[l][r].push_back(l_val+r_val);
                    else if(ops[i]=='-') dp[l][r].push_back(l_val-r_val);
                    else    dp[l][r].push_back(l_val*r_val);
                }
            }
        }
        return dp[l][r];
    }
};

932. 漂亮数组

对于一个正整数 N, 我们将其等分为两部分，left 和 right， 如果 left 部分是漂亮数组，right 部分也是漂亮数组， 同时 left 部分全部是奇数，right 部分全部是偶数，那么此时 left+right 组成的数组一定也是一个漂亮数组。

class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<int> ans(n,1);
        divide(ans,0,n-1);
        return ans;
    }

    void divide(vector<int>& ans,int left,int right){
        if(left>=right)
            return;
        int mid=(left+right)/2;
        divide(ans,left,mid);
        divide(ans,mid+1,right);
        for(int i=left;i<=mid;i++)
            ans[i]=ans[i]*2-1;
        for(int i=mid+1;i<=right;i++)
            ans[i]=2*ans[i];
    }
};

1763. 最长的美好子字符串

tag：切割出符合条件的子串，判断出现的大小写字符集

class Solution {
public:
    int maxLen=0,pos=-1;
    string longestNiceSubstring(string s) {
        int n=s.size();
        check(s,0,n-1);
        return maxLen==0?"":s.substr(pos,maxLen);
    }

    void check(string &s,int left,int right){
        if(left>=right)
            return;

        int lower=0,upper=0;
        for(int i=left;i<=right;i++){
            if(islower(s[i])){
                lower|=(1<<s[i]-'a');
            }else{
                upper|=(1<<s[i]-'A');
            }
        }
        // 大写字符集和小写字符集一样
        if(lower==upper){
            int len=right-left+1;
            if(len>maxLen){
                pos=left;
                maxLen=len;
            }
            // 从左到右分割，不需要下面的  
            // else if(len==maxLen&&left<pos){
            //     pos=left;
            // }
            return;
        }
        int valid=upper&lower;
        //大写字符集和小写字符集不一样，需要分割，没有成对出现时，valid相应位置为0
        int beg=left,end=left;
        while(end<=right){
            while(end<=right&&(valid&(1<<(tolower(s[end])-'a'))))
                end++;
            // cout<<left<<" "<<right<<" "<<beg<<" "<<end<<endl;
            check(s,beg,end-1);
            beg=end+1;
            end++;
        }

    }
};

395. 至少有 K 个重复字符的最长子串

class Solution {
public:
    int ans=0;
    int longestSubstring(string s, int k) {
        int n=s.size();
        check(s,0,n,k);
        return ans;
    }

    void check(string &s,int left,int right,int &k){
        if(left>=right)
            return;
        unordered_map<char,int> cnt;
        for(int i=left;i<right;i++){
            cnt[s[i]]++;
        }

        bool flag=true;
        int beg=left;
        for(int end=left;end<right;end++){
            if(cnt[s[end]]<k){
                flag=false;
                // cout<<beg<<" "<<end<<endl;
                check(s,beg,end,k);
                beg=end+1;
            }
        }

        if(flag)
            ans=max(ans,right-left);
        else
            check(s,beg,right,k);
      
    }
};

发表于

@resource
postConstruct

1 Map

1.1 Map对象遍历

(50条消息) Java中如何遍历Map对象的4种方法_map遍历_Java高知社区的博客-CSDN博客

//遍历的是一个空的map对象，for-each循环将抛出NullPointerException，因此在遍历前你总是应该检查空引用。
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
    System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
 }
//遍历map中的键
for (Integer key : map.keySet()) {
    System.out.println("Key = " + key);
}
 
//遍历map中的值
for (Integer value : map.values()) {
    System.out.println("Value = " + value);
 }

1.2 TreeMap

1.2.1 自定义排序

package indiv.yyg;

import java.util.Comparator;
import java.util.TreeMap;

/**
 * @description:
 * @author: yyg
 * @date: 2024/5/14
 */
public class Person {
    private  Integer age;

    public Person(Integer age){
        this.age=age;
    }

    public Integer getAge(){
        return age;
    }

    public static void main(String[] args){
        //传入匿名类
        TreeMap<Person,String> treeMap=new TreeMap<>(new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                int num=o1.getAge()-o2.getAge();
                return Integer.compare(num,0);
            }
        });
        treeMap.put(new Person(3), "person1");
        treeMap.put(new Person(18), "person2");
        treeMap.put(new Person(35), "person3");
        treeMap.put(new Person(16), "person4");
        treeMap.entrySet().stream().forEach(personStringEntry -> {
            System.out.println(personStringEntry.getValue());
        });
        //lamada表达式
        TreeMap<Person,String> treeMap1=new TreeMap<>((o1,o2)->{
            int num=o1.getAge()-o2.getAge();
            return Integer.compare(num,0);
        });
    }
}

1.3 时间

(50条消息) Java中如何获取当前日期和时间的4种方法_获取当前时间_小楼星辰的博客-CSDN博客

1.4 文件

//获取目录下所有文件名
File dir;
String[] list=dir.list();

//删除目录
public static void deleteDir(File file){
    if(file.isDirectory()){
        for(File f:file.listFiles()){
            deleteDir(f);
        }
    }
    file.delete();
}

Java 实例 – 删除目录 | 菜鸟教程 (runoob.com)

1.4.1 复制文件

import java.nio.file.Files;
//from和to是File对象，如果要复制到的文件已经存在，则复制失败
try {
    Files.copy(from.toPath(), to.toPath());
} catch (Exception e) {
}

1.4.2 删除文件

java.io.File;

File f;
f.delete();

/**
 * 得到当前工作目录下的所有文件
 */
private void showFileList(File filename) {
    if (filename.isDirectory()) {
        System.out.println("文件夹：" + filename);
        File[] listfile = filename.listFiles();
        for (File f : listfile) {
            showFileList(f);
        }
    } else {
        //    处理
    }
}

2 String

public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("message: " + message + "\n");
    sb.append("date: " + date + "\n");
    for (String parent : parentID) {
        sb.append(parent + "\n");
    }
    return sb.toString();
}
String str1=null; //引用为空，没有地址，是一个没有被实例化的对象
String str2="";//空字符串，它有地址，它是被实例化的对象，值为空而已。

//如果是string对象是null,用 == 来判断，否则会抛出异常 java.lang.NullPointerException

str1==str2; //“ == ”操作在对String这种引用数据类型来说，比较的是地址
str1.equals(str2) //equals比较的是内容

发表于

  • 最值

  • 二分查找（解的值域范围具有单调性，小于x的值范围都符合，大于x的值范围都不符合）

  • 动态规划

  • 二分查找

  • 使……最大值尽可能小

  • 前缀和

  • 子数组

  • 动态规划

  • 将数组分割为割为m段，求……

  • 滑动窗口
    • 长度固定的子数组

数值范围

int：4字节，32位，最大值:$2^{31}-1=2147483647$，最小值$-2147483648$。

$105$的数据范围不能用$O(n2)$解法
$10^9$的时间复杂度不行

数据范围 复杂度
$10^5$ $nlog(n)$

区间

对于两个区间$[S_1,e_1)$和$[S_2,e_2)$，如果两者没有交集，则此时应当满足$s_1 \ge e_2$或者$s_2 \ge e_1$，即如果$s_1 <e_2 且 s_2<e_1$，两者会产生交集。

num/mid上取整
(num-1)/mid+1 (num+mid-1)/mid

K小问题

k 小问题有三种解法：按位确定答案（多用于字符串和二进制数），用堆维护当前最小答案（用于 kkk 比较小的情况），二分（用于 kkk 比较大的情况）。

字符串

出现的大小写字母集合

因此可以利用二进制位来进行标记，lower标记字符中出现过小写英文字母，upper标记字符中出现过大写英文字母。如果满足lower=upper，则认为字符串中所有的字符都满足大小写形式同时出现。

1763. 最长的美好子字符串

字符是否出现
1684. 统计一致字符串的数目 - 力扣（LeetCode）

数组

「长度固定的子数组」就要想到滑动窗口对角线上是否放置元素

  • record.count(x-y)

  • record.count(x+y)

出现超过一半的数字

找出数组中出现次数超过数组长度一半的数字

169. 多数元素

  1. 哈希表记录出现次数

  2. 排序后取中位数

  3. 抵消法

  4. 快排取中位数

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cnt=0,pre=nums[0];
        for(int num:nums){
            if(cnt==0){
                pre=num;
            }
            if(num==pre){
                cnt++;
            }else{
                cnt--;
            }
        }
        return pre;
    }
};

动态规划

动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如这里的统计方案数的问题，它们都存在一定的递推性质。「将数组分割为割为m  段，求……」是动态规划题目常见的问法。410. 分割数组的最大值

二分查找

适合求解具有单调最优性质的题目

「使……最大值尽可能小」是二分搜索题目常见的问法。410. 分割数组的最大值

预处理回文数

枚举回文数左半部分

vector<int> pal;

auto init=[]{
    // 严格按顺序从小到大生成所有回文数（不用字符串转换）
    for(int base=1;base<=10000;base*=10){
        //生成奇数长度回文数
         for(int i=base;i<base*10;i++){
             int x=i;
             for(int t=i/10;t;t/=10){
                 x=x*10+t%10;
             }
             pal.push_back(x);
         }

         //生成偶数长度回文数
         if(base<=1000){
             for(int i=base;i<base*10;i++){
                 int x=i;
                 for(int t=i;t;t/=10){
                     x=x*10+t%10;
                 }
                 pal.push_back(x);
             }
         }
    }
    pal.push_back(1'000'000'001); // 哨兵，防止下面代码中的 i 下标越界
    return 0;
}();

发表于

1 差分数组、前缀和

差分数组是与前缀和数组所对应的一种逆操作，类似于求导和积分，也就是说，对差分数组求前缀和，可以得到原数组，同样的，对前缀和数组求差分，也可以得到原数组。
差分数组适用于频繁对数组区间进行增减操作，通过求前缀和得到最终数组每一元素的值。但是不适用求区间和。

前缀和、差分、树状数组、块状数组 - 力扣（LeetCode）

2 前缀和

525. 连续数组
$$
nums[L:R]=\frac{R+1-L}{2}\
s[R+1]-S[L]=\frac{R+1-L}{2}\
2s[R+1]-R=2s[L]-(L-1)
$$

class Solution {
  public:
    int findMaxLength(vector<int> &nums) {
        int n = nums.size();
        vector<int> s(n + 1);
        unordered_map<int, int> pos;        //哈希表记录和第一次出现的位置
        pos[1] = 0;

        int ans = 0;
        for (int i = 0; i < n;i++){
            s[i + 1] = s[i] + nums[i];

            if(pos.count(2*s[i+1]-i)){
                int diff = i + 1 - pos[2 * s[i + 1] - i];
                ans = max(ans, diff);
            }else{
                pos[2 * s[i + 1] - i] = i + 1;
            }
        }
        return ans;
    }
};

$$
0和1数量相同\rightarrow 1的数量-0的数量=0
$$

class Solution {
  public:
    int findMaxLength(vector<int> &nums) {
        int n = nums.size();
        vector<int> s(n + 1);
        unordered_map<int, int> pos;        //哈希表记录和第一次出现的位置
        pos[0] = 0;

        int ans = 0;
        for (int i = 0; i < n;i++){
            s[i + 1] = s[i] + (nums[i] == 1 ? 1 : -1);

            if(pos.count(s[i+1])){
                int diff = i + 1 - pos[s[i + 1]];
                ans = max(ans, diff);
            }else{
                pos[s[i + 1]] = i + 1;
            }
        }
        return ans;
    }
};

3 差分数组

差分数组对应的概念是前缀和数组，d[i]=nums[i]-nums[i-1]，d[0]=nums[0]，对差分数组求前缀和可得到原数组。

对原数组的区间[l,r]增加x时，差分数组对应的改变为：d[l]增加x，d[r+1]减少x。

d[r+1]=nums[r+1]-nums[r]，其中nums[r]增加x。

这种修改是可以叠加的，即当我们多次对原数组的不同区间施加不同的增量，我们只要按规则修改差分数组即可。

可以理解为公交车问题，在l站上车，乘坐区间[l,r]，在[r+1]站下车。

特别地，当 r 为 n 时，我们无需修改 d[r]，因为这个位置溢出了下标范围。如果求前缀和时考虑该位置，那么该位置对应的前缀和值必定为 0。读者们可以自行思考原因，以加深对差分数组的理解。

6919. 使数组中的所有元素都等于零

把子数组改成子序列要怎么做？【力扣周赛 353】_哔哩哔哩_bilibili

Leetcode-动态规划DP-差分数组 6919. 使数组中的所有元素都等于零.png 
class Solution {
  public:
    bool checkArray(vector<int> &nums, int k) {
        int n = nums.size();
        vector<int> d(n + 1);
        // d[0] = nums[0];

        int sum_d = 0;
        for (int i = 0; i < n;i++){
            sum_d += d[i];

            int x = sum_d+nums[i];
            if(x==0)
                continue;
            if(x<0||i+k>n)
                return false;
            sum_d -= x;
            d[i + k] += x;
        }
        return true;
    }
};

方法二

class Solution {
public:
    bool checkArray(vector<int>& nums, int K) {
        int n = nums.size();
        // 计算差分数组
        int f[n + 1];
        f[0] = nums[0];
        for (int i = 1; i < n; i++) f[i] = nums[i] - nums[i - 1];
        f[n] = -nums[n - 1];
        // 从左到右对差分数组里的每个元素进行操作
        for (int i = 0; i + K <= n; i++) if (f[i] > 0) {
            f[i + K] += f[i];
            f[i] = 0;
        }
        // 检查差分数组中是否所有元素均为 0
        for (int i = 0; i <= n; i++) if (f[i] != 0) return false;
        return true;
    }
};

★★

★★★

★★★★★

4 题目

4.1 前缀和

题目 标签
560. 和为 K 的子数组 - 力扣（LeetCode） 前缀和、哈希表(计数前缀和出现次数)

发表于

pytorch

torch Tensor

import torch

x=torch.arange(12)
x
tensor([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11])

#张量的形状
x.shape

#含有元素个数
x.numel()

#维度自动推断
X=x.reshape(3,4)=x.reshape(-1,4)=x.reshape(3,-1)

torch.zeros((2,3,4))
torch.ones(2,3,4)
torch.randn(3,4)

转置函数

在pytorch中转置用的函数就只有这两个

  1. transpose()

  2. permute()

transpose()
torch.transpose(input, dim0, dim1, out=None) → Tensor

函数返回输入矩阵input的转置。交换维度dim0和dim1

参数:

  • input (Tensor) – 输入张量，必填

  • dim0 (int) – 转置的第一维，默认0，可选

  • dim1 (int) – 转置的第二维，默认1，可选

注意只能有两个相关的交换的位置参数。

permute()
参数：

dims (int…*)-换位顺序，必填

常用函数

one_hot

image-20220414102235414

图像转换

当用PIL中的Image.open打开RGB图像时，image.size = (w,h)
即（列，行）—>(x,y)
在这里插入图片描述
如果把该图载转换为易于操作的ndarray形式，则：
image = np.asarray(image)

转换后的image.shape=（h,w,c）c为通道数，RGB图像c=3
(h,w)为（行，列），即为（y,x）

numpy

numpy库数组属性查看：类型、尺寸、形状、维度

import numpy as np  
      
a1 = np.array([1,2,3,4],dtype=np.complex128)  
print(a1)  
print("数据类型",type(a1))           #打印数组数据类型  
print("数组元素数据类型：",a1.dtype) #打印数组元素数据类型  
print("数组元素总数：",a1.size)      #打印数组尺寸，即数组元素总数  
print("数组形状：",a1.shape)         #打印数组形状  
print("数组的维度数目",a1.ndim)      #打印数组的维度数目

PIL

from PIL import Image
from matplotlib import pyplot as plt

#显示图片，图片尺寸，通道数
img=Image.open("Image/1.jpg")
plt.imshow(img)
img.size,img.layers
#图片变为numpy对象，W*H*C,范围[0-256]
import numpy as np
img_ndarray=np.asarray(img)
#W*H*C
img_ndarray.shape

#numpy转化为torch，C*W*H
trans=torchvision.transforms.ToTensor()
img2_trans=trans(img2_n)
img2_trans.shape

tensor变为整数类型

a = [[1.,2.],[3.,4.]]
b = torch.tensor(a)
# c = torch.tensor(b,dtype=torch.int)
c = b.clone().type(torch.int)

print(b)
print(c)

image-20220413151208381

argmax：求某一维度最大值的下标

image-20220324201852580

detach

image-20220413110006761

torch.nn

Flatten

展平层，将1维到最后1维展开成一个向量形式

image-20220324174809807

image-20220324174836609

torch.utils.data

image-20220323213832027

image-20220323215218953

torch.zeros

image-20220323223004246

矩阵转置

image-20220324105139852

损失函数

nn.CrossEntropyloss

image-20220404215314933

image-20220404215358048

optim

SGD

image-20220324170304790

torchvision

transforms

ToTensor

image-20220407121440273