数据结构（一）

wsuo

发布于 2020-07-31 15:11:28

4730

发布于 2020-07-31 15:11:28

文章被收录于专栏：技术进阶之路技术进阶之路

一、队列

先进先出的数据结构 FIFO

1.实现队列

// "static void main" must be defined in a public class.

class MyQueue {
    // store elements
    private List<Integer> data;         
    // a pointer to indicate the start position
    private int p_start;            
    public MyQueue() {
        data = new ArrayList<Integer>();
        p_start = 0;
    }
    /** Insert an element into the queue. Return true if the operation is successful. */
    public boolean enQueue(int x) {
        data.add(x);
        return true;
    };    
    /** Delete an element from the queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (isEmpty() == true) {
            return false;
        }
        //直接将头指针后移
        p_start++;
        return true;
    }
    /** Get the front item from the queue. */
    public int Front() {
        return data.get(p_start);
    }
    /** Checks whether the queue is empty or not. */
    public boolean isEmpty() {
        return p_start >= data.size();
    }     
};

public class Main {
    public static void main(String[] args) {
        MyQueue q = new MyQueue();
        q.enQueue(5);
        q.enQueue(3);
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
        q.deQueue();
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
        q.deQueue();
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
    }
}

2.分析

+缺点：随着起始指针的移动，浪费了越来越多的空间。解决方案：更有效的方法是使用循环队列。 +具体来说，我们可以使用固定大小的数组和两个指针来指示起始位置和结束位置。目的是重用我们之前提到的被浪费的存储。 +循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 +循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

3.循环队列实现

class MyCircularQueue {
    
    private int[] data;
    private int head;
    private int tail;
    private int size;

    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        data = new int[k];
        head = -1;
        tail = -1;
        size = k;
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if (isFull() == true) {
            return false;
        }
        if (isEmpty() == true) {
            head = 0;
        }
        tail = (tail + 1) % size;
        data[tail] = value;
        return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (isEmpty() == true) {
            return false;
        }
        //再出队一次就为空
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head + 1) % size;
        return true;
    }
    
    /** Get the front item from the queue. */
    public int Front() {
        if (isEmpty() == true) {
            return -1;
        }
        return data[head];
    }
    
    /** Get the last item from the queue. */
    public int Rear() {
        if (isEmpty() == true) {
            return -1;
        }
        return data[tail];
    }
    
    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return head == -1;
    }
    
    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        return ((tail + 1) % size) == head;
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

二、队列和 BFS

广度优先搜索（BFS）的一个常见应用是找出从根结点到目标结点的最短路径。 用队列实现BFS的模板

/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                add next to queue;
            }
            remove the first node from queue;
        }
    }
    return -1;          // there is no path from root to target
}

下面这个可以保证不会访问一个节点两次,使用了哈希表

/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    Set<Node> used;     // store all the used nodes
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    add root to used;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                if (next is not in used) {
                    add next to queue;
                    add next to used;
                }
            }
            remove the first node from queue;
        }
    }
    return -1;          // there is no path from root to target
}

岛屿数量问题

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。示例输入: 11110 11010 11000 00000 输出: 1

class Solution {
  int nr = 0;//数组的行数
  int nc = 0;//数组的列数
  void dfs(char[][] grid, int r, int c) {
    nr = grid.length;
    nc = grid[0].length;

	//如果周围的数字有零则结束本次查找,继续向另一个方向查找
    if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
      return;
    }
	//最关键的一步:将查找过得数字赋值为0,避免重复查找,因为前面有约束条件
    grid[r][c] = '0';
    dfs(grid, r - 1, c);//往左查找
    dfs(grid, r + 1, c);//往右查找
    dfs(grid, r, c - 1);//往下查找
    dfs(grid, r, c + 1);//往上查找
  }

  public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
      return 0;
    }

    nr = grid.length;
    nc = grid[0].length;
    
    int num_islands = 0;//计数
    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          dfs(grid, r, c);//调用广度优先遍历,查看周围的数字
        }
      }
    }

    return num_islands;
  }
}

三、栈

在 LIFO 数据结构中，将首先处理添加到队列中的最新元素。

与队列不同，栈是一个 LIFO 数据结构。通常，插入操作在栈中被称作入栈 push 。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈 pop ，将始终删除队列中相对于它的最后一个元素。

1. 实现堆栈

// "static void main" must be defined in a public class.
class MyStack {
    private List<Integer> data;               // store elements
    public MyStack() {
        data = new ArrayList<>();
    }
    /** Insert an element into the stack. */
    public void push(int x) {
        data.add(x);
    }
    /** Checks whether the queue is empty or not. */
    public boolean isEmpty() {
        return data.isEmpty();
    }
    /** Get the top item from the queue. */
    public int top() {
        return data.get(data.size() - 1);
    }
    /** Delete an element from the queue. Return true if the operation is successful. */
    public boolean pop() {
        if (isEmpty()) {
            return false;
        }
        data.remove(data.size() - 1);
        return true;
    }
};

