Jinzhe Shan

剑指offer|解题代码-3-Stack-Queue-Heap-HashMap-Graph(Java)

目录：

Stack & Queue

​ 005-用两个栈实现队列 √

​ 020-包含min函数的栈 √

​ 021-栈的压入、弹出序列 √

​ 044-翻转单词顺序列(栈) √

​ 043-左旋转字符串(矩阵翻转) √

​ 064-滑动窗口的最大值 √

Heap

​ 029-最小的K个数 √

Hash Table

​ 034-第一个只出现一次的字符 √

图 （图的遍历 + 回溯法）

​ 065-矩阵中的路径(BFS) √

​ 066-机器人的运动范围(DFS) √

Stack & Queue

005-用两个栈实现队列 √

题目描述: 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思路：

栈 ---先入后出 ；队列 --- 先入先出 1. 一个栈负责入队，另一个负责出队，出栈为空则从入栈中导入到出栈中 2. 相当于每次弹出前，先把栈掉了一个顺序，然后再把栈尾（队头）pop出来

解题代码：（Java）

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if (stack2.empty()){
            while (!stack1.empty()){
                stack2.push(stack1.pop());
        }
        }
        return stack2.pop();
    }
}

020-包含min函数的栈 √

题目描述: 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））

思路： 1. 因为要求时间复杂度为 O(1) 自然想到用额外空间换时间 2. 创建两个 Stack： 1 - dataStack 正常顺序存储堆栈；2 - minStack 存当前堆栈最小值 3. push时判定 新加入的 node 是否比 minStack.peek() 小，如果小则 minStack.push(node) 4. 否则 minStack.push(minStack.peek()) // 相当于新加入的node比之前的min大， minStack中存入一个之前的min值（minStack.peek()）

解题代码：（java）

import java.util.Stack;

public class Solution {

    Stack<Integer> dataStack = new Stack<Integer>();
    Stack<Integer> minStack  = new Stack<Integer>();

    public void push(int node) {
        dataStack.push(node);
        if(minStack.isEmpty() || node < minStack.peek())
            minStack.push(node);
        // add the old peek value as new peak value (min value)
        else
            minStack.push(minStack.peek());
    }

    public void pop() {
        dataStack.pop();
        minStack.pop();
    }

    // get top node value in Stack
    public int top() {
        return dataStack.peek();
    }

    // get min node value in Stack
    public int min() {
        return minStack.peek();
    }

}

021-栈的压入、弹出序列 √

题目描述 : 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

给定栈的压入序列，判断某序列是否可能为栈的弹出序列是一道笔试中常考的选择题，那么如何用代码来判定呢？

思路: 1. 循环，找和pop序列第一个元素相同的值 - 找到，则 stack.pop()，indexPop后移 - 未找到，则 stack.push(pushA[indexPush]) 2. 退出条件：如果弹出序列指针还没到结尾但已经无元素可压入，则被测序列不是弹出序列。 3. 循环结束依然没有退出，返回 true

解题代码：（java）

import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA == null || popA == null || pushA.length != popA.length)
            return false;
        Stack<Integer> stack = new Stack<Integer>();
        int indexPush = 0;
        int indexPop  = 0;
        while (indexPop < popA.length){
            // Do not find the equal value
            if (stack.isEmpty() || stack.peek() != popA[indexPop]){
                // the push sequence is not clear
                if(indexPush < pushA.length){
                    stack.push(pushA[indexPush]);
                    indexPush += 1;
                }
                else
                    return false;
            }
            // Find the equal value
            else{
                stack.pop();
                indexPop += 1;
            }
        }
        return true;
    }
}

044-翻转单词顺序列(栈) √

题目描述：句子中单词翻转，但是单词里的字母不翻转 “student. a am I” --> “I am a student.”

思路: 1. 先把整个字符串反转 2. 再将每一个单词分别反转会原状

解题代码：（java）

import java.util.Stack;

public class Solution {
    // reverse a whole sentence but do not reverse letters in a word.
    public String ReverseSentence(String str) {
        // using str.trim().equals("") to remove multiple space 
        if(str==null||str.trim().equals(""))
            return str;
        String reverseStr = Reverse(str);
        String [] words = reverseStr.split(" ");
        StringBuffer sb = new StringBuffer();
        for(int i = 0; i< words.length-1;i++){
            sb.append(Reverse(words[i])+" ");
        }
        // Note : the last word without space symbol
        sb.append(Reverse(words[words.length-1]));
        return sb.toString();
    }
    public String Reverse(String str){
        StringBuffer sb = new StringBuffer();
        int index = 0;
        Stack<Character> stack = new Stack<Character>();
        for(;index < str.length();index++){
            stack.push(str.charAt(index));
        }
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.toString();
    }

}

