百题 其二 蓝桥杯

刷题

1
2
3
4
5
6
1.注意循环中i，j的使用有没有错误
2.注意dfs中标记数组的清空
3.dfs参数问题，遍历的起始值要注意
4.数组定义的时候要检查[][]，而不是[,]
5.在有些题目中即使它是数字1,0，但是他说的是字符输入也要改成字符，不然可能因为间隔问题输入失败
6.每次每组搜索前一定要重置标记数组memset(vis, 0, sizeof(vis));

1.高精度问题

0R 格式 - 蓝桥云课

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//在一些计算中，题目可能会给出一串远远超出我们运算的数据类型的范围的数据

//对于大浮点数，先把其字符转整型，然后删小数点，转换为一个大整数之间的运算

//注意，前提还是先把字符数组翻转一下，再处理
vector<int>a;//这里的a默认一个大整数做演示
int t=0;//进位数
for(int i=0;i<len;++i){
	a[i]=2*a[i]+t;
	if(a[i]>=10){
		t=a[i]/10;
		a[i]%=10;	
	}
	else{
		t=0;
	}
}
if(t){
	a.push_back(t);
	len++;
}

//以上部分都是运算部分，四舍五入部分要单独写
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//知识点
//对于这道题，c++要好写一些
//首先是万能头文件#include<bits/stdc++>

//查找字符串中的某一字符的位置

string s;
int pos=s.find('.');//里面传字符和字符串都是有效的

//删除字符串中的某一系列字符

s.erase(pos,n);//从pos位置开始删去n个字符
reverse(s.begin(),s.end());//反转字符串

vector<int> a;
a.push_back(n);//动态加，
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>

#define N 10010
using namespace std;

int main(){ 
	string s;
	int n;
	vector<int>a;
	cin>>n>>s;
	reverse(s.begin(),s.end());
	int pos=s.find('.');
	s.erase(pos,1);//经过删除小数点，现在pos的位置是小数后一位 
	int len=s.size();
	for(int i=0;i<len;++i){
		a.push_back(s[i]-'0');
		//cout<<a[i];
	}
	while(n--){
		int t=0;
		for(int i=0;i<len;++i){
			a[i]=2*a[i]+t;
			if(a[i]>=10){
				t=a[i]/10;
				a[i]%=10;
				
			}
			else{
				t=0;
			}
			
		}
		if(t){
			a.push_back(t);
			len++;
		}
	}
	if(a[pos-1]>=5){//这里呀单独地四舍五入
		if(pos==len-1){
			a.push_back(1);
		}
		else{
			a[pos]++;
		}
	}
	for(int i=len-1;i>=pos;--i){
		cout<<a[i];
	}
	return 0;
}

2.关于最大公约数和最小公倍数的关系

0宝石组合 - 蓝桥云课

1
2
3
//这里澄清一点，对于两个数a,b的最小公倍数，我们有：lcm(a,b)=(a*b)/gcd(a,b)

//对于多个的，我们也是类似的：lcm(a,b,c)=lcm(lcm(a,b),c);先计算2个的，再计算3个的

3.关于多个限制条件的dfs问题

0数字接龙 - 蓝桥云课

1
2
3
4
5
6
7
//首先，这种dfs大体分3部分，一部分是满足条件，return；

//另一部分是深搜部分，首先先判断限制条件，不行就continue过滤

//最后一部分就是根据深搜条件搜索

//如果题目有什么限制条件比如防止交叉搜索(看一个点的两个临点有没有都被标记，都被标记了就交叉了)什么的，多观察一下每个点越界的通解
1
2
3
4
5
//string头文件的知识点

