Java与算法（2）
题目：
一个栈依次压入1,2,3,4,5，那么从栈顶到栈底分别为5,4,3,2,1，将这个栈转置后，从栈顶到栈底为1,2,3,4,5，也就是实现栈中元素的逆序，但是只能使用递归函数来实现，不能使用其它数据结构
public class ReverseByStack {
Stack<Integer> stack;
public ReverseByStack(Stack<Integer> stack) {
this.stack = stack;
}
public int getAndRemoveLastElemt() {
int result = stack.pop();
if (stack.isEmpty()) {
return result;
}
else {
int last = getAndRemoveLastElemt();
stack.push(result);
return last;
}
}
public void reverse() {
if (stack.isEmpty()) {
return;
}
int i = getAndRemoveLastElemt();
reverse();
stack.push(i);
}
public static void main(String[] args) {
Stack<Integer> stack =
new Stack<>();
stack.push(
5);
stack.push(
4);
stack.push(
3);
ReverseByStack reverseByStack =
new ReverseByStack(stack);
reverseByStack.reverse();
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
题目：
一个栈中元素的类型为整型，现在想将该栈从顶到底按从小到大的顺序排序，只许申请一个栈，除此之外，可以申请新的变量，但不能申请额外的数据结构
public class SortStackbyStack {
Stack<Integer> stack;
public SortStackbyStack(Stack<Integer> stack) {
this.stack = stack;
}
public void sort() {
Stack<Integer> help =
new Stack<>();
while (!stack.isEmpty()) {
int cur = stack.pop();
while (!help.isEmpty() && help.peek()>cur) {
stack.push(help.pop());
}
help.push(cur);
}
while (!help.isEmpty()) {
stack.push(help.pop());
}
}
public static void main(String[] args) {
Stack<Integer> stack =
new Stack<>();
stack.push(
0);
stack.push(
9);
stack.push(
10);
stack.push(
1);
SortStackbyStack sortStackbyStack =
new SortStackbyStack(stack);
sortStackbyStack.sort();
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
题目：
有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置
如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口，
实现一个函数：
输入：
整型数组arr，窗口大小w
输出：
一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值
public class GetTheWidow {
public int[] window(
int[] a,
int w) {
LinkedList<Integer> linkedList =
new LinkedList<>();
int[] res =
new int[a.length-w+
1];
int index =
0;
for(
int i=
0;i<a.length;i++) {
while (!linkedList.isEmpty() && a[i]>=a[linkedList.peekLast()]) {
linkedList.pollLast();
}
linkedList.addLast(i);
if (linkedList.peekFirst()==i-w) {
linkedList.pollFirst();
}
if (i>=w-
1) {
res[index++] = a[linkedList.peekFirst()];
}
}
return res;
}
public static void main(String[] args) {
int[] a = {
4,
3,
5,
4,
3,
3,
6,
7};
int w =
3;
GetTheWidow getTheWidow =
new GetTheWidow();
int[] data = getTheWidow.window(a, w);
for(
int i=
0;i<data.length;i++) {
System.out.println(data[i]);
}
}
}