public class Main {
    public static void main(String[] args) {
        MyStack s = new MyStack();
        s.push(1);
        s.push(2);
        s.push(3);
        for (int i = 0; i < 4; ++i) {
            if (!s.isEmpty()) {
                System.out.println(s.top());
            }
            System.out.println(s.pop());
        }
    }
}

大多数流行的语言都提供了内置的栈库，因此你不必重新发明轮子。除了初始化，我们还需要知道如何使用两个最重要的操作：入栈和退栈。除此之外，你应该能够从栈中获得顶部元素。下面是一些供你参考的代码示例：

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        // 1. Initialize a stack.
        Stack<Integer> s = new Stack<>();
        // 2. Push new element.
        s.push(5);
        s.push(13);
        s.push(8);
        s.push(6);
        // 3. Check if stack is empty.
        if (s.empty() == true) {
            System.out.println("Stack is empty!");
            return;
        }
        // 4. Pop an element.
        s.pop();
        // 5. Get the top element.
        System.out.println("The top element is: " + s.peek());
        // 6. Get the size of the stack.
        System.out.println("The size is: " + s.size());
    }
}

push(x) – 将元素 x 推入栈中。
pop() – 删除栈顶的元素。
peek() – 获取栈顶元素。

2. 最小栈问题

解法一

最直接的方法就是用两个栈,一个去保存正常出入栈的值,一个去保存最小值（实际上是用栈顶去保存最小值）

元素同时入两个栈
第二个元素来了，二话不说先入第一个栈，再和第二个栈的栈顶元素比较，如果小于等于他就入栈，假如确实小了，那就入栈
第三个元素来了，二话不说入第一个栈，在和第二个栈的栈顶比较，加入比栈顶元素大，不入栈
出栈就简单了，如果第一个栈中要出栈的元素等于第二个栈的栈顶元素，就同时出栈，否则只出第一个栈，因为右边的栈顶始终保持的是最小值，你后面不管入栈多少大于它的值我都不管，因为我没入栈。

代码实现

class MinStack {
    /** initialize your data structure here. */
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if (!minStack.isEmpty()) {
            int top = minStack.peek();
            //小于的时候才入栈
            if (x <= top) {
                minStack.push(x);
            }
        }else{
            minStack.push(x);
        }
    }

    public void pop() {
        int pop = stack.pop();

        int top = minStack.peek();
        //等于的时候再出栈
        if (pop == top) {
            minStack.pop();
        }

    }

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

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

解法二

刚才用了两个栈，那能不能只用一个栈呢？

如果只用一个栈，之前的最小元素会被下一个覆盖掉，这样min存的就只是目前的最小值了
只能是将当过最小值的数在下一个数入栈之前入栈就可以了，如果要过来的数比min大就不用管，只看小于等于
当出栈元素是目前的最小元素怎么办？
只需要把出栈元素放心的出栈，然后把下一个元素出栈并赋值给min

class MinStack {
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    public void push(int x) {
        //当前值更小
        if(x <= min){   
            //将之前的最小值保存
            stack.push(min);
            //更新最小值
            min=x;
        }
        stack.push(x);
    }

    public void pop() {
        //如果弹出的值是最小值，那么将下一个元素更新为最小值
        if(stack.pop() == min) {
            min=stack.pop();
        }
    }

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

    public int getMin() {
        return min;
    }
}

3. 有效的括号

这个题目的任务相当于编译器给我们提供功能，即检查括号是否匹配：

让我们看看下面的这个想法，从整体表达式中一次删除一个较小的表达式，因为这是一个有效的表达式，我们最后剩留下一个空字符串。

根据题目要求可以想到使用栈来解决问题，因为栈就是后进先出，仔细观察上面的图片，你会发现它具有以下特点：

如果外层括号匹配，那么里面的括号也一定匹配
那就可以使用递归来从内到外判断
我们无法真正地从内到外处理这个问题，因为我们对整体结构一无所知。但是，栈可以帮助我们递归地处理这种情况，即从外部到内部。

注意：

如果字符串的长度为奇数，直接返回false
最后栈应该是空的

设想一种解决方案：

初始化栈；
依次处理表达式里的每个括号；
如果遇到开括号，我们只需要把它推到栈上；
如果遇到一个闭括号，在处理他之前先检查它是否与目前的栈顶元素匹配，如果匹配，就把它们全部踢出去（pop）。如果不匹配，那这个字符串就不是一个有效的括号，因为我们刚才分析了，要想有效，由内而外必须都匹配；
如果到最后栈不为空，那么该字符串无效，因为如果都匹配，我们应该是都踢完了才对。

代码实现

class Solution {
    
