想上岸找上岸

No.1 Sign of the Product of an Array

解题思路

遍历分以下三种情况

正数，*1

负数，*-1

零，直接return 0

代码展示

public int arraySign(int[] nums) { 
         if (nums == null || nums.length == 0) { 
             return -1; 
         } 
         int res = 1; 
         for (int num:nums) { 
             if (num < 0) { 
                 res *= -1; 
             } 
             else if (num > 0) { 
                 res *= 1; 
             } 
             else { 
                 return 0; 
             } 
         } 
         return res; 
     }

No.2 Find the Winner of the Circular Game

解题思路

经典问题，约瑟夫环，Josephus problem

每隔 k 步，移除一个元素

最终保留单个元素

代码展示

public int findTheWinner(int n, int k) { 
       List<Integer> list = new ArrayList<>(); 
       for (int i = 1; i <= n; i++) { 
           list.add(i); 
       } 
       int start = 0; 
       while (list.size() > 1) { 
           // 区域保证数据不会越界 
           int id = (start + k - 1) % list.size(); 
           list.remove(id); 
           start = id; 
       } 
       return list.get(0); 
   }

No.3 Minimum Sideway Jumps

解题思路

序列型动态规划

-dp[i][j]，表示在 index = i 的位置，跳跃在 j 这条跑道的最小代价

移动到 index = i, j 需要满足当前点的当前跑道没有障碍，移动到这条跑道有两种方式，

同跑道直接移动

同index位置的其他跑道跳跃一次过来

以上情况取最小值

答案，最后一个index的三条跑道中其中最小的一个代价

代码展示

public int minSideJumps(int[] obstacles) { 
       if (obstacles ==null || obstacles.length == 0) { 
           return 0; 
       } 
       int n = obstacles.length; 
       int[][] dp = new int[n][3]; 
       for (int i = 0; i < n; i++) { 
           for (int j = 0; j < 3; j++) { 
               dp[i][j] = Integer.MAX_VALUE / 2; 
           } 
       } 
       // 初始化 
       dp[0][1] = 0; 
       dp[0][0] = 1; 
       dp[0][2] = 1; 

       for (int i = 1; i < n; i++) { 
           /** 没有障碍，直接移动 */ 
           if (obstacles[i] != 1) { 
               dp[i][0] = dp[i - 1][0]; 
           } 
           if (obstacles[i] != 2) { 
               dp[i][1] = dp[i - 1][1]; 
           } 
           if (obstacles[i] != 3) { 
               dp[i][2] = dp[i - 1][2]; 
           } 
           /** 没有障碍的情况下，确定是否可以从更加小的一条跑道跳跃过来*/ 
           if (obstacles[i] != 1) { 
               dp[i][0] = Math.min(dp[i][0], Math.min(dp[i][1], dp[i][2]) + 1); 
           } 
           if (obstacles[i] != 2) { 
               dp[i][1] = Math.min(dp[i][1], Math.min(dp[i][0], dp[i][2]) + 1); 
           } 
           if (obstacles[i] != 3) { 
               dp[i][2] = Math.min(dp[i][2], Math.min(dp[i][0], dp[i][1]) + 1); 
           } 

       } 
       return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2])); 
   }

No.4 Finding MK Average

解题思路

设计数据结构的题，根据数据范围模拟设计就可以

过程需要排序方便计算，详情见注释

代码展示

public int[] container, newContainer; 
   int T, m, k; 

   public MKAverage(int m, int k) { 
       // 根据数据范围初始化index, container 容量 
       T = 0; 
       container = new int[100010]; 
       this.m = m; 
       this.k = k; 
   } 

   public void addElement(int num) { 
       container[T++] = num; 
   } 

   public int calculateMKAverage() { 
       if (T < m) return -1; 
       int tmpT = T; 
       long sum = 0; 
       // 大于 m 个拷贝到最后 n 个新的数组中 
       newContainer = new int[m]; 
       for (int i = 0; i < m; i++) { 
           newContainer[i] = container[--tmpT]; 
       } 
       // 新容器排序后从第 k 个累加到最后一个 
       Arrays.sort(newContainer); 
       for (int i = k; i < m - k; i++) { 
           sum += newContainer[i]; 
       } 
       return (int) (sum / (m - 2 * k)); 
   }

上岸DS秋招最新大厂面经公开课

活动介绍：为北美同学免费提供大厂面试官面经重点，为你在线提分 活动时间：2021/4/5-2021/4/26

活动全程 免费 免费 免费！！！