剑指offer篇
2019-11-04 本文已影响0人
后来丶_a24d
栈
两个栈实现队列
- puhs的时候push s1， pop的时候如果s2为空，则把s1的元素一个一个拿出来给s2, 最后从s2 pop元素。
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(stack2.empty()) {
while (!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
包含min的栈
- push的时候，s1进， s2如果为空或者当前元素比s2的栈定元素小，则进当前元素，否则s2进top元素。
public class Solution {
Stack<Integer> dataStack = new Stack<Integer>();
Stack<Integer> minStack = new Stack<Integer>();
public void push(int node) {
dataStack.push(node);
if(minStack.isEmpty() || node < minStack.peek()){
minStack.push(node);
}
else{
minStack.push(minStack.peek());
}
}
public void pop() {
dataStack.pop();
minStack.pop();
}
public int top() {
return dataStack.peek();
}
public int min() {
return minStack.peek();
}
}
栈压入弹出顺序
- 当入栈 1 2 3 4 5 出栈 4 3 2 1 5 用辅助栈，根据入栈一个个压入，直到辅助栈顶等于出站元素，
- 循环作辅助栈出栈以及出栈的index往后移， 最后判断辅助栈是否为空
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length == 0 || pushA.length != popA.length){
return false;
}
Stack<Integer> stack = new Stack<>();
int popAIndex = 0;
for(int i = 0; i < pushA.length; i++){
stack.push(pushA[i]);
while(!stack.isEmpty() && stack.peek() == popA[popAIndex]){
stack.pop();
popAIndex++;
}
}
return stack.isEmpty();
}
}
链表
从尾到头打印链表
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode == null){
return new ArrayList<>();
}
ArrayList<Integer> list = new ArrayList<>();
while(listNode != null){
list.add(listNode.val);
listNode = listNode.next;
}
Collections.reverse(list);
return list;
}
链表中倒数第k个节点
- pre,now都指向头结点 now开始跑,跑了k - 1之后,pre开始一直跑， now一直跑完就输出, 注意考虑 k超过链表的长度
public ListNode FindKthToTail(ListNode head,int k) {
if(k < 0){
return null;
}
ListNode pre = head;
ListNode now = head;
int kTemp = k;
int listNodeLength = 0;
while(now != null){
listNodeLength++;
now = now.next;
if(k < 1){
pre = pre.next;
}
k--;
}
if(listNodeLength < kTemp){
return null;
}
return pre;
}
反转链表
public ListNode ReverseList(ListNode head) {
if(head == null){
return null;
}
ListNode pre = null;
ListNode next = null;
while(head != null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
合并两个排序的链表
- 归并的思路
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
}
ListNode head;
if(list1.val > list2.val){
head = new ListNode(list2.val);
list2 = list2.next;
}else{
head = new ListNode(list1.val);
list1 = list1.next;
}
ListNode temp = head;
while(list1 != null && list2 != null){
ListNode next;
if(list1.val > list2.val){
next = new ListNode(list2.val);
list2 = list2.next;
}else{
next = new ListNode(list1.val);
list1 = list1.next;
}
head.next = next;
head = head.next;
}
while(list1 != null){
ListNode next = new ListNode(list1.val);
list1 = list1.next;
head.next = next;
head = head.next;
}
while(list2 != null){
ListNode next = new ListNode(list2.val);
list2 = list2.next;
head.next = next;
head = head.next;
}
return temp;
}
复杂链表复制
/*
1、复制每个节点，如：复制节点A得到A1，将A1插入节点A后面
2、遍历链表，A1->random = A->random->next;`
3、将链表拆分成原链表和复制后的链表`
*/
public RandomListNode Clone(RandomListNode pHead) {
if(pHead == null) {
return null;
}
RandomListNode currentNode = pHead;
//1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
while(currentNode != null){
RandomListNode cloneNode = new RandomListNode(currentNode.label);
RandomListNode nextNode = currentNode.next;
currentNode.next = cloneNode;
cloneNode.next = nextNode;
currentNode = nextNode;
}
currentNode = pHead;
//2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
while(currentNode != null) {
currentNode.next.random = currentNode.random==null?null:currentNode.random.next;
currentNode = currentNode.next.next;
}
//3、拆分链表，将链表拆分为原链表和复制后的链表
currentNode = pHead;
RandomListNode pCloneHead = pHead.next;
while(currentNode != null) {
RandomListNode cloneNode = currentNode.next;
currentNode.next = cloneNode.next;
cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
currentNode = currentNode.next;
}
return pCloneHead;
}
二叉搜索树与双向链表
//直接用中序遍历
public class Solution {
TreeNode head = null;
TreeNode realHead = null;
public TreeNode Convert(TreeNode pRootOfTree) {
ConvertSub(pRootOfTree);
return realHead;
}
private void ConvertSub(TreeNode pRootOfTree) {
if(pRootOfTree==null) return;
ConvertSub(pRootOfTree.left);
//当左子树为空时，左右都赋值根节点
if (head == null) {
head = pRootOfTree;
realHead = pRootOfTree;
} else {
//pRootOfTree 根节点右子树
head.right = pRootOfTree;
pRootOfTree.left = head;
head = pRootOfTree;
}
ConvertSub(pRootOfTree.right);
}
}
两个链表的第一个公共节点
- 无环, 求出两个链表长度，让长的先走两个长度差值，然后再一起走。
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode p1 = pHead1;
ListNode p2 = pHead2;
int count_p1 = 0,count_p2 = 0;
while(p1 != null){
count_p1++;
p1=p1.next;
}
while(p2 != null){
count_p2++;
p2=p2.next;
}
if (count_p1 > count_p2) {
int length = count_p1 - count_p2;
while(length != 0){
pHead1=pHead1.next;
length--;
}
}else{
int length = count_p2 - count_p1;
while(length != 0){
pHead2=pHead2.next;
length--;
}
}
while(pHead1 != null && pHead2 != null && pHead1 != pHead2){
pHead1 = pHead1.next;
pHead2= pHead2.next;
}
return pHead1;
}
求链表中环入口
/**
使用两个指针，一个快指针，一个慢指针，快指针一次走两步，慢指针一次走一步；
若快指针最后变为空，则单链表为无环单链表，返回空指针；
若快慢指针在某一时刻指向同一节点，即二者完全一样，则为有环单链表，
此时让快指针重新指向链表头结点，然后快慢指针均一次走一步，
当快慢指针再次相同时，则此节点即为链表入环节点，将其返回。
**/
public ListNode EntryNodeOfLoop(ListNode pHead){
if(pHead == null || pHead.next == null) return null;
ListNode l1 = pHead;
ListNode l2 = pHead;
while(l2 != null && l2.next != null){
l1 = l1.next;
l2 = l2.next.next;
if(l1 == l2){
l2 = pHead;
while(l1 != l2){
l1 = l1.next;
l2 = l2.next;
}
if(l1 == l2) return l2;
}
}
return null;
}
删除重复节点
//temp为头结点的前一个节点，当当前于下一个节点不重复时，temp节点往下，当前节点往下
//当重复时一直到不重复的地方temp节点next指向它。
public ListNode deleteDuplication(ListNode pHead) {
if (pHead == null) return null;
ListNode pHeadTemp = pHead;
ListNode temp = new ListNode(-1);
temp.next = pHead;
ListNode tempPhead = temp;
while(pHeadTemp!=null && pHeadTemp.next != null){
if(pHeadTemp.val == pHeadTemp.next.val){
int val = pHeadTemp.val;
while(pHeadTemp != null && pHeadTemp.val == val){
pHeadTemp = pHeadTemp.next;
}
tempPhead.next = pHeadTemp;
}else{
tempPhead = pHeadTemp;
pHeadTemp = pHeadTemp.next;
}
}
return temp.next;
}