043-左旋转字符串(矩阵翻转) √

题目描述：对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”

思路： 1. 直接两个for循环反转就行，时间复杂度 O(n) 2. 注意当传入值 n > str.length() 时做取模操作

解题代码：（java）

public class Solution {
    public String LeftRotateString(String str,int n) {
        if(str==null||str.trim().equals("")|| n < 0)
            return str;
        if(n > str.length())
            n = n % str.length();
        StringBuffer sb = new StringBuffer();
        int i;
        for(i = n;i<str.length();i++){
            sb.append(str.charAt(i));
        }
        for(i=0;i<n;i++){
            sb.append(str.charAt(i));
        }
        return sb.toString();
    }
}

064-滑动窗口的最大值 √

题目描述 : 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}

解法1 - 暴力循环法 时间复杂度 O(n*size)，空间复杂度O(1) 解题代码 （Java）： 

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(num.length<=0 || size <= 0)
            return res;
        int i = 0;
        for(; i<num.length;i++){
            int j = 1;
            int max = num[i];
            for(;j<size && j+i<num.length;j++){
                if(num[i+j] > max)
                    max = num[i+j];
            }
            // avoid beyond the range
            if(size+i<num.length+1)
                res.add(max);
        }
        return  res;
    }
}
  • [ ] 解法2 - 双端队列 待补充

解题代码：（java）

Heap

029-最小的K个数 *** √

题目描述 ： 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

这是典型的TopK问题，常见的几种解法有： 1. 全排序，然后取出前K位。但是这在数据量很大的情况下很明显是做了后K位数字排序的无用功。时间复杂度为O(nlogn),空间复杂度为O(1) 2. 堆排序，创建一个长度为K的堆，TopMaxK则用最大堆，TopMinK则用最小堆，并且不会更改原数组，适合处理海量数据情况。时间复杂度为O(nlogk),空间复杂度为O(k)

解题代码 1-优先级实现 minHeap：（java）

import java.util.PriorityQueue;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if (k > input.length || k <= 0) 
            return new ArrayList<>();
        // Max Heap
        //PriorityQueue<Integer> maxHeap = new PriorityQueue<>();

        // Min Heap
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o2 - o1); 
        for (int num : input) { 
            minHeap.add(num); 
            if (minHeap.size() > k) 
                minHeap.poll();
        } 
        return new ArrayList<>(minHeap);
    }
}
  • [ ] 解题代码 2-手撸Heap ：（java）

Hash Table

034-第一个只出现一次的字符 √

题目描述 : 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

思路：利用一个额外数组times[char]存储str中不同字符的个数，顺序存储第二次扫描时遇到的第一个 times[char] == 1 的 char所在str中的index即为答案

解题代码 1- int [] （java）：

public class T34_FirstNotRepeatingChar {
    public int FirstNotRepeatingChar(String str) {
        if(str == null)
            return -1;
        int [] times = new int[256];
        for (int i = 0; i<str.length();i++){
            System.out.println(str.charAt(i));
            times[str.charAt(i)]+=1;
        }

        for (int i = 0; i<str.length();i++){
            System.out.println(str.charAt(i) + " : "+times[str.charAt(i)]);
            if (times[str.charAt(i)] == 1)
                return str.indexOf(str.charAt(i));
        }
        return -1;
    }
}

解题代码 2- HashMap (Java):

import java.util.HashMap;
public class T34_FirstNotRepeatingChar {
    public int FirstNotRepeatingCharHashMap(String str){
        HashMap<Character, Integer> map = new HashMap<>();
            if (str==null)
                return -1;
            int length = str.length();
            for(int i = 0;i<length;i++) {
                if(map.containsKey(str.charAt(i))){
                    int value = map.get(str.charAt(i));
                    map.put(str.charAt(i),value+1);
                }else{
                    map.put(str.charAt(i),1);
                }
            }
            for(int i = 0;i<length;i++){
                if(map.get(str.charAt(i))==1)
                    return i;
            }
            return -1;
    }
}

图 （图的遍历 + 回溯法）

065-矩阵中的路径(BFS) √

题目描述 : 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

