【九章算法基础班】数据结构

Outline

• 线性数据结构
  • Queue
  • Stack
  • HashTable
• 树形数据结构
  • Heap/Priority Queue
  • TreeMap

队列Queue

• 支持操作：Push/Pop/Top，时间复杂度都是$O(1)$
• 考点：宽度优先搜索BFS
• 多做做BFS就可以了

栈Stack

• 支持操作：Push/Pop/Top，时间复杂度都是$O(1)$
• 考点：非递归实现DFS

例题Min Stack

题目

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• getMin() — Retrieve the minimum element in the stack.

Example:

> MinStack minStack = new MinStack();
> minStack.push(-2);
> minStack.push(0);
> minStack.push(-3);
> minStack.getMin();   --> Returns -3.
> minStack.pop();
> minStack.top();      --> Returns 0.
> minStack.getMin();   --> Returns -2.
>

要求实现一个stack能够在0(1)时间内实现push(x),pop(),top(),getMin()获取最小值

思路

额外维护一个stack，存储最小值

代码

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class MinStack {
    Stack<Integer> queue;
    Stack<Integer> minqueue;
    //int min = Integer.MAX_VALUE;

    /** initialize your data structure here. */
    public MinStack() {
        queue = new Stack<>();
        minqueue = new Stack<>();
    }

    public void push(int x) {
        queue.add(x);
        int min;
        if(minqueue.isEmpty()){
            min = x;
        }
        else {
            if (x < minqueue.peek()) {
                min = x;
            }
            else min = minqueue.peek();
        }
        minqueue.add(min);
    }

    public void pop() {
        queue.pop();
        minqueue.pop();
    }

    public int top() {
        return queue.peek();
    }

    public int getMin() {
        return minqueue.peek();
    }
}

Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) — Push element x to the back of queue.
• pop() — Removes the element from in front of queue.
• peek() — Get the front element.
• empty() — Return whether the queue is empty.

用stack实现queue

stack：先进后出

queue：先进先出

需要两个stack实现一个queue。

push时先将元素压入stack1，然后当pop时，如果stack2非空，就从stack2中pop出一个，否则将stack1中元素全部加入stcak2之后再pop

import java.util.Stack;
public class MyQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        stack1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    /** Get the front element. */
    public int peek() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        if(stack2.isEmpty() && stack1.isEmpty()){
            return true;
        }
        else {
            return false;
        }
    }
}

Largest Rectangle in Histogram

题目

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

求直方图中的最大举行的面积。

分析

baseline：

两个指针i和j分别从前往后扫描，k在i和j之间扫描，找i和j中间最低的柱子Kmin，计算Kmin*(j-i)的最大值。时间复杂度$O(n^3)$

优化：

K从左向右遍历，在每一位置，向左看，找到左边第一个比它小的位置i，向右看，找到右边第一个比他小的位置j，此时矩形面积为$K*(j-i-1)$ ，找到最小的即可。时间复杂度$O(n^2)$

Stack：

对于任意一个bar n，我们得到的包含该bar n的矩形区域里面bar n是最小的。我们使用ln和rn来表示bar n向左以及向右第一个小于bar n的bar的索引位置。

我们可以从左到右遍历所有bar，并将其push到一个stack中，如果当前bar的高度小于栈顶bar，我们pop出栈顶的bar，同时以该bar计算矩形面积。那么我们如何知道该bar的ln和rn呢？rn就是当前遍历到的bar的索引，而ln则是弹出当前元素之后的栈顶bar的索引，因为此时栈顶中的元素都是递增的。

为了更好的处理最后一个bar的情况，我们在实际中会插入一个高度为0的bar，这样就能pop出最后一个bar并计算了。

stack中存储的是下标！！！

时间复杂度$O(n)$

代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for(int i = 0 ; i < heights.length;i++){
            while (stack.peek() != -1 && heights[i] < heights[stack.peek()]){
                int size = heights[stack.pop()] * (i-stack.peek()-1);
                max = Math.max(max,size);
            }
            stack.push(i);
        }
        while (stack.peek() != -1){
            int size = heights[stack.pop()] * (heights.length-stack.peek()-1);
            max = Math.max(max,size);
        }
        return max;
    }
}

Maximal Rectangle

题目

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

For example, given the following matrix:

> 1 0 1 0 0
> 1 0 1 1 1
> 1 1 1 1 1
> 1 0 0 1 0
>
>

题目给定一个01矩阵，要求求出矩阵中面积最大的全1矩阵。

思路

把每一行看作直方图的底，可以把这个题转化成上一道题，对每一行建立一个直方图，利用stack求直方图中的最大矩形，返回全局最大矩形的面积。

