上岸算法

任何只教知识的课程凑是耍流氓

我们直击上岸

关注我们，第一时间获得大厂面试真题讲解

No.1 比赛中的配对次数

★

解题思路

模拟过程即可，较简单。

代码展示

class Solution { 
   public int numberOfMatches(int n) { 
       int res = 0; 
       while (n > 1) { 
           res += n / 2; 
           n = (n + 1) / 2; 
       } 
       return res; 
   } 
}

No.2 十-二进制数的最少数目

★解题思路

取决于最大的数字是多少。

代码展示

class Solution { 
   public int minPartitions(String n) { 
       int res = 0; 
       for (int i = 0; i < n.length(); i++) { 
           res = Math.max(res, n.charAt(i) - '0');  
       } 
       return res; 
   } 
}

No.3 石子游戏VII

★解题思路

区间动态规划问题。

定义状态: dp[i][j] 表示区间 [i, j] 的得分差值

状态转移: 当一个人面临 [i, j] 的情况时，在拿左边和拿右边之间选择自己获得分数更大的情况，详见代码。

定义 prefixSum 表示前缀和以辅助计算。

代码展示

class Solution { 
   public int stoneGameVII(int[] stones) { 
       int n = stones.length; 
       int[] prefixSum = new int[n + 1]; 
       for (int i = 0; i < n; i++) { 
           prefixSum[i + 1] = prefixSum[i] + stones[i]; 
       } 
       int[][] dp = new int[n][n]; 
       for (int i = n - 1; i >= 0; --i) { 
           for (int j = i; j < n; ++j) { 
               if (i != j) { // 边界: dp[i][i] = 0 
                   dp[i][j] = Math.max( 
                           // 拿了左边的 
                           (prefixSum[j + 1] - prefixSum[i + 1]) - dp[i + 1][j], 
                           // 拿了右边的 
                           (prefixSum[j] - prefixSum[i]) - dp[i][j - 1] 
                   ); 
               } 
           } 
       } 
       return dp[0][n - 1]; 
   } 
}

No.4 堆叠长方体的最大高度

★解题思路

该题目类似嵌套矩形的问题，而嵌套矩形问题又是最长上升子序列的变体，所以本质上和 LIS 问题没有太大区别。

定义状态: dp[i] 表示以 i 结尾的长方体上最高能堆叠多高。

与处理二维一样地，先要对长方体进行排序，然后再递推求解。

注意最终答案是 max{ dp }

代码展示

class Solution { 
   public int maxHeight(int[][] cuboids) { 
       // 排序 
       for (int[] c : cuboids) { 
           Arrays.sort(c); 
       } 
       Arrays.sort(cuboids, (a, b) -> { 
           if (a[0] != b[0]) 
               return Integer.compare(a[0], b[0]); 
           if (a[1] != b[1]) 
               return Integer.compare(a[1], b[1]); 
           return Integer.compare(a[2], b[2]); 
       }); 
       // dp[i] 表示以第 i 个长方体为末尾时，能堆叠的最大高度 
       int[] dp = new int[cuboids.length]; 
       for (int i = 0; i < cuboids.length; i++) { 
           dp[i] = cuboids[i][2]; 
           for (int j = 0; j < i; j++) 
               if (cuboids[j][0] <= cuboids[i][0] && 
                       cuboids[j][1] <= cuboids[i][1] && 
                       cuboids[j][2] <= cuboids[i][2]) { 
                   dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]); 
               } 
       } 
       return Arrays.stream(dp).max().getAsInt(); 
   } 
}

    杭州上岸算法网络科技有限公司

上岸算法网络科技有限公司是一家致力于用高质量，高互动性小班课程来帮助学生更好的在就业市场中定位以及求职的公司。我们以顶级的课程质量，高互动性的教学方式以及独特的小班教学模式来帮助学生更快的跨过求职的鸿沟，用最高效，经济，合理的方式帮助更多学生快速找到梦寐以求的工作。