回溯法思路： 1. 从0 rows 0 cols 开始 坐标 (i,j) index依次加一判定 （ index = i * rows + j） 2. 需要一个flag数组记录 当前位置有没有被走过

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
        {
            boolean [] flags = new boolean[matrix.length]; // gone position is true
            int position = 0;
            for(int i =0; i<rows; i++){
                for(int j =0; j < cols; j++){
                    if(findPath(matrix,rows,cols,i,j,position,str,flags))
                        return true;
                }
            }
            return false;
        }
        public boolean findPath(char[] matrix, int rows, int cols, int i, int j,int position,char[] str,boolean[] flags){
            int curIndex = i*rows+j;
            if(i<0 || i>=rows|| j<0 || j>= cols || matrix[curIndex] != str[position] || flags[curIndex])
                return false;
            if(position == str.length -1)
                return true;
            flags[curIndex] = true; // mark (i,j) as true
            if(findPath(matrix,rows,cols,i+1,j,position+1,str,flags)||
                    findPath(matrix,rows,cols,i-1,j,position+1,str,flags)||
                    findPath(matrix,rows,cols,i,j+1,position+1,str,flags)||
                    findPath(matrix,rows,cols,i,j-1,position+1,str,flags))
            return true;
            // no possibility to find path at current index, so mark flags[curIndex] = false
            flags[curIndex] = false;
            return false;
        }
}

066-机器人的运动范围(DFS) √

题目描述: 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

思路 1： 回溯 + 递归 1. 定义一个二维数组 flags 来标记走过的格子，这是之后递归函数退出的条件之一 2. 定义一个函数 sum 计算当前方格坐标阈值（行坐标和列坐标的数位之和），这也是之后递归函数退出的条件之一 3. 根据题意构造回溯方法，返回值为满足条件的格子数 4. 按照上下左右顺序，递归调用回溯方法，只要满足则count值+1

递归解题代码：（java）

public class Solution {
    public int movingCount(int threshold, int rows, int cols)
    {
        int[][] flags = new int[rows][cols];
        return count(0,0,threshold,rows,cols,flags);
    }

    private int count(int i, int j, int threshold, int rows, int cols,int[][] flags) {
        if(i<0 || j<0 || i>=rows || j>=cols || sum(i,j)>threshold || flags[i][j] == 1)
            return 0;
        flags[i][j] = 1;
        // 按照上下左右格子的顺序递归调用回溯方法
        return  count(i-1,j,threshold,rows,cols,flags)
                + count(i+1,j,threshold,rows,cols,flags)
                + count(i,j-1,threshold,rows,cols,flags)
                + count(i,j+1,threshold,rows,cols,flags)
                + 1;// 当前格子满足条件，返回值+1
    }
    private  int sum(int i, int j){
        int sum = 0;
        do {
            sum += i%10;
            i = i/10;
        }while (i>0);
        do {
            sum += j%10;
            j = j/10;
        }while (j>0);
        return sum;
    }
}

思路 2： 回溯 + 非递归 1. 定义一个 flags 来标记走过的格子，这是之后递归函数退出的条件之一 2. 定义一个函数 sum 计算当前方格坐标阈值（行坐标和列坐标的数位之和），这也是之后递归函数退出的条件之一 3. 递归的本质是系统帮压栈，所以非递归实现则是自己定义一个栈 stack 用来记录还没有被访问过的上下左右邻居，如果满足条件则压入栈 4. 每次弹出一个栈顶元素，直到栈为空

非递归解题代码：（java）

import java.util.Stack;
public class Solution {
public int movingCount(int threshold, int rows, int cols)
    {
        if(threshold<0 || rows<0 || cols<0)
            return 0;
        // 上下左右格子
        int[] x = {-1,1,0,0};
        int[] y = {0,0,-1,1};

        boolean [] flags = new boolean[rows*cols];
        flags[0] = true; // 访问过标记为 true

        Stack<Integer> stack = new Stack<>();
        stack.add(0);

        int count = 0;

        while (!stack.isEmpty()){
            int curIndex = stack.pop();
            count += 1;
            for (int i = 0; i<4;i++){
                int curRow = curIndex / cols + x[i];
                int curCol = curIndex % cols + y[i];
                int digitalSum = sum(curRow,curCol);
                if (curCol>=0 && curCol<cols && curRow>=0 && curRow<rows && digitalSum <= threshold && !flags[curRow * cols + curCol]){
                    stack.add(curRow * cols + curCol);
                    flags[curRow * cols + curCol] = true;
                }
            }
        }
        return count;
    }

    private  int sum(int i, int j){
        int sum = 0;
        do {
            sum += i%10;
            i = i/10;
        }while (i>0);
        do {
            sum += j%10;
            j = j/10;
        }while (j>0);
        return sum;
    }
}

Published

Category

interview

Tags

Contact