面经小记：
资料来源于网络收集。
腾讯实习基地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) {// 主函数，最终返回numsrandomizedQuicksort(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);// 将右指针所指向的元素添入Setres = res > right - left + 1 ? res : right - left + 1;// 尝试更新}return res;}
}
