leetcode剑指offer5
剑指 Offer 24. 反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof
双指针方法：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *pre,*cur,*mid;
cur=head;
pre=NULL;
if(head==NULL)return head;
while(cur!=NULL){
mid=cur->next;
cur->next=pre;
pre=cur;
cur=mid;
}
return pre;
}
};
递归：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==NULL||head->next==NULL)return head;
ListNode* node=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return node;
}
};
使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 node .
此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转
当递归函数全部出栈后，链表反转完成。
作者：huwt
链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/fan-zhuan-lian-biao-yi-dong-de-shuang-zhi-zhen-jia/
双指针2：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==NULL)return head;
ListNode *cur=head,*t;
while(head->next!=NULL){
t=head->next->next;
head->next->next=cur;
cur=head->next;
head->next=t;
}
return cur;
}
};
剑指 Offer 25. 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
非递归：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *ans,*p;
ans= new ListNode(0);
p=ans;
while(l1!=NULL&&l2!=NULL){
if(l1->val<l2->val){
p->next=l1;
l1=l1->next;
}else{
p->next=l2;
l2=l2->next;
}
p=p->next;
}
if(l1!=NULL){
p->next=l1;
}
if(l2!=NULL){
p->next=l2;
}
return ans->next;
}
};
递归：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==NULL)return l2;
if(l2==NULL)return l1;
ListNode *ans;
if(l1->val < l2->val){
ans=l1;
ans->next=mergeTwoLists(l1->next,l2);
}else{
ans=l2;
ans->next=mergeTwoLists(l1,l2->next);
}
return ans;
}
};
- 总是喜欢给head单独拿出来判断，事实上返回head->next即可
- 链表题似乎都有递归写法
剑指 Offer 26. 树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/ \
4 5
/
1 2
给定的树 B：
4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
递归：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSubStructureContinue(TreeNode* A, TreeNode* B){
bool isSub=0;
if(B==NULL)return 1;
if(A==NULL)return 0;
if(B->val==A->val){
isSub=isSubStructureContinue(A->left, B->left)&isSubStructureContinue(A->right,B->right);
}
return isSub;
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
bool isSub=0;
if(B==NULL||A==NULL)return false;
if(B->val==A->val){
isSub=isSubStructureContinue(A,B);
}
if(!isSub){
return isSubStructure(A->left, B) | isSubStructure(A->right,B);
}
return 1;
}
};
时间复杂度O(MN)
剑指 Offer 27. 二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出：
4
/ \
7 2
/ \ / \
9 6 3 1
递归：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(root==NULL)return root;
TreeNode *t;
t = root->left;
root->left = mirrorTree(root->right);
root->right = mirrorTree(t);
return root;
}
};
- 用 nullptr 比 NULL 快很多，或许
- 有用栈写的，就是把所有点存进栈，然后交换其左右节点。
剑指 Offer 28. 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
递归：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool recur(TreeNode *t1, TreeNode* t2){
if(t1==nullptr&&t2==nullptr)return 1;
if(t1==nullptr||t2==nullptr)return 0;
if(t1->val!=t2->val)return 0;
return recur(t1->left,t2->right)&recur(t1->right,t2->left);
}
bool isSymmetric(TreeNode* root) {
if(root==nullptr) return 1;
return recur(root->left,root->right);
}
};
- 还有层序遍历解法，每加入一层，判断是否对称
层序遍历：
class Solution {
int INF = 0x3f3f3f3f;
TreeNode emptyNode = new TreeNode(INF);
boolean isSymmetric(TreeNode root) {
if (root == null) return true;
Deque<TreeNode> d = new ArrayDeque<>();
d.add(root);
while (!d.isEmpty()) {
// 每次循环都将下一层拓展完并存到「队列」中
// 同时将该层节点值依次存入到「临时列表」中
int size = d.size();
List<Integer> list = new ArrayList<>();
while (size-- > 0) {
TreeNode poll = d.pollFirst();
if (!poll.equals(emptyNode)) {
d.addLast(poll.left != null ? poll.left : emptyNode);
d.addLast(poll.right != null ? poll.right : emptyNode);
}
list.add(poll.val);
}
// 每一层拓展完后，检查一下存放当前层的该层是否符合「对称」要求
if (!check(list)) return false;
}
return true;
}
// 使用「双指针」检查某层是否符合「对称」要求
boolean check(List<Integer> list) {
int l = 0, r = list.size() - 1;
while (l < r) {
if (!list.get(l).equals(list.get(r))) return false;
l++;
r--;
}
return true;
}
}
作者：AC_OIer
链接：https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/solution/gong-shui-san-xie-cong-ju-bu-he-zheng-ti-02qk/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
剑指 Offer 29. 顺时针打印矩阵（模拟）
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
模拟：
class Solution {
public:
int m,n;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
bool isOK(int x,int y,vector<vector<bool>>& vis){
return x>=0&&x<m&&y>=0&&y<n&&(!vis[x][y]);
}
void squra(int x,int y,int dir,int dep, vector<int> &ans, vector<vector<int>>& matrix, vector<vector<bool>>&vis){
ans[dep]=matrix[x][y];
vis[x][y]=1;
if(dep==m*n-1) return;
while(true){
int nx=x+dx[dir];
int ny=y+dy[dir];
if(isOK(nx,ny,vis)){
squra(nx,ny,dir,dep+1,ans,matrix,vis);
break;
}
dir=(dir+1)%4;
}
}
vector<int> spiralOrder(vector<vector<int>>& matrix) {
m=matrix.size();
vector<int> temp;
if(m==0)return temp;
n=matrix[0].size();
vector<vector<bool>> vis(m,vector<bool>(n,0));
vector<int> ans(m*n);
squra(0,0,0,0,ans,matrix,vis);
return ans;
}
};
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
res = []
while matrix:
res += matrix.pop(0)
matrix = list(zip(*matrix))[::-1]
return res
python感觉挺好用的，可惜用的不熟
版权声明：本文为Wuuuuuu2019原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。