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

Abner 👍（0） 💬（1）
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(); } }
2019-02-12

神盾局闹别扭 👍（0） 💬（1）
全排列实现： 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); }
2019-02-09

molybdenum 👍（0） 💬（1）
老师新年好这是我的作业 https://blog.csdn.net/github_38313296/article/details/86819684
2019-02-09

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

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

Abner 👍（3） 💬（0）
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]; } } }
2019-02-11

Abner 👍（2） 💬（0）
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); } }
2019-02-11

Abner 👍（2） 💬（0）
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); } }
2019-02-11

kai 👍（2） 💬（0）
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; } }
2019-02-11

Abner 👍（1） 💬（0）
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(); } }
2019-02-12

Abner 👍（1） 💬（0）
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; } }
2019-02-11

ALAN 👍（1） 💬（0）
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; } }
2019-02-08

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

杨建斌(young) 👍（0） 💬（0）
滑动窗口最大值 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); }
2023-06-29

杨建斌(young) 👍（0） 💬（0）
双端队列 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; } }
2023-06-29