举几个例子，具体说一下面试的时候最优解和次优解的取舍。

第一个例子，也是一个很高频的题目。
https://leetcode.com/problems/longest-increasing-subsequence/
很经典的dp问题。

1. public class Solution {
   
2.     public int lengthOfLIS(int[] nums) {
   
3.         if (nums.length == 0) {
   
4.             return 0;
   
5.         }
   
6.         int[] dp = new int[nums.length];
   
7.         dp[0] = 1;
   
8.         int maxans = 1;
   
9.         for (int i = 1; i < dp.length; i++) {
   
10.             int maxval = 0;
    
11.             for (int j = 0; j < i; j++) {
    
12.                 if (nums > nums[j]) {
    
13.                     maxval = Math.max(maxval, dp[j]);
    
14.                 }
    
15.             }
    
16. [i]            dp[i] = maxval + 1;
    
17.             maxans = Math.max(maxans, dp);
    
18.         }
    
19.         return maxans;
    
20.     }
    
21. }

复制代码

这个是最容易想到的，也比较不容易出错。
第二种使用二分查找的算法代码如下：

1. public class Solution {
   
2.     public int lengthOfLIS(int[] nums) {            
   
3.         int[] dp = new int[nums.length];
   
4.         int len = 0;
   
5. 
   
6.         for(int x : nums) {
   
7.             int i = Arrays.binarySearch(dp, 0, len, x);
   
8.             if(i < 0) i = -(i + 1);
   
9.             dp[i] = x;
   
10.             if(i == len) len++;
    
11.         }
    
12. 
    
13.         return len;
    
14.     }
    
15. }

复制代码

第二种解法还是比较难以解释的。比如，这个dp数组的意义是什么？前len个数，是不是就等同于最长递增子序列？如果面试官让你输出最长递增子序列，你应该怎么办？
如果包括但不限于这几个问题，你可以很轻松掌握，并且有信心给面试官讲明白，你当然是可以直接给出这个解法。但是如果你不那么自信的话，建议你先把常见的dp写法给出来。

第二个例子，PathSumIII。
https://leetcode.com/problems/path-sum-iii/
第一种最容易想到的解法，

1. public class Solution {
   
2.     public int pathSum(TreeNode root, int sum) {
   
3.         if (root == null) return 0;
   
4.         return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
   
5.     }
   
6.    
   
7.     private int pathSumFrom(TreeNode node, int sum) {
   
8.         if (node == null) return 0;
   
9.         return (node.val == sum ? 1 : 0)
   
10.             + pathSumFrom(node.left, sum - node.val) + pathSumFrom(node.right, sum - node.val);
    
11.     }
    
12. }

复制代码

这种办法的复杂度最差是n^2, 平均nlogn。
第二种办法是采用prefix Sum，以及HashMap，可以达到O（n）的复杂度。

1.     public int pathSum(TreeNode root, int sum) {
   
2.         HashMap<Integer, Integer> preSum = new HashMap();
   
3.         preSum.put(0,1);
   
4.         return helper(root, 0, sum, preSum);
   
5.     }
   
6.    
   
7.     private int helper(TreeNode root, int currSum, int target, HashMap<Integer, Integer> preSum) {
   
8.         if (root == null) {
   
9.             return 0;
   
10.         }
    
11.         
    
12.         currSum += root.val;
    
13.         int res = preSum.getOrDefault(currSum - target, 0);
    
14.         preSum.put(currSum, preSum.getOrDefault(currSum, 0) + 1);
    
15.         
    
16.         res += helper(root.left, currSum, target, preSum) + helper(root.right, currSum, target, preSum);
    
17.         preSum.put(currSum, preSum.get(currSum) - 1);
    
18.         return res;
    
19.     }

复制代码

这种办法确实复杂度更好，但是你需要注意的细节也有不少。如果只是问是否存在，这种做法就类似2sum，很好写。但是求数量会有一些细节问题。
如果你掌握的很好，自然是一个加分项。我的建议就是先写出最基本的recursion/dfs的做法，然后再给出这个优化与实现。这样至少有一个保底。

第三个例子，subset
https://leetcode.com/problems/subsets/
最基本的做法，自然是dfs/backtracking了。

1. 
   
2. public class Solution {
   
3. 
   
4.     public List<List<Integer>> subsets(int[] nums) {
   
5.         int size = nums.length;
   
6.         List<List<Integer>> res = new ArrayList<>();
   
7.         if (size == 0) {
   
8.             return res;
   
9.         }
   
10.         Stack<Integer> stack = new Stack<>();
    
11.         for (int i = 0; i < size + 1; i++) {
    
12.             dfs(nums, 0, i, stack, res);
    
13.         }
    
14.         return res;
    
15.     }
    
16. 
    
17.     private void dfs(int[] nums, int start, int depth, Stack<Integer> path, List<List<Integer>> res) {
    
18.         if (depth == path.size()) {
    
19.             res.add(new ArrayList<>(path));
    
20.             return;
    
21.         }
    
22.         for (int i = start; i < nums.length; i++) {
    
23.             path.add(nums[i]);
    
24.             dfs(nums, i + 1, depth, path, res);
    
25.             path.pop();
    
26.         }
    
27.     }
    
28. 
    
29. }
    

复制代码

当然，也有炫技一点的写法。利用位掩码。

1. 
   
2. public class Solution {
   
3. 
   
4.     public List<List<Integer>> subsets(int[] nums) {
   
5.         int size = nums.length;
   
6.         int n = 1 << size;
   
7.         List<List<Integer>> res = new ArrayList<>();
   
8. 
   
9.         for (int i = 0; i < n; i++) {
   
10.             List<Integer> cur = new ArrayList<>();
    
11.             for (int j = 0; j < size; j++) {
    
12.                 if (((i >> j) & 1) == 1) {
    
13.                     cur.add(nums[j]);
    
14.                 }
    
15.             }
    
16.             res.add(cur);
    
17.         }
    
18.         return res;
    
19.     }
    
20. }

复制代码

位掩码的代码短，看着也精巧。
但是其实面试官更注重dfs之类的基本功。全写出来可以用来炫技。

第四个例子，confusing number
这是一道收费题目，我把题目复制过来。
代码稍微有点繁琐，我就不贴了。有兴趣的话我在后面贴。

最直接想法就是从1遍历到n，然后看是否confuse，这样的复杂度是O(nlogn),TLE！
第二种做法就是枚举所有可能性，因为只有0 1 6 8 9可能混淆，总共需要枚举的次数也就是5^(log10n)
第三种做法，也就是最优解，是数位dp。复杂度只有O（logn）， 但是我强烈不建议大家面试的时候写。
一是难想，二是难debug，细节又太多。
个人水平我觉得应该还是可以的，contest基本也可以一小时内写完全四道题目，leetcode基本上可以不看题解写出大部分题目。
我自己尝试去实现数位dp，加上debug，非面试状态下花了一个半小时以上才调试好，而且写得很长很丑。面试时间有限，几乎不可能写出来。
当然大神除外。。
举这几个例子的意思就是说，很多时候，面试官想要考察的是基本功，所以，一些通用的套路和写法一定要会写。当然，一些好的算法和最优解肯定是加分项，前提是你理解清楚。
然后就是说，一些偏门的奇技淫巧可能没有那么大意义，稍微一点变化很可能就答不上来。
所以，面试的时候，不停沟通，要展示出自己会写通用的解法，了解基本的套路。然后，码完之后你可以跟面试官提，你有更好的解法，但是一定要解释得清楚。


[/i]

面试中真的很难取舍！谢谢建议！