常见面试算法题带解析整理

本文主要是介绍常见面试算法题带解析整理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

因为我本身就是一个很平凡的人。但是至少，我知道生命是美好的。

颠倒给定的 32 位无符号整数的二进制位。

分治算法

public class Solution {// you need treat n as an unsigned valueprivate static final int M1 = 0x55555555; // 01010101010101010101010101010101private static final int M2 = 0x33333333; // 00110011001100110011001100110011private static final int M4 = 0x0f0f0f0f; // 00001111000011110000111100001111private static final int M8 = 0x00ff00ff; // 00000000111111110000000011111111public int reverseBits(int n) {int res = n;// 交换前后16位res = (res >>> 16) | (res << 16);// 在每个16位中再交换8位res = ((res & 0xff00ff00) >>> 8) | ((res & 0x00ff00ff) << 8);// 在每个8位中再交换4位res = ((res & 0xf0f0f0f0) >>> 4) | ((res & 0x0f0f0f0f) << 4);// ... 1100110011001100...          0011001100110011...res = ((res & 0xcccccccc) >>> 2) | ((res & 0x33333333) << 2);//     1010101010101010...          0101010101010101...res = ((res & 0xaaaaaaaa) >>> 1) | ((res & 0x55555555) << 1);return res;}
}

循环替换

public class Solution {// you need treat n as an unsigned valuepublic int reverseBits(int n) {int res = 0;for (int i=0;i<32;i++) {res <<= 1;// res 左移一位，给 n 的最后一位留出位置res += n & 1;// n 和 1 与，取出 n 的最后一位，放在 res 的最后一位n >>= 1;// n 右移一位，把已经挪到 res 中的最后一位释放掉}return res;//return Integer.reverse(n);}}

 

二维数组：

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

/*** @return boolean* @Author Liruilong* @Description 方法一，自己想的笨办法,对角线遍历。缩小区域后，暴力寻找。* @Description 方法二，利用二维数组由上到下，由左到右递增的规律，那么选取右上角或者左下角的元素a[row][col]与target进行比较，* 当target小于元素a[row][col]时，那么target必定在元素a所在行的左边,即col--；当target大于元素a[row][col]时，* 那么target必定在元素a所在列的下边,即row++；**/
public static boolean Find1(int target, int[][] array) {int row = 0;int col = array[0].length - 1;while (row <= array.length - 1 && col >= 0) {if (target == array[row][col])return true;else if (target > array[row][col])row++;elsecol--;}return false;
}

感觉比较好的解题思路:分析题意,选择最优的比较路径,数组对角线的值是最值,先与最值比较,太大就和比他小的比,向上比.太下就和比他小的比,向下.

两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9, 返回 [0, 1]

class Solution {public int[] twoSum(int[] nums, int target) {for (int i = 0; i < nums.length; i++){for (int j = i + 1; j <nums.length; j++){if (nums[i] + nums[j] == target){return new int[]{i,j};}}}return  new int[]{};}
}

替换空格

实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

public static String replaceSpace(StringBuffer str) {String string = str.toString();// 字符序列替换//string = string.replace(" ","%20");// 正则表达式换string = string.replaceAll(" ", "%20");return string;
}

 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

• 示例：
• 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
• 输出：7 -> 0 -> 8
• 原因：342 + 465 = 807

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode root = new ListNode(0);ListNode cursor = root;int carry = 0;while(l1 != null || l2 != null || carry != 0) {int l1Val = l1 != null ? l1.val : 0;int l2Val = l2 != null ? l2.val : 0;int sumVal = l1Val + l2Val + carry;carry = sumVal / 10;ListNode sumNode = new ListNode(sumVal % 10);cursor.next = sumNode;cursor = sumNode;if(l1 != null) l1 = l1.next;if(l2 != null) l2 = l2.next;}return root.next;}
}

从尾到头打印链表

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {ListNode temp = listNode;ArrayList list = new ArrayList();ArrayList lists = new ArrayList();if(temp == null){return list;}while(temp != null){list.add(temp.val);temp = temp.next;}for(int i = list.size() -1; i >=0; i--){lists.add(list.get(i));}return lists;
}

思路分析:

• 利用List的有序性和Stack的现进后出的特性
• 利用递归实现,
• 利用数组反转

扩展,链表反转:

