查看原文
其他

【面试现场】如何编程获得最多的年终红包奖?

channingbreeze 互联网侦察 2019-02-16


小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。


今天小史又去了一家互联网小巨头公司面试了。



【面试现场】



小史眉头一皱,发现事情并不简单。


题目:在数字矩阵中,从左上角到右下角,每次只能向右或向下,如何规划路径,能获得最大数字总和?


小史开始仔细分析问题,一时间竟想不到很好的方法。


小史心中反复默念题目,进行思考。


小史仔细回忆起了吕老师教他的华容道搜索算法



【请教大神】


回到学校,小史把面试情况和吕老师说了一下。


吕老师:红色和蓝色两条路都能到达中间的100这个点,但是很明显,红色的路拿到的奖金更多。所以蓝色的路,后面不管再怎么走,都不可能拿到最大的奖金数了。

吕老师:假设蓝色路径再往后走出一条绿色路径是最大奖金,那么我把蓝色路径替换成红色路径,红色加绿色得到的奖金就比蓝色加绿色得到的多呀。


【记忆化搜索】


小史:哦,我明白了,这样我每搜到一个点,都可以和这个数比较,如果比它大,就更新这个数,继续搜,如果比它小,就不搜了,直接剪枝。

理解了算法之后,小史的代码写起来也是非常快,不一会儿就写好了:


DeepFirstSearch.java

import java.util.ArrayList;
import java.util.List;

/**
 * @author xiaoshi on 2018/10/20.
 */

public class DeepFirstSearch {

    // 定义best(i,j) 和 M N
    private int[][] best = null;
    private int M = 0;
    private int N = 0;

    // 定义方向常量
    private static final int RIGHT = 1;
    private static final int DOWN = 2;
    // 当前搜索的方向数组
    private List<Integer> curPath = null;
    // 记录最大值对应的方向数组
    private Integer[] bestPath = null;

    // 当前搜索点
    private int curX = 0;
    private int curY = 0;
    // 当前搜索累计值
    private int value = 0;
    // 记录搜索到的最大值
    private int maxValue = 0;

    // 往某个方向前进
    private void goDir(int dir, int[][] matrix) {
        // 前进
        if(dir == DOWN) {
            curX++;
            value += matrix[curX][curY];
        } else if(dir == RIGHT) {
            curY++;
            value += matrix[curX][curY];
        }
        // 记录方向
        curPath.add(dir);
    }

    // 往某个方向回退
    private void goBackDir(int dir, int[][] matrix) {
        // 回退
        if(dir == DOWN) {
            value -= matrix[curX][curY];
            curX--;
        } else if(dir == RIGHT) {
            value -= matrix[curX][curY];
            curY--;
        }
        // 移除方向
        curPath.remove(curPath.size() - 1);
    }

    // 深搜
    private void search(int dir, int[][] matrix) {
        // 往某方向前进
        goDir(dir, matrix);
        // 到达终点
        if(curX == M - 1 && curY == N - 1) {
            if(value > maxValue) {
                // 记录最大值和路径
                maxValue = value;
                bestPath = new Integer[curPath.size()];
                curPath.toArray(bestPath);
            }
        } else if(value <= best[curX][curY]) {
            // 不搜索了,等着goBack,剪枝
        } else {
            // 更新best(i,j),记忆
            best[curX][curY] = value;
            // 朝下一个方向搜索
            if(curX < M - 1) {
                search(DOWN, matrix);
            }
            if(curY < N - 1) {
                search(RIGHT, matrix);
            }
        }
        // 往某方向回退
        goBackDir(dir, matrix);
    }

    // 获取最大值
    public int getMaxAward(int[][] matrix) {
        // 初始化
        value = matrix[0][0];
        M = matrix.length;
        N = matrix[0].length;
        best = new int[M][N];
        curPath = new ArrayList<Integer>();
        // 开始搜索
        if(M > 1) {
            search(DOWN, matrix);
        }
        if(N > 1) {
            search(RIGHT, matrix);
        }
        // 最大值
        return maxValue;
    }

    // 打印最佳路径
    public void printBestPath() {
        // 打印路径
        for(int i = 0; i < bestPath.length; i++) {
            if(bestPath[i] == RIGHT) {
                System.out.print("右 ");
            } else {
                System.out.print("下 ");
            }
        }
        System.out.println();
    }

}

(友情提示:可左右滑动)


Main.java

/**
 * @author xiaoshi on 2018/10/20.
 */

public class Main {