代码

class Solution {
    public int calMax(char[][] matrix,int[] heights){
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int j = 0; j < heights.length;j++){
            while(stack.peek() != -1 && heights[j] < heights[stack.peek()]){
                int area = heights[stack.pop()] * (j - stack.peek()- 1);
                max = Math.max(max,area);
            }
            stack.push(j);
        }
        while(stack.peek() != -1){
            int area = heights[stack.pop()] * (heights.length - stack.peek()- 1);
            max = Math.max(max,area);
        }
        return max;
    }


    public int maximalRectangle(char[][] matrix) {
        int maxArea = 0;
        if(matrix.length == 0){
            return 0;
        }
        int[] heights = new int[matrix[0].length];
        for(int i = 0 ; i <matrix.length;i++){
            //计算本行heights
            for(int j = 0 ; j < matrix[0].length;j++){
                if(matrix[i][j] == '0'){
                    heights[j] = 0;
                }
                else {
                    heights[j] += 1;
                }
            }
            maxArea = Math.max(maxArea,calMax(matrix,heights));
        }
        return maxArea;
    }
}

Implement Stack using Queues

Implement the following operations of a stack using queues.

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• empty() — Return whether the stack is empty.

题目要求用队列实现栈。

方法一：

用两个queue实现，push时间复杂度$O(1)$ , pop时间复杂度$O(n)$

push的时候加入queue1:

pop的时候利用queue1，每次pop的时候将queue1中的元素放到queue2，保留一个pop，然后再把queue1和queue2交换，此时queue2又是空的了。

Queue<Integer> queue1;
Queue<Integer> queue2;

/** Initialize your data structure here. */
public MyStack() {
  queue1 = new LinkedList<>();
  queue2 = new LinkedList<>();
}

/** Push element x onto stack. */
public void push(int x) {
  queue1.add(x);

}

/** Removes the element on top of the stack and returns that element. */
public int pop() {
  int size = queue1.size();
  while(size > 1){
    queue2.add(queue1.remove());
    size--;
  }
  int res = queue1.poll();
  Queue<Integer> temp = queue1;
  queue1 = queue2;
  queue2 = temp;
  return res;
}

/** Get the top element. */
public int top() {
  int size = queue1.size();
  while(size > 1){
    queue2.add(queue1.remove());
    size--;
  }
  int res = queue1.peek();
  queue2.add(queue1.remove());
  Queue<Integer> temp = queue1;
  queue1 = queue2;
  queue2 = temp;
  return res;
}

/** Returns whether the stack is empty. */
public boolean empty() {
  return queue1.isEmpty();
}

方法二：

用两个queue实现，push时间复杂度$O(n)$ , pop时间复杂度$O(1)$

push时先将元素push进queue2,然后将queue2中元素加入queue2，然后交换queue1和queue2

pop时直接pop q1中元素

Queue<Integer> queue1;
Queue<Integer> queue2;

/** Initialize your data structure here. */
public MyStack() {
  queue1 = new LinkedList<>();
  queue2 = new LinkedList<>();
}

/** Push element x onto stack. */
public void push(int x) {
  queue2.add(x);
  while(!queue1.isEmpty()){
    queue2.add(queue1.remove());
  }
  Queue<Integer> temp = queue1;
  queue1 = queue2;
  queue2 = temp;
}

/** Removes the element on top of the stack and returns that element. */
public int pop() {
  return queue1.poll();
}

/** Get the top element. */
public int top() {
  return queue1.peek();
}

/** Returns whether the stack is empty. */
public boolean empty() {
  return queue1.isEmpty();
}

方法三：

用一个队列实现，push时间复杂度$O(n)$ , pop时间复杂度$O(1)$