/*** @Author Liruilong* @Description  链表反转* @Date 16:58 2019/9/2* @Param [listNode1]* @return void**/
public static  void  linkInt(ListNode listNode1){// 链表的反转,
// 思路一: 递归反转法,在反转当前节点之前先反转后续节点,从头节点开始
// 思路二:遍历反转法: 从前往后反转各个节点的指针域指向.
}
// 递归反转
public  static  ListNode Reverse(ListNode listNode){if ( listNode == null || listNode.next == null){return  listNode;}ListNode reNode = Reverse(listNode.next);listNode.next.next = listNode;listNode.next = null;return  reNode;
}
// 遍历反转
public  static  ListNode Reverses(ListNode listNode){if (listNode == null){return listNode;}// 上一节点ListNode prt = listNode;// 当前节点ListNode cur = listNode.next;// 临时节点ListNode temp ;while (cur != null){temp = cur.next;cur.next = prt;// 反转指针域的指向prt = cur; // 指针往下移动cur = temp;}listNode.next = null;return prt;
}

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回

public TreeNode reConstructBinaryTree(int [] pre,int [] in) {if(pre == null || in == null){return null;}TreeNode root = reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);return root;
}
private TreeNode reConstructBinaryTree(int[] pre,int startPre,int endPre,int[] in,int startIn,int endIn){if(startPre>endPre||startIn>endIn){return null;}//前序遍历的第一个数字是根节点的值TreeNode root = new TreeNode(pre[startPre]);//遍历中序数组，找到根节点的位置,创建左右子树for(int i = startIn;i <=endIn; i++){if(in[i]==pre[startPre]){root.left = 
reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);root.right = 
reConstructBinaryTree(pre,startPre+i+1-startIn,endPre,in,i+1,endIn);}}return root;
}

整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。溢出返回0

• 思路：
• 通过循环将数字x的每一位拆开，在计算新值时每一步都判断是否溢出。

• public int reverse(int x) {int ans = 0;while (x != 0) {int pop = x % 10;if (ans > Integer.MAX_VALUE / 10 || (ans == Integer.MAX_VALUE / 10 && pop > 7))return 0;if (ans < Integer.MIN_VALUE / 10 || (ans == Integer.MIN_VALUE / 10 && pop < -8))return 0;ans = ans * 10 + pop;x /= 10;}return ans;
  }
  

   

• 溢出条件有两个，一个是大于整数最大值MAX_VALUE，另一个是小于整数最小值MIN_VALUE，设当前计算结果为ans，下一位为pop。
• 从ans * 10 + pop > MAX_VALUE这个溢出条件来看
• 当出现 ans > MAX_VALUE / 10 且 还有pop需要添加 时，则一定溢出
• 当出现 ans == MAX_VALUE / 10 且 pop > 7 时，则一定溢出，7是2^31 - 1的个位数
• 从ans * 10 + pop < MIN_VALUE这个溢出条件来看
• 当出现 ans < MIN_VALUE / 10 且 还有pop需要添加 时，则一定溢出
• 当出现 ans == MIN_VALUE / 10 且 pop < -8 时，则一定溢出，8是-2^31的个位数

无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

• 示例 1:
• 输入: "abcabcbb"
• 输出: 3
• 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
• 示例 2:
• 输入: "bbbbb"
• 输出: 1
• 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
• 示例 3:
• 输入: "pwwkew"
• 输出: 3
• 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
•      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

• public static int lengthOfLongestSubstring(String s) {if (s.equals(" ")){return 1;}// 滑窗LinkedList<Character> linkedList = new LinkedList<>();// 最大互异连续子串大小int size = 0;char[] chars = s.toCharArray();for (int i = 0; i < chars.length; i++){if (!linkedList.contains(chars[i])){linkedList.addLast(chars[i]);size = linkedList.size() > size ? linkedList.size() : size;}else {size = linkedList.size() > size ? linkedList.size() : size;while (linkedList.removeFirst() != chars[i]){}linkedList.addLast(chars[i]);}}return size;
  }
  

  用两个栈实现队列

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

• public static class Solutions {Stack<Integer> stack1 = new Stack<Integer>();Stack<Integer> stack2 = new Stack<Integer>();public void push(int node) {stack1.push(node);}public int pop() {if(stack1.empty()&&stack2.empty()){throw new RuntimeException("Queue is empty!");}if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.pop());}}return stack2.pop();}
  }
  

  思路：栈特性是先进后出,队列的特性为先进先出.

旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

public int minNumberInRotateArray(int [] array) {if(array.length == 0){return 0;}for(int i = 0; i < array.length; i++){if( array[i] > array[i+1]){return array[i+1];}}return 0;
}

斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

n<=39   嘻嘻，三种方法。

//递归方式
public static long fibonacci0(int n){if (n == 1 || n == 2)return 1;if (n > 2)return fibonacci0(n-1) + fibonacci0(n-2);return 0;
}

