春节7天练 | Day 2：栈、队列和递归

李皮皮皮皮皮

2019-02-05 21:22:16

基础数据结构和算法是基石，灵活运用是解题的关键。栈，队列这些数据结构说到底就是给顺序表添加约束，更便于解决某一类问题。学习中培养算法的设计思想是非常关键的。而且思想是可以通用的。之前读《暗时间》一书，收获颇深。书中介绍之正推反推我在做程序题时竟出奇的好用。
Abner

2019-02-11 16:12:14

java用数组实现一个顺序栈
代码如下：
package stack;

public class ArrayStack {

private String[] data;
private int count;
private int size;

public ArrayStack(int n) {
this.data = new String[n];
this.count = 0;
this.size = n;
}

public boolean push(String value) {
if (count == size) {
return false;
} else {
data[count] = value;
count++;
return true;
}
}

public String pop() {
if (count == 0) {
return null;
} else {
count--;
return data[count];
}
}
}
Abner

2019-02-11 17:24:14

java用递归实现斐波那契数列
代码如下：
package recursion;

public class Fib {

public long calFib(long n) {
if (n == 0 || n == 1) {
return 1;
} else {
return calFib(n - 1) + calFib(n - 2);
}
}

public static void main(String[] args) {
Fib fib = new Fib();
long result = fib.calFib(5);
System.out.println(result);
}
}
Abner

2019-02-11 17:07:30

java用递归实现求解n!
代码如下：
package recursion;

public class Fac {

public long calFac(long n) {
if (n == 0) {
return 1;
}
return calFac(n - 1) * n;
}

public static void main(String[] args) {
Fac fac = new Fac();
long result = fac.calFac(10);
System.out.println(result);
}
}
kai

2019-02-11 10:25:20

1. 编程实现斐波那契数列求值 f(n)=f(n-1)+f(n-2）
public class Fibonacci {
public static int fib(int n) {
if (n <= 0) {
return 0;
}
if (n == 1) {
return 1;
}

return fib(n-1) + fib(n-2);
}
}

2. Climbing Stairs（爬楼梯）
public class ClimbStairs {
public int climbFloor(int n) {
if (n == 1 || n == 2) {
return n;
}

return climbFloor(n - 1) + climbFloor(n - 2);
}

public int climbFloorIter(int n) {
if (n == 1 || n == 2) {
return n;
}

int jump1 = 1;
int jump2 = 2;
int jumpN = 0;

for (int i = 3; i <= n; i++) {
jumpN = jump1 + jump2;

jump1 = jump2;
jump2 = jumpN;
}

return jumpN;
}
}

3. Sliding Window Maximum（滑动窗口最大值)
import java.util.ArrayList;
import java.util.LinkedList;

public class MaxNumOfSlidingWindow {
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> res = new ArrayList<>();

if (num == null || num.length <= 0 || size <= 0 || size > num.length) {
return res;
}

LinkedList<Integer> qMax = new LinkedList<>(); // 双端队列：左端更新max,右端添加数据

int left = 0;

for (int right = 0; right < num.length; right++) {
// 更新右端数据
while (!qMax.isEmpty() && num[qMax.peekLast()] <= num[right]) {
qMax.pollLast();
}

qMax.addLast(right);

// 更新max：如果max的索引不在窗口内,则更新
if (qMax.peekFirst() == right - size) {
qMax.pollFirst();
}

// 待窗口达到size，输出max
if (right >= size-1) {
res.add(num[qMax.peekFirst()]);
left++;
}
}

return res;
}
}
Abner

2019-02-12 13:46:31

java用链表实现一个链式栈
代码如下：
package stack;

public class LinkedStack {

private Node top = null;

public static class Node {

private String data;
private Node next;

public Node(String data, Node next) {
this.data = data;
this.next = next;
}

public String getData() {
return data;
}
}

public void push(String item) {
Node newNode = new Node(item, null);
if (top == null) {
top = newNode;
} else {
newNode.next = top;
top = newNode;
}
}

public String pop() {
if (top == null) {
return null;
}
String value = top.data;
top = top.next;
return value;
}

public void printAll() {
Node pNode = top;
while (pNode != null) {
System.out.print(pNode.data + " ");
pNode = pNode.next;
}
System.out.println();
}

public static void main(String[] args) {
LinkedStack linkedStack = new LinkedStack();
linkedStack.push("haha");
linkedStack.push("nihao");
linkedStack.printAll();
}
}
Abner

2019-02-11 16:50:58

java用数组实现一个顺序队列
代码如下：
package queue;

public class ArrayQueue {

private String[] data;
private int size;
private int head;
private int tail;

public ArrayQueue(int capacity) {
data = new String[capacity];
size = capacity;
head = 0;
tail = 0;
}

public boolean enqueue(String value) {
if (tail == size) {
return false;
}
data[tail] = value;
tail++;
return true;
}

public String dequeue() {
if (tail == 0) {
return null;
}
String value = data[head];
head++;
return value;
}
}
ALAN