    private Map<Character, Character> mapping = null;
    
    
    public Solution() {
        mapping = new HashMap<>();
        mapping.put(')', '(');
        mapping.put(']', '[');
        mapping.put('}', '{');
    }
    
    public boolean isValid(String s) {
        
        Stack<Character> stack = new Stack<>();
        
        //如果长度为奇数,直接返回
        if (s.length() % 2 == 1) {
            return false;
        }
        
        //遍历这个字符串
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            
            //如果是右括号
            if (mapping.containsKey(ch)) {
                
                char top = stack.isEmpty() ? '#' : stack.pop();
                
                //如果返回的值和它不匹配,直接返回
                if (top != mapping.get(ch)) {
                    return false;
                }
                
            //如果是左括号
            } else {
                stack.push(ch);
            }
        }
        //最后的栈应该为空
        return stack.isEmpty();
    }
}

四、栈和DFS

与 BFS 类似，深度优先搜索（DFS）也可用于查找从根结点到目标结点的路径。在本文中，我们提供了示例来解释 DFS 是如何工作的以及栈是如何逐步帮助 DFS 工作的。

节点的处理顺序：

在我们到达最深的结点之后，我们只会回溯并尝试另一条路径。

因此，你在 DFS 中找到的第一条路径并不总是最短的路径。

栈的入栈和退栈顺序是什么：

我们首先将根结点推入到栈中；然后我们尝试第一个邻居并将该结点推入到栈中；等等等等。当我们到达最深的结点时，我们需要回溯。当我们回溯时，我们将从栈中弹出最深的结点，这实际上是推入到栈中的最后一个结点。
结点的处理顺序是完全相反的顺序，就像它们被添加到栈中一样，它是后进先出（LIFO）。这就是我们在 DFS 中使用栈的原因。

1. 模板

正如我们在本章的描述中提到的，在大多数情况下，我们在能使用 BFS 时也可以使用 DFS。但是有一个重要的区别：遍历顺序。

与 BFS 不同，更早访问的结点可能不是更靠近根结点的结点。因此，你在 DFS 中找到的第一条路径可能不是最短路径。

DFS 的递归模板：

1. 实现一

有两种实现 DFS 的方法。第一种方法是进行递归

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}

当我们递归地实现 DFS 时，似乎不需要使用任何栈。但实际上，我们使用的是由系统提供的隐式栈，也称为调用栈（Call Stack）。

示例

在每个堆栈元素中，都有一个整数 cur，一个整数 target，一个对访问过的数组的引用和一个对数组边界的引用，这些正是我们在 DFS 函数中的参数。我们只在上面的栈中显示 cur。

每个元素都需要固定的空间。栈的大小正好是 DFS 的深度。因此，在最坏的情况下，维护系统栈需要 O(h)，其中 h 是 DFS 的最大深度。在计算空间复杂度时，永远不要忘记考虑系统栈。

2. 实现二

递归解决方案的优点是它更容易实现。但是，存在一个很大的缺点：如果递归的深度太高，你将遭受堆栈溢出。在这种情况下，您可能会希望使用 BFS，或使用显式栈实现 DFS。

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(int root, int target) {
    Set<Node> visited;
    Stack<Node> s;
    add root to s;
    while (s is not empty) {
        Node cur = the top element in s;
        return true if cur is target;
        for (Node next : the neighbors of cur) {
            if (next is not in visited) {
                add next to s;
                add next to visited;
            }
        }
        remove cur from s;
    }
    return false;
}

该逻辑与递归解决方案完全相同。但我们使用 while 循环和栈来模拟递归期间的系统调用栈。

2. 目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

1.解法一：枚举

可以使用递归,你把所有的可能全都列举出来肯定可以解决问题，这种就是自底向上解决问题，从最小的分支往上不断的循环。因为你把它拆分了就是两个数比较。

代码如下：

class Solution {
    
    private int count = 0;
    
    public int findTargetSumWays(int[] nums, int s) {
        calculate(nums, 0, 0, s);
        return count;
    }
    
    public void calculate(int[] nums, int i, int sum, int s) {
        //终止条件是什么? 应该是到头了,这时的i应该等于数组长度
        if (i == nums.length) {
            //到头了就看看是不是等于s
            if (sum == s) {
                count++;
            }
        } else {
            //如果没到头
            calculate(nums, i + 1, sum + nums[i], s);
            calculate(nums, i + 1, sum - nums[i], s);
        }
    }
}

但是枚举的时间复杂度太高了

时间复杂度：O(2^N)，其中 NN 是数组 nums 的长度。
空间复杂度：O(N)，为递归使用的栈空间大小。

2. 解法二：动态规划

这道题也是一个常见的背包问题，我们可以用类似求解背包问题的方法来求出可能的方法数。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-02-06 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

数据结构

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

数据结构

登录后参与评论

0 条评论

热度