// 数组方式
public static long fibonacci2(int n){long  a = 1L, b = 1L, c=0L;long[] array = new long[n];array[0] = a;array[1] = b;if (n < 1)return  0;if (n == 1 || n == 2)return 1;if (n > 2)for (int i = 2; i < array.length; i++)array[i] = array[i-1] + array[i-2];return array[n-1];
}

public static long fibonacci1(int n){long  a = 1L, b = 1L, c=0L;if (n < 1){return  0;}if (n > 2){for (int i=3; i <= n; i++){c = a + b;a = b;b = c;}}if (n ==1 || n==2){return 1;}return c;
}

斐波那契扩展:跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

对于本题,前提只有 一次 1阶或者2阶的跳法。

a.如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);

b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)

c.由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2) 

d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2

e.可以发现最终得出的是一个斐波那契数列：

              | 1, (n=1)

f(n) =     | 2, (n=2)

            | f(n-1)+f(n-2) ,(n>2,n为整数)

public int JumpFloor(int target) {if(target ==1){return 1;}else if(target == 2){return 2;}else{return JumpFloor(target -1) + JumpFloor(target -2);}
}

斐波那契扩展:矩形覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法

public int RectCover(int target) {if(target == 1 ||target == 2){return target;}else if(target == 0){return 0;}else{return RectCover(target -1) + RectCover(target -2);}
}

变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法

贪心算法，获取所有的可能，：

因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级

跳1级，剩下n-1级，则剩下跳法是f(n-1)

跳2级，剩下n-2级，则剩下跳法是f(n-2)

所以f(n)=f(n-1)+f(n-2)+...+f(1)

因为f(n-1)=f(n-2)+f(n-3)+...+f(1)

所以f(n)=2*f(n-1)

public int JumpFloorII(int target) {if(target == 1){return 1;}else if(target == 2){return 2;}else{return JumpFloorII(target - 1) << 1;}
}

二进制数中1的个数

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

思路：在二进制整数中，一个数减一可使二进制数最后一位1变成零，之后的0都变成1，利用这个特性，原二进制数与减1的二进制数做与运算，得到的是去掉最有一位1的二进制数，依次循环，可以知道有几个1；

位运算:

public int NumberOf1(int n) {int count = 0;while(n!= 0){count++;n = n & (n - 1);}return count;
}

Integer方法:

public int NumberOf1s(int n) {int t=0;// toBinaryString(n) 以二进制（基数 2）无符号整数形式返回一个整数参数的字符串表示形式。char[]ch=Integer.toBinaryString(n).toCharArray();for(int i=0;i<ch.length;i++){if(ch[i]=='1'){t++;}}return t;
}

数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

public double Power(double base, int exponent) {double  result=1;for(int i=0;i<Math.abs(exponent);i++){result*=base;}if(exponent<0){result=1/result;}return result;
}

public double Power(double base, int exponent) {double  result=1;result = Math.pow(base, exponent);return result;
}

调整数组顺序使奇数位于偶数前

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的

后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

public void reOrderArrays(int [] array) {if (array != null) {int[] even = new int[array.length];int indexOdd = 0;int indexEven = 0;for (int num : array) {if ((num & 1) == 1) {array[indexOdd++] = num;} else {even[indexEven++] = num;}}for (int i = 0; i < indexEven; i++) {array[indexOdd + i] = even[i];}}
}

链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个结点。