2019-02-08 14:14:37

import java.util.Arrays;

/**
*
*Stack 1 solution
*/
public class StackArray {

public Object[] arr = new Object[10];
public int count;

public void push(Object ele) {
if (count == arr.length) { // expand size
arr = Arrays.copyOf(arr, arr.length * 2);
}
arr[count] = ele;
count++;
}

public Object pop() {
if (count == 0)
return null;
if (count < arr.length / 2) {
arr = Arrays.copyOf(arr, arr.length / 2);
}
return arr[--count];

}
}

/**
*
*Stack 2 solution
*/
class StackLinked {
Node head;
Node tail;

public void push(Object ele) {

if (head == null) {
head = new Node(ele);
tail = head;
} else {
Node node = new Node(ele);
tail.next = node;
node.prev = tail;
tail = node;
}
}

public Object pop() {
if (tail == null)
return null;
Node node = tail;
if (tail == head) {
head = null;
tail = null;
} else
tail = tail.prev;
return node;

}
}
class Node {
Node prev;
Node next;
Object value;

public Node(Object ele) {
value = ele;
}
}
TryTs

2019-02-06 15:29:19

之前有个类似的题，走楼梯，装苹果，就是把苹果装入盘子，可以分为有一个盘子为空（递归），和全部装满没有空的情况，找出状态方程，递归就可以列出来了。我觉得最关键是要列出状态方程，之前老师类似于说的不需要关注特别细节，不要想把每一步都要想明白，快速排序与递归排序之类的算法，之前总是想把很细节的弄懂，却发现理解有困难。
杨建斌(young)

2023-06-29 14:42:57

滑动窗口最大值
public static void main(String[] args) {

PriorityQueue<Integer[]> queue = new PriorityQueue(3, new Comparator<Integer[]>() {
@Override
public int compare(Integer[] o1, Integer[] o2) {
if (o1[0] == o2[0]) {
return o2[1] - o1[1];
}
return o2[0] - o1[0];
}
});

int[] nums = new int[]{7, 3, -1, -3, 5, 3, 6, 7};
for (int i = 0; i < 3; i++) {
queue.add(new Integer[]{nums[i], i});
}

int[] ret = new int[nums.length - 3 + 1];
ret[0] = queue.peek()[0];
for (int i = 3; i < nums.length; i++) {
queue.add(new Integer[]{nums[i], i});
if (queue.peek()[1] < i - 3 + 1) {
queue.poll();
}
ret[i - 3 + 1] = queue.peek()[0];
}

System.out.println(ret);

}
杨建斌(young)

2023-06-29 11:47:20

双端队列
static class MyCircularDeque {
private int[] elements;
//获得双端队列的最后rear一个元素

private int rear, front;
//内容个数
private int capacity;

public boolean insertFront(int value) {
if (elements.length == capacity) {
return false;
}
if (capacity == 0) {
rear = front = 0;
} else {
front = front - 1;
if (front < 0) {
front += elements.length;
}
}
elements[front] = value;
capacity++;
return true;
}

public boolean insertLast(int value) {
if (elements.length == capacity) {
return false;
}
if (capacity == 0) {
rear = front = 0;
} else {
rear = (rear + 1) % elements.length;
}
elements[rear] = value;
capacity++;
return true;
}

public boolean deleteFront() {
if (capacity == 0) {
return false;
}
int idx = front;
front = front + 1;
if (front > elements.length) {
front = 0;
}
elements[idx] = -1;
capacity--;
return true;
}

public boolean deleteLast() {
if (capacity == 0) {
return false;
}
int idx = rear;
rear = rear - 1;
elements[idx] = -1;
capacity--;
return true;
}

public int getFront() {
if (front != -1) {
return elements[front];
}
return -1;
}

public int getRear() {
if (rear != -1) {
return elements[rear];
}
return -1;
}
}
杨建斌(young)

2023-06-28 18:19:01

逆波兰表达式
public static void main(String[] args) {

List<String> str = new ArrayList<>();
//"10","6","9","3","+","-11","*","/","*","17","+","5","+
str.add("10");
str.add("6");
str.add("9");
str.add("3");
str.add("+");
str.add("-11");
str.add("*");
str.add("/");
str.add("*");
str.add("17");
str.add("+");
str.add("5");
str.add("+");

Stack<String> stack = new Stack();
for (int i = 0; i < str.size(); i++) {
if (!str.get(i).equals("+") &&
!str.get(i).equals("-") &&
!str.get(i).equals("*") &&
!str.get(i).equals("/")) {
stack.push(str.get(i));
} else {
String pop = stack.pop();
int old = Integer.parseInt(pop);
int newV = Integer.parseInt(stack.pop());
int value = 0;
if (str.get(i).equals("+")) {
value = old + newV;
} else if (str.get(i).equals("-")) {
value = newV - old;
} else if (str.get(i).equals("*")) {
value = old * newV;
} else if (str.get(i).equals("/")) {
value = newV / old;
}
stack.push(String.valueOf(value));
}
}

System.out.println(stack.pop());

}
杨建斌(young)

