算法笔记-第03节课

男娘i 2022-09-11 05:28 110阅读 0赞

## 第03节课 ##

### 1. 单向链表反转 ###

思路：带头指针的链表可以不使用返回值进行翻转，不带头指针的必须有返回值，函数的形参改变不影响调用端的值，引用改变影响调用端。

代码展示：

// 带链表头
    public void reverse1(ListNode head) { 
      if(head == null) return;
      ListNode ptr = head.next;
      ListNode ptrNext;
      head.next = null; // 这个必须置为null,否则会出现环
      while(ptr != null) { 
        ptrNext = ptr.next;
        ptr.next = head.next;
        head.next = ptr;
        ptr = ptrNext;
      }
    }
    
    // 不带链表头 两个变量 pre next 分别用于指定结果的头和当前迭代的临时下一个元素
    public ListNode reverse2(ListNode head) { 
      ListNode pre = null;
      ListNode next = null;
      while(node!=null) { 
        next = head.next;
        head.next = pre;
        pre = node;
        head = next;
      }
      return pre;
    }

### 2. 删除所有单向链表指定值的节点 ###

思路：

遍历链表，删除所有指定的值

代码展示：

// 带头部节点
    public static void deleteElements1(ListNode head, int element) { 
      if(head == null || head.next == null) return;
      ListNode pre = head;
      ListNode ptr = head.next;
      while(ptr != null) { 
        if(ptr.value = element) { 
          pre.next = ptr.next;
        } else { 
          pre = ptr;
        }
        ptr = ptr.next;
      }
    }
    
    // 不带头部节点
    public static ListNode deleteElements2(ListNode head, int element) { 
      if(head == null) return;
      while(head.value == element) { 
        head = head.next;
      }
      ListNode pre = head;
      ListNode ptr = head.next;
      while(ptr != null) { 
        if(ptr.value == element) { 
          pre.next = ptr.next;
        } else { 
          pre = ptr;
        }
        ptr = ptr.next;
      }
      return pre;
    }

### 3. 双向链表实现队列和栈 ###

思路：构建一个双向链表（带头）

static class DoubleEndsList { 
    
      static class DoubleEndsListNode { 
        public int data;
        public DoubleEndsListNode pre;
        public DoubleEndsListNode next;
    
      }
    
      private DoubleEndsListNode head;
      private DoubleEndsListNode tail;
      private int size;
    
      public DoubleEndsList() { 
        this.head = new DoubleEndsListNode();
        this.tail = new DoubleEndsListNode();
        head.pre = null;
        head.next = tail;
        tail.pre = head;
        tail.next = null;
        this.size = 0;
      }
    
      public void addToHead(int element) { 
        // 构建节点
        DoubleEndsListNode node = new DoubleEndsListNode();
        node.data = element;
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        this.size++;
      }
    
      public DoubleEndsListNode delFromHead() { 
        DoubleEndsListNode deletedNode = head.next;
        if (deletedNode != tail) { 
          head.next = deletedNode.next;
          if (head.next != null) { 
            head.next.pre = head;
          }
          this.size--;
          return deletedNode;
    
        } else { 
          return null;
        }
      }
    
      public void delElement(int element) { 
        DoubleEndsListNode ptr = head.next;
        while (ptr != tail) { 
          if (ptr.data == element) { 
            ptr.pre.next = ptr.next;
            ptr.next.pre = ptr.pre;
            this.size--;
          }
          ptr = ptr.next;
        }
      }
    
      public void addToTail(int element) { 
        // 构建节点
        DoubleEndsListNode node = new DoubleEndsListNode();
        node.data = element;
        node.next = tail;
        node.pre = tail.pre;
        tail.pre.next = node;
        tail.pre = node;
        this.size++;
      }
    
