Queue
队列的特性是先进先出FIFO
Design Circular Queue
设计环形队列的数据操作类，环形队列的优势在于节省空间，但指针的控制复杂，设计思路重点看isFull & isEmpty这两个方法
class MyCircularQueue {
private int[] queue;
private int headP;
private int tailP;
public MyCircularQueue(int k) {
queue = new int[k + 1];
headP = 0;
tailP = 0;
for (int i = 0; i < k + 1; i++) {
queue[i] = -1;
}
}
//3、既然tailP指向空位，入队列就简单了
public boolean enQueue(int value) {
if (!isFull()) {
queue[tailP] = value;
tailP = (tailP + 1) % queue.length;
return true;
}
return false;
}
//4、出队列时要清空数据（非必须、但有造成内存泄漏的风险）
public boolean deQueue() {
if (!isEmpty()) {
queue[headP] = -1;
headP = (headP + 1) % queue.length;
return true;
}
return false;
}
public int Front() {
return queue[headP];
}
//5、注意指针越界
public int Rear() {
return queue[(tailP + queue.length - 1) % queue.length];
}
//1、tailP指向的永远是空位，headP指向头元素
public boolean isEmpty() {
return headP == tailP;
}
//2、这就会浪费一个空间，用来区分Empty、Full的状态
public boolean isFull() {
return (tailP + 1) % queue.length == headP;
}
}
Queue and BFS
由于队列FIFO的性质，BFS广度优先查找一般由Queue来实现
先处理顶层，记录同层的数量，依次处理此层的数据，与其相关的下层加入队尾，从而实现广度优先查找
Number of Islands
用二维数组表示平面，其中1代表岛屿，0代表海，相连岛屿算一个岛，计算平面内共有多少座岛屿
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] != '0') {//找到第一个岛
export(grid, i, j);//探索该岛
count++;
}
}
}
return count;
}
private void export(char[][] grid, int x, int y) {
if (x < 0 || y < 0) {//超出地图范围
return;
}
if (x < grid.length && y < grid[x].length && grid[x][y] == '1') {
grid[x][y] = '0';//将岛屿打小
} else {
return;
}
//上下左右各方探索
export(grid, x, y + 1);
export(grid, x, y - 1);
export(grid, x + 1, y);
export(grid, x - 1, y);
}
}
Open the Lock
四位数字密码锁，每次转动一下，已知密码和死亡触发，求解最少的解锁步骤
这种最少的求解算法，多数要用到BFS
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> visited = new HashSet<String>();
Set<String> deadEnds = new HashSet<String>(deadends.length);
deadEnds.addAll(Arrays.asList(deadends));
Queue<String> queue = new LinkedList();
queue.offer("0000");//起始位置
visited.add("0000");
int level = 0;
while (!queue.isEmpty()) {
int length = queue.size();//每一层要查找的次数
for (int j = 0; j < length; j++) {
String poll = queue.poll();
if (poll.equals(target)) {//命中
return level;
}
if (deadEnds.contains(poll)) continue;//陷阱！避开
String cur = new String(poll);
for (int i = 0; i < 4; i++) {//一共四位，走向每一位的前后
char c = cur.charAt(i);
String next = cur.substring(0, i) + (c == '9' ? 0 : c - '0' + 1) + cur.substring(i + 1);
String pre = cur.substring(0, i) + (c == '0' ? 9 : c - '0' - 1) + cur.substring(i + 1);
//避开陷阱和重复
if (!visited.contains(pre) && !deadEnds.contains(pre)) {
queue.offer(pre);
visited.add(pre);
}
if (!visited.contains(next) && !deadEnds.contains(next)) {
queue.offer(next);
visited.add(next);
}
}
}
level++;
}
return -1;
}
}
Perfect Squares
给定数字n，求它由最少多少个完全平方数的和组成
两种解法：
一种是纯数学定理【四平方和定理】；
第二种则是动态规划（所采取的），将0-n全部数字找出完全平方数的最少个数
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
for (int i = 1; i < dp.length; i++) {//遍历0-n
int j = 1;
int min = 5;
while (i - j * j >= 0) {//计算第i位数字i，完全平方数的最少个数
min = Math.min(min, dp[i - j * j] + 1);
j++;
}
dp[i] = min;
}
return dp[n];
}
}
Stack
栈的特性是后进先出LIFO
Min Stack
设计简单的栈结构类，能够检索最小值。
难点：正常情况下，入栈时比较最小值，能够保留最小值。问题发生在最小值出栈后，剩余数据中的最小值怎么获取？？
思路：既然次小值、次次小值无法确定，那就想方法将其保留。当出栈为最小值时，栈顶是次小值的话问题就解决了
class MinStack {
int min = Integer.MAX_VALUE;
Stack<Integer> stack;
public MinStack() {
stack = new Stack();
}
public void push(int x) {
if (x <= min) {//1、入栈发现最小值
stack.push(min);//2、将次小值先入栈
min = x;//3、记录最小值
}
stack.push(x);//4、再将最小值入栈；5、如果是一般值，则正常入栈，不经过1、2、3
}//由此就保证了栈内最小值的下方为次小值
public void pop() {
if (stack.pop() == min)//出栈值为最小值
min = stack.pop();//取出次小值，为最小值
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
Valid Parentheses
判断输入的括号是否配对
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
if (s.length() % 2 != 0) return false;//奇数项的话一定不能配对
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {//反向入栈，看后续内容是否匹配栈内内容
stack.push(')');
} else if (c == '{') {
stack.push('}');
} else if (c == '[') {
stack.push(']');
} else if (stack.isEmpty() || stack.pop() != c) {//不匹配则不能配对
return false;
}
}
return stack.isEmpty();
}
}
Daily Temperatures
给出连续几天的温度，计算出，还要等几天，温度才比现在的温度高。
class Solution {
public int[] dailyTemperatures(int[] T) {
Stack<Integer> stack = new Stack<Integer>();//没有找到结果的集合，栈内栈顶永远小于栈底，从上到下是升序
int[] waits = new int[T.length];//结果集合
for (int i = 0; i < T.length; i++) {//从第一天开始遍历
while (!stack.isEmpty() && T[i] > T[stack.peek()]) {//今天大于栈内最小元素，则栈顶元素可计算出结果
int index = stack.pop();
waits[index] = i - index;//保存结果
}
stack.push(i);
}
return waits;
}
}
Evaluate Reverse Polish Notation
这是计算机编译原理中的概念，书中是由计算公式引申到栈内的表示，而这里题目则是反向，给出了栈内表示反推计算公式的结果
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<Integer>();
for (String str : tokens) {
if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
int num2 = stack.pop();//先出栈的是num2
int num1 = stack.pop();
int result = 0;
if (str.equals("+")) {
result = num1 + num2;
}
if (str.equals("-")) {
result = num1 - num2;
}
if (str.equals("*")) {
result = num1 * num2;
}
if (str.equals("/")) {
result = num1 / num2;
}
stack.push(result);
} else {
stack.push(Integer.valueOf(str));
}
}
return stack.pop();
}
}
Stack and DFS
由于栈LIFO的性质，DFS深度优先查找一般由Stack来实现
逮到一根线深入（即入栈），碰到南墙就回头（出栈），遇到分叉口再次深入（即入栈），知道得出结果，因此Stack与DFS密不可分
Clone Graph
将无向图深度复制
因为是无向图，所以同一节点可以被多个节点关联，可以使用Map避免同一节点被多次复制的问题
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {}
public Node(int _val,List<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public Node cloneGraph(Node node) {
Stack<Node> stack = new Stack<Node>();
HashMap<Node, Node> map = new HashMap<Node, Node>();
Node root = new Node();//先复制根节点
root.val = node.val;
root.neighbors = new ArrayList<Node>();
map.put(node, root);//记录已复制的节点
stack.push(node);//记录将要复制其子节点的节点
while (!stack.isEmpty()) {
Node node1 = stack.pop();
for (Node node2 : node1.neighbors) {//子节点
if (!map.containsKey(node2)) {//已有子节点，避免重复复制
Node newNode = new Node();
newNode.val = node2.val;
newNode.neighbors = new ArrayList<Node>();
map.put(node2, newNode);
stack.push(node2);
}
map.get(node1).neighbors.add(map.get(node2));
}
}
return map.get(node);
}
}
Target Sum
给定一正整型数组和一目标值，只能通过加减法遍历操作数组内所有项使其结果为目标值，求共有多少种操作方式。
class Solution {
int result = 0;
public int findTargetSumWays(int[] nums, int S) {
helper(nums, 0, S);
return result;
}
private void helper(int[] nums, int position, int S) {//数组、第几位开始、当前结果
if (position >= nums.length) {//最后一位
if (S == 0) {//且结果为0
result++;
}
return;
}
helper(nums, position + 1, S - nums[position]);//DFS
helper(nums, position + 1, S + nums[position]);
}
}
Implement Queue using Stacks
通过使用栈来实现队列，即利用LIFO的数据结构实现FIFO的操作方式
重点：在peek方法，通过左右手倒换来实现
class MyQueue {
Stack<Integer> inStack;
Stack<Integer> outStack;
public MyQueue() {
inStack=new Stack<Integer>();
outStack=new Stack<Integer>();
}
public void push(int x) {
inStack.push(x);
}
public int pop() {
peek();
return outStack.pop();
}
public int peek() {
if (outStack.isEmpty()) {//将入栈的栈底元素，转到了栈顶
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty()&&outStack.isEmpty();
}
}
Implement Stack using Queues
通过使用队列来实现栈
class MyStack {
Queue<Integer> q = new LinkedList<Integer>();
public void push(int x) {
q.add(x);
int n = q.size();
while (n-- > 1)//每入队一元素，将其前面的元素出队并再次入队，达到新进元素在队首的效果
q.add(q.poll());
}
public int pop() {
return q.poll();
}
public int top() {
return q.peek();
}
public boolean empty() {
return q.isEmpty();
}
}
Decode String
看效果比题目描述更直观
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
class Solution {
public static String decodeString(String s) {
String res = "";
Stack<Integer> countStack = new Stack();//记录数字
Stack<String> resStack = new Stack();//记录字符
int index = 0;
while (index < s.length()) {
if (Character.isDigit(s.charAt(index))) {
int count = 0;
while (Character.isDigit(s.charAt(index))) {//多位整数
count = count * 10 + (s.charAt(index) - '0');
index++;
}
countStack.push(count);
} else if (s.charAt(index) == '[') {//字符的开始
resStack.push(res);
res = "";
index++;
} else if (s.charAt(index) == ']') {//字符的结束，表示要开始重复拼接字符
StringBuffer temp = new StringBuffer(resStack.pop());
int repeat = countStack.pop();
for (int i = 0; i < repeat; i++) {
temp.append(res);
}
res = temp.toString();
index++;
} else {
res += s.charAt(index++);
}
}
return res;
}
}
Flood Fill
泛洪算法，即指定一点，将该点周围与其相同的点统一变换
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int oldColor = image[sr][sc];
fun(image, sr, sc, newColor, oldColor);
return image;
}
private void fun(int[][] image, int sr, int sc, int newColor, int oldColor) {
if (sr < 0 || sc < 0) {//越界处理
return;
}
if (sr >= image.length || sc >= image[0].length) {
return;
}
if (oldColor == newColor) {//已处理过，或不需处理的相邻点
return;
}
if (image[sr][sc] == oldColor) {//必须是相同的点
image[sr][sc] = newColor;
//四个方向拓展
fun(image, sr + 1, sc, newColor, oldColor);
fun(image, sr - 1, sc, newColor, oldColor);
fun(image, sr, sc + 1, newColor, oldColor);
fun(image, sr, sc - 1, newColor, oldColor);
}
}
}
01 Matrix
二位数组中，求出所有点距离最近0点的距离
class Solution {
public int[][] updateMatrix(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {//当前点本身是0点
continue;
} else {
int count = find(matrix, i, j);//找到此点距最近0点的距离
matrix[i][j] = count;
}
}
}
return matrix;
}
private int find(int[][] matrix, int r, int c) {//BFS
Queue<String> queue = new LinkedList<String>();
queue.offer(r + "-" + c);
int count = 0;
while (!queue.isEmpty()) {
int loop = queue.size();
for (int i = 0; i < loop; i++) {
String[] temp = queue.poll().split("-");
int row = Integer.parseInt(temp[0]);
int col = Integer.parseInt(temp[1]);
if (matrix[row][col] == 0) {
return count;
}
if (row + 1 < matrix.length) {
queue.offer((row + 1) + "-" + col);
}
if (col + 1 < matrix[0].length) {
queue.offer(row + "-" + (col + 1));
}
if (row > 0) {
queue.offer((row - 1) + "-" + col);
}
if (col > 0) {
queue.offer(row + "-" + (col - 1));
}
}
count += 1;
}
return count;
}
}
Keys and Rooms
有多间房，每间房内存在开启其他房间的钥匙，问是否能进入所有房间
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
Queue<Integer> queue = new LinkedList<Integer>();//手上有的钥匙
Set<Integer> visited = new HashSet<Integer>();//已进过的房间
for (int i = 0; i < rooms.get(0).size(); i++) {
queue.offer(rooms.get(0).get(i));//拿到房间0的所有钥匙
}
visited.add(0);//去过房间0
while (!queue.isEmpty()) {
int room = queue.poll();
visited.add(room);//拿钥匙去其他房间
List<Integer> keys = rooms.get(room);
for (int i = 0; i < keys.size(); i++) {//并将其他房间的钥匙拿入手中
if (!visited.contains(keys.get(i))) {
queue.offer(keys.get(i));
}
}
}
return visited.size() == rooms.size();//去过的房间数等于房间总数则表示能够遍历所有房间，反之不能
}
}
网友评论