腾讯--背景开发实习生一面的算法真题整理（2025年3月4日） ...

面经小记：

资料来源于网络收集。
腾讯实习基地Java后端一面准备：

算法模式：ACM模式卡码网ACM模式练习

必要独立完成完整代码，包罗方法类的创建、功能函数和主函数，大抵给出模板如下：

1. public class Main {
2.     public static void function() {
3.         System.out.println("Hello");
4.     }
6.     public static void main(String[] args) {
7.         function();
8.         System.out.println(" world!");
9.     }
10. }

复制代码

腾讯后端真题-234.回文链表（234.回文链表）

标题分析：

实验用O(n)的时间复杂度和O(1)的空间复杂度办理此题目，
考虑用快慢指针法帮忙办理此题目。又由于是回文串，考虑采用链表反转进行验证。
解题思路：

起首，借助快慢指针法，确定链表的midNode：
然后，找到midNode后，该节点的next节点作为待反转的后半链表的头结点，对后半列表进行翻转。

• 
  
  
  
  • 采用从前去后的迭代法进行反转，使空间复杂度为O(1)
    
  
  

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public boolean isPalindrome(ListNode head) {
13.         if (head == null) return true;
15.         ListNode fast = head;
16.         ListNode slow = head;
17.         ListNode midNode = null;
18.         ListNode preHalfHead = head;
19.         ListNode postHalfHead = null;
20.         while (fast.next != null && fast.next.next != null) {
21.             fast = fast.next.next;
22.             slow = slow.next;
23.         }
24.         midNode = slow;
25.         postHalfHead = reverseList(midNode.next);// 从后往前反转后半链表，得到反转后该链表的头结点
26.         while (preHalfHead != null && postHalfHead != null) {
27.             if (preHalfHead.val != postHalfHead.val) {
28.                 return false;
29.             }
30.             preHalfHead = preHalfHead.next;
31.             postHalfHead = postHalfHead.next;
32.         }
33.         return true;
34.     }
35.     public ListNode reverseList(ListNode head) {
36.         ListNode prev = null;
37.         ListNode curr = head;
38.         while (curr != null) {
39.             ListNode nextemp = curr.next;
40.             curr.next = prev;
41.             prev = curr;
42.             curr = nextemp;
43.         }
44.         return prev;
45.     }
46. }

复制代码

腾讯后端真题--912.排序数组（912.排序数组）

手撕时间复杂度为O(nlogn)的排序算法。

解题思路：

1.快速排序：

快速排序的主要思想是通过划分将待排序的序列分成前后两部分，其中前一部分比后一部分的数据要小，然后递归调用函数对两部分序列分别进行快速排序，直至整个序列到达有序。
注意：Java中数组作为参数传递，传递的是引用而非值。

1. class Solution {
2.     public int[] sortArray(int[] nums) {// 主函数，最终返回nums
3.         randomizedQuicksort(nums, 0, nums.length - 1);
4.         return nums;
5.     }
7.     public void randomizedQuicksort(int[] nums, int l, int r) {// 功能函数，递归实现快速排序
8.         if (l < r) {
9.             int mid = randomizedPartition(nums, l, r);
10.             randomizedQuicksort(nums, l, mid - 1);
11.             randomizedQuicksort(nums, mid + 1, r);
12.         }
13.     }
15.     public int randomizedPartition(int[] nums, int l, int r) {// 辅助函数，随机选择基准数并交换至末尾，调用分组函数
16.         int i = new Random().nextInt(r - l + 1) + l;
17.         swap(nums, i, r);
18.         return partition(nums, l, r);
19.     }
21.     public int partition(int[] nums, int l, int r) {//  辅助函数，以基准数为界实现对数组的划分
22.         int pivot = nums[r];
23.         int i = l - 1;
24.         for (int j = l; j < r; j++) {
25.             if (nums[j] <= pivot) {
26.                 i++;
27.                 swap(nums, i, j);
28.             }
29.         }
30.         i++;
31.         swap(nums, i, r);
32.         return i;
33.     }
35.     private void swap(int[] nums, int i, int j) {// 辅助函数，进行两个下标处的元素交换
36.         if (i == j) return;
37.         int temp = nums[j];
38.         nums[j] = nums[i];
39.         nums[i] = temp;
40.     }
41. }

复制代码

2.归并排序：

归并排序的主要思想是分而治之，将一个长为n的待排序列不断对半分解，每次先递归调用函数式两个子序列有序，然后再线性合并使得两个有序的子序列合并成整个有序的序列。

1. class Solution {
2.     int[] tmp;
4.     public int[] sortArray(int[] nums) {
5.         tmp = new int[nums.length];
6.         mergeSort(nums, 0, nums.length - 1);
7.         return nums;
8.     }
10.     public void mergeSort(int[] nums, int l, int r) {
11.         if (l >= r) return;
13.         int mid = (l + r) / 2;
14.         mergeSort(nums, l, mid);
15.         mergeSort(nums, mid + 1, r);
17.         int i = l, j = mid + 1;
18.         int cnt = 0;
19.         while (i <= mid && j <= r) {
20.             if (nums[i] <= nums[j]) {
21.                 tmp[cnt++] = nums[i++];
22.             } else {
23.                 tmp[cnt++] = nums[j++];
24.             }
25.         }
26.         while (i <= mid) {
27.             tmp[cnt++] = nums[i++];
28.         }
29.         while (j <= r) {
30.             tmp[cnt++] = nums[j++];
31.         }
32.         for (int k = 0; k < r - l + 1; k++) {
33.             nums[k + l] = tmp[k];
34.         }
35.     }
36. }

复制代码

腾讯后端真题--3.无重复字符的最宗子串（腾讯后端真题--3.无重复字符的最宗子串）

标题分析：

给定一个字符串，请找出其中不含有重复字符的最宗子串的长度。
注意：最终返回的是一个整型值，代表最宗子串的长度，且子串是字符串中一连的部分。
别的，给定的字符串由英笔墨母、数字、符号和空格构成，排除了借助构造定长数组以记载子串内所出现的字符的方式。
解题思路：

要求出最宗子串，起首考虑的是用双指针的滑动窗口法界定子串，从而尽可能遍历最长的无重复字符的子串。
用Set记载当前子串所包含的元素，右指针移动时向Set中增加元素，左指针移动时从Set中删除元素。
不断实验移动右指针以增宗子串长度，当碰到重复元素时，不断移动左指针并从Set中去除左指针所指向的元素，直至重复元素被移除，将该元素添入Set。

1. class Solution {
2.     public int lengthOfLongestSubstring(String s) {
3.         Set<Character> set = new HashSet<>();// 记录出现元素
4.         int res = 0;// 结果
5.         for(int left = 0, right = 0; right < s.length(); right++) {// 不断移动右指针以尝试扩大子串长度
6.             char ch = s.charAt(right);// right指向的元素，也是当前要考虑的元素
7.             while(set.contains(ch)) {// Set中有ch，则缩短左边界，同时从Set集合出元素
8.                 set.remove(s.charAt(left));
9.                 left++;
10.             }
11.             set.add(ch);// 将右指针所指向的元素添入Set
12.             res = res > right - left + 1 ? res : right - left + 1;// 尝试更新
13.         }
14.         return res;
15.     }
16. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。