string s;
s.empty();//检查字符串是不是空的，当然，c语言可以设置一个函数检查字符串的第一个字符是不是'\0'
to_string(i);//将数字转换为字符，用于拼接
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
//这个代码通过案例数是75%，嗯，还没找出原因
using namespace std;
int n,k;
int a[20][20];
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
int vis[20][20]={0};
string res;
void dfs(int x,int y,int pre,int step,string s){
  if(step==n*n && x==n && y==n){
    if(res.empty()){
      res=s;
    }
    return;
  }
  for(int i=0;i<8;++i){
    int nx=x+dx[i];
    int ny=y+dy[i];
    if(nx<1 || nx>n || ny<1 || ny>n || vis[nx][ny]){
      continue;
    }
    if(i==1 && vis[x-1][y] && vis[x][y+1]) continue;
    else if(i==3 && vis[x+1][y] && vis[x][y+1]) continue;
    else if(i==5 && vis[x+1][y] && vis[x][y-1]) continue;
    else if(i==7 && vis[x-1][y] && vis[x][y-1]) continue;
    if((pre+1==a[nx][ny] && a[nx][ny]<k) || (pre+1==k && a[nx][ny]==0)){
      vis[nx][ny]=1;
      dfs(nx,ny,a[nx][ny],step+1,s+to_string(i));
      if(!res.empty()){
        return;
      }
      vis[nx][ny]=0;
    }
  }
}
int main(){
  cin>>n>>k;
  for(int i=1;i<=n;++i){
    for(int j=1;j<=n;++j){
      cin>>a[i][j];
    }
  }
  string tmp;
  vis[1][1]=1;
  dfs(1,1,0,1,tmp);
  if(!res.empty()) cout<<res;
  else{
    cout<<-1;
  }
  return 0;
}

4.在不同条件下的存在解问题

0飞机降落 - 蓝桥云课

1
2
3
4
5
6
//首先，这题第一思路我是想着搞个结构体，然后多条件的比较，但是没想到突破口

//看了题解后，给我了个新思路，就是，用dfs深搜，来遍历每个情况，找出可行的情况，因为本题只用yes和no，所以找到直接return就好

//深搜dfs还是三步：出口，筛选，(条件)深搜
//这里最关键的就是剪枝操作了现在
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
typedef struct{
  int t;
  int d;
  int l;
}p;
int n;
p pl[20];
int vis[20]={0};
int se;
void dfs(int num,int last){//下一架飞机降落的最早时间
  if(n==num){
    se=1;
    return;
  }
  for(int i=1;i<=n;++i){
    if(vis[i]) continue;
    if(last>pl[i].t+pl[i].d) continue;
    vis[i]=1;
    dfs(num+1,max(pl[i].t,last)+pl[i].l);
    vis[i]=0;
  }
  return;
}
int main()
{
  int t;
  cin>>t;
  while(t--){
  	memset(vis, 0, sizeof(vis));
    cin>>n;
    se=0;
    for(int i=1;i<=n;++i){
      cin>>pl[i].t>>pl[i].d>>pl[i].l;
    }
    dfs(0,0);
    if(se==1){
      cout<<"YES";
    }
    else{
      cout<<"NO";
    }
  }
  return 0;
}

5.dfs环套子岛屿问题

0岛屿个数 - 蓝桥云课

1
2
3
4
5
//首先这道题肯定要用到dfs的

//最开始我想的是标记岛屿，只要最外层的不可进岛屿标记了，里面就不用再搜索了，但是失败了
//有时思考可以往反的方向想想
//可以用标记海水法+扩展地图：即只要一个岛屿的每个面都与标记过的海水相邻，这个岛屿就是有效的岛屿，这样，环内就是没有标记的海水，就不管了，其实反过来也差不多
1
2
3
//对于找岛屿数量的问题，一般是遍历，找到没有被标记过 的岛屿，然后dfs，标记这块岛屿，sum++；

//对于找岛屿面积那就好说，直接在dfs里面每次标记的时候++；
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
int t, m, n;
int s[62][62] = {0};
int sea_vis[62][62] = {0};
int land_vis[62][62] = {0}; 
int sum;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

void mark_sea(int x, int y) {
    if(x < 0 || x > m+1 || y < 0 || y > n+1) return;
    if(sea_vis[x][y] || s[x][y] != 0) return;
    
    sea_vis[x][y] = 1; 
    for(int i=0; i<4; ++i){
        int nx = x + dx[i];
        int ny = y + dy[i];
        mark_sea(nx, ny);
    }
}
void check_land(int x, int y, int& valid) {
    if(x < 1 || x > m || y < 1 || y > n) return;
    if(land_vis[x][y] || s[x][y] != 1) return;
    
    land_vis[x][y] = 1;
    for(int i=0; i<4; ++i){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(sea_vis[nx][ny]) valid = 1;
    }
    for(int i=0; i<4; ++i){
        int nx = x + dx[i];
        int ny = y + dy[i];
        check_land(nx, ny, valid);
    }
}

