Leetcode刷题、常用算法汇总(Java版本)，腾讯T3大牛总结_leetcode中相关java题型

String limit = sc.nextLine();

int row = Integer.parseInt(limit.split(" ")[0]);

int column = Integer.parseInt(limit.split(" ")[1]);

int[][] matrix = new int[row][column];

for (int i = 0; i < row; i++) {

String[] lineArr = sc.nextLine().split(" ");

int[] lintIntArr = new int[lineArr.length];

for (int j = 0; j < lineArr.length; j++) {

lintIntArr[j] = Integer.parseInt(lineArr[j]);

}

matrix[i] = lintIntArr;

}

for (int[] i : matrix) {

System.out.println(Arrays.toString(i));

}

int[][] result = new int[column][row];

result = transpose(matrix);

for (int[] i : result) {

System.out.println(Arrays.toString(i));

}

}

public static int[][] transpose1(int[][] matrix) {

int m = matrix.length, n = matrix[0].length;

int[][] transposed = new int[n][m];

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

transposed[j][i] = matrix[i][j];

}

}

return transposed;

}

public static int[][] transpose(int[][] matrix) {

int row = matrix.length, column = matrix[0].length;

int[][] res = new int[column][row];

for (int i = 0; i < row * column; i++) {

res[i / row][i % row] = matrix[i % row][i / row];

}

return res;

}

}

---

✔螺旋矩阵 II

===================================================================

① 题目

---

② 思路

---

1. 模拟法，设定边界

③ 代码

---

package dataStructure.Array;

import java.util.Scanner;

/**

• leetCode 59. 螺旋矩阵 II

*/

public class generateMatrix {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int[][] result = generateMatrixDemo(n);

for (int[] r : result) {

for (int j : r) {

System.out.printf("%d ", j);

}

System.out.println();

}

}

public static int[][] generateMatrixDemo(int n) {

int l = 0, r = n - 1, t = 0, b = n - 1;

int[][] mat = new int[n][n];

int num = 1, tar = n * n;

while (num <= tar) {

for (int i = l; i <= r; i++) mat[t][i] = num++; // left to right.

t++;

for (int i = t; i <= b; i++) mat[i][r] = num++; // top to bottom.

r–;

for (int i = r; i >= l; i–) mat[b][i] = num++; // right to left.

b–;

for (int i = b; i >= t; i–) mat[i][l] = num++; // bottom to top.

l++;

}

return mat;

}

}

---

✔子数组最大平均数 I

======================================================================

① 题目

---

② 思路

---

1. 滑动窗口：在数组中不断右滑，寻找第i到i+k个元素之和最大的窗口。滑动窗口参考

2. preSum方法：preSum方法

③ 代码

---

package algorithm;

import java.lang.reflect.Array;

import java.util.Arrays;

import java.util.Scanner;

/*

• leetcode 643. 子数组最大平均数 I

• 给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

• */

public class findMaxAverage {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

String[] nums = scanner.nextLine().split(" ");

int[] numsArr = new int[nums.length];

for (int i = 0; i < nums.length; i++) {

numsArr[i] = Integer.parseInt(nums[i]);

}

int k = scanner.nextInt();

System.out.println(findMaxAverageDemo2(numsArr, k));

}

public static double findMaxAverageDemo2(int[] nums, int k) {

int[] preSum = new int[nums.length + 1];

int sum = 0;

for (int i = 0; i < k; i++) {

sum += nums[i];

}

for (int i = 1; i < nums.length + 1; i++) {

preSum[i] = preSum[i - 1] + nums[i - 1];

if (i >= k) {

int currentSum = preSum[i] - preSum[i - k];

if (currentSum > sum) sum = currentSum;

}

}

return 1.0 * sum / k;

}

}

---

✔公平的糖果棒交换

====================================================================

① 题目

---

② 思路

---

1. 方法一：暴力双层for循环 超时

2. 方法二：哈希表。时间复杂度：O(n + m)O(n+m)，其中 nn 是序列 AA 的长度，mm 是序列 BB 的长度。空间复杂度：O(n)O(n)，其中 nn 是序列 AA 的长度。我们需要建立一个和序列 AA 等大的哈希表。

3. 方法三：双指针。要求数组有序。

③ 代码

---

package algorithm;

import java.util.Arrays;

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

public class fairCandySwap {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

String[] aNums = scanner.nextLine().split(" ");

String[] bNums = scanner.nextLine().split(" ");

int[] aArray = new int[aNums.length];

int[] bArray = new int[bNums.length];

for (int i = 0; i < aNums.length; i++) aArray[i] = Integer.parseInt(aNums[i]);

for (int i = 0; i < bNums.length; i++) bArray[i] = Integer.parseInt(bNums[i]);

int[] result = fairCandySwapDemo3(aArray, bArray);

System.out.println(Arrays.toString(result));

}