    public static void main(String[] args) {

        int[][] matrix1 = {
            {300500560400160},
            {1000100200340690},
            {600500500460320},
            {300400250210760}
        };

        int[][] matrix2 = {
            {3005002560400},
            {1000100200340},
            {600500500460},
            {300400250210},
            {860690320760}
        };

        DeepFirstSearch dp = new DeepFirstSearch();

        System.out.println(dp.getMaxAward(matrix1));
        dp.printBestPath();

        System.out.println(dp.getMaxAward(matrix2));
        dp.printBestPath();

    }
}

(友情提示:可左右滑动)


运行结果

4440
下 下 右 右 右 右 下 
5530
右 右 右 下 下 下 下 


【记忆广搜】


吕老师:记忆深搜确实可以剪枝,但是假如有人刻意安排数字,把较小的数都安排在你先搜的路径上,那么你的计算量还是不会减少太多。

小史:还有这么坏的人呢?不过你这样一说我到想起来,深搜确实缺少一种“全局观”,可能第一条路搜完了,再来看第二条路,发现更好,结果第一条路全白搜了。

理解了算法之后,小史的代码写起来也是非常快,不一会儿就写好了:


BreadthFirstSearch.java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author xiaoshi on 2018/10/20.
 */

public class BreadthFirstSearch {

    // 定义 M N
    private int M = 0;
    private int N = 0;

    // 定义方向常量
    private static final int RIGHT = 1;
    private static final int DOWN = 2;

    // 代表广搜的每一步,通过lastItem链起来
    private class SearchItem {
        private int curX;
        private int curY;
        private int dir;
        // 这里记录 (curX, curY) 路径的最大值,相当于best(i,j)
        private int value;
        private SearchItem lastItem;
        public SearchItem(int curX, int curY, int dir, int value) {
            this.curX = curX;
            this.curY = curY;
            this.dir = dir;
            this.value = value;
        }
    }

    // 最终搜到的结果
    private SearchItem bestItem = null;

    // 广搜的存储队列
    private List<SearchItem> statusToSearch = new LinkedList<SearchItem>();

    // 替换广搜队列中较小的item,返回值为搜索队列中是否找到相应item
    private boolean replaceStatusList(SearchItem newItem) {
        // 是否找到
        boolean find = false;
        // 遍历查找
        for(int i=0; i<statusToSearch.size(); i++) {
            SearchItem searchItem = statusToSearch.get(i);
            // 找到对应item
            if(searchItem.curX == newItem.curX && searchItem.curY == searchItem.curY) {
                find = true;
                // 这里相当于在对比best(i,j)
                if(searchItem.value < newItem.value) {
                    // 替换成更好的item
                    statusToSearch.remove(i);
                    statusToSearch.add(i, newItem);
                }
                break;
            }
        }
        return find;
    }

    // 广搜
    private void search(int[][] matrix) {

        // 搜索队列中不为空
        while(statusToSearch.size() > 0) {
            // 从搜索队列中获取一个item
            SearchItem searchItem = statusToSearch.remove(0);
            int curX = searchItem.curX;
            int curY = searchItem.curY;
            int curValue = searchItem.value;
            // 如果已经搜到
            if(curX == M - 1 && curY == N - 1) {
                bestItem = searchItem;
            }
            // 可往下搜
            if(curX < M - 1) {
                SearchItem newItem = new SearchItem(curX + 1, curY, DOWN, curValue + matrix[curX + 1][curY]);
                newItem.lastItem = searchItem;
                // 是否替代
                if(!replaceStatusList(newItem)) {
                    // 搜索队列中没有找到,则添加
                    statusToSearch.add(newItem);
                }
            }
            // 可往右搜
            if(curY < N - 1) {
                SearchItem newItem = new SearchItem(curX, curY + 1, RIGHT, curValue + matrix[curX][curY + 1]);
                newItem.lastItem = searchItem;
                // 是否替代
                if(!replaceStatusList(newItem)) {
                    // 搜索队列中没有找到,则添加
                    statusToSearch.add(newItem);
                }
            }
        }
    }

    // 获取最大值
    public int getMaxAward(int[][] matrix) {
        // 初始化
        M = matrix.length;
        N = matrix[0].length;
        int value = matrix[0][0];
        SearchItem searchItem = new SearchItem(000value);
        statusToSearch.add(searchItem);
        // 开始搜索
        search(matrix);
        // 返回最大值
        return bestItem.value;
    }