public class MyStack {
    Queue<Integer> queue;

    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        queue.add(x);
        int size = queue.size();
        while(size > 1){
            queue.add(queue.poll());
            size--;
        }
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();

    }

    /** Get the top element. */
    public int top() {
        return queue.peek();

    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

Next Greater Element I

题目

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1‘s elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:

> Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
> Output: [-1,3,-1]
> Explanation:
>     For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
>     For number 1 in the first array, the next greater number for it in the second array is 3.
>     For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
>
>

>

Example 2:

> Input: nums1 = [2,4], nums2 = [1,2,3,4].
> Output: [3,-1]
> Explanation:
>     For number 2 in the first array, the next greater number for it in the second array is 3.
>     For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
>

给定数组nums2,nums1中的元素来自nums2,返回nums1中的元素在nums2中右边第一个比它的大元素。

分析

baseline：两层循环，在nums2中寻找右边第一个比它大的,时间复杂度$O(m*n)$

优化：利用栈+hashmap

将nums2中元素依次入栈：

1. 如果当前元素<栈顶元素,压栈
2. 当前元素i>栈顶元素j，弹出栈顶元素i，此时i右边第一个大于i的元素为j，可以加入hashmap中
3. 一次出栈之后如果还是满足当前元素i>栈顶元素j，重复2知道栈为空或者站顶元素>当前元素，将i压栈

时间复杂度$O(m+n)$

代码

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    int[] result = new int[nums1.length];
    LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>();
    for(int i = 0 ;i < nums1.length;i++){
        map.put(nums1[i],-1);
    }

    Stack<Integer> stack = new Stack<>();
    for(int i = 0;i < nums2.length;i++){
        //如果栈空，入栈
        if(stack.isEmpty() || nums2[i] < stack.peek()){
            stack.push(nums2[i]);
        }
        else{
            while (!stack.isEmpty() && nums2[i] > stack.peek()){
                int val = stack.pop();
                if(map.containsKey(val)){
                    map.put(val,nums2[i]);
                }
            }
            stack.push(nums2[i]);
        }
    }
    int ii = 0;
    for(Integer val:map.values()){
        result[ii] = val;
        ii++;
    }
    return result;
}

Next Greater Element II

题目

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, output -1 for this number.

Example 1:

> Input: [1,2,1]
> Output: [2,-1,2]
> Explanation: The first 1's next greater number is 2; 
> The number 2 can't find next greater number; 
> The second 1's next greater number needs to search circularly, which is also 2.
>

给定一个循环数组，返回数组中每个数字x右边第一个比x大的数字

思路

和上一题一样的思路，但这次需要吧数组扩大2倍，做同样的操作

加入stack的元素是数组的下标，这样可以方便后面存储比x大的数字。

代码

public int[] nextGreaterElements(int[] nums) {
    int[] result = new int[nums.length];
    Arrays.fill(result,-1);
    Stack<Integer> stack = new Stack<>();
    for(int i = 0;i < 2*nums.length-1;i++){
        if(stack.isEmpty() || nums[stack.peek()] >= nums[i%nums.length]){
            stack.push(i%nums.length);
        }
        else {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i%nums.length]){
                int idx = stack.pop();
                result[idx] = nums[i%nums.length];
            }
            stack.push(i%nums.length);
        }
    }
    return result;
}

Decode String

题目

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

> s = "3[a]2[bc]", return "aaabcbc".
> s = "3[a2[c]]", return "accaccacc".
> s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
>

分析

利用stack，从左向右遍历字符串：

