4-20-2023

发表于 2023-04-20 分类于 2023

1.半夜背东西的效果

2.一边看田静长难句每日一句，忘记的语法看了英语兔，觉得看懂中高阶难度的文章单词重要语法也重要

3.写的越来越慢了，进展到链表（TAT）

4.数学干掉了第三章和知识框架，进展到张宇30讲第三讲函数极限，

正在做7种未定式归纳。

感觉怪怪的：

首先把所以定义理了一遍（超级费时间），

然后把张宇和武忠祥的题归纳在了活页本上，感觉做题方法啥的有点乱，一道题不一定用了一个知识点，不过第三遍看张宇的，思路清晰很多。

这周希望能写1800那上面的题吧（有思路的写）

5.半夜报复性的玩代号鸢，单词都咩有背完（投降）（认错）（再也不敢了）

比起看英语文章，背单词的还是比看文章的轻松太多的。

知道了那个考南邮的是哪个师兄了！！！

acm铜的江苏师兄，专业课110 数学98 政治50英语60多总分320无缘南邮直接上班去了（掰了掰手指头算了算我考的学校，好像我得数学上百，zz70英语80才可以哦（怎么感觉在梦里可以做到呢）（考不上就进流水线（摆）））

707.设计链表

发表于 2023-04-18 分类于代码随想录

707. 设计链表

struct LinkNode{
    int val;
    LinkedNode* next;
    LinkedNode(int val):val(val),next(NULL){}
};
//初始化链表
MyLinkedList(){
 	dummyHead=new LinkedNode(0);//虚拟头结点
    size=0;
}
//获取第index个结点数值，index是从0开始的，第0个结点就是头结点
int get(int index){
    if(index>(size-1)||index<0){ //如果index是非法数值返回-1，
        return -1;
    }
    LinkedNode* cur=dummyHead->next;
    while(index){  //当index的值不为0的时候
        cur=cur->next; //continue 到下一个，因为加了个dummy虚拟头节点所以第一个cur->next就是头结点
        index--;
    }
    return cur->val;
}
void addAtHead(int val){
    LinkedNode* newNode=new LinkedNode(val);//创建个的结点
    newNode->next=dummyHead->next;//让新节点的地址指向当初的头节点
    dummyHead->next=newNode; //然后再让虚拟头结点的地址指向新的结点
    size++;
}
//在链表最后面添加一个结点
void addAtTail(int val){
    LinkedNode* newNode =new LinkedNode(val);//创建一个结点
    LinkedNode* cur=dummyHead;//设置一个cur来操作dummy
    while(cur->next!=NULL){//当当前结点不为空的时候 ，继续往下找
        cur=cur->next;
    }
    cur->next=newNode; //把最后一个结点的地址变成newnode
    size++;
}

//在index之前的地方插入新结点
void addIndex(int index,int val){
    if(index>size) return ;// ilegal
    if(index<0) index=0;
    LinkedNode* newNode=new LinkedNode(val); //set new node
    LinkedNode* cur=dummyHead;// set cur 
    while(index){  //index!=NULL
        cur=cur->next; //point to next address
        index--;
    }
    newNode->next=cur->next; //把 newNode的 地址 变成cur地址（后面的值放入） 
    cur->next=newNode;//再把newNode放到cur的地址上（前面的值改变）
    size++;
    
}

//删除第index个结点
void deleteAtIndex(int index){
    if(index>=size||index<0){
        return;
    }
    LinkedNode* cur = dummyHead;
    while(index){
        cur=cur->next;
        index--;
    }
    LinkedNode* tmp =cur->next;
    cur->next=cur->next->next;
    delete tmp;
    size--;
}
//打印链表
void printLinkedList(){
    LinkedNode* cur =dummyHead;
    while(cur->next!=NULL){
        cout<<cur->next->val<<" ";
        cur=cur->next;
    }
    cout<<endl;
}

203.移除链表元素

发表于 2023-04-17 更新于 2023-04-18 分类于代码随想录

203. 移除链表元素

直接使用原来的链表来进行移除节点操作：

