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

精选留言(46)

• abner

  2019-02-11

   2

  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-05

   2

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

  展开
• abner

  2019-02-12

   1

  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

   1

  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

   1

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

  展开
• abner

  2019-02-11

   1

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

  展开
• 
  kai

  2019-02-11

   1

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

  展开
• 
  ALAN

  2019-02-08

   1

  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

   1

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

  展开
• 
  Sharry

  2019-02-20

  

  有意思, 递归的 LeeCode 题目, 使用简单粗暴的回溯法并没有办法通过, 还是得使用动态规划求解
• 
  hopeful

  2019-02-19

  

  #一组数据集合的全排列
  def f(start , b):
      a = list(b)
      if start==len(a):
          print(b)
      else:
          for i in range(start , len(a)):
              a[start] , a[i] = a[i] , a[start]
              c = tuple(a)
              f(start+1 , c)
              a[start] , a[i] = a[i] , a[start]

  展开
• 
  hopeful

  2019-02-15

  

  #实现快速排序、归并排序
  #---------快排(三数取中)---------
  def QuickSort():
      array = Array(10000)
      qsort(0 , len(array)-1 , array)
      return array
  def qsort(start , end , array):
      if start < end:
          key = partation(array , start , end)
          qsort(start , key-1 , array)
          qsort(key+1 , end , array)
  def swap(array , start , end):
      temp = array[start]
      array[start] = array[end]
      array[end] = temp
  def change(array , start , mid , end):
      if array[start] > array[mid]:
          swap(array , start , mid)
      if array[start]>array[end]:
          swap(array , start , end)
      if array[mid] > array[end]:
          swap(array , mid , end)
      swap(array , mid , start)
  def partation(array , start , end):
      #mid = int((start+end)/2)
      #change(array , start , mid , end)
      temp = array[start]
      while start < end :
          while start<end and array[end]<=temp:
              end-=1
          swap(array , start , end)
          while start<end and array[start]>=temp:
              start+=1
          swap(array , start , end)
      return start
  #---------------归并------------
  def merge(a , b):
      c = []
      i = 0
      j = 0
      while i<len(a) and j<len(b):
          if a[i] > b[j]:
              c.append(a[i])
              i+=1
          else:
              c.append(b[j])
              j+=1
      if i>=len(a):
          for k in range(j , len(b)):
              c.append(b[k])
      if j>=len(b):
          for k in range(i , len(a)):
              c.append(a[k])
      return c
  def devide(array):
      if len(array) == 1:
          return array
      else:
          mid = int((0 + len(array)) / 2)
          leftArray = devide(array[0:mid])
          rightArray = devide(array[mid:len(array)])
          return merge(leftArray , rightArray)
  def mergesort():
      array = Array(100)
      m = devide(array)
      return m

  展开
• 
  hopeful

  2019-02-15

  

  #冒泡、选择、插入排序
  import random
  import time
  def Array(n):
      a = []
      for i in range(n):
          a.append(random.randint(0 , n))
      return a
  #插入排序
  def insert():
      array = Array(100)
      time_start=time.time()
      for i in range(1 , len(array)):
          for j in range(i , 0 , -1):
              if array[j] > array[j-1]:
                  temp = array[j]
                  array[j] = array[j-1]
                  array[j-1] = temp
              else:
                  break
      time_end=time.time()
      print(array)
      print('totally cost',time_end-time_start)
  def select():
      array = Array(100)
      time_start=time.time()
      for i in range(len(array)):
          for j in range(i+1 , len(array)):
              if array[j] > array[i]:
                  temp = array[j]
                  array[j] = array[i]
                  array[i] = temp
      time_end=time.time()
      print(array)
      print('totally cost',time_end-time_start)
  def bubble():
      array = Array(100)
      time_start=time.time()
      for i in range(len(array)-1 , 0 , -1):
          flag = False
          for j in range(i):
              if array[j] > array[j+1]:
                  temp = array[j]
                  array[j] = array[j+1]
                  array[j+1] = temp
                  flag = True
          if not flag:
              break
      time_end=time.time()
      print(array)
      print('totally cost',time_end-time_start)

  展开
• 
  hopeful

  2019-02-15

  

  //阶乘n!
  def f(n):
      if(n<=1):
          return 1
      else:
          return f(n-1)*n

  展开
• 
  hopeful

  2019-02-15

  

  //斐波那契数列
  def f(n):
      if(n<=0):
          return 0
      elif(n==1):
          return 1
      else:
          return f(n-1)+f(n-2)

  展开