// 笨方法
import java.util.ArrayList;
public class Solution {public ListNode FindKthToTail(ListNode head,int k) {if(head == null){return null;}ListNode root = head;ArrayList list =new ArrayList();while(root != null){list.add(root);root = root.next;}return k > list.size() || k <= 0 ? null:(ListNode) list.get(list.size()-k);}

public ListNode FindKthToTail(ListNode head,int k) {ListNode pre=null,p=null;//两个指针都指向头结点p=head;pre=head;//记录k值int a=k;//记录节点的个数int count=0;//p指针先跑，并且记录节点数，当p指针跑了k-1个节点后，pre指针开始跑，//当p指针跑到最后时，pre所指指针就是倒数第k个节点while(p!=null){p=p.next;count++;if(k<1){pre=pre.next;}k--;}//如果节点个数小于所求的倒数第k个节点，则返回空if(count<a) return null;return pre;
}

好办法：

相当于制造了一个K长度的尺子，把尺子从头往后移动，当尺子的右端与链表的末尾对齐的时候，尺子左端所在的结点就是倒数第k个结点！

合并两个排序的列表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

递归方法:

public static ListNode Merge(ListNode list1,ListNode list2) {if (list1 == null){return list2;}if (list2 == null){return list1;}if (list1.val >= list2.val){list2.next = Merge(list1, list2.next);return list2;}else {list1.next = Merge(list1.next, list2);return list1;}
}

普通方法:

public ListNode Merges(ListNode list1,ListNode list2) {ListNode newHead = new ListNode(-1);ListNode current = newHead;while (list1 != null && list2 != null) {if (list1.val < list2.val) {current.next = list1;list1 = list1.next;} else {current.next = list2;list2 = list2.next;}current = current.next;}if (list1 != null) current.next = list1;if (list2 != null) current.next = list2;return newHead.next;
}

树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路：先判断A树和B树根节点是否相同，相同，遍历左右节点，不相同，A树的左右节点做根节点与B树点比较。依次递归。当B树遍历完之后，返回true。当A遍历完B树未遍历完，返回false。当A节点与B值不等时，返回false。

public boolean HasSubtree(TreeNode root1,TreeNode root2) {boolean result = false;//当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回falseif (root2 != null && root1 != null) {//如果找到了对应Tree2的根节点的点if(root1.val == root2.val){//以这个根节点为为起点判断是否包含Tree2result = doesTree1HaveTree2(root1,root2);}//如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2if (!result) {result = HasSubtree(root1.left,root2);}//如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2if (!result) {result = HasSubtree(root1.right,root2);}}//返回结果return result;
}
public static boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {//如果Tree2已经遍历完了都能对应的上，返回trueif (node2 == null) {return true;}//如果Tree2还没有遍历完，Tree1却遍历完了。返回falseif (node1 == null) {return false;}//如果其中有一个点没有对应上，返回falseif (node1.val != node2.val) {return false;}//如果根节点对应的上，那么就分别去子节点里面匹配return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);
}

二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

public void Mirror(TreeNode root) {if(root == null) {return ;}TreeNode temp = root.left;root.left = root.right;root.right = temp;Mirror(root.left);Mirror(root.right);
}

顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

public ArrayList<Integer> printMatrix_2(int[][] matrix) {ArrayList<Integer> al = new ArrayList<>();int row = matrix.length;while (row != 0) {for (int i = 0; i < matrix[0].length; i++) al.add(matrix[0][i]);if (row == 1)break;matrix = turn(matrix);row = matrix.length;}return al;
}
private int[][] turn(int[][] matrix) {
int col = matrix[0].length;int row = matrix.length;int[][] newMatrix = new int[col][row - 1];for (int j = col - 1; j >= 0; j--) for (int i = 1; i < row; i++) newMatrix[col - 1 - j][i - 1] = matrix[i][j];   return newMatrix;
}

public ArrayList<Integer> printMatrix(int [][] matrix) {ArrayList<Integer> result=new ArrayList<Integer>();  //将顺时针输出的矩阵元素都存放在结果列表里if(matrix.length==0) return result;  //如果矩阵行数为0，说明是空矩阵，则直接返回空列表int row=matrix.length,column=matrix[0].length;  //初始化矩阵行数和列数if(column==0) return result;int layers=(Math.min(row,column)-1)/2+1;for(int i=0;i<layers;i++){for(int j=i;j<column-i;j++) result.add(matrix[i][j]);for(int k=i+1;k<row-i;k++) result.add(matrix[k][column-1-i]);for(int j=column-2-i;(j>=i)&&(row-1-i!=i);j--)result.add(matrix[row-1-i][j]);for(int k=row-2-i;(k>i)&&(column-1-i!=i);k--)result.add(matrix[k][i]);}return result;
}

public ArrayList<Integer> printMatrix_1(int[][] matrix) {ArrayList<Integer> al = new ArrayList<>();int row = matrix.length;if (row == 0)return al;int col = matrix[0].length;// 短的边/2，向上取整int circle = ((row > col ? col : row) + 1) / 2;for (int i = 0; i < circle; i++) {// 从左向右打印，j=i; j<col-i, 这一行的前i个已经在第i圈从下往上被打印，故j=i// 倒数i个都已经在第i圈从上往下被打印，故j=col-i-1<col-ifor (int j = i; j < col - i; j++)al.add(matrix[i][j]);for (int j = i + 1; j < row - i; j++)al.add(matrix[j][col - i - 1]);
// 从右往左打印，j=col-i-2;j>=i&&row-i-1!=i;，这一行倒数i个已经在第i圈从上往下被打印// 这一行倒数第i+1个已经在从上往下时被打印，故j=col-1-(i+1)=col-i-2// 这一行的前i个已经在从下往上时被打印，故j=i>=i// 当第i圈为0时即从未由上往下打印时，col有多列时，会造成重复打印，故判断row-i-1!=i以避免for (int j = col - i - 2; j >= i && row - i - 1 != i; j--)al.add(matrix[row - i - 1][j]);for (int j = row - i - 2; j > i && col - i - 1 != i; j--)al.add(matrix[j][i]);}return al;
}

包含min方法的栈

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

public class Solution {private ArrayList<Integer> dataList = new ArrayList<>();private ArrayList<Integer> minList = new ArrayList<>();private Integer min = Integer.MAX_VALUE;public void push(int node) {dataList.add(node);if (node <= min) {minList.add(node);min = node;} else { minList.add(min);  }}public int getSize() { return dataList.size();   }public void pop() {int end = getSize() - 1;dataList.remove(end);minList.remove(end);min = minList.get(getSize() - 1);}public int top() { return dataList.get(getSize() - 1);	}public int min() { return min;	}
}

栈的压入，弹出序列

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

public boolean IsPopOrder(int [] pushA,int [] popA) {if(pushA.length == 0 || popA.length == 0)return false;Stack<Integer> s = new Stack<Integer>();//用于标识弹出序列的位置int popIndex = 0;for(int i = 0; i< pushA.length;i++){s.push(pushA[i]);//如果栈不为空，且栈顶元素等于弹出序列while(!s.empty() &&s.peek() == popA[popIndex]){//出栈s.pop();//弹出序列向后一位popIndex++;}}return s.empty();
}

重上往下打印二叉树,层序遍历

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思路：用两个列表，一个存值，一个存节点，节点列表每次获取值后移除

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {ArrayList<Integer> list = new ArrayList<>();ArrayList<TreeNode> queue = new ArrayList<>();if (root == null) {return list;}queue.add(root);while (queue.size() != 0) {TreeNode temp = queue.remove(0);if (temp.left != null){queue.add(temp.left);}if (temp.right != null) {queue.add(temp.right);}list.add(temp.val);}return list;
}

二叉搜索树的后序遍历

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路：
BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。完美的递归定义 : ) 。