public static int[] fairCandySwapDemo1(int[] A, int[] B) {

for (int i = 0; i < A.length; i++) {

for (int j = 0; j < B.length; j++) {

int tempA = A[i];

int tempB = B[j];

A[i] = tempB;

B[j] = tempA;

if (arraySum(A) == arraySum(B)) {

return new int[]{tempA, tempB};

}

A[i] = tempA;

B[j] = tempB;

}

}

return new int[]{0, 0};

}

public static int[] fairCandySwapDemo2(int[] A, int[] B) {

int sumA = Arrays.stream(A).sum();

int sumB = Arrays.stream(B).sum();

int delta = (sumA - sumB) / 2;

Set rec = new HashSet<>();

for (int a : A) rec.add(a);

for (int y : B) {

int x = y + delta;

if (rec.contains(x)) {

return new int[]{x, y};

}

}

return new int[]{0, 0};

}

public static int[] fairCandySwapDemo3(int[] A, int[] B) {

Arrays.sort(A);

Arrays.sort(B);

int sum = (Arrays.stream(A).sum() - Arrays.stream(B).sum()) / 2;

int x = 0, y = 0;

while (x < A.length && y < B.length) {

if (A[x] - B[y] == sum) {

return new int[]{A[x], B[y]};

} else if (A[x] - B[y] > sum) {

++y;

} else {

++x;

}

}

return new int[]{0, 0};

}

public static int arraySum(int[] array) {

int sum = 0;

for (int i : array) {

sum += i;

}

return sum;

}

}

---

✔两数之和、三数之和

=====================================================================

参考：漫画算法题：两数之和与三数之和

这里考虑的两数之和、三数之和答案结果都是唯一的，因此返回的为int数组，如果结果不唯一，则需要返回List。

两数之和

---

① 题目

② 思路

1. 方法一：暴力法双层for循环 O(n2)

2. 方法二：哈希表 两次循环 第一次循环添加哈希表数据 第二次循环查询结果 O(n)

3. 方法三：哈希表 一次循环 在第一次插入数据之前先判断有没有满足结果的，有的话返回，没有的话再插入数据 O(n)

③ 代码

package dataStructure.Array;

import java.util.*;

public class twoSum {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

String[] nums = scanner.nextLine().split(" ");

int[] numArr = new int[nums.length];

for (int i = 0; i < nums.length; i++) {

numArr[i] = Integer.parseInt(nums[i]);

}

int target = scanner.nextInt();

int[] resultArr = twoSumDemo1(numArr, target);

System.out.println(Arrays.toString(resultArr));

}

public static int[] twoSumDemo1(int[] nums, int target) {

for (int i = 0; i < nums.length; i++) {

for (int j = i + 1; j < nums.length; j++) {

if (nums[i] + nums[j] == target) {

return new int[]{i, j};

}

}

}

return new int[]{0, 0};

}

public static int[] twoSumDemo2(int[] nums, int target) {

Map<Integer, Integer> map = new HashMap<>();

for (int i = 1; i < nums.length; i++) {

map.put(nums[i], i);

}

for (int i = 0; i < nums.length; i++) {

int other = target - nums[i];

if (map.containsKey(other) && map.get(other) != i) {

return new int[]{i, map.get(other)};

}

}

return new int[]{0, 0};

}

public static int[] twoSumDemo3(int[] nums, int target) {

Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < nums.length; i++) {

int other = target - nums[i];

if (map.containsKey(other)) {

return new int[]{i, map.get(other)};

}

map.put(nums[i], i);

}

return new int[]{0, 0};

}

}

三数之和

---

① 题目

求数组中三个数之和等于某数

② 思路

1. 方法一：外层一层for循环，内层使用两数之和的方法进行求解。时间复杂度：O(n2)。空间复杂度：O(n)。

2. 方法二：首先数组排序，外层仍然为一层for循环，for循环内容，采用"夹逼法"，左右两侧双指针，判断外层循环当前数组值与两个指针值的和与target的关系，从而进行指针的移动，最终求的结果。

③ 代码

package dataStructure.Array;

import java.util.Arrays;

import java.util.HashMap;

import java.util.Map;

import java.util.Scanner;

public class threeSum {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

String[] nums = scanner.nextLine().split(" ");

int[] numsArr = new int[nums.length];

for (int i = 0; i < nums.length; i++) {

numsArr[i] = Integer.parseInt(nums[i]);

}

int target = scanner.nextInt();

int[] result = threeSumDemo2(numsArr, target);

System.out.println(Arrays.toString(result));

}

