面试中遇到的手撕代码题（一）_面试手撕代码的数据结构

1.重建二叉树

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

根据二叉树的性质：

public class Rebuild_Tree {

    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        // 从头开始重建
        TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in, 0,
                in.length - 1);
        return root;
    }

    public TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre,
            int[] in, int startIn, int endIn) {
        if (startPre > endPre || startIn > endIn)// 表示已经构建好了
            return null;
        TreeNode node = new TreeNode(pre[startPre]);// 前序遍历第一个就是根节点了
        for (int i = 0; i < in.length; i++) {
            if (pre[startPre] == in[i]) {
                node.left = reConstructBinaryTree(pre, startPre + 1, startPre
                        + i - startIn, in, startIn, i - 1);
                node.right = reConstructBinaryTree(pre, startPre + i - startIn
                        + 1, endPre, in, i + 1, endIn);
            }
        }
        return node;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

2.旋转数组的最小数字

需要考虑三种情况：
(1)array[mid] > array[high]:
出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。
low = mid + 1
(2)array[mid] == array[high]:
出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边还是右边,这时只好一个一个试 ，high = high - 1
(3)array[mid] < array[high]:
出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左
边。因为右边必然都是递增的。
(4)当剩下两个数据的时候，那么最小值就是小的那一个树。

public class Rotate_Min {

    public static int minNumberInRotateArray(int[] array) {
        if(array.length==1) return array[0];
        int low = 0, high = array.length - 1, mid;
        int min = 0;
        while (low < high) {
            if (low + 1 == high)// 只剩下一个的时候target肯定是最小的哪一个
                min = Math.min(array[low], array[high]);
            mid = (low + high) / 2;
            if (array[mid] > array[high])
                low = mid + 1;
            if (array[mid] < array[high])
                high = mid;// 注意，这里不是mid-1.
            else {
                high = high - 1;
            }
        }
        return min;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

3.给一个数组返回最小堆或者最大堆

先来看看数据结构

然后大顶堆用数组表示如下：

我们用简单的公式来描述一下堆的定义就是：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

public class Max_Heap {

    public static int[] maxHeap(int[] array) {
        // 1.构建大顶堆
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            // 从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(array, i, array.length);
        }
        return array;
    }

    private static void adjustHeap(int[] array, int i, int length) {
        int parent = array[i];
        for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
            // 2*i+1表示左节点，k = k * 2 + 1表示继续调整子节点
            if (k + 1 < length && array[k] < array[k + 1])
                k = k + 1;// 找到子节点中更大的节点
            if (array[k] > parent) {
                array[i] = array[k];// 父节点变为更大的值
                i = k;// 修改i的值，使之成爲新的要調整的父節點
            } else {
                break;// 表示无需调整，因为是自底向上的
            }
        }
        array[i] = parent;// 将temp值放到最终的位置
    }

    public static void main(String[] args) {
        int[] array = { 4, 6, 8, 5, 9 };
        int[] maxHeap = maxHeap(array);
        for (int i : maxHeap) {
            System.out.print(i + " ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

那么手写堆排序你会不会？

public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12

---

4.最大公约数非递归算法

求a、b两个数的最大公约数。

if(a < b){
        temp = a;
        a = b;
        b = temp;

    }
    while(a%b != 0){
            temp = a%b;
            a = b;
            b = temp;
    }
    return b;
1
2
3
4
5
6
7
8
9
10
11
12

---

5.二维平面有n个点，求一条直线，使最多的点落在该直线上

可以根据A点跟其他点所构成线段的斜率判断与A点共线的点的个数.遍历所有点,取出最大值即可,
1.考虑重复点的情况.
2.考虑斜率为无穷大的情况.

import java.util.HashMap;

//定义坐标点

class Point {
    int x;
    int y;
    Point() { x = 0; y = 0; }
    Point(int a, int b) { x = a; y = b; }
}

public class Solution {
//判断坐标点集是否为空
    public int maxPoints(Point[] points) {
        if(points==null||points.length==0){
            return 0;
        }
//建立Hash表
        HashMap<Double,Integer> map= new HashMap<Double,Integer>();
        int max=1;
        for(int i=0;i<points.length;i++){
            map.clear();       //每次重设A点时,清空Hash表
            map.put((double)Integer.MIN_VALUE,1);//斜率—点数
            int dup=0;
            for(int j=i+1;j<points.length;j++){
            //判断点是否重合
                if(points[j].x==points[i].x&&points[j].y==points[i].y){
                    dup++;
                    continue;
                }
            //判断斜率的K值.
                double key=points[j].x-points[i].x==0?
                        Integer.MAX_VALUE:
                            0.0+(double)(points[j].y-points[i].y)/(double)(points[j].x-points[i].x);
                if(map.containsKey(key)){
                    map.put(key,map.get(key)+1);
                }else{
                    map.put(key, 2);
                }
            }
            for(int temp:map.values()){
                if(temp+dup>max){
                    max=temp+dup;
                }
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

---

6.两数之和

题目的意思：给定任意一个数组，和一个固定值，要求你在数组中找出满足a+b = target的情况，并返回这两个值的索引。

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
比较简单，我们只需要借助一个HashMap即可
其中key=target-nums[i],value=数组的下标

import java.util.HashMap;
import java.util.Map;
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < numbers.length; i++) {
            if(map.containsKey(numbers[i])){
                result[0] = map.get(numbers[i])+1;
                result[1] = i+1;
            }else {
                map.put(target-numbers[i], i);
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

7.三个数之和

这里我们可以借鉴两数之和的思想，将三数之和看成两之和与一个target。

public class Three_Sum {

    public static Set<ArrayList<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        Set<ArrayList<Integer>> result = new HashSet<>();
        for (int i = 0; i < num.length; i++) {
            //target = target-num[i]
            twoSum(num, i, target - num[i], result);
        }
        return result;
    }
    //两数之和的方法
    public static void twoSum(int[] numbers, int start,
            int target, Set<ArrayList<Integer>> result) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = start + 1; i < numbers.length; i++) {
            if (map.containsKey(numbers[i])) {
                ArrayList<Integer> round = new ArrayList<Integer>();
                round.add(numbers[start]);
                round.add(numbers[map.get(numbers[i])]);
                round.add(numbers[i]);
                result.add(round);
            }
            map.put(target-numbers[i], i);
        }
    }

    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        Set<ArrayList<Integer>> threeSum = threeSum(nums);
        for (ArrayList<Integer> arrayList : threeSum) {
            for (Integer integer : arrayList) {
                System.out.print(integer+",");
            }
            System.out.println();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

ps：第一部分先写到这里