飞思布克昂塞面经

楼主碰到的题怎么都这么非主流啊？难道脸家最近换题库了？

好难。。好难。。

li89xin 发表于 2018-10-23 09:58
第四题的话，按x轴排序后，最大值斜率只可能出现在相邻两点的连线上。

请问这个怎么证明呀？

kate8528577 发表于 2018-10-23 14:37
楼主我想问问第二题是dp么？

顺便写了一下第二题，如果不对请指正呀

1. public static int makeStringPalindrome(String s) {
   
2.         if(s == null || s.length() == 0) {
   
3.             return 0;
   
4.         }
   
5.         int n = s.length();
   
6.         int[][] dp = new int[n][n];
   
7.         for(int i = 0; i < n; i++) {
   
8.             dp[i][i] = 0;
   
9.         }
   
10. 
    
11.         for(int len = 2; len <= n; len++) {
    
12.             for(int i = 0; i < n; i++) {
    
13.                 int j = i + len - 1;
    
14.                 if(j < n) {
    
15.                     if(s.charAt(i) == s.charAt(j)) {
    
16. 
    
17.                         dp[i][j] = dp[i+1][j-1];
    
18.                     } else {
    
19.                         dp[i][j] = Math.min(dp[i+1][j-1], Math.min(dp[i+1][j], dp[i][j-1])) + 1;
    
20.                     }
    
21.                 }
    
22.             }
    
23.         }
    
24.         return dp[0][n-1];
    
25.     }

复制代码

呆毛littledream 发表于 2018-10-25 04:11
请问这个怎么证明呀？

证明方法类似微积分里面的中值定理。这里的值想象成斜率就好了。