1. 遇到数字：数字可能不止一位，因此继续遍历，累加数字，直到遇到非数字，将数字入栈
2. 遇到字母和’[‘：入栈
3. 遇到’]’：出栈，将字母加入字符串直到遇见’[‘，将’[‘弹出，将前面的数字弹出，计算完字符串之后入栈
4. 重复上面操作，最后将stack中的字符串弹出连接成最终结果

代码

class Solution {
    public String decodeString(String s) {
        StringBuilder reusult = new StringBuilder();
        Stack<String> stack = new Stack<>();
        int i = 0;
        while(i < s.length()){
            //数字
            if(Character.isDigit(s.charAt(i))){
                int num = 0;
                while (Character.isDigit(s.charAt(i))){
                    num = num * 10 + (s.charAt(i)-'0');
                    i++;
                }
                stack.push(String.valueOf(num));
            }
            //字母和‘[’
            else if(s.charAt(i) != ']'){
                stack.push("" + s.charAt(i));
                i++;
            }
            else {
                StringBuilder temp = new StringBuilder();
                while(!stack.peek().equals("[")){
                    temp.insert(0,stack.pop());
                }
                stack.pop();
                int times = Integer.parseInt(stack.pop());
                StringBuilder ntemp = new StringBuilder();
                while (times > 0){
                    ntemp = ntemp.append(temp);
                    times--;
                }
                stack.push(ntemp.toString());
                i++;
            }
        }
        while (!stack.isEmpty()){
            reusult.insert(0,stack.pop());
        }
        return reusult.toString();
    }
}

Remove Duplicate Letters

题目

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

移除字符串中重复的字母，保证字母间的相对顺序不变，返回结果中字典序最小的结果。

思路

这道题让我们移除重复字母，使得每个字符只能出现一次，而且结果要按字母顺序排，前提是不能打乱其原本的相对位置。我们的解题思路是：先建立一个哈希表来统计每个字母出现的次数，还需要一个visited数字来纪录每个字母是否被访问过，我们遍历整个字符串，对于遍历到的字符，先在哈希表中将其值减一，然后看visited中是否被访问过，若访问过则继续循环，说明该字母已经出现在结果中并且位置已经安排妥当。如果没访问过，我们和结果中最后一个字母比较，如果该字母的ASCII码小并且结果中的最后一个字母在哈希表中的值不为0(说明后面还会出现这个字母)，那么我们此时就要在结果中删去最后一个字母且将其标记为未访问，然后加上当前遍历到的字母，并且将其标记为已访问，以此类推直至遍历完整个字符串s，此时结果里的字符串即为所求。

代码

public String removeDuplicateLetters(String s) {
    StringBuilder res = new StringBuilder();
    Stack<String> stack = new Stack<>();
    int[] map = new int[26];
    boolean[] visited = new boolean[26];

    for(int i = 0;i < s.length();i++){
        map[s.charAt(i)-'a']++;
    }

    for(int i = 0;i < s.length();i++){if(visited[s.charAt(i)-'a']){
            map[s.charAt(i)-'a']--;
            continue;
        }
        else {
            while (!stack.isEmpty() && s.charAt(i) < stack.peek().charAt(0) && map[stack.peek().charAt(0)-'a'] > 0){
                visited[stack.peek().charAt(0)-'a'] = false;
                stack.pop();
            }
            stack.push(String.valueOf(s.charAt(i)));
            visited[s.charAt(i)-'a'] = true;
            map[s.charAt(i)-'a']--;
        }
    }
    while (!stack.isEmpty()){
        res.insert(0,stack.pop());
    }
    return res.toString();
}

Basic Calculator

题目

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negativeintegers and empty spaces ``.

You may assume that the given expression is always valid.

Some examples:

> "1 + 1" = 2
> " 2-1 + 2 " = 3
> "(1+(4+5+2)-3)+(6+8)" = 23
>

分析

这道题让我们实现一个基本的计算器来计算简单的算数表达式，而且题目限制了表达式中只有加减号，数字，括号和空格。我们需要一个栈来辅助计算，用个变量sign来表示当前的符号，由于有括号的存在，所以用变量res存储当前括号中计算的结果，将之前计算结果存在栈里。

我们遍历给定的字符串s：

1. 如果遇到了数字，由于可能是个多位数，所以我们要用while循环把之后的数字都读进来，然后用sign*num来更新结果res；
2. 如果遇到了加号，则sign赋为1，如果遇到了符号，则赋为-1；
3. 如果遇到了左括号，则把当前结果res和符号sign压入栈，res重置为0，sign重置为1；
4. 如果遇到了右括号，结果res乘以栈顶的符号，栈顶元素出栈，结果res加上栈顶的数字，栈顶元素出栈。

代码

public int calculate(String s) {
    Stack<Integer> stack = new Stack<>();
    int res = 0;
    int sign = 1;
    int i = 0;
    while(i < s.length()){
        if(Character.isDigit(s.charAt(i))){
            int sum = 0;
            while(i <s.length() && Character.isDigit(s.charAt(i))){
                sum = sum*10 + s.charAt(i)-'0';
                i++;
            }
            res += sum * sign;
        }
        else if(s.charAt(i) == '+'){
            sign = 1;
            i++;
        }
        else if(s.charAt(i) == '-'){
            sign = -1;
            i++;
        }
        else if(s.charAt(i) == '('){
            stack.push(res);
            stack.push(sign);
            i++;
            res = 0;
            sign = 1;
        }
        else if(s.charAt(i) == ')'){
            res *= stack.pop();
            res += stack.pop();
            i++;
        }
      else{i++;}
    }
    return res;
}

Basic Calculator II

题目

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces ``. The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

> "3+2*2" = 7
> " 3/2 " = 1
> " 3+5 / 2 " = 5
>

加减乘除运算，没有括号，求结果

思路

用一个变量sign存储符号，用stack存储计算完的值。

遍历字符串：

1. 遇到符号：更新sign
2. 遇到数字，计算数字num，根据sign的值入栈：
   1. sign==’+’:num入栈
   2. sign==’-‘:-num入栈
   3. sign==’*’:和栈顶元素做乘法后入栈
   4. sign==’/‘:和栈顶元素做除法后入栈
3. 最后将栈中所有元素弹出做加法得到result

总之核心思想就是将减法转化成相反数入栈，将*和/计算之后入栈，最后就都转化成加法了

代码

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        char sign = '+';
        for(int i = 0; i < s.length();i++){
            //记录符号
            if(s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '*' || s.charAt(i) == '/'){
                sign = s.charAt(i);
            }
            //如果是数字
            if(Character.isDigit(s.charAt(i))){
                int sum = 0;
                while(i < s.length() && Character.isDigit(s.charAt(i))){
                    sum = sum*10 + (s.charAt(i)-'0');
                    i++;
                }
                i--;
                if(sign == '+'){
                    stack.push(sum);
                }
                if(sign == '-'){
                    stack.push(-sum);
                }
                if(sign == '*'){
                    stack.push(stack.pop() * sum);
                }
                if(sign == '/'){
                    stack.push(stack.pop()/sum);
                }
            }
        }
        int res = 0;
        while (!stack.isEmpty()){
            res += stack.pop();
        }
        return res;
    }
}

