No.1 重新排列数组

★解题思路

做好下标的映射即可. 

 对于  i < n , 原数组  i  对应新数组  i 2 , 原数组  i + n  对应新数组  i 2 + 1 .

代码展示

class Solution { 
   public int[] shuffle(int[] nums, int n) { 
       int[] res = new int[nums.length]; 
       for (int i = 0; i < n; i++) { 
           res[i * 2] = nums[i]; 
           res[i * 2 + 1] = nums[i + n]; 
       } 
       return res; 
   } 
}

No.2 数组中的k个最强值

★解题思路

首先排序, 找到中位数.

然后从两端开始取最强值 —— 根据强度的定义可知, 与中位数相差越远, 强度越大, 所以排序之后首尾的一定是最强的.

代码展示

class Solution { 
   public int[] getStrongest(int[] arr, int k) { 
       int n = arr.length; 
       Arrays.sort(arr); 
       int m = arr[(n - 1) / 2]; 
       int[] res = new int[k]; 
       int l = 0, r = n - 1; 
       // 从两端开始取 k 个, 哪个更强取哪个 
       for (int i = 0; i < k; i++) { 
           if (stronger(arr[l], arr[r], m)) { 
               res[i] = arr[l++]; 
           } else { 
               res[i] = arr[r--]; 
           } 
       } 
       return res; 
   } 

   // 判断 lhs 是否比 rhs 更强 
   private boolean stronger(int lhs, int rhs, int m) { 
       int absl = Math.abs(lhs - m); 
       int absr = Math.abs(rhs - m); 
       return absl != absr ? absl > absr : lhs > rhs; 
   } 
}

No.3 设计浏览器历史记录

★解题思路

使用一个  ArrayList  和一个下标就可以完成. 具体方案见代码注释.

代码展示

class BrowserHistory { 

   private int index; // 当前页面对应的 history 下标 
   private final List<String> history; // 访问记录 

   public BrowserHistory(String homepage) { 
       index = 0; 
       history = new ArrayList<>(); 
       history.add(homepage); 
   } 

   public void visit(String url) { 
       // 若执行过 back, 那么 index 一定位于 history.size() - 1 之前 
       // 此时可以进行 forward 
       // 按照题意, 执行 visited 之后会抹除可以 forward 的页面 
       // 所以把那些页面 remove 掉 
       while (history.size() - 1 != index) { 
           history.remove(history.size() - 1); 
       } 
       history.add(url); 
       index = history.size() - 1; 
   } 

   public String back(int steps) { 
       // 将 index 向前移动 steps 个位置即可 
       steps = Math.min(steps, index); 
       index -= steps; 
       return history.get(index); 
   } 

   public String forward(int steps) { 
       // 将 index 向后移动 steps 个位置即可 
       steps = Math.min(steps, history.size() - 1 - index); 
       index += steps; 
       return history.get(index); 
   } 
}

No.4

给房子涂色III

★解题思路

动态规划问题:

定义  f[i][j][k] 表示前 i 个房子组成 j 个街区, 最后一个街区颜色为 k 时的最小花费. 每个房子有两种选择: 与前面的房子组成一个街区或者开始一个新的街区.

初始状态设置为 0x3f3f3f3f 表示正无穷 (不设置 Integer.MAX_VALUE 是为了避免涉及加法运算时导致溢出).

注意: 若房子 i 已经被染成颜色 c, 那么只有 f[i][j][c] 有效, 其他的 f[i][j][k] (k != c) 均为无效状态.

代码展示

class Solution { 
   public int minCost(int[] houses, int[][] cost, int m, int n, int target) { 
       int[][][] f = new int[m + 1][target + 1][n]; 
       for (int i = 1; i <= m; i++) { 
           for (int j = 0; j <= target; j++) { 
               Arrays.fill(f[i][j], 0x3f3f3f3f); 
           } 
       } 
       for (int i = 1; i <= m; i++) { 
           if (houses[i - 1] != 0) { // 已经被染色, k 为固定值, 无需枚举 
               int k = houses[i - 1] - 1; 
               // j > i 也是无效状态 (街区数量不能超过房子数量) 
               for (int j = 1; j <= Math.min(target, i); j++) { 
                   f[i][j][k] = f[i - 1][j][k]; // 加入最后一个街区 
                   for (int l = 0; l < n; l++) { // 开始新街区 
                       if (l != k) { 
                           f[i][j][k] = Math.min(f[i - 1][j - 1][l], f[i][j][k]); 
                       } 
                   } 
               } 
           } else { // 尚未被染色 
               for (int j = 1; j <= Math.min(target, i); j++) { 
                   for (int k = 0; k < n; k++) { 
                       f[i][j][k] = f[i - 1][j][k] + cost[i - 1][k]; // 加入最后一个街区 
                       for (int l = 0; l < n; l++) { // 开始新街区 
                           if (l != k) { 
                               f[i][j][k] = Math.min(f[i - 1][j - 1][l] + cost[i - 1][k], f[i][j][k]); 
                           } 
                       } 
                   } 
               } 
           } 
       } 

       int res = 0x3f3f3f3f; 
       for (int i : f[m][target]) { 
           res = Math.min(res, i); 
       } 
       return res < 0x3f3f3f3f ? res : -1; 
   } 
}

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

上岸科技，一家位于西雅图致力于帮助北美小伙伴们上岸的团体。

团队主要由一群怀揣情怀于美国高校毕业的一线IT公司工程师构成。我们坚持采用小班课形式，并结合大量”面试式“和”白板“的教学和交流形式，最终帮助大家提升求职成功概率同时大大减少刷题的痛苦。

正如我们的信仰：我们教的是如何上岸而不仅是算法。