public static int[] threeSumDemo1(int[] nums, int target) {

for (int i = 0; i < nums.length; i++) {

Map<Integer, Integer> map = new HashMap<>();

int d1 = target - nums[i];

// 寻找两数之和等于d1的组合

for (int j = i + 1; j < nums.length; j++) {

int d2 = d1 - nums[j];

if (map.containsKey(d2)) {

return new int[]{i, j, map.get(d2)};

}

map.put(nums[j], j);

}

}

return new int[]{0, 0, 0};

}

public static int[] threeSumDemo2(int[] nums, int target) {

Arrays.sort(nums);

for (int i = 0; i < nums.length; i++) {

int d = target - nums[i];

// j和k双指针循环定位,j在左端,k在右端

for (int j = i + 1, k = nums.length - 1; j < nums.length; j++) {

// k指针向左移动

while (j < k && (nums[j] + nums[k]) > d) {

k–;

}

// 如果指针重合，跳出本次循环

if (j == k) break;

if (nums[j] + nums[k] == d) {

return new int[]{i, j, k};

}

}

}

return new int[]{0, 0, 0};

}

}

---

✔ln(N!)

==================================================================

① 题目

---

编写一个递归的静态方法计算ln(N!)的值

② 思路

---

ln(N!) = ln(N) + ln(N-1) + ln(N-2) + ······ + ln(3) + ln(2) + ln(1)

③ 代码

---

package algorithm;

public class lgN {

public static void main(String[] args) {

System.out.println(lgNDemo(10));

}

public static double lgNDemo(int n) {

if (n == 1 || n == 0) return 0.0;

return Math.log(n) + lgNDemo(n - 1);

}

}

---

✔返回数组中每个元素出现的次数

==========================================================================

① 题目

---

编写一个静态方法histogram(),接受一个整型数组a[]和一个整数M为参数并返回一个大小为M的数组，其中第i个元素的值为整数i在参数数组中出现的次数。如果a[]中的值均在0-M-1之间，返回数组中所有元素之和应该等于a.length

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以添加V获取：vip1024b （备注Java）

结局：总结+分享

看完美团、字节、腾讯这三家的一二三面试问题，是不是感觉问的特别多，可能咱们真的又得开启面试造火箭、工作拧螺丝的模式去准备下一次的面试了。

开篇有提及我可是足足背下了Java互联网工程师面试1000题，多少还是有点用的呢，换汤不换药，不管面试官怎么问你，抓住本质即可！能读到此处的都是真爱

• Java互联网工程师面试1000题

而且从上面三家来看，算法与数据结构是必备不可少的呀，因此我建议大家可以去刷刷这本左程云大佬著作的 《程序员代码面试指南 IT名企算法与数据结构题目最优解》，里面近200道真实出现过的经典代码面试题。

• 程序员代码面试指南–IT名企算法与数据结构题目最优解

• 其余像设计模式，建议可以看看下面这4份PDF（已经整理）

• 更多的Java面试学习笔记如下，关于面试这一块，我额外细分出Java基础-中级-高级开发的面试+解析，以及调优笔记等等等。。。

以上所提及的全部Java面试学习的PDF及笔记，如若皆是你所需要的，那么都可发送给你！

img-Sdkt7imq-1712095870993)]
[外链图片转存中…(img-Tsk8hq6P-1712095870994)]

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以添加V获取：vip1024b （备注Java）
[外链图片转存中…(img-VW6Ocgba-1712095870994)]

结局：总结+分享

看完美团、字节、腾讯这三家的一二三面试问题，是不是感觉问的特别多，可能咱们真的又得开启面试造火箭、工作拧螺丝的模式去准备下一次的面试了。

开篇有提及我可是足足背下了Java互联网工程师面试1000题，多少还是有点用的呢，换汤不换药，不管面试官怎么问你，抓住本质即可！能读到此处的都是真爱

• Java互联网工程师面试1000题

[外链图片转存中…(img-pGKc1nWm-1712095870995)]

而且从上面三家来看，算法与数据结构是必备不可少的呀，因此我建议大家可以去刷刷这本左程云大佬著作的 《程序员代码面试指南 IT名企算法与数据结构题目最优解》，里面近200道真实出现过的经典代码面试题。

• 程序员代码面试指南–IT名企算法与数据结构题目最优解

[外链图片转存中…(img-sun57jUA-1712095870995)]

• 其余像设计模式，建议可以看看下面这4份PDF（已经整理）

[外链图片转存中…(img-lKcgpAmp-1712095870995)]

• 更多的Java面试学习笔记如下，关于面试这一块，我额外细分出Java基础-中级-高级开发的面试+解析，以及调优笔记等等等。。。

[外链图片转存中…(img-yEmMDk9Y-1712095870996)]

以上所提及的全部Java面试学习的PDF及笔记，如若皆是你所需要的，那么都可发送给你！