Datawhale 系列数据结构

Task2.1 栈

2.1.1用数组实现一个顺序栈

public class ArrayStack<T> { private T [] data; private int size; private int cnt; @SuppressWarnings("unchecked") public ArrayStack(){ data= (T[]) new Object [10]; cnt = 0; size =10; } public void push(T t){ if(cnt>=size){ data=Arrays.copyOf(data, data.length*2); size*=2; } data[size] = t; cnt++; } public T peek(){ if (cnt==0) { throw new EmptyStackException(); } return data[cnt]; } public T pop(){ if (cnt==0) { throw new EmptyStackException(); } cnt--; return data[cnt]; } public int search(T t){ for(int i=cnt;i>0;i--){ if(data[i]==t) return i; } return -1; } public boolean isEmpty(){ return cnt==0; } }

2.1.2 用链表实现一个链式栈

public class ListStack<T> { private List<T> data; private int cnt; public ListStack(){ data= new LinkedList<T>(); cnt = 0; } public void push(T t){ data.add(t); cnt++; } public T peek(){ if (cnt==0) { throw new EmptyStackException(); } return data.get(cnt); } public T pop(){ if (cnt==0) { throw new EmptyStackException(); } T t=data.remove(cnt); cnt--; return t; } public int search(T t){ for(int i=cnt;i>0;i--){ if(data.get(i)==t) return i; } return -1; } public boolean isEmpty(){ return cnt==0; } } 

2.1.3 编程模拟实现一个浏览器的前进后退功能