      public DoubleEndsListNode delFromTail() { 
        DoubleEndsListNode deletedNode = tail.pre;
        if (deletedNode != head) { 
          tail.pre = deletedNode.pre;
          if (tail.pre != null) { 
            tail.pre.next = tail;
          }
          this.size--;
          return deletedNode;
        } else { 
          return null;
        }
      }
    
      public void reverse1() { 
        if (head.next == tail || tail.pre == head) { 
          return;
        }
        DoubleEndsListNode ptr = head.next;
        DoubleEndsListNode next;
        head.next = tail;
        while (ptr != tail) { 
          next = ptr.next;
    
          ptr.pre = head;
          ptr.next = head.next;
          head.next.pre = ptr;
          head.next = ptr;
    
          ptr = next;
        }
      }
    
      public void reverse2() { 
        if (head.next == tail || tail.pre == head) { 
          return;
        }
        DoubleEndsListNode tmp;
        DoubleEndsListNode ptr = head.next;
        DoubleEndsListNode next;
        while (ptr != tail) { 
          next = ptr.next;
    
          tmp = ptr.next;
          ptr.next = ptr.pre;
          ptr.pre = tmp;
    
          ptr = next;
    
        }
        // 交换头尾
        DoubleEndsListNode tmp1 = head.next;
        DoubleEndsListNode tmp2 = tail.pre;
        tail.pre = tmp1;
        tmp1.next = tail;
        head.next = tmp2;
        tmp2.pre = head;
    
    
      }
    
      @Override
      public String toString() { 
        // 遍历链表，打印所有元素
        DoubleEndsListNode ptr = head.next;
        StringBuilder sb = new StringBuilder();
        while(ptr != tail) { 
          sb.append(ptr.data).append("\t");
          ptr = ptr.next;
        }
        sb.deleteCharAt(sb.length() -1);
        return sb.toString();
      }
    }

思路：构建一个双向队列(不带头)，然后使用双向队列实现栈和队列

public class DoubleEndsQueueNode<T> { 
    
      public T data;
      public DoubleEndsQueueNode prev;
      public DoubleEndsQueueNode next;
    
      public DoubleEndsQueueNode(T data) { 
        this.data = data;
      }
    }
    
    public class DoubleEndsQueue<T> { 
    
      public int size;
      public DoubleEndsQueueNode<T> head;
      public DoubleEndsQueueNode<T> tail;
    
      public DoubleEndsQueue() { 
        this.size = 0;
        this.head = null;
        this.tail = null;
      }
    
      public void pushToHead(T element) { 
        DoubleEndsQueueNode<T> node = new DoubleEndsQueueNode<>(element);
        if (head != null) { 
          node.next = head;
          head.prev = node;
          head = node;
        } else { 
          head = node;
          tail = node;
        }
        this.size++;
      }
    
      public T popFromHead() { 
        if (head == null) { 
          return null;
        }
        DoubleEndsQueueNode<T> node = head;
        if (head == tail) { 
          this.tail = null;
          this.head = null;
        } else { 
          head = head.next;
        }
        this.size--;
        return node.data;
    
      }
    
      public void pushToTail(T element) { 
        DoubleEndsQueueNode<T> node = new DoubleEndsQueueNode<>(element);
        if (tail != null) { 
          node.prev = tail;
          tail.next = node;
          tail = node;
        } else { 
          head = node;
          tail = node;
        }
        this.size++;
      }
    
      public T popFromTail() { 
        if (tail == null) { 
          return null;
        }
        DoubleEndsQueueNode<T> node = tail;
        if (head == tail) { 
          this.head = null;
          this.tail = null;
        } else { 
          tail = tail.prev;
        }
        this.size--;
        return node.data;
      }
    
      public boolean isEmpty() { 
        return size <= 0;
      }
    }
    
    public class MyQueue<T> { 
    
      private DoubleEndsQueue<T> dq = null;
    
      public MyQueue() { 
        this.dq = new DoubleEndsQueue<>();
      }
    
      public void push(T element) { 
        this.dq.pushToHead(element);
      }
    
      public T pop() { 
        return this.dq.popFromHead();
      }
    
      public boolean isEmpty() { 
        return this.dq.isEmpty();
      }
    }
    
    public class MyStack<T> { 
    
      private DoubleEndsQueue<T> dq = null;
    
      public MyStack() { 
        this.dq = new DoubleEndsQueue<>();
      }
    
      public void push(T element) { 
        this.dq.pushToHead(element);
      }
    
      public T pop() { 
        return this.dq.popFromTail();
      }
    
      public boolean isEmpty() { 
        return this.dq.isEmpty();
      }
    }