Flatten Nested List Iterator

题目

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,[6]]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

给定一个list，里面元素是nestedInteger,可能是Integer，也可能是个IntegerList,要求实现hasNext()和next()函数

思路

利用stack

1. 初始化：将给定list中的元素都放入stack

2. 在hasNext()中，如果栈顶元素是Integer直接返回true,如果不是Integer则是个List,遍历这个List将元素入栈。

   循环上面的操作，直到栈空如果依然没有integer则返回false

3. next()函数直接pop()

代码

import java.util.Iterator;
import java.util.List;
import java.util.Stack;

public class FlattenNestedListIterator {
    public interface NestedInteger {
        // @return true if this NestedInteger holds a single integer, rather than a nested list.
        public boolean isInteger();

        // @return the single integer that this NestedInteger holds, if it holds a single integer
        // Return null if this NestedInteger holds a nested list
        public Integer getInteger();

        // @return the nested list that this NestedInteger holds, if it holds a nested list
        // Return null if this NestedInteger holds a single integer
        public List<NestedInteger> getList();
    }
    public class NestedIterator implements Iterator<Integer> {
        Stack<NestedInteger> stack = new Stack();
        public NestedIterator(List<NestedInteger> nestedList) {
            for(int i = nestedList.size()-1;i >=0;i--){
                stack.push(nestedList.get(i));
            }
        }

        @Override
        public Integer next() {
            return stack.pop().getInteger();
        }

        @Override
        public boolean hasNext() {
            while (!stack.isEmpty()) {
                if (stack.peek().isInteger()) {
                    return true;
                }
                else {
                    List<NestedInteger> list = stack.pop().getList();
                    for (int i = list.size() - 1; i >= 0; i--) {
                        stack.push(list.get(i));
                    }
                }
            }
            return false;
        }
    }
}

Simplify Path

题目

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

• Did you consider the case where path = "/../"?
  In this case, you should return "/".
• Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
  In this case, you should ignore redundant slashes and return "/home/foo".

思路

linux系统中“../”代表上层文件夹，“./”代表当前文件夹

利用stack存储路径

将给定字符串按“/”分割：

1. 遇到.和空字符串跳过，遇到“..”pop栈顶字符串
2. 遇到正常字符串push(“/“+str)

代码

class Solution {
    public String simplifyPath(String path) {
        if(path.length()==0){
            return "";
        }
        Stack<String> stack = new Stack<>();
        for(String str : path.split("/")){
            //遇到..
            if(str.equals("..")){
                if(!stack.isEmpty()){
                    stack.pop();
                }
            }
            //遇到.或者空字符串，跳过
            else if(str.equals(".") || str.equals("")){
                continue;
            }
            else {
                stack.push("/"+str);
            }
        }
        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()){
            res.insert(0,stack.pop());
        }
        if(res.length() == 0){
            return "/";
        }
        return res.toString();
    }
}

Verify Preorder Sequence in Binary Search Tree

题目

验证一个序列是否是BST的中序遍历

思路

BST根节点左边的元素都比根节点小，右边的元素都比跟节点大

利用这个性质，用一个栈和一个low变量来维护遍历过程

当出现比根大的元素之后，说明在根节点的右子树，此后就不可能出现比根小的元素了

代码

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Stack<Integer> stack = new Stack<>();
        int low = Integer.MIN_VALUE;
        for(int p : preorder){
            if(p < low){
                return false;
            }
            while(!stack.isEmpty() && p>stack.peek()){
                low = stack.pop();
            }
            stack.push(p);
        }
        return true;
    }
}

Mini Parser

题目

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

• String is non-empty.
• String does not contain white spaces.
• String contains only digits 0-9, [, - ,, ].

Example 1:

> Given s = "324",
>
> You should return a NestedInteger object which contains a single integer 324.
>
>

>

Example 2:

> Given s = "[123,[456,[789]]]",
>
> Return a NestedInteger object containing a nested list with 2 elements:
>
> 1. An integer containing value 123.
> 2. A nested list containing two elements:
>     i.  An integer containing value 456.
>     ii. A nested list with one element:
>          a. An integer containing value 789.
>

