写点什么

Android 复习资料——常见面试算法题汇总,2021 年最新 Android 大厂面试笔试题分享

用户头像
Android架构
关注
发布于: 刚刚

合并两个已排序链表

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode lastNode = dummy;


while (l1 != null && l2 != null) {if (l1.val < l2.val) {lastNode.next = l1;l1 = l1.next;} else {lastNode.next = l2;l2 = l2.next;}lastNode = lastNode.next;}


if (l1 != null) {lastNode.next = l1;} else {lastNode.next = l2;}


return dummy.next;}

链表排序

可利用归并、快排等算法实现


// 归并排序 public ListNode sortList(ListNode head) {if (head == null || head.next == null) {return head;}


ListNode mid = findMiddle(head);


ListNode right = sortList(mid.next);mid.next = null;ListNode left = sortList(head);


return mergeTwoLists(left, right);}


// 快速排序 public ListNode sortList(ListNode head) {quickSort(head, null);return head;}


private void quickSort(ListNode start, ListNode end) {if (start == end) {return;}


ListNode pt = partition(start, end);quickSort(start, pt);quickSort(pt.next, end);}


private ListNode partition(ListNode start, ListNode end) {int pivotKey = start.val;ListNode p1 = start, p2 = start.next;while (p2 != end) {if (p2.val < pivotKey) {p1 = p1.next;swapValue(p1, p2);}p2 = p2.next;}


swapValue(start, p1);return p1;}


private void swapValue(ListNode node1, ListNode node2) {int tmp = node1.val;node1.val = node2.val;node2.val = tmp;}

删除倒数第 N 个节点

public ListNode removeNthFromEnd(ListNode head, int n) {if (n <= 0) {return null;}


ListNode dummy = new ListNode(0);dummy.next = head;


ListNode preDelete = dummy;for (int i = 0; i < n; i++) {if (head == null) {return null;}head = head.next;}// 此时 head 为正数第 N 个节点 while (head != null) {head = head.next;preDelete = preDelete.next;}preDelete.next = preDelete.next.next;return dummy.next;}

两个链表是否相交

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}


ListNode currA = headA;ListNode currB = headB;int lengthA = 0;int lengthB = 0;


// 让长的先走到剩余长度和短的一样 while (currA != null) {currA = currA.next;lengthA++;}while (currB != null) {currB = currB.next;lengthB++;}


currA = headA;currB = headB;while (lengthA > lengthB) {currA = currA.next;lengthA--;}while (lengthB > lengthA) {currB = currB.next;lengthB--;}


// 然后同时走到第一个相同的地方 while (currA != currB) {currA = currA.next;currB = currB.next;}// 返回交叉开始的节点 return currA;}

栈 / 队列

带最小值操作的栈

实现一个栈, 额外支持一个操作:min() 返回栈中元素的最小值


public class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack; // 维护一个辅助栈,传入当前栈的最小值


public MinStack() {stack = new Stack<Integer>();minStack = new Stack<Integer>();}


public void push(int number) {stack.push(number);if (minStack.isEmpty()) {minStack.push(number);} else {minStack.push(Math.min(number, minStack.peek()));}}


public int pop() {minStack.pop();return stack.pop();}


public int min() {return minStack.peek();}}

有效括号

给定一个字符串所表示的括号序列,包含以下字符: '(', ')', '{', '}', '[' and ']', 判定是否是有效的括号序列。括号必须依照 "()" 顺序表示, "()[]{}" 是有效的括号,但 "([)]" 则是无效的括号。


public boolean isValidParentheses(String s) {Stack<Character> stack = new Stack<Character>();for (Character c : s.toCharArray()) {if ("({[".contains(String.valueOf(c))) {stack.push(c);} else {if (!stack.isEmpty() && isValid(stack.peek(), c)) {stack.pop();} else {return false;}}}return stack.isEmpty();}


private boolean isValid(char c1, char c2) {return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}')|| (c1 == '[' && c2 == ']');}

用栈实现队列

