【大厂春招高频题】腾讯（1）

【大厂春招高频题】腾讯（1）

1、LRU缓存机制

2、反转链表

整个链表翻转可以
1、头插法；
2、翻转指针；
3、递归
4、用栈

class Solution{public ListNode reverseList(ListNode head){if(head == null|| ==null){return head;}ListNode pre = new ListNode(0); = head;ListNode cur = ; = null;while(cur!=null){ListNode tmp = ; = ; = cur;cur = tmp;};}
}

在这里插入代码片

//递归
class Solution{public ListNode reverseList(ListNode head){if(head == null ||  == null){return head;}ListNode node = );//这个是原链表的最后一个元素 = head;//倒数第二层递归，head在倒数第二个节点,此时开始反转 = null;//这里一定要设置空，不然会有环return node;}
}

class Solution{public ListNode reverseList(ListNode head){// if(head == null ||  == null){return null;}ListNode tailNode = null;while(head!=null){tailNode = new ListNode(head.val,tailNode);head = ;}return tailNode;}
}

//栈
class Solution {public ListNode reverseList(ListNode head) {Stack<ListNode> st = new Stack<ListNode>();!=null){st.push(head);head = ;}//System.out.pty());while(!st.empty()){ListNode s = st.pop();s.next = ; = s;head = ;}return head;}
}

反转链表 II

指定区间翻转

class Solution{public ListNode reverseBetween (ListNode head, int m, int n) {if(head == null ||  == null){return head;}//让pre指向第一个翻转节点的前驱节点int gap = n-m+1;ListNode dummy = new ListNode(0);ListNode pre =  = head;while(m > 1){pre = head;head = ;m--;}   //现在让cur指向第一个翻转节点ListNode cur = ; = null;while(gap > 1){ListNode node = ;// =  = ; = cur;cur = node;gap--;} = cur;;}
}

3、合并两个有序链表

class Solution{public ListNode mergeTwoLists(ListNode l1,ListNode l2){if(l1 == null){return l2;}if(l2 == null){return l1;}ListNode newHead = new ListNode(-1);ListNode cur = newHead;while(l1!=null && l2!=null){if(l1.val < l2.val){ = l1;cur = l1;l1 = l1.next;}else{ = l2;cur = l2;l2 = l2.next;}} = l1==null?l2:l1;;}
}

合并两个有序数组

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {if(nums1.length == 0 || nums2.length == 0){return;}int k = nums1.length-1,i = m-1,j = n-1;while(i >=0 && j >=0 && k >=0){if(nums1[i] < nums2[j]){nums1[k] = nums2[j];j--;}else{nums1[k] = nums1[i];i--;}k--;}while(j >=0){nums1[k--] = nums2[j--];}return;}
}

4、用 Rand7() 实现 Rand10()

class Solution extends SolBase {public int rand10() {int a = rand7();int b = rand7();if(a > 4 && b < 4){return rand10();}else{return (a+b)%10+1;//a,b是从1开始的，不是从0开始，所以要加一}}
}

5、回文链表

比起30行代码，递归除了费内存一点，其他没毛病

class Solution{ListNode temp;public boolean isPalindrome(ListNode head){if(head == null ||  == null) return true;temp = head;return dfs(head);}private boolean dfs(ListNode head){if(head == null) return true;boolean res = ) && temp.val == head.val;temp = ;return res;}
}

6、最大子序和

找最大和的连续子数组。

class Solution {public int