2023-06-28 17:35:22

最长有效挎号
public static void main(String[] args) {

String s = "";
Stack<Integer> stack = new Stack<>();
int[] arr = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.add(i);
} else {
if (!stack.isEmpty()) {
Integer pop = stack.pop();
arr[pop] = 1;
arr[i] = 1;
}
}
}
int max = 0;
int curr = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1) {
curr++;
max = Math.max(curr, max);
} else {
curr = 0;
}
}
System.out.println(max);

}
杨建斌(young)

2023-06-28 16:18:55

有效的挎号
public static void main(String[] args) {

String s = "((((";
if (s.length() % 2 != 0) {
System.out.println(false);
return;
}
Stack<Character> stack = new Stack();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ']' || c == '}' || c == ')') {
Character pop = stack.pop();
if ((c == ']' && pop != '[') || (c == '}' && pop != '{') || (c == ')' && pop != '(')) {
System.out.println(false);
break;
}
} else {
stack.add(c);
}
}
System.out.println(stack.isEmpty());

}
杨建斌(young)

2023-06-28 16:16:22

有效的挎号
public static void main(String[] args) {

String s = "()[][}";
if (s.length() % 2 != 0) {
System.out.println(false);
return;
}
Stack<Character> stack = new Stack();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ']' || c == '}' || c == ')') {
Character pop = stack.pop();
if ((c == ']' && pop != '[') || (c == '}' && pop != '{') || (c == ')' && pop != '(')) {
System.out.println(false);
break;
}
} else {
stack.add(c);
}
}
System.out.println(true);

}
风行者

2021-02-16 23:34:30

递归写法的话简单加一层缓存就可以有很大的性能提升了，不用动态规划也可以做
class Solution:
cache = {}
def climbStairs(self, n: int) -> int:
if self.cache.__contains__(n):
return self.cache[n]
else:
self.cache[n]=(self.climbStairs(n-2)+self.climbStairs(n-1) if n>2 else n)
return self.cache[n]
何沛

2020-01-03 17:49:35

用数组实现一个顺序队列
/**
* @author hepei
* @date 2020/1/3 17:12
**/
public class ArrayQueue {

private int[] data;
private int head;
private int tail;

public ArrayQueue(int[] data) {
this.data = data;
}

public void enqueue(int v) {
if (tail == data.length && head == 0) {
return;
}
if (tail == data.length && head > 0) {
for (int i = 0; i < tail - head; i++) {
data[i] = data[i + head];
}
tail = tail - head;
head = 0;
}
data[tail] = v;
tail++;
}

public int dequeue() {
if (tail == 0||head==tail) {
return -1;
}
int r = data[head];
head++;
return r;
}

public void display() {
for (int i = head; i < tail; i++) {
System.out.print( data[i] + " " );
}
}

public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue( new int[5] );
queue.enqueue( 1 );
queue.enqueue( 2 );
queue.enqueue( 3 );
queue.enqueue( 4 );
queue.enqueue( 5 );
queue.dequeue();
queue.dequeue();
queue.dequeue();
queue.dequeue();
queue.enqueue( 6 );
queue.enqueue( 7 );
queue.display();
}

}
Hxz

2019-10-12 16:07:33

我用js写的题解都放在了https://github.com/abchexuzheng/algorithm-for-js这里，前端学算法的小伙伴们可以看看一起学习下哈
Geek_18b741

2019-09-11 08:21:32

再做Climbing Stairs这个题目的时候，提交了两个版本的代码。理论上来说内存应该是有区别的，但是LeetCode给的结果，内存大小却没有什么区别。请帮忙看看。
/**
* 动态规划
* @param n
* @return
*/
public int climbStairsV3(int n) {
if(n==1) return 1;
int[] dp = new int[n+1];
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}

/**
* 节省内存的动态规划，但实际LeetCode反馈出来的内存并不少
* @param n
* @return
*/
public int climbStairsV4(int n) {
if(n==1) return 1;
int num1 =1;
int num2 =2;
int num3=0;
for(int i=3;i<=n;i++){
num3=num1+num2;
num1=num2;
num2=num3;
}
return num2;
}
猫猫

2019-08-26 15:02:46

全排列js
//9.一组数据集合的全排列回溯（暴力枚举）
let count = 1

function permutation(nums, result = []) {
if (nums.length == 0) {
console.log(`${count}:${result}`)
count++
return
}
for (let i = 0; i < nums.length; i++) {
permutation(nums.filter((value, index) => index != i), [...result, nums[i]])
}
}