### 4. 循环数组实现队列 ###

思路：利用定长取模来定位位置，利用一个变量来记录队列中的元素个数

代码：

public class MyQueue { 
      private final int[] cache;
      private int size;
      private int head;
      private int tail;
      private final int cacheCapacity;
    
      public MyQueue(int cacheCapacity) { 
        this.cacheCapacity = cacheCapacity;
        this.head = 0;
        this.tail = 0;
        this.size = 0;
        this.cache = new int[cacheCapacity];
      }
    
      public void push(int e) throws RuntimeException { 
        if (size < cacheCapacity) { 
          this.cache[tail] = e;
          this.tail = (tail + 1) % cacheCapacity;
          this.size++;
        } else { 
          throw new RuntimeException("队列满,不能加入元素");
        }
      }
    
      public int pop() throws RuntimeException { 
        if (size > 0) { 
          int ret = this.cache[head];
          this.head = (head + 1) % cacheCapacity;
          this.size--;
          return ret;
        } else { 
          throw new RuntimeException("队列空,不能弹出元素");
        }
      }
    }

### 5. 获取栈中最小值，要求O(1) ###

思路1：使用两个栈，一个栈放入正规数据，另一个栈同步放入最小值（当前值小于栈顶，押入当前值，否则押入栈顶值），同步弹出

代码：

public class MyStack { 
    
      private Stack<Integer> stackData;
      private Stack<Integer> stackMin;
    
      public MyStack() { 
        this.stackData = new Stack<>();
        this.stackMin = new Stack<>();
      }
    
      public void push(Integer e) { 
        stackData.push(e);
        if(this.stackMin.isEmpty()) { 
          this.stackMin.push(e);
        } else { 
          Integer top = this.stackMin.peek();
          if(e < top) { 
            this.stackMin.push(e);
          } else { 
            this.stackMin.push(top);
          }
        }
      }
    
      public Integer pop() { 
        if(stackData.isEmpty()) { 
          throw new RuntimeException("栈中为空，无元素弹出.");
        }
        Integer e = stackData.pop();
        stackMin.pop();
        return e;
      }
    
      public Integer getMinElement() { 
        if (this.stackMin.isEmpty()) { 
          throw new RuntimeException("栈中为空,无法获取最小元素.");
        }
        return stackMin.peek();
      }
    
    }

思路2：使用两个栈，一个栈放入正规数据，另一个栈放入最小值（当前值小于栈顶，押入当前值，否则不压栈），弹出时如果弹出的当前值和下一个值相等，则不弹出出另一个栈，如果不想等，则弹出

代码：

// 采用两个基础栈，在添加的元素比最小栈元素小时添加
    public class MyStack { 
    
      private Stack<Integer> stackData;
      private Stack<Integer> stackMin;
    
      public MyStack() { 
        this.stackData = new Stack<>();
        this.stackMin = new Stack<>();
      }
    
      public void push(Integer e) { 
        this.stackData.push(e);
        if(this.stackMin.isEmpty()) { 
          this.stackMin.push(e);
        } else { 
          Integer top = this.stackMin.peek();
          if(e <= top) { 
            this.stackMin.push(e);
          }
        }
      }
    
      public Integer pop() { 
        if(stackData.isEmpty()) { 
          throw new RuntimeException("栈中为空，无元素弹出.");
        }
        Integer e = stackData.pop();
    
        if(this.stackMin.peek() >= e) { 
          this.stackMin.pop();
        }
        return e;
      }
    
      public Integer getMinElement() { 
        if (this.stackMin.isEmpty()) { 
          throw new RuntimeException("栈中为空,无法获取最小元素.");
        }
        return stackMin.peek();
      }
    }

