面经小记：
资料来源于网络收集。
腾讯实习基地Java后端一面准备：
算法模式：ACM模式卡码网ACM模式练习
需要独立完成完整代码，包括方法类的创建、功能函数和主函数，大致给出模板如下：
public class Main {
public static void function() {
System.out.println("Hello");
}
public static void main(String[] args) {
function();
System.out.println(" world!");
}
}腾讯后端真题-234.回文链表（234.回文链表）
题目分析：
尝试用O(n)的时间复杂度和O(1)的空间复杂度解决此问题，
考虑用快慢指针法协助解决此问题。又因为是回文串，考虑采用链表反转进行验证。
解题思路：
首先，借助快慢指针法，确定链表的midNode：
然后，找到midNode后，该节点的next节点作为待反转的后半链表的头结点，对后半列表进行翻转。
-
- 采用从前往后的迭代法进行反转，使空间复杂度为O(1)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) return true;
ListNode fast = head;
ListNode slow = head;
ListNode midNode = null;
ListNode preHalfHead = head;
ListNode postHalfHead = null;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
midNode = slow;
postHalfHead = reverseList(midNode.next);// 从后往前反转后半链表，得到反转后该链表的头结点
while (preHalfHead != null && postHalfHead != null) {
if (preHalfHead.val != postHalfHead.val) {
return false;
}
preHalfHead = preHalfHead.next;
postHalfHead = postHalfHead.next;
}
return true;
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextemp;
}
return prev;
}
}腾讯后端真题--912.排序数组（912.排序数组）
手撕时间复杂度为O(nlogn)的排序算法。
解题思路：
1.快速排序：
快速排序的主要思想是通过划分将待排序的序列分成前后两部分，其中前一部分比后一部分的数据要小，然后递归调用函数对两部分序列分别进行快速排序，直至整个序列达到有序。
注意：Java中数组作为参数传递，传递的是引用而非值。
class Solution {
public int[] sortArray(int[] nums) {// 主函数，最终返回nums
randomizedQuicksort(nums, 0, nums.length - 1);
return nums;
}
public void randomizedQuicksort(int[] nums, int l, int r) {// 功能函数，递归实现快速排序
if (l < r) {
int mid = randomizedPartition(nums, l, r);
randomizedQuicksort(nums, l, mid - 1);
randomizedQuicksort(nums, mid + 1, r);
}
}
public int randomizedPartition(int[] nums, int l, int r) {// 辅助函数，随机选择基准数并交换至末尾，调用分组函数
int i = new Random().nextInt(r - l + 1) + l;
swap(nums, i, r);
return partition(nums, l, r);
}
public int partition(int[] nums, int l, int r) {// 辅助函数，以基准数为界实现对数组的划分
int pivot = nums[r];
int i = l - 1;
for (int j = l; j < r; j++) {
if (nums[j] <= pivot) {
i++;
swap(nums, i, j);
}
}
i++;
swap(nums, i, r);
return i;
}
private void swap(int[] nums, int i, int j) {// 辅助函数，进行两个下标处的元素交换
if (i == j) return;
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}2.归并排序：
归并排序的主要思想是分而治之，将一个长为n的待排序列不断对半分解，每次先递归调用函数式两个子序列有序，然后再线性合并使得两个有序的子序列合并成整个有序的序列。
class Solution {
int[] tmp;
public int[] sortArray(int[] nums) {
tmp = new int[nums.length];
mergeSort(nums, 0, nums.length - 1);
return nums;
}
public void mergeSort(int[] nums, int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
int i = l, j = mid + 1;
int cnt = 0;
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
tmp[cnt++] = nums[i++];
} else {
tmp[cnt++] = nums[j++];
}
}
while (i <= mid) {
tmp[cnt++] = nums[i++];
}
while (j <= r) {
tmp[cnt++] = nums[j++];
}
for (int k = 0; k < r - l + 1; k++) {
nums[k + l] = tmp[k];
}
}
}腾讯后端真题--3.无重复字符的最长子串（腾讯后端真题--3.无重复字符的最长子串）
题目分析：
给定一个字符串，请找出其中不含有重复字符的最长子串的长度。
注意：最终返回的是一个整型值，代表最长子串的长度，且子串是字符串中连续的部分。
此外，给定的字符串由英文字母、数字、符号和空格组成，排除了借助构造定长数组以记录子串内所出现的字符的方式。
解题思路：
要求出最长子串，首先考虑的是用双指针的滑动窗口法界定子串，从而尽可能遍历最长的无重复字符的子串。
用Set记录当前子串所包含的元素，右指针移动时向Set中增加元素，左指针移动时从Set中删除元素。
不断尝试移动右指针以增长子串长度，当遇到重复元素时，不断移动左指针并从Set中去除左指针所指向的元素，直至重复元素被移除，将该元素添入Set。
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();// 记录出现元素
int res = 0;// 结果
for(int left = 0, right = 0; right < s.length(); right++) {// 不断移动右指针以尝试扩大子串长度
char ch = s.charAt(right);// right指向的元素，也是当前要考虑的元素
while(set.contains(ch)) {// Set中有ch，则缩短左边界，同时从Set集合出元素
set.remove(s.charAt(left));
left++;
}
set.add(ch);// 将右指针所指向的元素添入Set
res = res > right - left + 1 ? res : right - left + 1;// 尝试更新
}
return res;
}
}