public class MyQueue {private Stack<Integer> outStack;private Stack<Integer> inStack;


public MyQueue() {outStack = new Stack<Integer>();inStack = new Stack<Integer>();}


private void in2OutStack(){while(!inStack.isEmpty()){outStack.push(inStack.pop());}}


public void push(int element) {inStack.push(element);}


public int pop() {if(outStack.isEmpty()){this.in2OutStack();}return outStack.pop();}


public int top() {if(outStack.isEmpty()){this.in2OutStack();}return outStack.peek();}}

逆波兰表达式求值

在反向波兰表示法中计算算术表达式的值, ["2", "1", "+", "3", "*"] -> (2 + 1) * 3 -> 9


public int evalRPN(String[] tokens) {Stack<Integer> s = new Stack<Integer>();String operators = "+-*/";for (String token : tokens) {if (!operators.contains(token)) {s.push(Integer.valueOf(token));continue;}


int a = s.pop();int b = s.pop();if (token.equals("+")) {s.push(b + a);} else if(token.equals("-")) {s.push(b - a);} else if(token.equals("*")) {s.push(b * a);} else {s.push(b / a);}}return s.pop();}

二分

二分搜索

public int binarySearch(int[] arr, int start, int end, int hkey){if (start > end) {return -1;}


int mid = start + (end - start) / 2; //防止溢位 if (arr[mid] > hkey) {return binarySearch(arr, start, mid - 1, hkey);}if (arr[mid] < hkey) {return binarySearch(arr, mid + 1, end, hkey);}return mid;


}

X 的平方根

public int sqrt(int x) {if (x < 0) {throw new IllegalArgumentException();} else if (x <= 1) {return x;}


int start = 1, end = x;// 直接对答案可能存在的区间进行二分 => 二分答案 while (start + 1 < end) {int mid = start + (end - start) / 2;if (mid == x / mid) {return mid;} else if (mid < x / mid) {start = mid;} else {end = mid;}


}if (end > x / end) {return start;}return end;}

哈希表

两数之和

给一个整数数组,找到两个数使得他们的和等于一个给定的数 target。需要实现的函数 twoSum 需要返回这两个数的下标。


用一个 hashmap 来记录,key 记录 target-numbers[i]的值,value 记录 numbers[i]的 i 的值,如果碰到一个 numbers[j]在 hashmap 中存在,那么说明前面的某个 numbers[i]和 numbers[j]的和为 target,i 和 j 即为答案


public int[] twoSum(int[] numbers, int target) {


HashMap<Integer,Integer> map = new HashMap<>();


for (int i = 0; i < numbers.length; i++) {if (map.containsKey(numbers[i])) {return new int[]{map.get(numbers[i]), i};}map.put(target - numbers[i], i);}


return new int[]{};}

连续数组

给一个二进制数组,找到 0 和 1 数量相等的子数组的最大长度


使用一个数字 sum 维护到 i 为止 1 的数量与 0 的数量的差值。在 loop i 的同时维护 sum 并将其插入 hashmap 中。对于某一个 sum 值,若 hashmap 中已有这个值,则当前的 i 与 sum 上一次出现的位置之间的序列 0 的数量与 1 的数量相同。


public int findMaxLength(int[] nums) {Map<Integer, Integer> prefix = new HashMap<>();int sum = 0;int max = 0;prefix.put(0, -1); // 当第一个 0 1 数量相等的情况出现时,数组下标减去-1 得到正确的长度 for (int i = 0; i < nums.length; i++) {int num = nums[i];if (num == 0) {sum--;} else {sum++;}


if (prefix.containsKey(sum)) {max = Math.max(max, i - prefix.get(sum));} else {prefix.put(sum, i);}}


return max;}

最长无重复字符的子串

用 HashMap 记录每一个字母出现的位置。设定一个左边界, 到当前枚举到的位置之间的字符串为不含重复字符的子串。若新碰到的字符的上一次的位置在左边界右边, 则需要向右移动左边界


public int lengthOfLongestSubstring(String s) {if (s == null || s.length() == 0) {return 0;}HashMap<Character, Integer> map = new HashMap<>();int max = Integer.MIN_VALUE;int start = -1; // 计算无重复字符子串开始的位置 int current = 0;for (int i = 0; i < s.length(); i++) {if (map.containsKey(s.charAt(i))) {int tmp = map.get(s.charAt(i));if (tmp >= start) { // 上一次的位置在左边界右边, 则需要向右移动左边界 start = tmp;}}


map.put(s.charAt(i), i);max = Math.max(max, i - start);}return max;}