ListNode* removeElements(ListNode* head,int val){
    //删除头结点
    while(head!=NULL&&head->val==val){
		ListNode* tmp=head;
        head=head->next;//直接让head等于下一个next
        delete tmp;
    }	
    //删除非头结点
    ListNode* cur =head;  //设置一个cur的东西来操作链表
    while(cur!=NULL&&cur->next!=NULL){ //当前不为空，且下一个结点也不为空
        if(cur->next->val==val){ // 如果当前的下一个结点为val 当前的next地址为下一个结点
            ListNode* tep=cur->next;
            cur->next=cur->next->next; //val的next变成 val的下一个下一个的next
        }else{
            cur=cur->next;
        }
    }
    return head;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //删除头结点
        while(head!=NULL&&head->val==val){
            ListNode* tmp=head;
            head=head->next;
            delete tmp;
        }
        //删除非头结点
        ListNode *cur=head;
        while(cur!=NULL&&cur->next!=NULL){ //当前不为空，且下一个也不为空
            if(cur->next->val==val){
                ListNode *tmp=cur->next;
                cur->next=cur->next->next;
                delete tmp;
            }
            else{ 
                cur=cur->next;
            }
        }
        return head;
    }
};

设置一个虚拟头结点在进行移除节点操作：

ListNode* removeElements(ListNode* head,int val){
    ListNode* dummyHead=new ListNode(0); //创建一个虚拟节点
    dummyHead->next=head;	//这个结点的地址指向head
    ListNode* cur=dummyHead;//用来操作的作为 当前的为虚拟结点
   	while(cur->next!=NULL){
   		 if(cur->next->val==val){// 当前的下一个结点值 等于 val
     	 	ListNode* tmp=cur->next;// 
        	cur->next=cur->next->next; //下一个等于下一个结点
         	delete tmp;
         }
         else{
            cur=cur->next; //cur移向下一个结点
    }
    head=dummyHead->next; //head为虚拟结点的下一个结点
    delete dummyHead;//
    return head;
    }

}

#include <iostream>
using namespace std;
//单链表
struct ListNode{
	int val;			//节点上存储的元素 
	ListNode *next;  	//指向下一个结点的指针
	ListNode(int x): val(x)  ,next(NULL){}
}; 
//创建链表
//ListNode* createList(){
//	ListNode* head=NULL;
//	ListNode* tail=NULL;
//	int val;
//	while(cin>>val){
//		ListNode* node=new ListNode(val);
//		if(tail==NULL){
//			head=node;
//			tail==node;
//		}
//		else{
//			tail->next=node;
//			tail=node;
//		}
//	}
//} 
ListNode* removeElements(ListNode* head,int val){
	
	ListNode *dymmy=new ListNode(0);
	dymmy->next=head;
	ListNode *cur=dymmy;
	while(cur->next!=NULL){
		if(cur->next->val==val){
		ListNode *tmp=cur->next;
		cur->next=cur->next->next;
		delete tmp;			
		}
		else{
			cur=cur->next;
		}
		 
	}
//	head=dymmy->next
		return head=dymmy->next;	
}
//打印链表
void printList(ListNode* head){
	while(head)//head is not empty
	{
		cout<<head->val<<" ";//pirnt the value of the head
		head=head->next;  //turn to the next address
	}
	cout<<endl;
} 
int main(){
	    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(6);
    head->next->next->next = new ListNode(3);
    head->next->next->next->next = new ListNode(4);
    head->next->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next->next = new ListNode(6);

    int val = 6;
    
	ListNode* newHead= removeElements(head,val);
	printList(newHead);
	return 0; 
}

链表的定义

链表的定义。

刷leetcode的链表的节点都默认定义好了，直接用就行了

没有注意到链表的节点是如何定义的。

C/C++的定义链表节点方式，如下所示：

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

我不定义构造函数行不行，答案是可以的，C++默认生成一个构造函数。

但是这个构造函数不会初始化任何成员变量，下面我来举两个例子：

通过自己定义构造函数初始化节点：

1	ListNode* head = new ListNode(5);

使用默认构造函数初始化节点：

1 2	ListNode* head = new ListNode(); head->val = 5;

果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！

性能分析

再把链表的特性和数组的特性进行一个对比，如图所示：

59.螺旋矩阵II

发表于 2023-04-17 分类于代码随想录

螺旋矩阵 II

