java&python版剑指offer(八) java&python版剑指offer(八)

本文按照牛客网的顺序，牛客网剑指offer刷题网址：https://www.nowcoder.com/ta/coding-interviews
本篇涉及的题目有：
1、链表中环的入口节点
2、删除链表中的重复结点
3、二叉树的下一个结点
4、对称的二叉树
5、滑动窗口的最大值
1、链表中环的入口节点问题描述
一个链表中包含环，请找出该链表的环的入口结点。
思路解析
定义两个指针，从头指针开始往后跑。快的指针一次跑两步，慢的指针一次跑一步。如果链表中存在环，且环中假设有n个节点，那么当两个指针相遇时，快的指针刚好比慢的指针多走了环中节点的个数，即n步。从另一个角度想，快的指针比慢的指针多走了慢的指针走过的步数，也是n步。如下图：

文章图片
上图中，环有5个节点，fast和slow从头节点开始，经过5步相遇。可以看到，如果此时fast指针再从头节点开始走的话，会最终在环的第一个节点和slow指针相遇。大家可以用数学公式证明一下，这里就不做过多的叙述啦。
代码实现
java

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ public class Solution {public ListNode EntryNodeOfLoop(ListNode pHead) { if(pHead==null || pHead.next == null || pHead.next.next == null) return null; ListNode fast = pHead.next.next; ListNode slow = pHead.next; while(fast != slow){ if(fast.next==null || fast.next.next==null) return null; fast = fast.next.next; slow = slow.next; } fast = pHead; while(fast != slow){ fast = fast.next; slow = slow.next; } return fast; } }

python

# -*- coding:utf-8 -*- # class ListNode: #def __init__(self, x): #self.val = x #self.next = None class Solution: def EntryNodeOfLoop(self, pHead): if pHead==None or pHead.next==None or pHead.next.next==None: return None low=pHead.next fast=pHead.next.next while low!=fast: if fast.next==None or fast.next.next==None: return None low=low.next fast=fast.next.next fast=pHead while low!=fast: low=low.next fast=fast.next return fast

2、删除链表中的重复结点问题描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
思路解析
定义以下几个元素：
p:用于遍历链表；
q：用于记录当前的链表中剩余的元素最后一个；
cur：当前链表节点的值，用于判断时候有重复结点；
flag：记录当前这个值是否有重复结点。
代码实现
java

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ public class Solution { public ListNode deleteDuplication(ListNode pHead) { if(pHead == null) return null; ListNode dummy = new ListNode(-1); dummy.next = pHead; ListNode q = dummy; ListNode p = pHead; int cur = p.val; boolean flag = true; while(p!=null){ while(p.next != null && p.next.val == cur){ p = p.next; flag = false; } if(flag){ q.next = p; q = p; } p = p.next; if(p==null) break; cur = p.val; flag = true; } q.next = null; return dummy.next; } }

python

# -*- coding:utf-8 -*- # class ListNode: #def __init__(self, x): #self.val = x #self.next = None class Solution: def deleteDuplication(self, pHead): # write code here if not pHead: return None dummy = ListNode(-1) dummy.next = pHead q = dummy p = pHead while p and p.next: if p.next and p.next.val != p.val: q.next = p q = p p = p.next elif p.next and p.next.val == p.val: while p.next and p.next.val==p.val: p = p.next p = p.next q.next = p return dummy.next

3、二叉树的下一个结点问题描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路解析
1、如果这个节点有右子树，那么找到右子树中的最左侧的一个节点并返回
2、如果这个节点没有右子树且是父节点的左子树，直接返回父节点
3、如果这个节点没有右子树且是父节点的右子树，那么我们往上找父节点，找到一个父节点满足：父节点是父节点的左子树的节点
4、返回None
代码实现
java

/* public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) { this.val = val; } } */ public class Solution { public TreeLinkNode GetNext(TreeLinkNode pNode) { if(pNode==null) return null; if(pNode.right!=null){ TreeLinkNode p = pNode.right; while(p.left!=null) p = p.left; return p; } else if(pNode.next!=null){ if(pNode.next.left == pNode) return pNode.next; else{ TreeLinkNode p = pNode; while(p.next!=null){ if(p.next.left == p){ return p.next; } p = p.next; } return null; } } else return null; } }

