面试手撕代码
- 判断链表是否有环
- 前k个大的数
- 给定一个字符串，返回后面k个字符（采用sunstring(int start, int end)，或者利用StringBuilder来Copy）
- 计算1/2=0.5,1/3=0.(3) 输入两个数，计算最后的结果，以字符串输出。要考虑负数，除数不为0，其他循环小数的情况比如12(125),(125)
- 输出链表：①线性存储；②递归；③分为两半，翻转后面一半，再依次连接 输入：1-2-3-4-5-6-7-8 输出：1-8-2-7-3-6-4-5
- 反转单链表（两种方法），斐波那契数列（跳台阶）（动态规划）
- 快速排序
- String字符串统计abc，链表倒数第k个（双指针）
- 长度为m的数组放1-m的数字，有些数字存在一次，有些存在两次，怎么得到只存在一次的数字（讲思路）
- 若只有一个，则采用异或运算
- 多个结果，则采用数组或HashMap计数，或者HashSet来实现
- 二叉树中寻找两个节点的公共父节点？
- 二叉树深度
- 数组里的第2大元素（堆，冒泡思想，快排）
- 单向链表的倒数第n个节点（双指针）
1、判断链表是否有环
class ListNode{
int val;
ListNode next;
public ListNode(int val){
this.val = val;
next = null;
}
}
public class ListCycle {
public ListNode detectCycle(ListNode head) {
// 采用快慢指针
ListNode fast = head, slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
fast = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
break;
}
}
return fast == null || fast.next == null ? null : fast;
}
}
删除有序数组中的重复项
public int removeDuplicates(int[] nums) {
// 采用快慢指针
int n = nums.length;
if(n == 0) return 0;
int slow = 0, fast = 0;
while(fast < n){
if(nums[fast] != nums[slow]){
slow++;
nums[slow] = nums[fast];
}
fast++;
}
return slow + 1;
}
删除排序链表中的重复元素
public ListNode deleteDuplicates(ListNode head) {
if(head == null) return null;
ListNode slow = head, fast = head.next;
while(fast != null){
if(fast.val != slow.val){
slow.next = fast;
slow = slow.next;
}
fast = fast.next;
}
slow.next = null;
return head;
}
快速排序/数组中前k个大的数（也可采用冒泡，k次循环）
import java.util.Comparator;
import java.util.PriorityQueue;
public class QuickSort {
// 快速排序
public static void sort(int[] arr, int start, int end){
if(start >= end) return;
int part = partition(arr, start, end);
sort(arr, start, part - 1);
sort(arr, part + 1, end);
}
// 获取第k大的元素/获取最大的k个元素（修改数组，无序）
public static int findKthLargest(int[] nums, int k){
int len = nums.length;
int low = 0, high = len - 1;
k = len - k;
while(low < high){// 采用二分法+快速排序
int p = partition(nums, low, high);
if(p < k){
low = p + 1;
}else if(p > k){
high = p - 1;
}else{
return nums[p];// 返回元素值
// return p;// 返回索引
}
}
return -1;
}
// 获取最大的k个元素（不修改数组，有序）
public static int[] firstK(int[] nums, int k){
int[] res = new int[k];
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});// 大顶堆
for (int num : nums) {
priorityQueue.add(num);
}
for (int i = k - 1; i >= 0 ; i--) {
res[i] = priorityQueue.poll();
}
return res;
}
public static int partition(int[] arr, int start, int end){
if(start == end) return start;
int left = start, right = end + 1;
int mid = arr[start];
while(true){
while(arr[++left] < mid){// 注意！！！
if (left == end) break;
}
while(arr[--right] > mid){
if (right == start) break;
}
if(left >= right) break;
swap(arr, left, right);
}
swap(arr, start, right);
return right;
}
public static void swap(int[] arr, int i, int j){
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
public static void main(String[] args) {
int[] arr = new int[]{5,6,9,5,7,3,2,4,8};
/*sort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num);
}*/
// System.out.println(findKthLargest(arr, 3));
int[] res = firstK(arr, 3);
for (int num : res) {
System.out.print(num + " ");
}
}
}
链表转换:将原链表的每个节点添加到新链表的头部和尾部
1->2->3->4->5 5->3->1->2->4
public ListNode formatList (ListNode head) {
if(head == null) return null;
if(head.next == null) return head;
ListNode cur = head.next;
ListNode start = head, end = head;
end.next = null;
ListNode next = cur.next;
while(cur != null){
// 插尾节点
end.next = cur;
cur = next;
if(cur == null) break;
next = cur.next;
end = end.next;
end.next = null;
// 先插头节点
cur.next = start;
start = cur;
cur = next;
if(next != null ) next = cur.next;
}
return start;
}
链表转换：
输入：1-2-3-4-5-6-7-8 输出：1-8-2-7-3-6-4-5
// 方式一：
public void reorderList(ListNode head) {
if (head == null) return;
//存到 list 中去
List<ListNode> list = new ArrayList<>();
while (head != null) {
list.add(head);
head = head.next;
}
//头尾指针依次取元素
int i = 0, j = list.size() - 1;
while (i < j) {
list.get(i).next = list.get(j);
i++;
//偶数个节点的情况，会提前相遇
if (i == j) break;
list.get(j).next = list.get(i);
j--;
}
list.get(i).next = null;
}
// 方式二：
public void reorderList(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return;
}
int len = 0;
ListNode h = head;
//求出节点数
while (h != null) {
len++;
h = h.next;
}
reorderListHelper(head, len);
}
private ListNode reorderListHelper(ListNode head, int len) {
if (len == 1) {
ListNode outTail = head.next;
head.next = null;
return outTail;
}
if (len == 2) {
ListNode outTail = head.next.next;
head.next.next = null;
return outTail;
}
//得到对应的尾节点，并且将头结点和尾节点之间的链表通过递归处理
ListNode tail = reorderListHelper(head.next, len - 2);
ListNode subHead = head.next;//中间链表的头结点
head.next = tail;
ListNode outTail = tail.next; //上一层 head 对应的 tail
tail.next = subHead;
return outTail;
}
// 方式三：
public void reorderList(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return;
}
//找中点，链表分成两个
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode newHead = slow.next;
slow.next = null;
//第二个链表倒置
newHead = reverseList(newHead);
//链表节点依次连接
while (newHead != null) {
ListNode temp = newHead.next;
newHead.next = head.next;
head.next = newHead;
head = newHead.next;
newHead = temp;
}
}
private ListNode reverseList(ListNode head) {
if (head == null) return null;
ListNode tail = head;
head = head.next;
tail.next = null;
while (head != null) {
ListNode temp = head.next;
head.next = tail;
tail = head;
head = temp;
}
return tail;
}
二叉树中寻找两个节点的公共父节点
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null && right == null) return null; // 1.
if(left == null) return right; // 3.
if(right == null) return left; // 4.
return root; // 2. if(left != null and right != null)
}
}
二叉树深度
// 后序遍历
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
// 层序遍历
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp;
int res = 0;
while(!queue.isEmpty()) {
tmp = new LinkedList<>();
for(TreeNode node : queue) {
if(node.left != null) tmp.add(node.left);
if(node.right != null) tmp.add(node.right);
}
queue = tmp;
res++;
}
return res;
}
}
// 二叉树的最小深度
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
// root 本身就是一层，depth 初始化为 1
int depth = 1;
while (!q.isEmpty()) {
int sz = q.size();
/* 遍历当前层的节点 */
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
/* 判断是否到达叶子结点 */
if (cur.left == null && cur.right == null)
return depth;
/* 将下一层节点加入队列 */
if (cur.left != null)
q.offer(cur.left);
if (cur.right != null)
q.offer(cur.right);
}
/* 这里增加步数 */
depth++;
}
return depth;
}
}
// 二叉树的最大深度
/***** 解法一，回溯算法思路 *****/
class Solution {
int depth = 0;
int res = 0;
public int maxDepth(TreeNode root) {
traverse(root);
return res;
}
// 遍历二叉树
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序遍历位置
depth++;
// 遍历的过程中记录最大深度
res = Math.max(res, depth);
traverse(root.left);
traverse(root.right);
// 后序遍历位置
depth--;
}
}
/***** 解法二，动态规划思路 *****/
class Solution2 {
// 定义：输入一个节点，返回以该节点为根的二叉树的最大深度
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 根据左右子树的最大深度推出原二叉树的最大深度
return 1 + Math.max(leftMax, rightMax);
}
}
LRU缓存
class LRUCache {
int cap;
LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
public LRUCache(int capacity) {
this.cap = capacity;
}
public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
// 将 key 变为最近使用
makeRecently(key);
return cache.get(key);
}
public void put(int key, int val) {
if (cache.containsKey(key)) {
// 修改 key 的值
cache.put(key, val);
// 将 key 变为最近使用
makeRecently(key);
return;
}
if (cache.size() >= this.cap) {
// 链表头部就是最久未使用的 key
int oldestKey = cache.keySet().iterator().next();
cache.remove(oldestKey);
}
// 将新的 key 添加链表尾部
cache.put(key, val);
}
private void makeRecently(int key) {
int val = cache.get(key);
// 删除 key，重新插入到队尾
cache.remove(key);
cache.put(key, val);
}
}
LFU缓存
class LFUCache {
// key 到 val 的映射，我们后文称为 KV 表
HashMap<Integer, Integer> keyToVal;
// key 到 freq 的映射，我们后文称为 KF 表
HashMap<Integer, Integer> keyToFreq;
// freq 到 key 列表的映射，我们后文称为 FK 表
HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
// 记录最小的频次
int minFreq;
// 记录 LFU 缓存的最大容量
int cap;
public LFUCache(int capacity) {
keyToVal = new HashMap<>();
keyToFreq = new HashMap<>();
freqToKeys = new HashMap<>();
this.cap = capacity;
this.minFreq = 0;
}
public int get(int key) {
if (!keyToVal.containsKey(key)) {
return -1;
}
// 增加 key 对应的 freq
increaseFreq(key);
return keyToVal.get(key);
}
public void put(int key, int val) {
if (this.cap <= 0) return;
/* 若 key 已存在，修改对应的 val 即可 */
if (keyToVal.containsKey(key)) {
keyToVal.put(key, val);
// key 对应的 freq 加一
increaseFreq(key);
return;
}
/* key 不存在，需要插入 */
/* 容量已满的话需要淘汰一个 freq 最小的 key */
if (this.cap <= keyToVal.size()) {
removeMinFreqKey();
}
/* 插入 key 和 val，对应的 freq 为 1 */
// 插入 KV 表
keyToVal.put(key, val);
// 插入 KF 表
keyToFreq.put(key, 1);
// 插入 FK 表
freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
freqToKeys.get(1).add(key);
// 插入新 key 后最小的 freq 肯定是 1
this.minFreq = 1;
}
private void increaseFreq(int key) {
int freq = keyToFreq.get(key);
/* 更新 KF 表 */
keyToFreq.put(key, freq + 1);
/* 更新 FK 表 */
// 将 key 从 freq 对应的列表中删除
freqToKeys.get(freq).remove(key);
// 将 key 加入 freq + 1 对应的列表中
freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
freqToKeys.get(freq + 1).add(key);
// 如果 freq 对应的列表空了，移除这个 freq
if (freqToKeys.get(freq).isEmpty()) {
freqToKeys.remove(freq);
// 如果这个 freq 恰好是 minFreq，更新 minFreq
if (freq == this.minFreq) {
this.minFreq++;
}
}
}
private void removeMinFreqKey() {
// freq 最小的 key 列表
LinkedHashSet<Integer> keyList = freqToKeys.get(this.minFreq);
// 其中最先被插入的那个 key 就是该被淘汰的 key
int deletedKey = keyList.iterator().next();
/* 更新 FK 表 */
keyList.remove(deletedKey);
if (keyList.isEmpty()) {
freqToKeys.remove(this.minFreq);
// 问：这里需要更新 minFreq 的值吗？
}
/* 更新 KV 表 */
keyToVal.remove(deletedKey);
/* 更新 KF 表 */
keyToFreq.remove(deletedKey);
}
}
查看21道真题和解析
投递深圳同为数码等公司10个岗位