• 
  hopeful

  2019-02-15

  

  //数组实现顺序队列
  public class MyQueue {
      
      private Object[] object;
      private int count;
      
      MyQueue(int size){
          this.object = new Object[size];
          count = 0;
      }
  
      @Override
      public Object pop() {
          // TODO Auto-generated method stub
          if(count==0) {
              return null;
          }else {
              Object temp = object[0];
              count--;
              for (int i = object.length-1; i > 0 ; i--) {
                  object[i-1] = object[i];
              }
              return temp;
          }
      }
  
      @Override
      public void push(Object h) {
          // TODO Auto-generated method stub
          if( (count+1) >= object.length) {
              Object[] ob = new Object[2*object.length];
              System.arraycopy(object, 0, ob, 0, count);
              this.object = ob;
          }
          object[count] = h;
          count++;
      }
  
      @Override
      public Object getFirst() {
          // TODO Auto-generated method stub
          if(count==0)
              return null;
          else
              return object[0];
      }
  
      @Override
      public Object getLast() {
          // TODO Auto-generated method stub
          if(count==0)
              return null;
          else
              return object[count-1];
      }
  
      @Override
      public boolean empty() {
          // TODO Auto-generated method stub
          if(count==0) {
              return true;
          }else
              return false;
      }
  
      @Override
      public int size() {
          // TODO Auto-generated method stub
          return count;
      }
  
  }
  

  展开
• 
  hopeful

  2019-02-15

  

  //用链表实现顺序栈
  #include<stdlib.h>
  #define true 1
  #define false 0
  #define ok 1
  #define error 0
  #define infeasible 1
  #define overflow 0
  #define stack_size 50
  typedef struct{
      int *base;
      int *top;
      int stacksize;
  }sqstack;
  
  //构造一个空栈
  int create_stack(sqstack *s)
  {
      s->base=(int *)malloc(5*sizeof(int)); //开始分配50个整形空间
      if(!s->base) exit(overflow);
      s->top=s->base;
      s->stacksize=5;
      return 0;
  }
  
  //插入新元素为栈顶元素
  int stack_push(sqstack *s)
  {
      int e;
      if(s->top - s->base>=5)
      { //栈满 ，追加存储空间
          s->base = (int *)realloc(s->base,(5+1)*sizeof(int));
      if(!s->base) exit(overflow);//存储分配失败
      s->top = s->base + 5;//新扩充空间后的栈顶指针位置
      s->stacksize += 1;
      }
      printf("请输入要入栈的值:");
      scanf("%d",&e);
      *s->top++ = e;
      return 0;
  }
  
  //出栈
  int stack_pop(sqstack *s)
  {
      if(s->base == s->top) {printf("栈为空！不能出栈！"); return error;}
      --s->top;
      return 0;
  }
  
  //打印栈
  int stack_top(sqstack *s)
  {
      int *w;
      printf("The stack is :");
      w=s->base;
      while(w!=s->top)
      {
          printf(" %d ",*w++);
      }
      printf("\n");
  }

  展开
• 
  hopeful

  2019-02-15

  

  //数组实现顺序栈
  public class MyStack {
      Object[] object;
      private int count;
      MyStack(int size){
          this.object = new Object[size];
          count = 0;
      }
      public void push(Object h) {
          if( (count+1) >= object.length) {
              Object[] ob = new Object[2*object.length];
              System.arraycopy(object, 0, ob, 0, count);
              this.object = ob;
          }
          object[count] = h;
          count++;
      }
      public Object pop() {
          if(count==0) {
              return null;
          }else {
              count--;
              return object[count-1];
          }
      }
      public Object peek() {
          if(count==0) {
              return null;
          }else {
              return object[count-1];
          }
      }
      public void removeAll() {
          while(count!=0) {
              this.pop();
              count--;
          }
      }
      public boolean empty() {
          if(count==0) {
              return true;
          }else
              return false;
      }
      public int getCount() {
          return this.count;
      }

  展开
• 
  TryTs

  2019-02-14

  

  递归爬楼梯
  
  #include<iostream>
  using namespace std;
  int floor(int n){
      if(n == 0) return 1;
      else if(n == 1) return 1;
      else return floor(n - 1) + floor(n - 2);
  }
  int main(){
      int n;
      cin>>n;
      cout<<floor(n)<<endl;
  }

  展开
• abner

  2019-02-12

  

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

  展开

  编辑回复: 感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您99元专栏通用阅码，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。