睡觉万岁

0%

发表于 更新于 分类于

209. 长度最小的子数组

暴力o(n^2)超时呵呵呵，不是能做出来就好了吗啊吧啊吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum;
        int min=100000;
        int count;
        for(int i=0;i<nums.size();i++){
            sum=0;
                for(int j = i;j<nums.size();j++){
                    sum+=nums[j];
                    if(sum>=target){
                        count=j-i+1;
                        min=min<count?min:count;
                        break;
                    }
                }
                if(min>nums.size()) min=0;
        }
        return min;
    }
};

滑动窗口

思路是先让

sum+nums[j]

当sum>=target的时候

算出子数组长度subL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

```while```循环```nums[i++]```一直减到它```<target```退出```while```

用result记录min的subL

然后再次大循环从nums[j+1]





```c
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
    int i=0;
    int subL=0;
    int sum=0;
    int result=INT_MAX;
    for(int j =0;j<nums.size();j++){
        sum+=nums[j];
        while(sum>=target){
            subL=j-i+1;
            sum-=nums[i];
            result=min(result,subL);
            i++;
        }
    }
    return result==INT_MAX ? 0 : result;
 
    }
};

如何理解

1
return result==INT_MAX ? 0 : result;

当result==INT_MAX时候

是 返回0

否 返回result

如何理解

1
result = result < subLength ? result : subLength;

当result<subL的时候

是 返回result

否 返回subL

发表于 分类于

977. 有序数组的平方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
    vector<int> result(nums.size(),0);
    int k=nums.size()-1;
    for(int i=0,j=nums.size()-1;i<=j;){  // 注意i<=j
        if(nums[i]*nums[i]<nums[j]*nums[j]){
            result[k--]=nums[j]*nums[j];
            j--;
        }
        else if(nums[i]*nums[i]>=nums[j]*nums[j]){
            result[k--]=nums[i]*nums[i];
            i++;

        }
    }
    return result;
    }
};

发表于 分类于

844. 比较含退格的字符串

我没看懂怎么用双指针，用栈吧（阿巴阿巴阿巴，傻子流口水）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        return build(S) == build(T);
    }

    string build(string str) {
        string ret;
        for (char ch : str) {
            if (ch != '#') {
                ret.push_back(ch);
            } else if (!ret.empty()) {
                ret.pop_back();
            }
        }
        return ret;
    }
};

发表于 分类于

283. 移动零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void moveZeroes(int* nums, int numsSize){
        int target=0;
        int slow=0;
        int fast;
        for(fast=0;fast<numsSize;fast++){
            if(nums[fast]!=target){
                nums[slow]=nums[fast];
                slow++;
            }
        }
        int i;
        for(i=slow;i<numsSize;i++){
            nums[i]=target;
            
        }
        
        
        return i;
}

在后面一个for那边卡了，不敢写（因为用了两个for）时间复杂度大不敢了

发表于 分类于

27. 移除元素

1
2
3
4
5
6
7
8
9
10
11
int removeElement(int* nums, int numsSize, int val){
        int slow=0;
        for( int fast=0;fast<numsSize;fast++){
            if(nums[fast]!=val){
                nums[slow]=nums[fast];
                slow++;
            }
   
        }
    return slow;
}

反而比暴力慢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int removeElement(int* nums, int numsSize, int val){
        int j=0;
        int nums2[100];
        int i;
        for( i =0;i<numsSize;i++){
            if (nums[i]==val){
                for(int j = i + 1;j < numsSize;j++){
                    nums[j-1]=nums[j];
                } 
                         numsSize--;
            i--;
            }
   
        }
        return numsSize;
}

发表于 分类于

IMG_0057

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

  • 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
  • 慢指针：指向更新 新数组下标的位置
1
2
3
4
5
6
7
8
9
10
slow=0;
val=3
nums[0,1,2,3,3,0,4,2];
for(int fast=0;fast<size;fast++){
    if(nums[fast]!=val){		 //当【fast】的不等于val的值的时候
    	nums[slow]=nums[fast];    // slow是下标  fast是数组元素
        slow++;
    }
}
	return slow;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* 相向双指针方法，基于元素顺序可以改变的题目描述改变了元素相对位置，确保了移动最少元素
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int leftIndex = 0;
        int rightIndex = nums.size() - 1;
        while (leftIndex <= rightIndex) {
            // 找左边等于val的元素
            while (leftIndex <= rightIndex && nums[leftIndex] == val){
                ++leftIndex;
            }
            // 找右边不等于val的元素
            while (leftIndex <= rightIndex && nums[rightIndex] != val) {
                -- rightIndex;
            }
            // 将右边不等于val的元素覆盖左边等于val的元素
            if (leftIndex < rightIndex) {
                nums[leftIndex++] = nums[rightIndex--];
            }
        }
        return leftIndex;   // leftIndex一定指向了最终数组末尾的下一个元素
    }
};

发表于 分类于

一、直接删除法

（1）使用 vector库函数“erase”删除，使用erase函数后容器size自动-1
1
2
3
4
5
6
7
8
9
10
int removeElement(vector<int>& nums, int detarget) {
       for (int i = 0; i < nums.size(); i++){
           if(nums[i] == detarget){
               nums.erase(nums.begin() + i); 
               i--; //由于容器size-1，还按原来的i的话相当于自动右移一位而漏掉一个元素
           }
       }
       return nums.size();      
   }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
using namespace std;
int removeElement(vector<int>& nums, int detarget) {
	for (int i = 0; i < nums.size(); i++){
			if(nums[i] == detarget){
			nums.erase(nums.begin() + i);
			i--; //由于容器size-1，还按原``	来的i的话相当于自动右移一位而漏掉一个元素
			}
	}
	return nums.size();
}

int main() {
    vector<int> nums ;
    nums.push_back(3);
	nums.push_back(2);
	nums.push_back(2);
	nums.push_back(3);
    int detarget = 3;
    int len = removeElement(nums, detarget);
    cout << "After removing " << detarget << ", the length of nums is " << len << endl;
    for(int i = 0; i < len; i++){
        cout << nums[i] << " ";
    }
    cout << endl;
    return 0;
}
（2）使用 vector库函数“swap和pop_back()”,由于pop_back删除的是最后一个元素，所以先移位再删除
1
2
3
4
5
6
7
8
9
10
int removeElement(vector<int>& nums, int detarget) {
        for (int i = 0; i < nums.size(); i++){
            if(nums[i] == detarget){   
                swap(nums[i], nums[nums.size() - 1]); //将要删除的元素交换到最后
                nums.pop_back(); 
                i--; //这里的i--与上面的作用一样
            }
        }
        return nums.size();      
    }

二、遍历覆盖法

如果从数组的角度理解，因为数组存储的内容在地址上是连续的，要移除目标元素，就没有库函数可以使用，那就需要对其他元素进行处理，进行覆盖和前移，比较暴力的思路是发现目标元素后，将后面的所有元素都前移覆盖原来的元素，这种方法需要两个for循环，时间复杂度为O(n2),这里不详细讲这种写法。
从覆盖的角度思考，我们可以通过一次遍历把非目标元素全部前移覆盖到前半部片

1
2
3
4
5
6
int removeElement(vector<int>& nums, int detarget) {
         int size = 0;
        for(auto x : nums)  //遍历全部元素
            if(x != detarget)  nums[size++] = x;//如果不是要删除的目标元素，把它前移覆盖到前半部分
        return size;  //这里的size即为删除后的容量大小
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//暴力
int removeElement(int* nums, int numsSize, int val){
        int j=0;
        int nums2[100];
        int i;
        for( i =0;i<numsSize;i++){
            if (nums[i]==val){
                for(int j = i + 1;j < numsSize;j++){
                    nums[j-1]=nums[j];
                } 
            numsSize--;
            i--;
            }
   
        }
        return numsSize;
}

三、相向双指针法

(1)使用vector库函数swap，通过有两个指针和一个for循环将所有元素分为两个部分,

左端的指针（快指针）控制前半部分的边界，swap后前半部分全部是要保留的元素
右端的指针（慢指针）控制后半部分的边界，swap后后半部分全部是要删除的元素

//时间复杂度：O（n)
//空间复杂度：O（1）

1
2
3
4
5
6
7
8
9
10
11
12


int removeElement(vector<int>& nums, int detarget) {
       int j = nums.size() - 1; 
       for (int i = 0; i <= j; i++) {
           if (nums[i] == detarget) {  
               swap(nums[i--], nums[j--]); //注意这里的i--，j--，代表先交换再移动，而不是先移动再交换
               //i--的原因：如果发生交换的两个元素全是要删除的目标元素，这样不会把换过来的漏删
           }
       }
       return j + 1; //j+1就是删除完的size大小
   }

ps：上面几种方法只给出了核心算法的代码，具体问题做出相应改动即可

发表于 分类于
drawing

2.打卡1681285904280

3.洛谷先mark一下之前的题目数量，vjudge就不去刷了。

1681286036053

Conclusion:一天2h打题目太少了

4.数学放缓(等张宇来了过第三遍一二章（发疯）理出思维导图)

改良计划:

①下午没课就看数学，看到5.吃饭，吃完回来继续数学，到7.30。

②看英语文章1h（尝试了一下，有难度的文章1h够呛）

③刷题到11.00

④回去床上背单词（当然课上不困最好课上干掉）

⑤最近沉迷策门有所懈怠（双手合十）（低头认错）

发表于 分类于

memset简介
memset是一个初始化函数，作用是将某一块内存中的全部设置为指定的值。

void *memset(void *s, int c, size_t n);

s指向要填充的内存块。
c是要被设置的值。
n是要被设置该值的字符数。
返回类型是一个指向存储区s的指针。

需要说明的几个地方

一、不能任意赋值

memset函数是按照字节对内存块进行初始化，所以不能用它将int数组出初始化为0和-1之外的其他值（除非该值高字节和低字节相同）。
其实c的实际范围应该在0~255，因为memset函数只能取c的后八位给所输入范围的每个字节。也就是说无论c多大只有后八位二进制是有效的。

对于int a[4];
memset(a, -1, sizeof(a)) 与 memset(a, 511, sizeof(a)) 所赋值的结果一样都为-1：
因为 -1 的二进制码为（11111111 11111111 11111111 11111111）；511 的二进制码为（00000000 00000000 00000001 11111111）；
后八位均为（11111111），所以数组中的每个字节都被赋值为（11111111）。
注意int占四个字节，例如a[0]的四个字节都被赋值为（11111111），那么a[0]（11111111 11111111 11111111 11111111），即a[0] = -1。

二、注意所要赋值的数组的元素类型

先来看两个例子：
例一：对char类型的数组a初始化，设置元素全为’1’

main(){
1
2
3
4
5
6
7
    char a[4];
    memset(a,'1',4);
    for(int i=0; i<4; i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

例二：对int类型的数组a初始化，设置元素值全为1

main(){
1
2
3
4
5
6
7
    int a[4];
    memset(a,1,sizeof(a));
    for(int i=0; i<4; i++){
        cout<<a[i]<<" ";
    }
    return 0;
}
1、首先要说明的第一点

 对于第二个程序，数组a是整型的，一般int所占内存空间为4个字节，所以在使用memset赋值时，下面的语句是错误的：

1
2
int a[4];
memset(a,1,4);

由于memset函数是以字节为单位进行赋值的，所以上述代码是为数组a的前4个字节进行赋值，那么所得到的执行结果就只能是：

正确的memset语句应为：

1
2
memset(a,1,16); //int所占内存为4字节的情况
memset(a,1,sizeof(a));

至于为什么不是预期得到的1，将在下面的第二点进行说明。

当然，不同的机器上int的大小可能不同，所以最好用sizeof()函数。

2、为什么第一个程序可以正确赋值1而第二个不可以？

这就又回到了刚刚说的第一个问题，memset函数中只能取c的后八位赋给每个字节。

第一个程序中，数组a是字符型的，字符型占据的内存大小就是1Byte，而memset函数也是以字节为单位进行赋值的，所以输出正确。
第二个程序中，数组a是整型的，整型占据的内存大小为4Byte，而memset函数还是按照字节为单位进行赋值，将1（00000001）赋给每一个字节。那么对于a[0]来说，其值为(00000001 00000001 00000001 00000001），即十进制的16843009。

关于所要赋值的字符数的写法
先来看一个示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

void fun1(int a[]){
    memset(a,-1,sizeof(a)); 
}

int main(){
    int a[6];
    fun1(a);
    for(int i=0; i<6; i++){
        cout<<a[i]<<" ";
    }
    return 0;
}
当数组作为参数传递时，其传递的实际上是一个指针，这个指针指向数组的首地址，如果用sizeof(a)函数得到的只是指针的长度，而不是数组的长度。

解决方案：
在函数中加入数组长度参数，在传递前先获取数组长度，然后将数组长度作为参数传递进去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

void fun1(int a[], int len){
    memset(a,-1,len); 
}

int main(){
    int a[6];
    int len = sizeof(a);
    fun1(a,len);
    for(int i=0; i<6; i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

具体用法实例
初始化数组

1
2
3
4
5
6
7
8
9
10
11
char str[100];
memset(str,0,100);
清空结构体类型的变量
typedef struct Stu{
	char name[20];
	int cno;
}Stu;
Stu stu1; 
memset(&stu1, 0 ,sizeof(Stu));
Stu stu2[10]; //数组
memset(stu2, 0, sizeof(Stu)*10);

此外，如果结构体中有数组的话还是需要对数组单独进行初始化处理的。