力扣24 两两交换链表中的值
第一步，发现头结点需要改变 先创建一个虚拟头结点，称为X 在真实头结点A 之前,A的下一个节点称为B节点
对于虚拟头结点来说，第一轮需要交换的是 这个虚拟头结点的后节点一届后后节点，即需要交换A 和 B
第二步，先将当前节点的next指向后后节点 (将X的next指向B)
第三步，将后节点的next指向后后节点的next(将A的next 指向 B的next)
第四步，将后后节点的next指向后节点(将B 的next指向A)
第一轮交换完毕，想要进行下一轮交换就需要改变虚拟头结点的位置，然后重复操作。(将A视为虚拟节点，开始对接下来的部分进行交换)
/**
* 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* swapPairs(ListNode* head) {
if(head == NULL || head -> next == NULL){
return head;
}
ListNode *p = new ListNode(0, head);//创建一个虚拟指针，其指针域指向头结点
ListNode *now = p;//记录，当前链表到哪里为止已经交换过了，也就是新的虚拟指针的位置
while(now -> next != NULL && now -> next -> next != NULL){
ListNode *l = now -> next;
ListNode *r = now -> next -> next;
//接下来进行交换操作
now -> next = r;
l -> next = r -> next;
r -> next = l;
now = l;
}
return p->next;
}
};
递归解法
首先要了解swapPairs函数的作用就是
将传入的节点和下一个节点进行交换，然后返回交换后的头结点
进行交换， 交换两个链表中的节点需要三个步骤
（这里的A 指代需要交换的第一个节点 ，B指代需要交换的另一个节点 C指代还未发生交换的节点）
A B C 初始的状态是 A的next指向B，B的next指向C
交换步骤
1：用指针记录B 的位置(因为一开始题目只会给A的位置，要确定B的位置才能进行交换)
2：将 A的next 指向C
3：将B的next指向A
/**
* 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* swapPairs(ListNode* head) {
if(head == NULL || head -> next == NULL){
return head;
}
//第一步首先确定B的位置，让一个指针指向B
ListNode *B = head->next;
//第二步，让A(head)的next指向 C
head -> next = swapPairs(B -> next);
//最后一步把B的next指向A
B -> next = head;
//交换完以后B变成了新的头结点，故返回B的值
return B;
}
};
判断一个数字是否是回文串
int func(int a){
int temp = a;//temp用来保存a原来的值
int r = 0;//r来存储翻转后的数字
while(a){
r = r * 10 + a % 10;
a = a / 10;
}
return r == temp;//如果翻转后的数字与原数字相等就表示是回文
}
Sine之舞
#include<iostream>
using namespace std;
int A(int i, int n){
if(i == n){
cout << "sin(" << i << ")";
}
else{
if(i % 2 == 0) cout << "sin(" << i << "+";
else cout << "sin(" << i << "-";
A(i + 1, n);
cout << ")";
}
}
int S(int i, int n){//S(i, n)的作用是打印出 Ai + n - i + 1
if(n == 1){
A(1, 1);
cout << "+" << i;
}
else{
cout << "(";
S(i + 1, n - 1);
cout << ")";
A(1, n);
cout << "+" << i;
}
}
int main()
{
int n;
cin >> n;
S(1, n);
return 0;
}
回形取数(经典dfs)
样例输入
3 3
1 2 3
4 5 6
7 8 9
样例输出
1 4 7 8 9 6 3 2 5
#include<iostream>
using namespace std;
const int maxn = 201;
int w[maxn][maxn];
int f[maxn][maxn] = {0};
int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
int n, m;
bool check(int x, int y){//检查这个点是否越界以及是否走过，如果没有越界并且没有走过就输出 1
return (x >= 0 && y >= 0 && x < n && y < m && f[x][y] != 1);
}
void dfs(int x, int y, int i, int j){//x,y为当前位置 i,j为当前方向
if(f[x][y] == 0 && x == 0 && y == 0) cout << w[x][y];//先输出第一个数，把 空格+数 变为一组来输出，这样结尾就不会有多余的空格
else if(f[x][y] == 0) cout << " " << w[x][y];
f[x][y] = 1;//搜到了x,y点，将其标记转为1表示搜过了
int xx = x + i;//当前方向的下一个点的横坐标
int yy = y + j;//当前方向的下一个点的纵坐标
if(check(xx, yy)) dfs(xx, yy, i, j);//检查下一个点是否能走，如果能走的话方向不变，继续向下搜索
else{//说明下一个方向不能走了，需要换一个方向
for(int i = 0; i < 4; i++){//用for循环来挑选下一个方向，实际上当一个方向走到头后，能走的方向也只剩一个了
int dx = x + dir[i][0];//尝试向新方向走向下一个点
int dy = y + dir[i][1];
if(check(dx, dy)){//如果朝这个方向往下走是可以的
dfs(dx, dy, dir[i][0], dir[i][1]);//就 以这个点为起点 以此时的方向进行搜索
break;//不需要在找其他方向了 这一行不要也可以，因为满足条件的方向只会有一个
}
}
}
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> w[i][j];
}
}
dfs(0, 0, 1, 0);
return 0;
}
危险系数
样例输入
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
样例输出
2
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 1001;
vector<int> v[maxn];
int f[maxn] = {0};//用于记录是否被访问
int count = 0;//用于记录关键点的个数
int success_load = 0;//用于记录能够成功到达终点的路径的条数
int pass_by[maxn];//用于记录全部成功路径路过某点的次数
int n, m;//点数和通道数
int e, c;//起点和终点
void dfs(int now){//现在now点
f[now] = 1;
if(now == c){//如果到达了终点
success_load++;
for(int i = 1; i <= n; i++){
if(f[i] == 1) pass_by[i]++;
}
f[now] = 0;//一条路径成功到达后，要清除终点的标记，否则其他路径找不到终点
return ;
}
for(int i = 0; i < v[now].size(); i++){//如果now点不是终点，那么就要从now点所连接的点开始搜索
if(f[ v[now][i] ] == 0){//因为要分别对now的连通点进行搜索，这里就表示是否搜索过第i个连通点，标记数组为0说明没有搜过
dfs(v[now][i]);
}
}
f[now] = 0;
}
int main(){
cin >> n >> m;
int a, b;
for(int i = 0; i < m; i++){
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
cin >> e >> c;
dfs(e);//从起点开始搜索
for(int i = 1; i <= n; i++){
if(pass_by[i] == success_load && i != e && i != c){
count++;
}
}
if(success_load == 0) cout << "-1";
else cout << count;
return 0;
}