合并两个已排序链表

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;}

主元素