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

java实现一个循环队列 代码如下： package queue; public class CircularQueue { private String[] data; private int size; private int head; private int tail; public CircularQueue(int capacity) { data = new String[capacity]; size = capacity; head = 0; tail = 0; } public boolean enqueue(String item) { if ((tail + 1) % size == head) { return false; } data[tail] = item; tail = (tail + 1) % size; return true; } public String dequeue() { if (head == tail) { return null; } String value = data[head]; head = (head + 1) % size; return value; } public void printAll() { if (0 == size) { return ; } for (int i = head;i % size != tail;i++) { System.out.print(data[i] + " "); } System.out.println(); } public static void main(String[] args) { CircularQueue circularQueue = new CircularQueue(5); circularQueue.enqueue("hello1"); circularQueue.enqueue("hello2"); circularQueue.enqueue("hello3"); circularQueue.enqueue("hello4"); circularQueue.dequeue(); circularQueue.printAll(); } }

全排列实现： void Dopermute(char *pstr, char *pBegin) { if (*pBegin == '\0') printf("%s\n", pstr); for (char *pCur = pBegin; *pCur != '\0'; pCur++) { char temp = *pBegin; *pBegin = *pCur; *pCur = temp; Dopermute_v2(pstr, pBegin + 1); temp = *pBegin; *pBegin = *pCur; *pCur = temp; } } void Permute(char* pstr) { if (pstr == nullptr) return; Dopermute(pstr, pstr); }

老师新年好 这是我的作业 https://blog.csdn.net/github_38313296/article/details/86819684

求斐波那契数列，当然最经典的算法就是递归，但是递归的效率非常低，因为中间过车会计算大量重复的子节点。在《剑指Offer》一书中，提到了一个自下而上计算的方法。我们知道f(0)=0,f(1)=1,再计算f(2),f(3)一直到f(n)。这样，时间复杂度就是O(n)。

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

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]; } } }

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); } }

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); } }

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; } }

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(); } }