1.固定数组实现栈
定义一个辅助空间index，一开始指向数组0的位置，所指位置即入栈或者出栈的位置。每次一个元素要入栈，则将该元素放进index所指向的位置，再将index+1；要出栈一个元素，则将index-1,将此时index上的元素取出。遇到边界则抛异常。
public static class ArrayStack{
public int[] arr;
public Integer index;
ArrayStack(int initSize){
if (initSize<0){
throw new IllegalArgumentException("The init size is less than 0");
}
arr=new int[initSize];
index=0;
}
public Integer peek(){
if(index==0){
return null;
}
return arr[index-1];
}
public void push(int obj){
if(index==arr.length){
throw new ArrayIndexOutOfBoundsException("the stack is full");
}
arr[index++]=obj;
}
public Integer pop(){
if(index==0){
throw new ArrayIndexOutOfBoundsException("the stack is empty");
}
return arr[--index];
}
}
2.固定数组实现队列
定义三个辅助空间start（指向要入的位置），end（指向要出的位置），size。定义size的原因是为了方便解耦，使得start只和size相关，end只和size相关，start和end各走各的没有关系（为了循环使用数组）。start，end一开始都指向数组0的位置。每次一个元素要入队，在size小于数组长度的情况下，将该元素放进start所指向的位置，再判断一下此时start是否为数组最后一个位置，如果是就回到0位置（之前肯定有元素出队了，因为没有出队的话size就会等于数组长度，以上都不会判断），否则则将start+1；要出栈一个元素，在size大于0的情况下，将end所指向的位置的元素取出，再判断一下此时end是否为数组最后一个位置，如果是就回到0位置（之前肯定有元素出队了，因为没有出队的话size就会等于数组长度，以上都不会判断），否则则将end+1。start和end互不影响。以下为实现代码：
package StackAndQyeue;
import java.util.Arrays;
public class Array_To_Stack_Queue {
public static class ArrayStack{
public Integer[] arr;
public Integer size;
ArrayStack(int initSize){
if (initSize<0){
throw new IllegalArgumentException("The init size is less than 0");
}
arr=new Integer[initSize];
size=0;
}
//返回栈顶的值
public Integer peek(){
if(size==0){
return null;
}
return arr[size-1];
}
public void push(int obj){
if(size==arr.length){
throw new ArrayIndexOutOfBoundsException("the stack is full");
}
arr[size++]=obj;
}
public Integer pop(){
if(size==0){
throw new ArrayIndexOutOfBoundsException("the stack is empty");
}
return arr[--size];
}
}
public static class ArrayQueue{
public Integer[] arr;
public Integer size;
public Integer start;
public Integer end;
ArrayQueue(int initSize){
if (initSize<0){
throw new IllegalArgumentException("The init size is less than 0");
}
arr=new Integer[initSize];
size=0;
//start 指着入的位置
start=0;
//end 指着出的位置
end=0;
}
public Integer peek(){
if (size==0){
throw new ArrayIndexOutOfBoundsException("the queue is empty");
}
return arr[end];
}
public void push(int obj){
if(size==arr.length){
throw new ArrayIndexOutOfBoundsException("the queue is full");
}
// 应该都行
arr[start++]=obj;
//循环使用数组 到达边界跳到0
if (start==arr.length){
start=0;
}
size++;
// arr[start]=obj;
// start= start==arr.length-1?0:start+1;
// size++;
}
public Integer pop(){
if (size==0){
throw new ArrayIndexOutOfBoundsException("the queue is empty");
}
if (end==arr.length){
end=0;
}
size--;
return arr[end++];
// int tmp=end;
// //记录一下队顶的元素，然后把该元素变成null
// Integer top=arr[tmp];
// arr[tmp]=null;
// end=end==arr.length-1?0:end+1;
// return top;
}
}
3.仅用队列结构实现栈结构
使用两个队列能够实现一个栈结构。
假设有队列A和队列B。
首先将元素依次入队列A，如果想要出一个元素，把除了最后一个元素其他的元素都入队列B,再将A中剩下的那个元素出队即可。此时B队列可以看成之前的A队列。
//假设有队列A和队列B。
//首先将元素依次入队列A，如果想要出一个元素，把除了最后一个元素其他的元素都入队列B,
// 再将A中的元素出队即可。
// 此时B队列可以看成之前的A队列。
public static class TwoQueueStack {
public Queue<Integer> queue;
public Queue<Integer> help;
TwoQueueStack(){
queue=new LinkedList<Integer>();
help=new LinkedList<Integer>();
}
public void push(int obj) {
queue.add(obj);
}
public Integer pop() {
if(queue.isEmpty()&&help.isEmpty()){
throw new RuntimeException("the stack is empty");
}
while(queue.size()>1){
help.add(queue.poll());
}
Integer res=queue.poll();
//交换这两个队列的名字
swap(queue,help);
return res;
}
private void swap(Queue<Integer> queue, Queue<Integer> help) {
this.help = queue;
this.queue=help;
}
public Integer peek(){
if(queue.isEmpty()&&help.isEmpty()){
throw new RuntimeException("the stack is empty");
}
while(queue.size()>1){
help.add(queue.poll());
}
Integer res=queue.peek();
help.add(res);
//交换这两个队列的名字
swap(queue,help);
return res;
}
4.仅用栈结构实现队列结构？
使用两个栈能够实现一个队列结构。
假设有栈A和栈B。
首先将元素依次入栈A，每一次元素要出的时候，将A中的所有元素都入栈B,前提是栈B中没有元素。只要满足两个限制即可：1.A栈元素入B栈的时候，一次要全倒完；2.B栈只有在空的情况下才能被倒入元素。何时倒入元素都可以，只要满足上述两个条件。
//假设有栈A和栈B。
//首先将元素依次入栈A，每一次元素要出的时候，将A中的所有元素都入栈B,前提是栈B中没有元素。
// 只要满足两个限制即可：1.A栈元素入B栈的时候，一次要全倒完；
// 2.B栈只有在空的情况下才能被倒入元素。
// 何时倒入元素都可以，只要满足上述两个条件。
public static class TwoStackQueue {
private Stack<Integer> stackPush;
private Stack<Integer> stackPop;
TwoStackQueue(){
stackPush=new Stack<Integer>();
stackPop=new Stack<Integer>();
}
public void push(int obj) {
stackPush.push(obj);
}
public Integer poll() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty");
} else if (stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
public Integer peek() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty");
} else if (stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.peek();
}
}
5.实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
【要求】 1．pop、push、getMin操作的时间复杂度都是O(1)。 2．设计的栈类型可以使用现成的栈结构。
第一种实现方案：
假设有栈stackData和栈stackMin。
栈stackData正常做栈的操作，保存当前栈中的元素，栈stackMin则每次把最小的元素入栈，用于保存每一步的最小值，栈stackData和栈stackMin保持同步。
假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空。
如果为空，则newNum也压入stackMin；如果不为空，比较newNum和stackMin的栈顶元素中哪个更小。
如果newNum更小或两者相等，将newNum入DataMin；否则，将stackMin的栈顶元素重复压入stackMin,即在栈顶元素上再压入一个栈顶元素。
出栈时，在stackData中弹出数据；弹出stackMin的栈顶。
public static class stack1{
Stack<Integer> stackData;
Stack<Integer> stackMin;
//栈A正常做栈的操作，保存当前栈中的元素，
// 栈B则每次把最小的元素入栈，用于保存每一步的最小值，栈A和栈B保持同步。
//假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空。
//如果为空，则newNum也压入stackMin；如果不为空，比较newNum和stackMin的栈顶元素中哪个更小。
// 如果newNum更小或两者相等，将newNum入DataMin；否则，将stackMin的栈顶元素重复压入stackMin,
// 即在栈顶元素上再压入一个栈顶元素。
stack1(){
this.stackData=new Stack<Integer>();
this.stackMin=new Stack<Integer>();
}
public void push(int obj){
stackData.push(obj);
if(stackMin.isEmpty()){
stackMin.push(obj);
}else{
if(obj<=stackMin.peek()){
stackMin.push(obj);
}else{
stackMin.push(getMin());
}
}
}
public Integer pop(){
if(stackData.isEmpty()){
throw new RuntimeException("Stack is empty");
}
this.stackMin.pop();
return stackData.pop();
}
public Integer getMin(){
if(stackData.isEmpty()){
throw new RuntimeException("Stack is empty");
}
return stackMin.peek();
}
}
第二种实现方案：
假设有栈stackData和栈stackMin。
假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空。
如果stackMin为空，则将newNum也压入stackMin；否则，比较stackNum和stackMin的栈顶元素哪一个更小。
如果newNum比stackMin的栈顶元素更小或相等，将newNum也压入stackMin；否则，不压入。
出栈时，在stackData中弹出数据value。然后比较value和stackMin的栈顶元素的大小。
如果value等于stackMin的栈顶元素时，弹出stackMin的栈顶元素；如果value大于stackMin的栈顶元素时，返回stackMin的栈顶元素，不弹出。
public static class stack2{
Stack<Integer> stackData;
Stack<Integer> stackMin;
//假设有栈stackData和栈stackMin。
//假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空。
//如果stackMin为空，则将newNum也压入stackMin；否则，比较stackNum和stackMin的栈顶元素哪一个更小。
//如果newNum比stackMin的栈顶元素更小或相等，将newNum也压入stackMin；否则，不压入。
//出栈时，在stackData中弹出数据value。然后比较value和stackMin的栈顶元素的大小。（vlaue只会大于或者等于stackMin的栈顶元素）
//如果value等于stackMin的栈顶元素时，弹出stackMin的栈顶元素；如果value大于stackMin的栈顶元素时，返回stackMin的栈顶元素，不弹出。
stack2(){
this.stackData=new Stack<Integer>();
this.stackMin=new Stack<Integer>();
}
public void push(int obj){
stackData.push(obj);
if(stackMin.isEmpty()){
stackMin.push(obj);
}else{
if(obj<=stackMin.peek()){
stackMin.push(obj);
}
}
}
public Integer pop(){
if(stackData.isEmpty()){
throw new RuntimeException("Stack is empty");
}
if(stackData.peek()==this.getMin()){
this.stackMin.pop();
}
return stackData.pop();
}
public Integer getMin(){
if(stackData.isEmpty()){
throw new RuntimeException("Stack is empty");
}
return stackMin.peek();
}
}
6.猫狗队列
【题目】 宠物、狗和猫的类如下： public class Pet { private String type; public Pet(String type) { this.type = type; } public String getPetType() { return this.type; } } public class Dog extends Pet { public Dog() { super("dog"); } } public class Cat extends Pet { public Cat() { super("cat"); } }
实现一种狗猫队列的结构，要求如下：
用户可以调用add方法将cat类或dog类的 实例放入队列中； 用户可以调用pollAll方法，将队列中所有的实例按照进队列 的先后顺序依次弹出； 用户可以调用pollDog方法，将队列中dog类的实例按照 进队列的先后顺序依次弹出； 用户可以调用pollCat方法，将队列中cat类的实 例按照进队列的先后顺序依次弹出； 用户可以调用isEmpty方法，检查队列中是 否还有dog或cat的实例； 用户可以调用isDogEmpty方法，检查队列中是否有dog 类的实例； 用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。
解决思路很简单，定义两个队列。
第一个队列是狗队列，第二个是猫队列。每个实例入队列的时候，都会记录一个类似时间戳的count。 用户调用pollAll方法的时候，根据count的大小，依次出队即可。其他的就正常入队出队即可。
public class DogCatQueue {
public static class Pet{
private String type;
public Pet(String type){
this.type=type;
}
public String getType(){
return this.type;
}
}
public static class Dog extends Pet{
public Dog(){
super("dog");
}
}
public static class Cat extends Pet{
public Cat(){
super("cat");
}
}
//count 类似时间戳
public static class PetEnterQueue {
private Pet pet;
private long count;
public PetEnterQueue(Pet pet, Long count) {
this.count = count;
this.pet = pet;
}
public Long getCount() {
return this.count;
}
public String getType() {
return this.pet.getType();
}
public Pet getPet() {
return this.pet;
}
}
public static class DogCatQueue01{
private Queue<PetEnterQueue> dogQ;
private Queue<PetEnterQueue> catQ;
private Long count;
public DogCatQueue01(){
this.dogQ=new LinkedList<PetEnterQueue>();
this.catQ=new LinkedList<PetEnterQueue>();
this.count = (long)0;
}
public void add(Pet pet){
if(pet.getType().equals("dog")){
dogQ.add(new PetEnterQueue(pet,count++));
}else if(pet.getType().equals("cat")){
catQ.add(new PetEnterQueue(pet,count++));
}else{
throw new RuntimeException("err,not dog or cat");
}
}
public Pet pollAll(){
if(!this.catQ.isEmpty()||!this.catQ.isEmpty()){
if(this.dogQ.peek().getCount()<this.catQ.peek().getCount()){
return this.dogQ.poll().getPet();
}else{
return this.catQ.poll().getPet();
}
}else if(!this.catQ.isEmpty()){
return this.catQ.poll().getPet();
}else if(!this.dogQ.isEmpty()){
return this.dogQ.poll().getPet();
}else{
throw new RuntimeException("err,queue is empty");
}
}
public Pet pollDog(){
if(!this.dogQ.isEmpty()){
return dogQ.poll().getPet();
}else {
throw new RuntimeException("err,dog queue is empty");
}
}
public Pet pollCat(){
if(!this.catQ.isEmpty()){
return catQ.poll().getPet();
}else {
throw new RuntimeException("err,dog queue is empty");
}
}
public boolean isEmpty() {
return this.dogQ.isEmpty() && this.catQ.isEmpty();
}
public boolean isDogQueueEmpty() {
return this.dogQ.isEmpty();
}
public boolean isCatQueueEmpty() {
return this.catQ.isEmpty();
}
}
7.转圈打印矩阵
【题目】 给定一个整型矩阵matrix，请按照转圈的方式打印它。 例如： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 打印结果为：1，2，3，4，8，12，16，15，14，13，9， 5，6，7，11， 10
【要求】 额外空间复杂度为O(1)。
跳出局部思维。
定义一个打印边界（子矩阵）的函数，这个函数只要知道左上角的点坐标（tr,tc）和右下角的点坐标(dr,dc)就能打印这一圈的数字。有两种特殊情况，第一种左上角的行与右下角的行相同，则只要打印这一行的数字；第二种左上角的列与右下角的列相同，则只要打印这一列的数字。
首先打印最外圈，然后让tr和tc加1，令dr和dc减1，继续打印。如果发现左上角坐标跑到右下角坐标的右方和下方，整个过程就停止。
package ArraysAndMatrices;
import java.util.ArrayList;
public class PrintMatrixSpiralOrder {
ArrayList<Integer> SOMatrix =new ArrayList<Integer>();
//首先打印最外圈，然后让tr和tc加1，令dr和dc减1，继续打印。
// 如果发现左上角坐标跑到右下角坐标的右方和下方，整个过程就停止。
public ArrayList<Integer> spiralOrderPrint(int[][] matrix){
int tr=0;
int tc=0;
int dr=matrix.length-1;
int dc=matrix[0].length-1;
while(tr<=dr&&tc<=dc){
printEdrdge(matrix,tr++,tc++,dr--,dc--);
}
return SOMatrix;
}
//定义一个打印边界（子矩阵）的函数，
// 这个函数只要知道左上角的点坐标（tr,tc）和右下角的点坐标(dr,dc)就能打印这一圈的数字。
// 有两种特殊情况，第一种左上角的行与右下角的行相同，则只要打印这一行的数字；
// 第二种左上角的列与右下角的列相同，则只要打印这一列的数字。
public void printEdrdge(int[][] matrix,int tr,int tc,int dr,int dc){
if(tr==dr){
for(int i=tc;i<dc;i++){
SOMatrix.add(matrix[tr][i++]);
}
}else if (tc==dc){
for(int i=tr;i<dr;i++){
SOMatrix.add(matrix[i][tc]);
}
}
//以下打印到边界前最后一个数字；如果只有一行，就会数组越界？
int curC=tc;
int curR=tr;
while(curC!=dc){
SOMatrix.add(matrix[tr][curC++]);
}
while(curR!=dr){
SOMatrix.add(matrix[curR++][dc]);
}
while(curC!=tc){
SOMatrix.add(matrix[dr][curC--]);
}
while(curR!=tr){
SOMatrix.add(matrix[curR--][tc]);
}
}
public static void main(String[] args) {
PrintMatrixSpiralOrder printMatrixSpiralOrder=new PrintMatrixSpiralOrder();
int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
System.out.println(printMatrixSpiralOrder.spiralOrderPrint(matrix).toString());
}
}
上题在我的每日一道编程题提过。加深一下理解。
8.旋转正方形矩阵
【题目】 给定一个整型正方形矩阵matrix，请把该矩阵调整成 顺时针旋转90度的样子。
【要求】 额外空间复杂度为O(1)。
和上题思路差不多。
定义一个能够旋转90度边界（子矩阵）的函数，这个函数只要知道左上角的点坐标（tr,tc）和右下角的点坐标(dr,dc)就能旋转边界数字90度。由于是正方形，不会出现只有一行或者一列的情况。
首先旋转最外圈，然后让tr和tc加1，令dr和dc减1，继续打印。如果发现左上角坐标跑到右下角坐标的地方（重合），整个过程停止。
旋转的过程就是抠边界的过程，每4个点进行一次90度旋转。
public class RotateMatrix {
public int[][] rotate(int[][] matrix){
int tr=0;
int tc=0;
int dr=matrix.length-1;
int dc=matrix[0].length-1;
while(tr<dr&&tc<dc){
rotateEdge(matrix,tr++,tc++,dr--,dc--);
}
return matrix;
}
//定义一个能够旋转边界的函数
//正方形。每4个点进行一次旋转。(只有一个边界)
public void rotateEdge(int[][] matrix,int tr,int tc,int dr,int dc){
int times=dc-tc;
for(int i=0;i<times;i++){
int temp=matrix[tr][tc+i];
matrix[tr][tc+i]=matrix[dr-i][tc];
matrix[dr-i][tc]=matrix[dr][dc-i];
matrix[dr][dc-i]=matrix[tr+i][dc];
matrix[tr+i][dc]=temp;
}
}
9.“之”字形打印矩阵
【题目】 给定一个矩阵matrix，按照“之”字形的方式打印这 个矩阵，例如： 1 2 3 4 5 6 7 8 9 10 11 12 “之”字形打印的结果为：1，2，5，9，6，3，4，7，10，11， 8，12
【要求】 额外空间复杂度为O(1)。
由于是之字型打印，每次打印的都是一条斜线，设计出一个打印斜线的函数。
1.上坐标（tr,tc）初始为（0,0）,沿着矩阵第一行移动（tc++）,当到达第一行最右边的元素后，再沿着矩阵最后一列移动（tr++）。
2.下坐标（dr,dc）初始为（0,0）,沿着矩阵第一列移动（dr++）,当到达第一列最下边的元素后，再沿着矩阵最后一行移动（dc++）。
3.上坐标和下坐标同步移动，每次移动后打印斜线。
4.打印的方向用boolean值表示，每次取反。
package ArraysAndMatrices;
public class ZigZagPrintMatrix {
public static void printMatrixZigZag(int[][] matrix){
int tR=0;
int tC=0;
int dR=0;
int dC=0;
int endR=matrix.length-1;
int endC=matrix[0].length-1;
boolean fromUp=false;
while(tR!=endR+1){
printLevel(matrix,tR,tC,dR,dC,fromUp);
//注意 tr=tr++; 就错了;且顺序不能错位，因为tC会自增
tR=tC==endC?tR+1:tR;
tC=tC==endC?endC:tC+1;
dC=dR==endR?dC+1:dC;
dR=dR==endR?endR:dR+1;
fromUp=!fromUp;
}
}
public static void printLevel(int[][] matrix,int tR,int tC,int dR,int dC,boolean f){
if(f){
while(tR!=dR+1){
System.out.println(matrix[tR++][tC--]+" ");
}
}else{
while(dR!=tR-1){
System.out.println(matrix[dR--][dC++]+" ");
}
}
}
}
