题目描述 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
通过辅助栈进行模拟进栈出栈操作，若模拟栈最后为空，则符合要求。
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length == 0 || popA.length == 0)
return false;
Stack<Integer> stack = new Stack<>();
int n = pushA.length;
for(int pushIndex = 0, popIndex = 0; pushIndex < n; pushIndex++) {
stack.push(pushA[pushIndex]);
while(!stack.empty() && stack.peek() == popA[popIndex]) {
stack.pop();
popIndex++;
}
}
return stack.empty();
}
}
题目描述 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数。
利用辅助栈minStack，开始minStack为空时压入第一个node，以后每次比较，压入node与peek中的小的那个。pop两个栈同时pop，min()函数中返回minStack的peek
代码实现：
import java.util.Stack;
public class Solution {
private Stack<Integer> dataStack = new Stack();
private Stack<Integer> minStack = new Stack();
public void push(int node) {
dataStack.push(node);
minStack.push(minStack.isEmpty() ? node : Math.min(minStack.peek(), node));
}
public void pop() {
dataStack.pop();
minStack.pop();
}
public int top() {
return dataStack.pop();
}
public int min() {
return minStack.peek();
}
}
题目描述 输入一个链表，反转链表后，输出新链表的表头。
迭代
代码实现：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode newList = new ListNode(-1);
while(head != null) {
ListNode next = head.next;
head.next = newList.next;
newList.next = head;
head = next;
}
return newList.next;
}
}
递归
代码实现：
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode next = head.next;
head.next = null;
ListNode newHead = ReverseList(next);
next.next = head;
return newHead;
}
}
题目描述 输入一个链表，输出该链表中倒数第k个结点。
设链表的长度为 N。设两个指针 P1 和 P2，先让 P1 移动 K 个节点，则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动，可以知道当 P1 移动到链表结尾时，P2 移动到 N - K 个节点处，该位置就是倒数第 K 个节点。 几个边界条件： 1.head为null 2.k大于链表长度
代码实现：
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null)
return null;
ListNode p1 = head;
ListNode p2 = head;
while(p1 != null && k-- > 0) {
p1 = p1.next;
}
if(k>0)
return null;
while(p1 != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
}
题目描述 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
两次循环分别记录奇数和偶数
代码实现：(O(N))
public class Solution {
public void reOrderArray(int [] array) {
int length = array.length;
int[] newArray = new int[length];
int j = 0;
for(int i=0; i<length; i++) {
if(array[i]%2 != 0 ) {
newArray[j++] = array[i];
}
}
for(int i=0; i<length; i++) {
if(array[i]%2 == 0) {
newArray[j++] = array[i];
}
}
for(int i=0; i<length; i++) {
array[i] = newArray[i];
}
}
}
题目描述 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
采用二分法解答这个问题，
mid = low + (high - low)/2
需要考虑三种情况：
(1)array[mid] > array[high]:
出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。
low = mid + 1
(2)array[mid] == array[high]:
出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边
还是右边,这时只好一个一个试 ，
high = high - 1
(3)array[mid] < array[high]:
出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左
边。因为右边必然都是递增的。
high = mid
注意这里有个坑：如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字
比如 array = [4,6]
array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;
如果high = mid - 1，就会产生错误， 因此high = mid
但情形(1)中low = mid + 1就不会错误
代码实现：O(logNN) + 1
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length == 0)
return 0;
int low = 0 ;
int high = array.length - 1;
while(low < high){
int mid = low + (high - low) / 2;
if(array[mid] > array[high]){
low = mid + 1;
}else if(array[mid] == array[high]){
high = high - 1;
}else{
high = mid;
}
}
return array[low];
}
}