public class BrowserSimula { public static void main(String[] args) { Browser b1=new Browser(); b1.open(); b1.open(); b1.open(); b1.open(); System.out.println(b1.backward()); System.out.println(b1.backward()); System.out.println(b1.forward()); System.out.println(b1.forward()); } } class Browser{ private Stack<Integer> s1; private Stack<Integer> s2; int cnt; Browser(){ s1=new Stack<Integer>(); s2=new Stack<Integer>(); cnt=0; } /** * 点开一个新的链接 */ public void open(){ cnt++; s1.push(cnt); } //后退 public Integer backward(){ if(cnt==0) throw new ArrayIndexOutOfBoundsException(cnt); Integer a =s1.pop(); s2.push(a); return s1.peek(); } //前进 public Integer forward(){ if(s2.isEmpty()) throw new ArrayIndexOutOfBoundsException(cnt); Integer a =s2.pop(); s1.push(a); return a; } } 

2.1.4 练习

//Valid Parentheses（有效的括号） private HashMap<Character, Character> mappings; public Solution() { this.mappings = new HashMap<Character, Character>(); this.mappings.put(')', '('); this.mappings.put('}', '{'); this.mappings.put(']', '['); } public boolean isValid(String s) { Stack<Character> stack = new Stack<Character>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (this.mappings.containsKey(c)) { char topElement = stack.empty() ? '#' : stack.pop(); if (topElement != this.mappings.get(c)) { return false; } } else { stack.push(c); } } return stack.isEmpty(); } //Longest Valid Parentheses（最长有效的括号）[作为可选] /*dp 方法: 我们用 dp[i] 表示以 i 结尾的最长有效括号； 1 当 s[i] 为 ( , dp[i] 必然等于0,因为不可能组成有效的括号; 2 那么 s[i] 为 ) 2.1 当 s[i-1] 为 (，那么 dp[i] = dp[i-2] + 2； 2.2 当 s[i-1] 为 ) 并且 s[i-dp[i-1] - 1] 为 (，那么 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]； 时间复杂度：O(n) */ public int longestValidParentheses(String s) { if (s == null || s.length() == 0) return 0; int[] dp = new int[s.length()]; int res = 0; for (int i = 0; i < s.length(); i++) { if (i > 0 && s.charAt(i) == ')') { if (s.charAt(i - 1) == '(') { dp[i] = (i - 2 >= 0 ? dp[i - 2] + 2 : 2); } else if (s.charAt(i - 1) == ')' && i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') { dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0); } } res = Math.max(res, dp[i]); } return res; } //Evaluate Reverse Polish Notatio（逆波兰表达式求值） public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for (int i = 0 ;i < tokens.length;i++){ String str = tokens[i]; if (str.length() == 1){ char ch = str.charAt(0); if (ch-'0' >= 0 && ch - '0' <= 9 ){ Integer a = Integer.valueOf(str); stack.push(a); } else{ if (stack.size() < 2) return 0; int num2 = stack.pop(); int num1 = stack.pop(); switch(ch){ case '+': stack.push(num1 + num2); break; case '-': stack.push(num1 - num2); break; case '*': stack.push(num1 * num2); break; case '/': stack.push(num1 / num2); break; } } }else{ int n = Integer.valueOf(str); stack.push(n); } } return stack.pop(); } 

TASK2.2 队列

2.2.1 用数组实现一个顺序队列

public class ArrayQueue<T> { private T [] data ; private int cnt;//元素个数 private int size;//队列长度 @SuppressWarnings("unchecked") public ArrayQueue(){ data =(T[]) new Object [10]; cnt = 0; size = 10; } @SuppressWarnings("unchecked") public ArrayQueue(int size){ data =(T[]) new Object [size]; cnt = 0; this.size = size; } public void add(T t){ if(cnt>=size){ throw new IllegalStateException(); } data[cnt]=t; cnt++; } public T remove(){ if(cnt<0){ throw new NoSuchElementException(); } T t= data[0]; data = Arrays.copyOfRange(data,0,size); cnt--; return t; } public boolean offer(T t){ if(cnt>=size){ return false; } data[cnt]=t; cnt++; return true; } public boolean pull(T t){ if(cnt<0){ return false; } data = Arrays.copyOfRange(data,0,size); cnt--; return true; } //返回队列头元素 public T element(){ return data[0]; } public boolean isEmpty(){ return cnt==0 ; } public boolean isFull(){ return cnt==size; } } 

2.2.2 用链表实现一个链式队列

public class ListQueue<T> { private List<T> data ; private int cnt;//元素个数 private int size;//队列长度(用链表的话这里可以强行定义) public ListQueue(){ data =new LinkedList<T>(); cnt = 0; size = 10; } public void add(T t){ data.add(t); cnt++; } public T remove(){ if(cnt<0){ throw new NoSuchElementException(); } T t= data.remove(cnt); cnt--; return t; } public boolean offer(T t){ if(cnt>=size){ return false; } data.add(t); cnt++; return true; } public boolean pull(T t){ if(cnt<0){ return false; } data.remove(cnt); cnt--; return true; } //返回队列头元素 public T element(){ return data.get(0); } public boolean isEmpty(){ return cnt==0 ; } public boolean isFull(){ return cnt==size; } } 

2.2.3 实现一个循环队列

public class MyCircularQueue { private final int capacity; private final int[] array; private int head = 0; private int tail = 0; private int count = 0; /** * Initialize your data structure here. Set the size of the queue to be k. */ public MyCircularQueue(int k) { this.capacity = k; this.array = new int[this.capacity]; } /** * Insert an element into the circular queue. Return true if the operation is successful. */ public boolean enQueue(int value) { //队列已满 if (count == capacity) { return false; } //队列为空, 重新设置头部 if (count == 0) { head = (head == capacity) ? 0 : head; tail = head; array[head] = value; count++; return true; } //队列未满 (有空位) if (tail == capacity - 1) { //tail 达到 maxIndex, 重置为 0 tail = 0; } else { //tail 未达到 maxIndex, tail++ tail++; } array[tail] = value; count++; return true; } /** * Delete an element from the circular queue. Return true if the operation is successful. */ public boolean deQueue() { if (count == 0) { //队列为空 return false; } count--; head++; return true; } /** * Get the front item from the queue. */ public int Front() { if (count == 0 ) { return -1; } return array[head]; } /** * Get the last item from the queue. */ public int Rear() { if (count == 0 ) { return -1; } return array[tail]; } /** * Checks whether the circular queue is empty or not. */ public boolean isEmpty() { return count == 0; } /** * Checks whether the circular queue is full or not. */ public boolean isFull() { return count == capacity; } } 

2.2.4 练习

//Design Circular Deque（设计一个双端队列） class MyCircularDeque { public int k; public int[] numbers; public int head; public int tail; /** Initialize your data structure here. Set the size of the deque to be k. */ public MyCircularDeque(int k) { numbers=new int[k+1]; head=0; tail=0; this.k=k; } /** Adds an item at the front of Deque. Return true if the operation is successful. */ public boolean insertFront(int value) { if(isFull()) return false; else{ head=(head+k)%(k+1); numbers[head]=value; return true; } } /** Adds an item at the rear of Deque. Return true if the operation is successful. */ public boolean insertLast(int value) { if(isFull()) return false; else{ numbers[tail]=value; tail=(tail+1)%(k+1); return true; } } /** Deletes an item from the front of Deque. Return true if the operation is successful. */ public boolean deleteFront() { if(isEmpty()) return false; else{ head=(head+1)%(k+1); return true; } } /** Deletes an item from the rear of Deque. Return true if the operation is successful. */ public boolean deleteLast() { if(isEmpty()) return false; else{ tail=(tail+k)%(k+1); return true; } } /** Get the front item from the deque. */ public int getFront() { if(isEmpty()) return -1; return numbers[head]; } /** Get the last item from the deque. */ public int getRear() { if(isEmpty()) return -1; return numbers[(tail+k)%(k+1)]; } /** Checks whether the circular deque is empty or not. */ public boolean isEmpty() { return tail==head; } /** Checks whether the circular deque is full or not. */ public boolean isFull() { return (tail+1)%(k+1)==head; } } //Sliding Window Maximum（滑动窗口最大值） class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(k==0){ return new int[0]; } List<Integer> list = new ArrayList<>();//存放窗口内的数字 int max = Integer.MIN_VALUE;//窗口内的最大数字 for(int i = 0; i<k;i++){ if(max<nums[i]){ max = nums[i]; } list.add(nums[i]); } int[] res = new int[nums.length - k + 1];//要返回的结果数据 res[0] = max; for(int i = k; i < nums.length;i++){ int z =list.remove(0);//移走第一位数并插入新的一位数 list.add(nums[i]); if(z!=max){//移走的数不是max，只需判断max与新插入的数哪个大 if(nums[i]> max){ max = nums[i]; } res[i-k+1] = max; }else{//移走的数是max，重新判断列表中哪个数是最大的 if(!list.contains(max)){ max = Integer.MIN_VALUE; for(Integer num : list){ if(max<num){ max = num; } } }else{ if(nums[i]> max){ max = nums[i]; } } } res[i-k+1] = max; } return res; } }

3 递归

3.1 编程实现斐波那契数列求值 f(n)=f(n-1)+f(n-2)

public static int Fibe(int n){ if(n==1) return 1; if(n==2) return 1; return Fibe(n-1)+Fibe(n-2); }

3.2 编程实现求阶乘 n!

public static int factorial(int n){ if(n==1) return 1; return factorial(n-1)*n; }

3.3 编程实现一组数据集合的全排列

class Solution { List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { permition(nums, 0, nums.length-1); return res; } public void permition(int[] nums, int p, int q){ if(p==q){ res.add(arrayToList(nums)); } for(int i = p; i <= q; i++){ swap(nums, i, p); permition(nums, p+1, q); swap(nums, i,p); } } private List<Integer> arrayToList(int[] nums){ List<Integer> res = new ArrayList<>(); for(int i = 0; i < nums.length; i++){ res.add(nums[i]); } return res; } private void swap(int[] nums, int i, int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }

3.4 练习

// Climbing Stairs（爬楼梯） //直接递归，但是直接递归leetcode竟然不能通过，于是又方法2 class Solution { public int climbStairs(int n) { if(n==1) return 1; if(n==2) return 2; return climbStairs(n-1)+climbStairs(n-2); } } //非递归放啊 class Solution { public int climbStairs(int n) { int [] ways = new int[n+1]; ways[0] = 0; for (int i = 1;i<ways.length;i++){ if (i < 3 ){ ways[i] = i; }else { ways[i] = ways[i-1] + ways[i-2]; } } return ways[n]; } }