最多点在一条直线上

给出二维平面上的 n 个点,求最多有多少点在同一条直线上


class Point {int x;int y;Point() {x = 0; y = 0;}Point(int a, int b) {x = a; y = b;}}


通过 HashMap 记录下


《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
浏览器打开:qq.cn.hn/FTe 免费领取
复制代码


两个点之间的斜率相同出现的次数,注意考虑点重合的情况


public int maxPoints(Point[] points) {if (points == null) {return 0;}


int max = 0;for (int i = 0; i < points.length; i++) {Map<Double, Integer> map = new HashMap<>();int maxPoints = 0;int overlap = 0;for (int j = i + 1; j < points.length; j++) {if (points[i].x == points[j].x && points[i].y == points[j].y) {overlap++; // 两个点重合的情况记录下来 continue;}double rate = (double)(points[i].y - points[j].y) / (points[i].x - points[j].x);if (map.containsKey(rate)) {map.put(rate, map.get(rate) + 1);} else {map.put(rate, 2);}maxPoints = Math.max(maxPoints, map.get(rate));}if (maxPoints == 0) maxPoints = 1;max = Math.max(max, maxPoints + overlap);}return max;}

堆 / 优先队列

前 K 大的数

// 维护一个 PriorityQueue,以返回前 K 的数 public int[] topk(int[] nums, int k) {int[] result = new int[k];if (nums == null || nums.length < k) {return result;}


Queue<Integer> pq = new PriorityQueue<>();for (int num : nums) {pq.add(num);if (pq.size() > k) {pq.poll();}}


for (int i = k - 1; i >= 0; i--) {result[i] = pq.poll();}


return result;}

前 K 大的数 II

实现一个数据结构,提供下面两个接口:1.add(number) 添加一个元素 2.topk() 返回前 K 大的数


public class Solution {private int maxSize;private Queue<Integer> minheap;public Solution(int k) {minheap = new PriorityQueue<>();maxSize = k;}


public void add(int num) {if (minheap.size() < maxSize) {minheap.offer(num);return;}


if (num > minheap.peek()) {minheap.poll();minheap.offer(num);}}


public List<Integer> topk() {Iterator it = minheap.iterator();List<Integer> result = new ArrayList<Integer>();while (it.hasNext()) {result.add((Integer) it.next());}Collections.sort(result, Collections.reverseOrder());return result;}}

第 K 大的数

public int kthLargestElement(int k, int[] nums) {if (nums == null || nums.length == 0 || k < 1 || k > nums.length){return -1;}return partition(nums, 0, nums.length - 1, nums.length - k);}


private int partition(int[] nums, int start, int end, int k) {if (start >= end) {return nums[k];}


int left = start, right = end;int pivot = nums[(start + end) / 2];


while (left <= right) {while (left <= right && nums[left] < pivot) {left++;}while (left <= right && nums[right] > pivot) {right--;}if (left <= right) {swap(nums, left, right);left++;right--;}}


if (k <= right) {return partition(nums, start, right, k);}if (k >= left) {return partition(nums, left, end, k);}return nums[k];}


private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

二叉搜索树

验证二叉搜索树

public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}


private boolean isValidBST(TreeNode root, long min, long max){if (root == null) {return true;}


if (root.val <= min || root.val >= max){return false;}


return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);}

第 K 小的元素

增加 getCount 方法来获取传入节点的子节点数(包括自己),从 root 节点开始判断 k 值和子节点数的大小决定递归路径是往左还是往右。


public int kthSmallest(TreeNode root, int k) {if (root == null) {return 0;}


int leftCount = getCount(root.left);if (leftCount >= k) {return kthSmallest(root.left, k);} else if (leftCount + 1 == k) {return root.val;} else {return kthSmallest(root.right, k - leftCount - 1);}}


private int getCount(TreeNode root) {if (root == null) {return 0;}


return getCount(root.left) + getCount(root.right) + 1;}

数组 / 双指针

加一

给定一个非负数,表示一个数字数组,在该数的基础上+1,返回一个新的数组。该数字按照数位高低进行排列,最高位的数在列表的最前面。


public int[] plusOne(int[] digits) {int carries = 1;for(int i = digits.length - 1; i >= 0 && carries > 0; i--){


int sum = digits[i] + carries;digits[i] = sum % 10;carries = sum / 10;}if(carries == 0) {return digits;}


int[] rst = new int[digits.length + 1];rst[0] = 1;for(int i = 1; i < rst.length; i++){rst[i] = digits[i - 1];}return rst;}

删除元素

给定一个数组和一个值,在原地删除与值相同的数字,返回新数组的长度。


public int removeElement(int[] A, int elem) {if (A == null || A.length == 0) {return 0;}


int index = 0;for (int i = 0; i < A.length; i++) {if (A[i] != elem) {A[index++] = A[i];}}


return index;}

删除排序数组中的重复数字

在原数组中“删除”重复出现的数字,使得每个元素只出现一次,并且返回“新”数组的长度。


public int removeDuplicates(int[] A) {if (A == null || A.length == 0) {return 0;}


int size = 0;for (int i = 0; i < A.length; i++) {if (A[i] != A[size]) {A[++size] = A[i];}}return size + 1;}

我的日程安排表 I

实现 MyCalendar 类来存储活动。如果新添加的活动没有重复,则可以添加。类将有方法 book(int start,int end)。这代表左闭右开的间隔[start,end)有了预定,范围内的实数 x,都满足 start <= x < end,返回 true。 否则,返回 false,并且事件不会添加到日历中。


TreeMap 是一个有序的 key-value 集合,它通过 红黑树 实现,继承于 AbstractMap,所以它是一个 Map,即一个 key-value 集合。TreeMap 可以查询小于等于某个值的最大的 key,也可查询大于等于某个值的最小的 key。 元素的顺序可以改变,并且对新的数组不会有影响。


class MyCalendar {TreeMap<Integer, Integer> calendar;


MyCalendar() {calendar = new TreeMap();}


public boolean book(int start, int end) {Integer previous = calendar.floorKey(start), next = calendar.ceilingKey(start);if ((previous == null || calendar.get(previous) <= start) && (next == null || end <= next)) {calendar.put(start, end);return true;}return false;}}

合并排序数组

合并两个排序的整数数组 A 和 B 变成一个新的数组。可以假设 A 具有足够的空间去添加 B 中的元素。


public void mergeSortedArray(int[] A, int m, int[] B, int n) {int i = m - 1, j = n - 1, index = m + n - 1;while (i >= 0 && j >= 0) {if (A[i] > B[j]) {A[index--] = A[i--];} else {A[index--] = B[j--];}}while (i >= 0) {A[index--] = A[i--];}while (j >= 0) {A[index--] = B[j--];}}

贪心

买卖股票的最佳时机

假设有一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。


public int maxProfit(int[] prices) {if (prices == null || prices.length == 0) {return 0;}


int min = Integer.MAX_VALUE; //记录最低的价格 int profit = 0;for (int price : prices) {min = Math.min(price, min);profit = Math.max(price - min, profit);}


return profit;}

买卖股票的最佳时机 II

给定一个数组 prices 表示一支股票每天的价格。可以完成任意次数的交易, 不过不能同时参与多个交易,设计一个算法求出最大的利润。


贪心:只要相邻的两天股票的价格是上升的, 我们就进行一次交易, 获得一定利润。


public int maxProfit(int[] prices) {int profit = 0;for (int i = 0; i < prices.length - 1; i++) {int diff = prices[i + 1] - prices[i];if (diff > 0) {profit += diff;}}return profit;}

最大子数组

给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。


public int maxSubArray(int[] A) {if (A == null || A.length == 0){return 0;}//max 记录全局最大值,sum 记录区间和,如果当前 sum>0,那么可以继续和后面的数求和,否则就从 0 开始 int max = Integer.MIN_VALUE, sum = 0;for (int i = 0; i < A.length; i++) {sum += A[i];max = Math.max(max, sum);sum = Math.max(sum, 0);}


return max;}

主元素

用户头像

Android架构

关注

还未添加个人签名 2021.10.31 加入

还未添加个人简介

评论

发布
暂无评论
Android复习资料——常见面试算法题汇总,2021年最新Android大厂面试笔试题分享