vector<vector<int>> res(n,vector<int>(n,0));//用vector定义一个二维数组
int startx=0,starty=0;
int loop=n/2;
int mid=n/2;
int count=1;
int offset=1;//需要控制每一条边遍历的长度，每次循环右边界收缩一位
int i,j;
while(loop--){
	i=startx;
	j=starty;
	
	//第一行
	for(j=starty;j<n-offset;j++){
		res[startx][j]=count++; //行不动，j++
	}
	for(i=startx;i<n-offset;i++){
		res[i][j]=count++; //保持上面的j的值，i++行++
	}
	for(;j>starty;j--){
		res[i][j]=count++;//保持上面的值，j--左边
	}
	for(;i>startx;i--){
		res[i][j]=count++;//保持上面的j的值,i--回到最上面
	}
	startx++;
	starty++;
	offset+=1;
}
//为奇数 单独思考
if(n%2){
	res[mid][mid]=count;
}
return res;

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> res(n,vector<int>(n,0));   //vector<int> a(10,1)  初始化 10个1
    int loop=n/2; //转圈次数
    int count=1;
    int mid=n/2;
    int startx=0,starty=0;
    int i,j;
    int offset=1;
    while(loop--){
        for(j=starty;j<n-offset;j++){
            // res[startx][j]=count++;
            //拆解出来就是,这个不是自增
            res[startx][j]=count;
            count++;


        }
        for(i=startx;i<n-offset;i++){
            res[i][j]=count++;
        }
        for(;j>starty;j--){
            res[i][j]=count++;
        }
        for(;i>startx;i--){
            res[i][j]=count++;
        }
        startx++;
        starty++;
        offset++;
    }
    if(n%2){
        res[mid][mid]=count;
    }
    return res;
    }
};

如何打开ipynb文件

发表于 2023-04-17 分类于 2023

安装 Jupyter Notebook 或 JupyterLab：您可以使用 pip 命令来安装，如下所示：

1	pip install jupyterlab

启动 Jupyter Notebook 或 JupyterLab：在命令行中输入 jupyter notebook 或 jupyter lab 命令，启动 Jupyter Notebook 或 JupyterLab。
打开 .ipynb 文件：在 Jupyter Notebook 或 JupyterLab 的主界面中，找到包含 .ipynb 文件的目录，点击文件名即可打开。
运行和编辑 .ipynb 文件：在打开的 .ipynb 文件中，您可以执行代码、编辑文本、添加图像等内容，并且可以在浏览器中进行交互式的运行和编辑。

滑动窗口904. 水果成篮

发表于 2023-04-16 分类于代码随想录

904. 水果成篮

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int left=0,right=0; 
        int n=fruits.size();    
        int max_fruit=INT_MIN;
        unordered_map<int,int> basket; //这个什么map不懂
        for(int i = 0 ; i<n;i++){ 		//大循环 从0-n-1
            int  fruit_num= fruits[i];  // 记录fruits[i]的数字，当比如fruits[0]=1,fruits[1]=1,那么，basket[1]=1+1=2
            basket[fruit_num]++;
            while(basket.size()>2){//当篮里种类大于2时
                int fruit_num=fruits[left];//记录从fruits[0]=1即basket[1]=2
                basket[fruit_num]--;      //把前面的减掉
                if(basket[fruit_num]==0){ 
                    basket.erase(fruit_num); //当这种水果为0的时候，就删除这种水果  //删除key就行了
                }
                left++;		//继续从当前的位置往右边移动
            }
            max_fruit=max_fruit>i-left+1?max_fruit:i-left+1;
        }
        return max_fruit;
    }
};

1. 简介

map和unordered_map都是c++中可以充当字典（key-value）来用的数据类型，但是其基本实现是不一样的。

2.map

对于map的底层原理，是通过红黑树（一种非严格意义上的平衡二叉树）来实现的，因此map内部所有的数据都是有序的，map的查询、插入、删除操作的时间复杂度都是O(logn)。此外，map的key需要定义operator <，对于一般的数据类型已被系统实现，若是用户自定义的数据类型，则要重新定义该操作符。

map的基本操作如下

#include<iostream>
#include<map>
#include<string>

using namespace std;

