链讯管理局
分享几个疫情之下的算法面试题（一）
摘要：最近由于疫情被裁员，还得在大环境不好的情况下面试，有点伤。分享几个我最近被问到的算法面试题吧
作者：Java 识堂 / 李立敏 （本文来自作者投稿）
前言
最近由于疫情被裁员，还得在大环境不好的情况下面试，有点伤。分享几个我最近被问到的算法面试题吧
指定元素第一次出现的位置
思路：立马就想到二分，因为返回的是第一次出现的位置，所以还得和前面的数比较一下
*
public class Solution { public static void main(String[] args) { Solution solution = new Solution(); int[] array = {1, 1, 1, 4}; int num = solution.firstIndex(array, 1); // 0 System.out.println(num); } public int firstIndex(int[] array, int search) { int index = binarySearch(array, search); if (index == -1) { return -1; } while (index > 0) { if (array[index] == array[index-1]) { index--; } else { break; } } return index; } public int binarySearch(int[] array,int search) { int start = 0; int end = array.length - 1; while (start <= end) { int mid = (start + end) >> 1; if (array[mid] == search) { return mid; } else if (search > array[mid]) { start = mid + 1; } else { end = mid - 1; } } return -1; }}
面试官：时间复杂度最坏为多少？
我：O(n)
面试官：还能优化吗？
我：…
面试官：相等的时候还能二分吗？
我：可以
所以正确答案就是这样的
public class Solution { public static void main(String[] args) { Solution solution = new Solution(); int[] array = {0, 1, 1, 1, 3, 4}; int num = solution.binarySearch(array, 3); // 4 System.out.println(num); } public int binarySearch(int[] array,int search) { int start = 0; int end = array.length - 1; while (start <= end) { int mid = (start + end) >> 1; if (array[mid] == search) { if (mid == start || array[mid - 1] != search) { return mid; } else { end = mid - 1; } } else if (search > array[mid]) { start = mid + 1; } else { end = mid - 1; } } return -1; }}
输出频率最高且最先出现的字符
假设有一个字符串，字符串内部的所有字符都是在 ascii 编码的范围内，编码求出字符串中出现频率最高的字符，如果频率最高的字符有几个字符出现的频率一样，则输出最先出现的字符。
如输入串为 “hello world, every body!”，则输出频率最高且最先出现的字符。
方法定义：char getMaxOccurChar(String str)
输入
hello world, every body!
输出
e
直接用 LinkedHashMap 模拟一下，最后求出最值即可
public class Main { public static void main(String[] args) { char result = getMaxOccurChar("hello world, every body!"); // e System.out.println(result); result = getMaxOccurChar("aaaahfdfbbbbbbbbbb"); // b System.out.println(result); } public static char getMaxOccurChar(String str) { int maxCount = 1; Character result = new Character(str.charAt(0)); Map map = new LinkedHashMap<>(); for (int i = 0; i < str.length(); i++) { Character content = str.charAt(i); Integer count = map.get(content); if (count == null) { map.put(content, 1); } else { map.put(content, count + 1); } } for (Map.Entry entry: map.entrySet()) { if (entry.getValue() > maxCount) { result = entry.getKey(); maxCount = entry.getValue(); } } return result; }}
面试官：有没有可能一次遍历搞定呢？
我：可以（然后没写出来）
面试官：倒着遍历可以吗？
我：哦，对
*
public class Main { public static void main(String[] args) { char result = getMaxOccurChar("hello world, every body!"); System.out.println(result); result = getMaxOccurChar("aaaahfdfbbbbbbbbbb"); System.out.println(result); } public static char getMaxOccurChar(String str) { int maxCount = 1; Character result = new Character(str.charAt(0)); Map<Character, Integer> map = new LinkedHashMap<>(); for (int i = str.length() - 1; i >= 0 ; i--) { Character content = str.charAt(i); Integer count = map.get(content); if (count == null) { map.put(content, 1); count = 1; } else { map.put(content, count + 1); count += 1; } if (count >= maxCount) { maxCount = count; result = str.charAt(i); } } return result; }}
最少猎头拿到全部简历问题
面试官：能做出来吗？
我：目前能想到的就是贪心算法（一直要简历最多的猎头，但是有可能不是最优解），可以用回溯解决吗？
面试官：你可以试一下
我：用回溯枚举了每个猎头取或者不取的情况，在能拿到所有简历的情况下，用打擂的方式算出最少的猎头数
public class Solution { public static void main(String[] args) { Solution solution = new Solution(); // 标记猎头及其拥有的简历 HashMap> listMap1 = new HashMap<>(); listMap1.put("A", Arrays.asList(1, 2, 3, 4)); listMap1.put("B", Arrays.asList(2, 3, 5)); listMap1.put("C", Arrays.asList(4, 5, 6)); listMap1.put("D", Arrays.asList(5, 6, 7, 8)); listMap1.put("E", Arrays.asList(1, 4, 6)); // [A, D] System.out.println(solution.query(listMap1)); HashMap> listMap = new HashMap<>(); // 测试贪心算法错误的情况 listMap.put("A", Arrays.asList(1, 3, 4, 5)); listMap.put("B", Arrays.asList(1, 3, 6)); listMap.put("C", Arrays.asList(2, 4, 5)); listMap.put("D", Arrays.asList(1, 3, 6)); // [C, D] System.out.println(solution.query(listMap)); } public List query(Map> map){ Set set = new HashSet<>(); List nameList = new ArrayList<>(); List finalList = new ArrayList<>(); Map> nameNumMap = new LinkedHashMap<>(); int num = 0; for (Map.Entry> m : map.entrySet()) { set.addAll(m.getValue()); nameList.add(m.getKey()); nameNumMap.put(num, m.getValue()); num++; } int[] visitor = new int[nameList.size()]; int minTotalNum = nameList.size(); dfs(0, set.size(), nameList.size(), nameList, nameNumMap, visitor, minTotalNum, finalList); return finalList; } /** * @param index 决定 index 个猎头是否选择 * @param visitorNum
- 免责声明
- 世链财经作为开放的信息发布平台，所有资讯仅代表作者个人观点，与世链财经无关。如文章、图片、音频或视频出现侵权、违规及其他不当言论，请提供相关材料，发送到：2785592653@qq.com。
- 风险提示：本站所提供的资讯不代表任何投资暗示。投资有风险，入市须谨慎。
- 世链粉丝群：提供最新热点新闻，空投糖果、红包等福利，微信：juu3644。
