Java 算法面试题
常见技术问题 刘宇帅 1月前 阅读量: 52
1. 反转字符串
题目描述：
编写一个函数，接受一个字符串作为输入，返回其反转后的字符串。
示例：
输入: "hello"
输出: "olleh"解答：
public String reverseString(String s) {
return new StringBuilder(s).reverse().toString();
}2. 判断回文数
题目描述：
判断一个整数是否是回文数。不能使用额外的空间。
示例：
输入: 121
输出: true
输入: -121
输出: false解答：
public boolean isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x != 0)) return false;
int revertedNumber = 0;
while (x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
return x == revertedNumber || x == revertedNumber / 10;
}3. 两数之和
题目描述：
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数的下标。
示例：
输入: nums = [2, 7, 11, 15], target = 9
输出: [0, 1]解答：
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int complement = target - nums[i];
if(map.containsKey(complement)){
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}4. 合并两个有序链表
题目描述：
将两个升序链表合并为一个新的升序链表并返回。
示例：
输入: 1->2->4, 1->3->4
输出: 1->1->2->3->4->4解答：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
current.next = l1;
l1 = l1.next;
} else{
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 != null ? l1 : l2;
return dummy.next;
}5. 二叉树的最大深度
题目描述：
给定一个二叉树，找出其最大深度。
示例：
输入: 二叉树 [3,9,20,null,null,15,7]
输出: 3解答：
public int maxDepth(TreeNode root) {
if(root == null) return 0;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}6. 字符串中的第一个唯一字符
题目描述：
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，返回 -1。
示例：
输入: "leetcode"
输出: 0
输入: "loveleetcode"
输出: 2解答：
public int firstUniqChar(String s) {
int[] count = new int[26];
for(char c : s.toCharArray()){
count[c - 'a']++;
}
for(int i = 0; i < s.length(); i++){
if(count[s.charAt(i) - 'a'] == 1) return i;
}
return -1;
}7. 判断有效的括号
题目描述：
给定一个只包括 (，)，{，}，[，] 的字符串，判断字符串是否有效。
示例：
输入: "()[]{}"
输出: true
输入: "([)]"
输出: false解答：
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(char c : s.toCharArray()){
if(c == '(') stack.push(')');
else if(c == '{') stack.push('}');
else if(c == '[') stack.push(']');
else if(stack.isEmpty() || stack.pop() != c) return false;
}
return stack.isEmpty();
}8. 合并两个有序数组
题目描述：
将两个有序整数数组 nums1 和 nums2 合并为一个新的有序数组。
示例：
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]解答：
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m -1, j = n -1, k = m + n -1;
while(i >=0 && j >=0){
if(nums1[i] > nums2[j]){
nums1[k--] = nums1[i--];
} else{
nums1[k--] = nums2[j--];
}
}
while(j >= 0){
nums1[k--] = nums2[j--];
}
}9. 实现二分查找
题目描述：
在排序数组中查找目标值的索引，如果不存在则返回 -1。
示例：
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4解答：
public int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length -1;
while(left <= right){
int mid = left + (right - left)/2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) left = mid +1;
else right = mid -1;
}
return -1;
}10. 找出数组中重复的数字
题目描述：
在一个长度为 n 的数组中，所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例：
输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3解答：
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int num : nums){
if(set.contains(num)) return num;
set.add(num);
}
return -1;
}11. 从排序数组中删除重复项
题目描述：
给定一个排序数组，删除其中的重复元素，使得每个元素只出现一次，并返回新的长度。
示例：
输入: nums = [0,0,1,1,1,2,2,3,3,4]
输出: 5, nums = [0,1,2,3,4]解答：
public int removeDuplicates(int[] nums) {
if(nums.length == 0) return 0;
int i = 0;
for(int j = 1; j < nums.length; j++){
if(nums[j] != nums[i]){
i++;
nums[i] = nums[j];
}
}
return i + 1;
}12. 实现快速排序
题目描述：
用 Java 实现快速排序算法，对数组进行排序。
解答：
public void quickSort(int[] arr, int left, int right) {
if(left < right){
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex -1);
quickSort(arr, pivotIndex +1, right);
}
}
private int partition(int[] arr, int left, int right){
int pivot = arr[right];
int i = left -1;
for(int j = left; j < right; j++){
if(arr[j] <= pivot){
i++;
swap(arr, i, j);
}
}
swap(arr, i+1, right);
return i+1;
}
private void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}13. 求斐波那契数列的第 N 项
题目描述：
实现一个函数，输入 n，求斐波那契数列的第 n 项。
解答：
public int fib(int n) {
if(n <= 1) return n;
int a = 0, b = 1;
for(int i = 2; i <= n; i++){
int sum = (a + b) % 1000000007;
a = b;
b = sum;
}
return b;
}14. 字符串全排列
题目描述：
输入一个字符串，打印出该字符串中字符的所有排列。
示例：
输入：abc
输出：["abc", "acb", "bac", "bca", "cab", "cba"]解答：
public List<String> permutation(String s) {
List<String> res = new ArrayList<>();
char[] chars = s.toCharArray();
Arrays.sort(chars);
boolean[] used = new boolean[chars.length];
backtrack(res, new StringBuilder(), chars, used);
return res;
}
private void backtrack(List<String> res, StringBuilder path, char[] chars, boolean[] used) {
if(path.length() == chars.length){
res.add(path.toString());
return;
}
for(int i = 0; i < chars.length; i++){
if(used[i]) continue;
if(i > 0 && chars[i] == chars[i -1] && !used[i -1]) continue;
used[i] = true;
path.append(chars[i]);
backtrack(res, path, chars, used);
used[i] = false;
path.deleteCharAt(path.length() -1);
}
}15. LRU 缓存机制
题目描述：
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。
解答：
class LRUCache {
private final int capacity;
private final Map<Integer, Integer> map;
private final LinkedList<Integer> list;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
list = new LinkedList<>();
}
public int get(int key) {
if(!map.containsKey(key)) return -1;
list.remove((Integer)key);
list.addFirst(key);
return map.get(key);
}
public void put(int key, int value) {
if(map.containsKey(key)){
list.remove((Integer)key);
} else if(map.size() == capacity){
int lastKey = list.removeLast();
map.remove(lastKey);
}
list.addFirst(key);
map.put(key, value);
}
}总结
以上列举了常见的 Java 算法面试题及其解答。在面试中，不仅要能够写出正确的代码，还要清晰地解释你的思路。建议在平时多练习 LeetCode、牛客网等平台的算法题，提升编程能力和思维逻辑。