    // 打印最佳路径
    public void printBestPath() {
        List<Integer> dirList = new ArrayList<Integer>();
        SearchItem curSearchItem = bestItem;
        // 根据lastItem,找到路径
        while(null != curSearchItem) {
            int dir = curSearchItem.dir;
            if(dir == DOWN) {
                dirList.add(DOWN);
            } else if(dir == RIGHT) {
                dirList.add(RIGHT);
            }
            curSearchItem = curSearchItem.lastItem;
        }
        // 打印路径
        for(int i = dirList.size() - 1; i >= 0; i--) {
            if(dirList.get(i) == DOWN) {
                System.out.print("下 ");
            } else if(dirList.get(i) == RIGHT) {
                System.out.print("右 ");
            }
        }
        System.out.println();
    }

}

(友情提示:可左右滑动)


Main.java

/**
 * @author xiaoshi on 2018/10/20.
 */

public class Main {

    public static void main(String[] args) {

        int[][] matrix1 = {
            {300500560400160},
            {1000100200340690},
            {600500500460320},
            {300400250210760}
        };

        int[][] matrix2 = {
            {3005002560400},
            {1000100200340},
            {600500500460},
            {300400250210},
            {860690320760}
        };

        BreadthFirstSearch dp = new BreadthFirstSearch();

        System.out.println(dp.getMaxAward(matrix1));
        dp.printBestPath();

        System.out.println(dp.getMaxAward(matrix2));
        dp.printBestPath();

    }
}

(友情提示:可左右滑动)


运行结果

4440
下 下 右 右 右 右 下 
5530
右 右 右 下 下 下 下 


【动态规划】


吕老师:小史,代码写得不错,咱们再来看看广搜的过程,其实就是在搜索的过程中从左上到右下计算出了best(i,j),所以为啥我们不能直接算出best(i,j)呢?

理解了算法之后,小史的代码写起来也是非常快,不一会儿就写好了:


DynamicProgramming.java

import java.util.ArrayList;
import java.util.List;

/**
 * @author xiaoshi on 2018/10/20.
 */

public class DynamicProgramming {

    // 定义best(i,j) 和 M N
    private int[][] best = null;
    private int M = 0;
    private int N = 0;

    // 定义方向常量
    private static final int RIGHT = 1;
    private static final int DOWN = 2;
    // 存储最好路径
    private List<Integer> bestPath = null;

    // 计算best(i,j)
    private void calcDp(int[][] matrix) {
        // 初始化
        M = matrix.length;
        N = matrix[0].length;
        best = new int[M][N];
        // 计算
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < N; j++) {
                // 边界
                if(i == 0 && j == 0) {
                    best[i][j] = matrix[i][j];
                } else if(i == 0) {
                    best[i][j] = best[i][j - 1] + matrix[i][j];
                } else if(j == 0) {
                    best[i][j] = best[i - 1][j] + matrix[i][j];
                } else {
                    // 状态转移
                    best[i][j] = Math.max(best[i - 1][j], best[i][j - 1]) + matrix[i][j];
                }
            }
        }
    }

    // 获取最大值
    public int getMaxAward(int[][] matrix) {
        // 计算状态
        calcDp(matrix);
        // 计算最佳路径
        calcBestPath();
        // 返回最大值
        return best[matrix.length - 1][matrix[0].length - 1];
    }

    // 计算最佳路径,从后往前
    private void calcBestPath() {
        bestPath = new ArrayList<Integer>();
        // 总共走 M + N - 2 步
        int curX = M - 1;
        int curY = N - 1;
        // 根据best(i,j)计算最佳路径
        for(int i = 0; i < M + N - 2; i++) {
            if(curX == 0) {
                curY--;
                bestPath.add(RIGHT);
            } else if(curY == 0) {
                curX--;
                bestPath.add(DOWN);
            } else {
                if(best[curX - 1][curY] > best[curX][curY - 1]) {
                    curX--;
                    bestPath.add(DOWN);
                } else {
                    curY--;
                    bestPath.add(RIGHT);
                }
            }
        }
    }

    // 打印最佳路径
    public void printBestPath() {
        // 倒序打印
        for(int i = bestPath.size() - 1; i >= 0; i--) {
            if(bestPath.get(i) == RIGHT) {
                System.out.print("右 ");
            } else {
                System.out.print("下 ");
            }
        }
        System.out.println();
    }

}

(友情提示:可左右滑动)


Main.java

/**
 * @author xiaoshi on 2018/10/20.
 */

public class Main {

    public static void main(String[] args) {

        int[][] matrix1 = {
            {300500560400160},
            {1000100200340690},
            {600500500460320},
            {300400250210760}
        };

        int[][] matrix2 = {
            {3005002560400},
            {1000100200340},
            {600500500460},
            {300400250210},
            {860690320760}
        };

        DynamicProgramming dp = new DynamicProgramming();

        System.out.println(dp.getMaxAward(matrix1));
        dp.printBestPath();

        System.out.println(dp.getMaxAward(matrix2));
        dp.printBestPath();

    }
}