思路

利用stack，每次遇到’[‘就新建一个nest放入stack,遇到，或者‘]’代表一个数字结束，放入栈顶的nest里

如果遇到的是‘]’还需要将栈顶的第一个nest嵌套入前一个nest中，最后栈中只有一个nest

代码

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public NestedInteger deserialize(String s) {
        if(s.length()==0){
            return new NestedInteger();
        }
        if(s.charAt(0) != '['){
            return new NestedInteger(Integer.parseInt(s));
        }
        Stack<NestedInteger> stack = new Stack<>();
        //NestedInteger nest = new NestedInteger();//存储当前未入栈nest
        int left = 0;
        for(int i = 0;i < s.length();i++){
            //遇到'['新建一个NestedInteger放入栈里
            if(s.charAt(i) == '['){
                stack.push(new NestedInteger());
                left = i+1;
            }
            //遇到','||']'将left和i之间的数字放入栈顶的nestedInteger里
            else if(s.charAt(i) == ',' || s.charAt(i) == ']'){
                if(left < i){
                    NestedInteger nest = new NestedInteger(Integer.parseInt(s.substring(left,i)));
                    NestedInteger top = stack.pop();
                    top.add(nest);
                    stack.push(top);
                }
                left = i+1;
              //遇到']'，将stack中nested嵌套，最后只剩一个nest
                if (s.charAt(i) == ']'){
                    if(stack.size() > 1){
                        NestedInteger first = stack.pop();
                        NestedInteger second = stack.pop();
                        second.add(first);
                        stack.push(second);
                    }
                }
            }
        }
        return stack.pop();
    }
}

Verify Preorder Serialization of a Binary Tree

题目

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.

>      _9_
>     /   \
>    3     2
>   / \   / \
>  4   1  #  6
> / \ / \   / \
> # # # #   # #
>
>

>

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where #represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false

给定一个二叉树的前序遍历，#代表空节点，判断是否是一个二叉树

思路

方法一：利用stack

遍历节点，压栈，如果遇到“#”，且当前栈顶也是“#”说明栈顶#前面的那个节点已经有两个空子节点了，则将栈顶的#和前一个节点弹出，压入一个“#”表示空节点，有点类似于剪枝，下面的如果是二叉树，就剪枝。

过程中如果有stack为空，则不是二叉树

最后如果栈里只剩一个“#”了就是二叉树

方法二：

根据节点的出度和入度

二叉树中，每增加一个非叶子节点增加2个出度1个入度，增加一个叶子节点增加0个出度1个入度

用一个变量diff记录出度-入度的差

跟节点时diff=1;

每增加一个非叶子节点diff+1;

每增加一个叶子节点diff-1;

在这个过程中diff应该恒大于0.

最后满二叉树的出度应该等于入度

代码

方法一：

public boolean isValidSerialization(String preorder) {
    String[] str = preorder.split(",");
    Stack<String> stack = new Stack<>();
    for(int i = 0 ; i < str.length;i++){
        while (str[i].equals("#") && !stack.isEmpty() && stack.peek().equals("#")){
            stack.pop();
            if(stack.isEmpty()){
                return  false;
            }
            stack.pop();
        }
        stack.push(str[i]);
    }
    return stack.size()==1 && stack.peek().equals("#");
}

方法二：

public boolean isValidSerialization(String preorder) {
    String[] str = preorder.split(",");
    int diff = 1;
    for(int i = 0 ; i < str.length;i++){
        diff--;
        if(diff < 0){
            return false;
        }
        if(!str[i].equals("#")){
            diff+=2;
        }
    }
    return diff==0;
}

Closest Binary Search Tree Value II

题目

给定一个BST，一个target，一个k

返回BST中和target最接近的k个节点的值。

思路

根据性质BST的中序遍历是递增序列

所以用栈实现BST的中序遍历。又因为求k个最接近的，也就是差值的绝对值最小的k个，可以用维护一个最大堆的方法。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        class Node{
            int val;
            double delta;
            Node(int val,double delta){
                this.delta = delta;
                this.val = val;
            }
        }
        Comparator<Node> cmp = new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if(o2.delta > o1.delta){
                    return 1;
                }
                else {return -1;}
            }
        };
        PriorityQueue<Node> heap = new PriorityQueue<>(cmp);
        //中序遍历
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curt = root;
        while (curt != null || !stack.isEmpty()){
            while(curt!= null){
                stack.push(curt);
                curt = curt.left;
            }
            if(!stack.isEmpty()){
                curt = stack.pop();
                int val = curt.val;
                //System.out.println(val);
                double delta = Math.abs(target-val);
                if(heap.size() == k && delta > heap.peek().delta){
                    //System.out.println("hh");
                    break;
                }
                else {
                    heap.add(new Node(val,delta));
                    if(heap.size() > k){
                        heap.poll();
                    }
                }
                curt = curt.right;
            }
        }
        List<Integer> res = new ArrayList<>();
        while(k > 0){
            res.add(heap.poll().val);
            k--;
        }
        return res;
    }
}

