递归、搜索和回溯算法练习day2
一、24. 两两交换链表中的节点
1.题目简介
24. 两两交换链表中的节点
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
2.解题思路
递归思路:
先处理第二个节点之后的节点,再将前两个节点进行交换,最后连接后面处理好的节点
迭代思路:
双指针法(三指针法)
两个指针进行交换,第三个指针进行遍历,直到将链表遍历结束
3.代码
递归:
/**
* 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 == nullptr || head -> next == nullptr) return head;
ListNode* t = head -> next -> next;
ListNode* next = head -> next;
next -> next = head;
head -> next = swapPairs(t);
return next;
}
};
迭代:
/**
* 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 == nullptr || head -> next == nullptr) return head;
ListNode* prev = head,* cur = head -> next,* next = cur -> next;
ListNode* newhead = cur;
int flag = 1;//假设链表的节点个数为偶数
while(next)
{
cur -> next = prev;
if(next -> next)//链表的节点个数是偶数个或者未到达链表结尾
{
prev -> next = next -> next;
cur = next -> next;
prev = next;
next = cur -> next;
}
else//如果链表的结点个数是奇数个
{
flag = 0;
prev -> next = next;
next = next -> next;
}
}
if(flag)
{
cur -> next = prev;
prev -> next = next;
}
return newhead;
}
};
4.运行结果
递归:
迭代:
二、50. Pow(x, n)
1.题目简介
2.解题思路
思路:先计算x的n / 2次,再相乘(注意n的正负性和奇偶性)
因为可能会出现n是INT_MIN的情况,因为-INT_MIN会导致溢出,所以我们将n的类型改为long long。
3.代码
class Solution {
public:
double myPow(double x, int n) {
return n < 0 ? 1 / func(x, -(long long)n) : func(x, n);
}
double func(double x, long long n)
{
if(n == 0) return 1.0;
double t = myPow(x, n / 2);
double ret = t * t;
if(n % 2) ret *= x;
return ret;
}
};
4.运行结果
三、2331. 计算布尔二叉树的值
1.题目简介
2.解题思路
先计算孩子节点,再根据孩子节点的布尔值和自身所表示的运算符来计算自身的布尔值
3.代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool evaluateTree(TreeNode* root) {
if(root -> val == 0) return false;
if(root -> val == 1) return true;
if(root -> val == 2) return evaluateTree(root -> left) || evaluateTree(root -> right);
return evaluateTree(root -> left) && evaluateTree(root -> right);
}
};
4.运行结果
总结
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfjjcck
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01