### 6. 两个栈模仿队列 ###

思路：使用两个栈模仿队列，需要注意一个原则，就是stackPop只有在没有元素的时候才能倒入stackPush的元素，并且一次性倒完。

代码：

public static class TwoStacksQueue { 
    
      public Stack<Integer> stackPush;
      public Stack<Integer> stackPop;
    
      public TwoStacksQueue() { 
        stackPush = new Stack<>();
        stackPop = new Stack<>();
      }
    
      // 进队列
      public void push(Integer value) { 
        this.stackPush.push(value);
      }
    
      // 出队列
      public Integer poll() { 
        // 弹出队列没有数据，则从stackPush倒入数据
        if (this.stackPop.isEmpty()) { 
          while (!this.stackPush.isEmpty()) { 
            this.stackPop.push(this.stackPush.pop());
          }
          if (this.stackPop.isEmpty()) { 
            throw new RuntimeException("没有元素弹出");
          }
        }
        return this.stackPop.pop();
      }
    
      // 获取队列对首元素
      public Integer peek() { 
        if (this.isEmpty()) { 
          throw new RuntimeException("队列为空");
        }
        pushToPop();
        return this.stackPop.peek();
      }
    
      // 两个栈倒元素
      private void pushToPop() { 
        if (stackPop.empty()) { 
          while (!stackPush.empty()) { 
            stackPop.push(stackPush.pop());
          }
        }
      }
    
      public boolean isEmpty() { 
        return this.stackPop.isEmpty() && this.stackPush.isEmpty();
      }
    }

### 7. 两个队列模仿栈 ###

思路：在需要读取栈顶元素或者弹出时，两个队列来回倒，然后获取最后一个元素（代码的两个方法采用两种方法实现）

代码：

public static class TwoQueueStack<T> { 
      public Queue<T> queue;
      public Queue<T> help;
    
      public TwoQueueStack() { 
        queue = new LinkedList<>();
        help = new LinkedList<>();
      }
      // 压栈
      public void push(T value) { 
        queue.offer(value);
      }
      // 弹出
      public T pop() { 
        if(queue.isEmpty()) throw new RuntimeException("没有元素弹出");
        if(queue.size() == 1) { 
          return queue.poll();
        }
        T prev = queue.poll();
        while (!queue.isEmpty()) { 
          help.offer(prev);
          prev = queue.poll();
        }
        // 对调
        Queue<T> tmp = this.queue;
        this.queue = help;
        this.help = tmp;
        return prev;
      }
      
      // 查看栈顶元素
      public T peek() { 
        while (queue.size() > 1) { 
          help.offer(queue.poll());
        }
        T ans = queue.poll();
        help.offer(ans);
        // 对调
        Queue<T> tmp = this.queue;
        this.queue = help;
        this.help = tmp;
        
        return ans;
      }
      public boolean isEmpty() { 
        return queue.isEmpty();
      }
    
    }

### 8. 递归获取乱序队列中的最大值 ###

思想：采用二分法递归方式获取数组中最大值

代码：

public int getMax(int[] arr) { 
      return process(arr, 0, arr.length - 1);
    }
    
    private int process(int[] arr, int L, int R) { 
      if (L == R) { 
        return arr[L];
      }
      int M = L + ((R - L) >> 1);
      int leftMax = process(arr, L, M);
      int rightMax = process(arr, M + 1, R);
      return leftMax > rightMax ? leftMax : rightMax;
    }