哈希表Hash

hash 特性

• 支持操作：Insert/Find/Delete,时间复杂度都是$O(1)$
• Hash Table/Hash Map/Hash Set的区别是什么？
  • hash set 只有key没有value
  • hash table是线程安全的数据结构，hash map线程不安全
  • 多线程和多进程的区别：线程之间共享同一片内存
  • hash table有锁，可以保证同一时间只有一个进程对其进行操作，因此是线程安全的

hash Table实现

通过一个Hash function将key映射到一个大数组中，查找的时候计算下标，直接获取$O(1)$

Hash function的设计：

• 无冲突
• 大数组的长度大概是key数量的10倍以上才是安全的

Hash 函数解决冲突的两种办法：

1. open hashing

   

   每个位置可以维护一个链表，插入时，遇到冲突就加到链表里；查找时，查找下标对应的链表

2. closed hashing

   

   占坑，如果hash函数计算完发现自己的坑被占了，就依次向后找到空位放进去；查找时，hash函数计算应该在的位置，如果不是该元素，继续向后寻找直到空

rehashing问题

当已经存储的元素个数已经超过大数组的1/10l了就需要扩大hash表数组了，这就是rehashing问题。

需要把hash表中现有的元素全部扫描一遍，重新计算其在新的大hash表中的位置，放到新位置。

Max Points on a Line

给定2维坐标平面上n个点，求最多有多少个点共线

遍历每一个点，针对每一个点，用hashmap记录其余跟该点共线的点的个数，key是斜率，value是个数，因为斜率相等的一定在同一直线。遇到跟该点重合的点需要单独累加个数

其中斜率要用分数形式存储，存分子和分母，这就需要计算最大公约数了。

计算最大公约数的方法：辗转相除法

 //求最大公约数，递归
public int gcd(int x, int y) {
  	if (y == 0) return x;
    if (x%y == 0) {
      	return y;
    }
    else {
      	return gcd(y,x%y);
    }
}

 //求最大公约数，非递归
public int gcd(int x, int y) {
  	if (y == 0) return x;
    while (x%y != 0){
      	int temp = y;
      	y = x%y;
      	x = temp;
    }
  	return y;
}

class Solution {
 //求最大公约数
    public int gcd(int x, int y) {
        if (y == 0) return x;
        if (x == 0) return y;
        while(x%y != 0){
            int temp = x%y;
            x = y;
            y = temp;
        }
        return y;
    }

    public int maxPoints(Point[] points) {
        if (points.length <= 2) {
            return points.length;
        }
        int res = 0;
        //遍历每一个点
        for(int i = 0;i < points.length;i++){
            HashMap<String,Integer> map = new HashMap();//存储斜率和个数
            Point p = points[i];
            int selfoverlap = 0;//记录与本身重合的点的个数
            int lineNum = 0;
            //遍历后面的点
            for (int j = i+1;j < points.length;j++){
                Point q = points[j];
                int delta_x = p.x-q.x;
                int delta_y = p.y-q.y;
                //重合的点，单独计算
                if(delta_x == 0 && delta_y == 0){
                    selfoverlap++;
                    continue;
                }
                int maxCommon = gcd(delta_x,delta_y);
                delta_x = delta_x/maxCommon;
                delta_y = delta_y/maxCommon;

                String k = delta_x +"/"+ delta_y;
                int count = map.getOrDefault(k,0)+1;
                map.put(k,count);
                lineNum = Math.max(lineNum,count);
            }
            res = Math.max(res,lineNum + selfoverlap + 1);
        }
        return res;
    }
}

堆Heap

基本性质

• 支持操作：Add $O(logN)$/Remove$O(logN)$/Min or Max$O(1)$

• heap可以用来求最大值或者最小值，不能同时求最大和最小值。

• Heap结构：

  一颗尽量填满的二叉树，每次插入节点时，插到最后一行的最左端的空余位置，如果本层没有空余位置了，另起一行。因此节点数目为N的堆对应的二叉树高度为$O(logN)$