int main() {
    cin >> t;
    while(t--) {
        memset(s, 0, sizeof(s));
        memset(sea_vis, 0, sizeof(sea_vis));
        memset(land_vis, 0, sizeof(land_vis));
        sum = 0;
        cin >> m >> n;
        for(int i=1; i<=m; ++i){
            string row;
            cin >> row;
            for(int j=1; j<=n; ++j){
                s[i][j] = row[j-1] - '0';
            }
        }
        mark_sea(0, 0); 
        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
                if(s[i][j] == 1 && !land_vis[i][j]){
                    int valid = 0;
                    check_land(i, j, valid);
                    sum += valid; 
                }
            }
        }
        cout << sum << "\n";
    }
    return 0;
}

6.链表的增删改查

好的，下面是用 C 语言实现链表增删改查的分步解释和代码示例：

📌 链表基础结构

c

复制

1
2
3
4
typedef struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域（指向下一个节点）
} Node;

1. 增加节点（增）

头插法（插入到链表头部）

c

复制

1
2
3
4
5
6
Node* insertAtHead(Node* head, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = head; // 新节点指向原头节点
    return newNode;       // 返回新头节点
}

尾插法（插入到链表尾部）

c

复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Node* insertAtTail(Node* head, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (head == NULL) {
        return newNode; // 链表为空时直接返回新节点
    }

    Node* current = head;
    while (current->next != NULL) {
        current = current->next; // 找到最后一个节点
    }
    current->next = newNode;    // 将新节点链接到末尾
    return head;
}

2. 删除节点（删）

删除特定值的节点

c

复制

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
Node* deleteNode(Node* head, int value) {
    if (head == NULL) return NULL;

    // 如果要删除的是头节点
    if (head->data == value) {
        Node* temp = head;
        head = head->next;
        free(temp);
        return head;
    }

    // 查找要删除的节点及其前驱
    Node* prev = head;
    Node* current = head->next;
    while (current != NULL) {
        if (current->data == value) {
            prev->next = current->next;
            free(current);
            break;
        }
        prev = current;
        current = current->next;
    }
    return head;
}

3. 修改节点（改）

c

复制

1
2
3
4
5
6
7
8
9
10
11
void updateNode(Node* head, int oldValue, int newValue) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == oldValue) {
            current->data = newValue; // 直接修改数据域
            return;
        }
        current = current->next;
    }
    printf("未找到值为 %d 的节点\n", oldValue);
}

4. 查找节点（查）

c

复制

1
2
3
4
5
6
7
8
9
10
Node* searchNode(Node* head, int value) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == value) {
            return current; // 返回找到的节点指针
        }
        current = current->next;
    }
    return NULL; // 未找到返回 NULL
}

🛠️ 工具函数：打印链表

c

复制

1
2
3
4
5
6
7
8
void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

📝 完整示例代码

c

复制

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
33
34
35
36
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 插入、删除、修改、查找函数实现（同上）

int main() {
    Node* head = NULL;

    // 插入测试
    head = insertAtHead(head, 3);
    head = insertAtHead(head, 2);
    head = insertAtHead(head, 1);
    head = insertAtTail(head, 4);
    printList(head); // 输出: 1 -> 2 -> 3 -> 4 -> NULL

    // 删除测试
    head = deleteNode(head, 2);
    printList(head); // 输出: 1 -> 3 -> 4 -> NULL

    // 修改测试
    updateNode(head, 3, 99);
    printList(head); // 输出: 1 -> 99 -> 4 -> NULL

    // 查找测试
    Node* found = searchNode(head, 99);
    if (found != NULL) {
        printf("找到值为 99 的节点\n");
    }

    return 0;
}