python

# -*- coding:utf-8 -*- # class TreeLinkNode: #def __init__(self, x): #self.val = x #self.left = None #self.right = None #self.next = None class Solution: def GetNext(self, pNode): # write code here # 判断是否为空 if not pNode: return None if pNode.right: res = pNode.right while res.left: res = res.left return res while pNode.next: tmp = pNode.next if tmp.left == pNode: return tmp pNode = tmp return None

4、对称的二叉树问题描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路解析
使用递归的思路实现。
代码实现
java

/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }} */ public class Solution { boolean isSymmetrical(TreeNode pRoot) { return isSymmetricalTree(pRoot,pRoot); }private static boolean isSymmetricalTree(TreeNode pRoot,TreeNode qRoot){ if(pRoot==null && qRoot==null) return true; else if(pRoot==null || qRoot==null) return false; else if(pRoot.val != qRoot.val) return false; else return isSymmetricalTree(pRoot.left,qRoot.right) && isSymmetricalTree(pRoot.right,qRoot.left); } }

python

# -*- coding:utf-8 -*- # class TreeNode: #def __init__(self, x): #self.val = x #self.left = None #self.right = None class Solution: def isSymmetrical(self, pRoot): # write code here return self.subSymmetrical(pRoot,pRoot)def subSymmetrical(self,root1,root2): if not root1 and not root2: return True if not root1 or not root2: return False if root1.val != root2.val: return False return self.subSymmetrical(root1.left,root2.right) and self.subSymmetrical(root1.right,root2.left)

5、滑动窗口的最大值问题描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
思路解析
我们用双向队列可以在O(N)时间内解决这题。当我们遇到新的数时，将新的数和双向队列的末尾比较，如果末尾比新数小，则把末尾扔掉，
直到该队列的末尾比新数大或者队列为空的时候才住手。这样，我们可以保证队列里的元素是从头到尾降序的，由于队列里只有窗口内的数，
所以他们其实就是窗口内第一大，第二大，第三大...的数。保持队列里只有窗口内数的方法和上个解法一样，也是每来一个新的把窗口最左边的扔掉，
然后把新的加进去。然而由于我们在加新数的时候，已经把很多没用的数给扔了，这样队列头部的数并不一定是窗口最左边的数。这里的技巧是，
我们队列中存的是那个数在原数组中的下标，这样我们既可以直到这个数的值，也可以知道该数是不是窗口最左边的数。这里为什么时间复杂度是O(N)呢？
因为每个数只可能被操作最多两次，一次是加入队列的时候，一次是因为有别的更大数在后面，所以被扔掉，或者因为出了窗口而被扔掉。
因此一个新数进来：
1、判断队列头部的数的下标是否还在窗口中
2、将新数加入到队列中
3、如果index已经达到窗口的大小了，则将队列头部的值加入到返回结果中
代码实现
java

import java.util.*; public class Solution { public ArrayList maxInWindows(int [] num, int size) { ArrayList res = new ArrayList(); if(size <= 0) return res; Deque queue = new ArrayDeque(); for(int i=0; i0 && (i - queue.getFirst()) >= size) queue.removeFirst(); while(queue.size()>0 && num[i] > num[queue.getLast()]) queue.removeLast(); queue.addLast(i); if(i+1>=size) res.add(num[queue.getFirst()]); } return res; } }

【java&python版剑指offer(八)】python

# -*- coding:utf-8 -*- import collections class Solution: def maxInWindows(self, num, size): # write code here if not num or size<=0: return [] queue = collections.deque() res = [] for index,val in enumerate(num): if len(queue)>0 and (index - queue[0] >= size): queue.popleft() while len(queue)>0 and val > num[queue[-1]]: queue.pop() queue.append(index) if index + 1 >= size: res.append(num[queue[0]]) return res