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

精选留言(50)

• 

  李皮皮皮皮皮

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

  2019-02-05

  

   5
• 

  abner

  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

  

   2
• 

  kai

  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

  

   2
• 

  abner

  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

  

   1
• 

  abner

  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

  

   1
• 

  abner

  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

  

   1
• 

  abner

  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

  

   1
• 

  ALAN

  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

  

   1
• 

  TryTs

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

  2019-02-06

  

   1
• 

  Hxz

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

  2019-10-12

  

  
• 

  Geek_18b741

  再做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-09-11

  

  
• 

  猫猫

  全排列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]])
    }
  }

  2019-08-26

  

  
• 

  懒猫

  练完打卡

  2019-05-22

  

  
• 

  Sharry

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

  2019-02-20

  

  
• 

  hopeful

  #一组数据集合的全排列
  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]

  2019-02-19

  

  
• 

  hopeful

  #实现快速排序、归并排序
  #---------快排(三数取中)---------
  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

  2019-02-15

  

  
• 

  hopeful

  #冒泡、选择、插入排序
  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)

  2019-02-15

  

  
• 

  hopeful

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

  2019-02-15

  

  
• 

  hopeful

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

  2019-02-15

  

  
• 

  hopeful

  //数组实现顺序队列
  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;
  }
  
  }
  

  2019-02-15

  

  