🔧 关键注意事项

  1. 内存管理：每次 malloc 后必须对应 free，避免内存泄漏。
  2. 边界条件：处理空链表、头节点/尾节点等特殊情况。
  3. 指针操作：修改链表结构时注意正确调整指针指向。
  4. 错误处理：检查 malloc 是否成功（示例中未展示，实际需添加）。

如果需要更详细的某个操作解释或更多变种操作（如中间插入、按位置删除），可以告诉我！ 😊

好的！以下是链表的 中间插入（在指定位置或节点后插入） 和 按位置删除 的详细实现和解释：

1. 中间插入节点（指定位置插入）

假设链表的索引从 0 开始，例如要在位置 pos 插入节点。

c

复制

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
// 在链表的第 pos 个位置插入节点（从 0 开始计数）
Node* insertAtPosition(Node* head, int value, int pos) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    // 如果插入到头部（pos=0）
    if (pos == 0) {
        newNode->next = head;
        return newNode; // 返回新头节点
    }

    // 找到插入位置的前驱节点
    Node* current = head;
    for (int i = 0; i < pos - 1 && current != NULL; i++) {
        current = current->next;
    }

    // 如果位置无效（例如链表长度不足）
    if (current == NULL) {
        printf("插入位置无效！\n");
        free(newNode); // 释放未使用的节点内存
        return head;
    }

    // 插入新节点
    newNode->next = current->next;
    current->next = newNode;
    return head;
}

2. 按位置删除节点

删除链表中指定位置 pos 的节点。

c

复制

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
33
Node* deleteAtPosition(Node* head, int pos) {
    if (head == NULL) {
        printf("链表为空！\n");
        return NULL;
    }

    // 删除头节点（pos=0）
    if (pos == 0) {
        Node* temp = head;
        head = head->next;
        free(temp);
        return head;
    }

    // 找到要删除节点的前驱
    Node* prev = head;
    Node* current = head;
    for (int i = 0; i < pos && current != NULL; i++) {
        prev = current;
        current = current->next;
    }

    // 如果位置无效
    if (current == NULL) {
        printf("删除位置无效！\n");
        return head;
    }

    // 调整指针并释放内存
    prev->next = current->next;
    free(current);
    return head;
}

3. 在指定节点后插入（另一种中间插入方式）

假设已知某个节点 targetNode，在其后插入新节点。

c

复制

1
2
3
4
5
6
7
8
9
10
11
void insertAfterNode(Node* targetNode, int value) {
    if (targetNode == NULL) {
        printf("目标节点不存在！\n");
        return;
    }

    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = targetNode->next;
    targetNode->next = newNode;
}

🛠️ 使用示例

c

复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main() {
    Node* head = NULL;

    // 创建初始链表: 1 -> 2 -> 3
    head = insertAtTail(head, 1);
    head = insertAtTail(head, 2);
    head = insertAtTail(head, 3);
    printList(head); // 输出: 1 -> 2 -> 3 -> NULL

    // 在位置 1 插入 99
    head = insertAtPosition(head, 99, 1);
    printList(head); // 输出: 1 -> 99 -> 2 -> 3 -> NULL

    // 在节点值为 2 的节点后插入 88
    Node* target = searchNode(head, 2);
    insertAfterNode(target, 88);
    printList(head); // 输出: 1 -> 99 -> 2 -> 88 -> 3 -> NULL

    // 删除位置 2 的节点（值为 2）
    head = deleteAtPosition(head, 2);
    printList(head); // 输出: 1 -> 99 -> 88 -> 3 -> NULL

    return 0;
}

🔧 关键点总结

  1. 中间插入：
    • 需要遍历链表找到插入位置的前驱节点。
    • 注意处理边界条件（如插入到头部或尾部）。
    • 确保插入位置的有效性（避免越界）。
  2. 按位置删除：
    • 同样需要遍历找到前驱节点。
    • 释放内存前务必调整指针，防止链表断裂。
  3. 时间复杂度：
    • 插入和删除操作的时间复杂度为 **O(n)**（需要遍历链表）。
    • 如果频繁按位置操作，可以考虑使用双向链表优化。

如果有其他具体场景或细节需要补充，请告诉我！ 😊