面试 - 几道编程题 Java笔记

最近面试一家国内外卖NO.1的互联网公司，总共手写了五道题，现将其记录下来。
1.从一个数组中找出满足符合条件的元素:它大于或等于前面所有元素,小于或等于后面所有元素。（这道题当时用很蠢的方法写的，没得什么技术含量，后来回来才去网上看了一下好的方式）

* 1.一个用来记录最大值的数组 * 2.一个用来记录最小值的数组 * 3.一个用来记录结果的数组(使用集合更方便) * * 比如有如下的一个序列： * 1 3 2 4 7 4 3 5 * "一个用来记录最大值的数组"的意思是，遍历到当前位置时，直至该处的最大值 * 1 3 3 4 7 7 7 7 -> max[] * "一个用来记录最小值的数组"的意思是，遍历到当前位置时，直至该处的最小值（反向遍历） * 1 2 2 3 3 3 3 5 -> min[] * 【面试 - 几道编程题】 * 结果数组（集合）存放的是，大于等于max[]数组，小于等于min[]数组的元素 */public class FindNumber {public static ArrayList find(int[] array) {//使用集合来保存符合条件的数 ArrayList result = new ArrayList<>(); int[] max = new int[array.length]; //定义一个存放最大值的数组 int[] min = new int[array.length]; //定义一个存放最小值的数组//先填充max[]和min[]数组 for (int i = 0; i < array.length; i++) { max[i] = array[i]; min[i] = array[i]; }//将max[]数组调整为符合条件的数组 for (int i = 1; i < array.length - 1; i++) { if (max[i] < max[i + 1]) { max[i] = max[i + 1]; } } //将min[]数组调整为符合条件的数组 for (int j = array.length - 1; j > 0; j--) { if (min[j] < min[j - 1]) { min[j - 1] = min[j]; } }//进行比较，输出满足条件的结果集合 for (int i = 0; i < array.length; i++) { if (array[i] >= max[i] && array[i] <= min[i]) { result.add(array[i]); } }return result; }//测试方法 public static void main(String[] args) { int[] array = {1, 3, 2, 4, 7, 4, 3, 5}; System.out.println(find(array)); }}

2.写一个死锁。

public class DeadLock { private static Object object1 = new Object(); private static Object object2 = new Object(); public static void main(String[] args) {DeadLock deadLock = new DeadLock(); new Thread(deadLock.new Thread1()).start(); new Thread(deadLock.new Thread2()).start(); }class Thread1 implements Runnable { @Override public void run() { synchronized (object1) { System.out.println("get lock1"); try { Thread.sleep(100); } catch (InterruptedException e) { e.printStackTrace(); }synchronized (object2) { System.out.println("get lock 2"); } } } }class Thread2 implements Runnable { @Override public void run() { synchronized (object2) { System.out.println("get lock2"); try { Thread.sleep(100); } catch (InterruptedException e) { e.printStackTrace(); }synchronized (object1) { System.out.println("get lock 1"); } } } }}

3.跳台阶。（这是剑指offer上的一道题，只用一行代码就写出来了）
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

public class Solution { public int JumpFloorII(int target) {//除了最后一个台阶，每个台阶都有两种选择，跳或者不跳，但是最后一个台阶必须跳return (int)Math.pow(2,target-1); } }

4.二分查找。这个是基础了，以前也写过。

public class BinarySearch { public int getPos(int[] array, int n, int value) { int result = -1; int position = 0; int left = 0; int right = n; position = (left + right) / 2; while (position >= left && position <= right) { if (array[position] > value) { right = position; position = (left + right) / 2; }else if (array[position] < value) { left = position; position = (left + right) / 2; } else { result = position; for (int i = 0; i <= position; i++) { if (array[position - i] == value) result = position - i; else return result; }return result; } }return result; } }

5.求一棵树的最大连通子节点的个数（求树宽度）。
我是这样想的，先求出左子树的高度，再求出右子树的高度，将两个高度相加再减去1（因为根结点加了两次），就是树的宽度了。（如有不对之处，请及时指正）

class TreeNode { int value; TreeNode left = null; TreeNode right = null; TreeNode(int value) { this.value = https://www.it610.com/article/value; } }public class TreeWidth {public static int treeWidth(TreeNode root) { if (root == null) { return 0; } int leftWidth = treeWidth(root.left); int rightWidth = treeWidth(root.right); int width = leftWidth + rightWidth - 1; return width; }}