public boolean VerifySquenceOfBST(int [] sequence) {if(sequence.length == 0){return false;}if(sequence.length == 1){return true;}return judge(sequence,0,sequence.length-1);
}
public boolean judge(int[] a,int start,int end){if(start >= end){return true;}int i = start;while(a[i] < a[end]){++i;// 确定根节点}for(int j=i;j<end;j++){if(a[j] < a[end]){return false;}}return judge(a,start,i-1) && judge(a,i,end-1);
}

二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

public int TreeDepth(TreeNode pRoot){return pRoot == null? 0 : Math.max(TreeDepth(pRoot.left),TreeDepth(pRoot.right)) + 1;
}

public int TreeDepth(TreeNode pRoot){if(pRoot == null){return 0;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.add(pRoot);int depth = 0, count = 0, nextCount = 1;while(queue.size()!=0){TreeNode top = queue.poll();count++;if(top.left != null){queue.add(top.left);}if(top.right != null){queue.add(top.right);}if(count == nextCount){nextCount = queue.size();count = 0;depth++;}}return depth;}
}

public static void main(List<Integer> nums,int num) {nums.sort((a, b) ->a.compareTo(b));List<Integer> list1 = new  ArrayList<>();int avg = nums.stream().reduce(Integer::sum).get() / 2;for (int i = nums.size() - 1; i >= 0; i--){int s1 = list1== null || list1.size() <= 0 ? 0 :list1.stream().reduce(Integer::sum).get() ;if (Math.abs(avg - s1) > Math.abs(avg - (s1 + nums.get(i)) )){list1.add(nums.remove(i));}else {break;}}System.out.println(Math.abs(nums.stream().reduce(Integer::sum).get()- list1.stream().reduce(Integer::sum).get()));System.out.println(Math.abs(nums.size() - list1.size()));
}

滑动窗口的最大值

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

public static ArrayList<Integer> maxInWindows(int[] num, int size) {// 存放最大值ArrayList<Integer>  ret = new ArrayList<>();// 存放滑动窗口Queue<Integer>  integerQueue = new LinkedList<>();if (num == null){return ret;}if ( num.length < size || size < 1){return ret;}for (int i = 0; i < num.length; i++){if (i == num.length - size + 1)break;for (int j = 0; j < size; j++){((LinkedList<Integer>) integerQueue).addFirst(num[i + j]);}int max = 0;Integer sum = integerQueue.stream().max((a, b) -> a.compareTo(b)).get();ret.add(sum);integerQueue.clear();}return ret;
}

 

这篇关于常见面试算法题带解析整理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---