• MaxHeap vs MinHeap

  • MaxHeap：父亲节点比左右孩子都大
  • MinHeap：父亲节点比左右孩子都小

  因此当取最大或最小时，将root值取出即可，因此getMin/Max的时间复杂度为$O(1)$

• 堆的存储

  由于我们需要频繁的对堆进行增加删除，所以一般堆的底层都是通过数组来实现（而不能用链表，因为链表需要频繁new 或 delete对象，非常慢）

  对于元素A[i]：

  • 父节点：A[i-2/2] (右移1)
  • 左孩子：A[2i+1] (左移1，可得到2i)
  • 右孩子：A[2i+2] (左移1，低位+1，可得到2i+1)

• 插入操作

  例子：在最小堆中插入元素：
  	1
    ↙  ↘
   2		3
  插入0，因为第二行已经满了，加入到第三行最左边：
  	1
    ↙  ↘
   2		3
  ↙
  0
  此时这个堆已经不满足最小堆的条件（父亲节点都比孩子小）了，因此，先交换0和2：
  	1
    ↙  ↘
   0		3
  ↙
  2
  此时仍然不满足最小堆条件，继续交换：
  	0
    ↙  ↘
   1		3
  ↙
  2
  此时满足最小堆条件了，因此，需要交换最多 O(logN)次，插入的时间复杂度为O(logN)

  ​

• 删除操作

  例子：在最小堆中删除元素：
       	 1
      ↙  		↘
     3			2
   ↙  ↘       ↙  	↘
  4      5	 10		100
  删除堆顶元素1，用堆中最后一个节点替换堆顶元素：
       	100
      ↙  		↘
     3			2
   ↙  ↘       ↙  	
  4      5	 10		
  此时这个堆已经不满足最小堆的条件（父亲节点都比孩子小）了，因此将堆顶元素下沉，选择左右孩子中较小的交换：
       	 2
      ↙  		↘
     3		  100
   ↙  ↘       ↙  	
  4      5	 10	
  此时仍然不满足最小堆条件，继续交换：
       	 2
      ↙  		↘
     3		  10
   ↙  ↘       ↙  	
  4      5	 100	
  
  好了，删好了

  PriorityQueue支持$O(logN)$ 删除堆顶元素，但对于删除除root外的任意一点的操作，PriorityQueue的时间复杂度会降到$O(N)$

  Java中还有另外一种数据结构TreeMap，支持$O(logN)$ 删除任意元素，而且支持同时获取最大和最小。

  TreeMap是一平衡二叉搜索树，因此插入和删除任意元素的时间复杂度都是$O(logN)$

  | | 用 | 原理 | 实现 |
  | ——————- | —— | —————- | —— |
  | TreeMap | 必会 | 平衡二叉搜索树，红黑树 | 不需要 |
  | PriorityQueue | 必会 | heap，二叉树 | 选做 |

leetcode相关习题

Ugly Number

题目

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

检验输入数组num是否是unly number：因子只有2,3,5

分析

思路就是把num中的2、3、5全部除掉，最后==1了就是ugly number，如果最后不是1，说明还有其他因数，因此返回false

代码

class Solution {
    public boolean isUgly(int num) {
        if(num == 0){
            return false;
        }
        if(num == 1){
            return true;
        }
        
        while(num % 2 == 0){
            num /= 2;
        }

        while(num % 3 == 0){
            num /= 3;
        }
        while(num % 5 == 0){
            num /= 5;
        }
        return num == 1;
    }
}

Ugly Number II

题目

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

思路

从1开始分别乘{2,3,5}，得到2,3,5是ugly number，然后对于2，依次乘2,3,5，得到4,6,10是ugly number，此时ugly number有：1,2,3,4,5,6,10，1,2处理过了，继续处理3，由此，我们需要一个最小堆来维护现有ugly number中还未与2,3,5相乘的最小的，相乘之后加入该堆，同时需要一个hashmap记录已经计算过的ugly number，以免重复入堆。

代码

import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;

public class UglyNumberII {
    public int nthUglyNumber(int n) {
        HashSet<Long> set = new HashSet<>();
        Comparator<Long> cmp = new Comparator<Long>(){
            public int compare(Long e1,Long e2){
                return Long.compare(e1,e2);
            }
        };
        PriorityQueue<Long> heap = new PriorityQueue(cmp);
        Long[] prime = {Long.valueOf(2),Long.valueOf(3),Long.valueOf(5)};
        heap.add(Long.valueOf(1));
        while(n > 1){
            Long ugly = heap.poll();
            for(long i:prime){
                if(!set.contains(ugly*i)){
                    heap.add(ugly*i);
                    set.add(ugly*i);
                }
            }
            n--;
        }
        return heap.peek().intValue();
    }
}