上岸算法

死磕100%上岸率的精品小班课

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

应广大同学们的需求，我们将定期整理各大厂最新的面试题题解，由我们【上岸算法】资深的老师给大家进行分析讲解，帮助大家实时掌握最新的面试动态，早日上岸！

Facebook OA 5月面经题

题目描述：Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.

The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:matrix = [  [1,   3,  5,  7],  [10, 11, 16, 20],  [23, 30, 34, 50]]target = 3

Output: true

Example 2:

Input:matrix = [  [1,   3,  5,  7],  [10, 11, 16, 20],  [23, 30, 34, 50]]target = 13Output: false

题解：

因为行和列都是升序序列，并且每行的第一个数大于前一行的最后一个数，所以整个二维数组可以映射为一个一维升序数组，因此我们可以用二分查找来搜索。

参考代码

class Solution { 
   public boolean searchMatrix(int[][] matrix, int target) { 
       //特殊情况判断 
       if (matrix.length == 0) { 
           return false; 
       } 
       if (matrix[0].length == 0) { 
           return false; 
       } 
       if (matrix[0][0] == target) { 
           return true; 
       } 
       //二分查找 
       int m = matrix.length; 
       int n = matrix[0].length; 
       if (matrix[m - 1][n - 1] < target) { 
           return false; 
       } else if (matrix[m - 1][n - 1] == target) { 
           return true; 
       } 
       int start = 0; 
       int end = m * n - 1; 
       while (start <= end) { 
           int mid = (start + end) / 2; 
           //一维映射到二维在第几行 
           int x = mid / n; 
           //一维映射到二维在第几列 
           int y = mid % n; 
           if (matrix[x][y] == target) { 
               return true; 
           } else if (matrix[x][y] > target) { 
               end = mid - 1; 
           } else { 
               start = mid + 1; 
           } 
       } 
       return false; 
   } 
}

Amazon OA 5月面经题

题目描述：Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example :

Input:[  1->4->5,  1->3->4,  2->6]Output: 1->1->2->3->4->4->5->6

题解：

用分治的思想，先把大数组分成更小的数组，并不断缩小数组规模，当数组长度为1的时候，用归并排序合并两个链表，然后再一步步合并成最大的链表

参考代码

class Solution { 
   public ListNode mergeKLists(ListNode[] lists) { 
       if(lists == null || lists.length == 0) { 
           return null; 
       } 
       return helper(lists, 0, lists.length - 1); 
   } 

   //通过mid将数组一分为二，并不断缩小规模，当规模为1时返回并开始合并 
   //通过合并两个链表，不断增大其规模，整体看就是不断缩小-最后不断扩大的过程 
   private ListNode helper(ListNode[] lists, int begin, int end) { 
       if(begin == end) { 
           return lists[begin]; 
       } 
       int mid = begin + (end - begin) / 2; 
       ListNode left = helper(lists, begin, mid); 
       ListNode right = helper(lists, mid+1, end); 
       return merge(left, right); 
   } 

   //合并两个有序链表 
   private ListNode merge(ListNode a, ListNode b) { 
       if(a == null || b == null) { 
           return (a == null) ? b : a; 
       } 
       if(a.val <= b.val) { 
           a.next = merge(a.next, b); 
           return a; 
       } else { 
           b.next = merge(a, b.next); 
           return b; 
       } 
   } 
}

Amazon OA 6月面经题

题目描述：Battleships in a Board

Given an 2D board, count how many battleships are in it. The battleships are represented with 'X's, empty slots are represented with '.'s. You may assume the following rules:

You receive a valid board, made of only battleships or empty slots.

Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.

At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.

Example 1:

X..X...X...XIn the above board there are 2 battleships.

题解：

因为战舰只能水平或者垂直排列，扫描二维数组时，我们判断当前 X 点的左边和上边是不是 X，若不是，当前 X 就是新的战舰。

参考代码

class Solution { 
   public int countBattleships(char[][] board) { 
       int ans = 0; 
       for(int i = 0; i < board.length; i++) 
       { 
           for(int j = 0; j < board[i].length; j++) 
           { 
               if(board[i][j] == 'X') 
                   //判断战舰的上方和左边是不是X，不是就是另一艘战舰 
                   if((i == 0 || board[i-1][j] != 'X') && (j == 0 || board[i][j-1] != 'X')) 
                       ans++; 
           } 
       } 
       return ans; 
   } 
}

Microsoft OA 6月面经题

题目描述：Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example 1:

Input: "aab"Output: 1Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

题解：

对于一个字符串，判断他是否是回文串，可以用动态规划来解决，首先满足两端的字符是否对称，然后再判断两端向内缩短是否仍然满足两端对称，直到缩短到字符串长度为1或者为2.最后在满足回文判断的条件下，尽量取最长的回文串进行切割，使得切割的次数最少。

参考代码

public class Solution { 
   public int minCut(String s) { 
       //judge[i][j]数组判断子串i到j是否是回文串 
       int [][] judge = new int[s.length()][s.length()]; 
       //cut数组最少切的次数 
       int [] cut = new int[s.length()+1]; 
       //逆序扫描 
       for(int i = s.length() - 1; i >= 0; i--) { 
           cut[i] = Integer.MAX_VALUE; 
           for(int j = i; j < s.length(); j++) 
           { 
               //当i，j位置满足回文条件，并且子问题也满足回文条件 
               if(s.charAt(i) == s.charAt(j) && (j - i <= 1 || judge[i+1][j-1] == 1)) 
               { 
                   judge[i][j] = 1; 
                   //cut[i]表示第i个字符到最后一个字符所构成的子串的最小分割次数，所以越左边回文串越长 
                   cut[i] = Math.min(1 + cut[j+1], cut[i]);   
               } 
           } 
       } 
       return cut[0] - 1;   
   } 
}

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

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

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

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