(友情提示:可左右滑动)


运行结果

4440
下 下 右 右 右 右 下 
5530
右 右 右 下 下 下 下 


【动态规划解析】


吕老师:状态的定义要满足几个点,第一,问题的答案是某种状态,或者可由状态进行推导。第二,当前状态可以由之前的状态推导而来。

【状态压缩】


小史:哦,我知道了,这道题,如果按照斜线方向来计算,只需要保留一条斜线的状态,就能计算出下一条斜线。所以之前的状态就不需要保留了。


理解了算法之后,小史的代码写起来也是非常快,不一会儿就写好了:


DpCompressed.java

/**
 * @author xiaoshi on 2018/10/20.
 */

public class DpCompressed {

    // 定义best(i) 和 M N
    private int[][] best = null;
    private int M = 0;
    private int N = 0;

    // 计算best(i)
    private void calcDp(int[][] matrix) {
        // 初始化
        M = matrix.length;
        N = matrix[0].length;
        int minMN = Math.min(M, N);
        int maxMN = Math.max(M, N);
        // best只需要M和N的最小值长度就行
        best = new int[2][minMN];
        // 需要计算 M+N-1 条斜线
        for(int i = 0; i < M + N - 1; i++) {
            // 第 i 条斜线的起始x坐标
            int startX = 0;
            // 第 i 条斜线的起始y坐标
            int startY = i;
            // 第 i 条斜线的数字个数
            int number = i + 1;
            if(i >= N) {
                startX = i + 1 - N;
                startY = N - 1;
            }
            if(i >= minMN) {
                number = minMN;
            }
            if(i >= maxMN) {
                number = M + N - i - 1;
            }
            // 第 i 条斜线上的 number 个数
            for(int j = 0; j < number; j++) {
                // 起始点
                if(i == 0 && j == 0) {
                    best[1][j] = matrix[startX + j][startY - j];
                } else {
                    if (i < N) {
                        // 前半部分
                        if (j == 0) {
                            // 上边界
                            best[1][j] = best[0][j] + matrix[startX + j][startY - j];
                        } else if (j == number - 1) {
                            // 左边界
                            best[1][j] = best[0][j-1] + matrix[startX + j][startY - j];
                        } else {
                            // 状态转移
                            best[1][j] = Math.max(best[0][j], best[0][j-1]) + matrix[startX + j][startY - j];
                        }
                    } else {
                        // 后半部分
                        if(i < M && j == number - 1) {
                            // 左边界
                            best[1][j] = best[0][j] + matrix[startX + j][startY - j];
                        } else {
                            // 状态转移
                            best[1][j] = Math.max(best[0][j], best[0][j+1]) + matrix[startX + j][startY - j];
                        }
                    }
                }
            }
            // 将best[1]上的状态拷贝到best[0]
            for(int j = 0; j < number; j++) {
                best[0][j] = best[1][j];
            }
        }
    }

    // 获取最大值
    public int getMaxAward(int[][] matrix) {
        calcDp(matrix);
        return best[0][0];
    }

}

(友情提示:可左右滑动)


Main.java

/**
 * @author xiaoshi on 2018/10/20.
 */

public class Main {

    public static void main(String[] args) {

        int[][] matrix1 = {
            {300500560400160},
            {1000100200340690},
            {600500500460320},
            {300400250210760}
        };

        int[][] matrix2 = {
            {3005002560400},
            {1000100200340},
            {600500500460},
            {300400250210},
            {860690320760}
        };

        DpCompressed dp = new DpCompressed();

        System.out.println(dp.getMaxAward(matrix1));

        System.out.println(dp.getMaxAward(matrix2));

    }
}

(友情提示:可左右滑动)


运行结果

4440
5530




PS:这次这篇花费了两周时间。如果你看到了这里,并且有所收获的话,可以动动手指转发一下哦,小史和吕老师都会感谢你。




面试现场是互联网侦察推出的一个新的板块,旨在回放真实的面试过程,并对面试题进行全面解析,提供多种思路,比较优劣,希望对大家的面试有所帮助。


往期回顾

【面试现场】如何在10亿数中找出前1000大的数

【面试现场】如何在500w个单词中统计特定前缀的单词有多少个?

【面试现场】如何找到字符串中的最长回文子串?

【面试现场】如何编程解决华容道问题?

【面试现场】为什么要分稳定排序和非稳定排序?

【面试现场】如何实现可以获取最小值的栈?

【面试现场】如何判断一个数是否在40亿个整数中?



    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存