《剑指offer》之链表、栈和队列专题
- 【前言】此文乃本人每天写算法训练，不断补充，自己阅读！
1.给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。
滑动窗口。
1）判断是否合法输入。
2）合法，则找出0~size-1 中最大值，其坐标为index。
3）滑动，判断index是否过期，过期则找到窗口中的最大值的index。添加到list当中。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> list = new ArrayList<>();
if(num ==null || num.length <size || size <=0 ){
return list;
}
//滑动数组下标
int index=0;
index = findMax(num,size,0);
list.add(num[index]);
for(int i=size;i<num.length;i++){
//先看是否过期
if(i-index>=size){
index = findMax(num,size,index+1);
}else{
if(num[i]>num[index]){
index = i;
}
}
list.add(num[index]);
}
return list;
}
public int findMax(int [] num,int size,int begin){
int index = begin;
for(int i = begin+1; i<begin+size;i++){
if(num[index]<num[i]){
index = i;
}
}
return index;
}
}2.一个链表中包含环，请找出该链表的环的入口结点。
第一步，找环中相汇点。分别用p1，p2指向链表头部，p1每次走一步，p2每次走二步，直到p1==p2找到在环中的相汇点。
第二步，找环的入口。接上步，当p1==p2时，p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x;
n=x;可以看出p1实际走了一个环的步数，再让p2指向链表头部，p1位置不变，p1,p2每次走一步直到p1==p2; 此时p1指向环的入口。
public class Solution {
ListNode EntryNodeOfLoop(ListNode pHead){
if(pHead == null || pHead.next == null)
return null;
ListNode p1 = pHead;
ListNode p2 = pHead;
while(p2 != null && p2.next != null ){
p1 = p1.next;
p2 = p2.next.next;
if(p1 == p2){
p2 = pHead;
while(p1 != p2){
p1 = p1.next;
p2 = p2.next;
}
if(p1 == p2)
return p1;
}
}
return null;
}
}思路二：链表中有环那就必然会有重复节点，利用HashMap的key唯一性！
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
import java.util.HashMap;
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead){
ListNode node = pHead;
HashMap<ListNode,Boolean> map = new HashMap<>();
while(node!=null){
if(map.containsKey(node)){
return node;
}else{
map.put(node,true);
node = node.next;
}
}
return null;
}
}3.输入一个链表，从尾到头打印链表每个节点的值。
常常使用反转时可以用上栈的后进先出来反转
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
//使用栈结构的先进后出
Stack<Integer> stack = new Stack<Integer>();
while(listNode!= null){
stack.push(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> list = new ArrayList<Integer>();
while(!stack.isEmpty()){
list.add(stack.pop());
}
return list;
}
}
4.用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
栈是后进先出，队列是先进先出
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if(stack1.empty()&&stack2.empty()){
throw new RuntimeException("Queue is empty!");
}
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}5.输入两个链表，找出它们的第一个公共结点。
使用HashSet存储其中一个链表，遍历另一个链表看是否存在相同节点
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
import java.util.HashSet;
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//使用HashSet存储其中一个链表，遍历另一个链表看是否存在相同节点
HashSet<ListNode> set =new HashSet<ListNode>();
while(pHead1 !=null){
set.add(pHead1);
pHead1 = pHead1.next;
}
while(pHead2 !=null){
if(set.contains(pHead2)){
return pHead2;
}
pHead2 = pHead2.next;
}
return null;
}
}利用栈的反转特性
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
import java.util.HashMap;
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode current1 = pHead1;
ListNode current2 = pHead2;
HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>();
while (current1 != null) {
hashMap.put(current1, null);
current1 = current1.next;
}
while (current2 != null) {
if (hashMap.containsKey(current2))
return current2;
current2 = current2.next;
}
return null;
}
}