int main()
{
	// 构造函数
	map<string, int> dict;
// 插入数据的三种方式
dict.insert(pair<string,int>("apple",2));
dict.insert(map<string, int>::value_type("orange",3));
dict["banana"] = 6;
 
// 判断是否有元素
if(dict.empty())
	cout<<"该字典无元素"<<endl;
else
	cout<<"该字典共有"<<dict.size()<<"个元素"<<endl;
 
// 遍历
map<string, int>::iterator iter;
for(iter=dict.begin();iter!=dict.end();iter++)
	cout<<iter->first<<ends<<iter->second<<endl;
 
// 查找
if((iter=dict.find("banana"))!=dict.end()) //  返回一个迭代器指向键值为key的元素，如果没找到就返回end()
	cout<<"已找到banana,其value为"<<iter->second<<"."<<endl;
else
	cout<<"未找到banana."<<endl;
 
if(dict.count("watermelon")==0) // 返回键值等于key的元素的个数
	cout<<"watermelon不存在"<<endl;
else
	cout<<"watermelon存在"<<endl;

pair<map<string, int>::iterator, map<string, int>::iterator> ret;
ret = dict.equal_range("banana"); // 查找键值等于 key 的元素区间为[start,end)，指示范围的两个迭代器以 pair 返回
cout<<ret.first->first<<ends<<ret.first->second<<endl;
cout<<ret.second->first<<ends<<ret.second->second<<endl;
 
iter = dict.lower_bound("boluo"); // 返回一个迭代器，指向键值>=key的第一个元素。
cout<<iter->first<<endl;
iter = dict.upper_bound("boluo"); // 返回一个迭代器，指向值键值>key的第一个元素。
cout<<iter->first<<endl;
return 0;
}

注意如果定义了map<string,int>这个类型，需要在头文件中包含#include<string>，这是因为默认的string是系统的xstring对象，但是没有定义operator<，从而报错。map用到自定义的类型，一定要定义operator<，具体用法如下。

struct person  
{  
    string name;  
    int age;  
person(string name, int age)  
{  
    this->name =  name;  
    this->age = age;  
}  
  
bool operator < (const person& p) const  
{  
    return this->age < p.age;   
}  
};  
map<person,int> m;

3.unordered_map

unordered_map和map类似，都是存储的key-value的值，可以通过key快速索引到value。不同的是unordered_map不会根据key的大小进行排序，存储时是根据key的hash值判断元素是否相同，即unordered_map内部元素是无序的。unordered_map的底层是一个防冗余的哈希表（开链法避免地址冲突）。unordered_map的key需要定义hash_value函数并且重载operator ==。

哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，时间复杂度为O(1)；而代价仅仅是消耗比较多的内存。哈希表的查询时间虽然是O(1)，但是并不是unordered_map查询时间一定比map短，因为实际情况中还要考虑到数据量，而且unordered_map的hash函数的构造速度也没那么快，所以不能一概而论，应该具体情况具体分析。

unordered_map的基本操作

#include<string>  
#include<iostream>  
#include<unordered_map>
using namespace std;  

int main()
{
	unordered_map<string, int>  dict; // 声明unordered_map对象
// 插入数据的三种方式
dict.insert(pair<string,int>("apple",2));
dict.insert(unordered_map<string, int>::value_type("orange",3));
dict["banana"] = 6;

// 判断是否有元素
if(dict.empty())
	cout<<"该字典无元素"<<endl;
else
	cout<<"该字典共有"<<dict.size()<<"个元素"<<endl;

// 遍历
unordered_map<string, int>::iterator iter;
for(iter=dict.begin();iter!=dict.end();iter++)
	cout<<iter->first<<ends<<iter->second<<endl;

// 查找
if(dict.count("boluo")==0)
	cout<<"can't find boluo!"<<endl;
else
	cout<<"find boluo!"<<endl;

if((iter=dict.find("banana"))!=dict.end())
	cout<<"banana="<<iter->second<<endl;
else
	cout<<"can't find boluo!"<<endl;

return 0;
}

unordered_map用到自定义的类型，需要对key定义hash_value函数并且重载operator ==，具体用法请参考文献3（有空再来补个示例）。

参考文献

C++11 新特性： unordered_map 与 map 的对比

2.C++ STL之map与unordered_map

3.std::unordered_map（提供自己的Hash函数和等价准则）

4.https://blog.csdn.net/jingyi130705008/article/details/82633778

关于最大值最小值的定义

发表于 2023-04-15 分类于代码随想录

最大值

1	int result = INT32_MAX;

最近在刷Leetcode的一些题的时候，发现经常会使用到最大值。
Xcode告诉我这个值在limits.h中
老版本的limit.h可能还会有NC++

1	#define INT_MAX 2147483647

但是现在新的版本已经是

1	#define INT_MAX __INT_MAX__

同样的 INT_MIN 、 LONG_MAX 等等数值都会有相应的定义。

最小值

1	int result = INT32_MIN

INT32_MAX

睡觉万岁