网页模板下载网站,综合门户网站是什么意思,wordpress怎么登陆地址,班级网站怎么做ppt模板Java高频算法面试题
以下是Java面试中常见的高频算法题目#xff0c;涵盖了数据结构、算法思想和实际应用场景。
一、数组与字符串
1. 两数之和
public int[] twoSum(int[] nums, int target) {MapInteger, Integer map new HashMap();for (int i 0; i …Java高频算法面试题
以下是Java面试中常见的高频算法题目涵盖了数据结构、算法思想和实际应用场景。
一、数组与字符串
1. 两数之和
public int[] twoSum(int[] nums, int target) {MapInteger, 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);
}2. 最长无重复字符子串
public int lengthOfLongestSubstring(String s) {MapCharacter, Integer map new HashMap();int max 0, left 0;for (int right 0; right s.length(); right) {char c s.charAt(right);if (map.containsKey(c)) {left Math.max(left, map.get(c) 1);}map.put(c, right);max Math.max(max, right - left 1);}return max;
}二、链表操作
3. 反转链表
public ListNode reverseList(ListNode head) {ListNode prev null;ListNode curr head;while (curr ! null) {ListNode next curr.next;curr.next prev;prev curr;curr next;}return prev;
}4. 合并两个有序链表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy new ListNode(-1);ListNode curr dummy;while (l1 ! null l2 ! null) {if (l1.val l2.val) {curr.next l1;l1 l1.next;} else {curr.next l2;l2 l2.next;}curr curr.next;}curr.next l1 null ? l2 : l1;return dummy.next;
}三、树结构
5. 二叉树的最大深度
public int maxDepth(TreeNode root) {if (root null) return 0;return Math.max(maxDepth(root.left), maxDepth(root.right)) 1;
}6. 验证二叉搜索树
private boolean isValidBST(TreeNode node, long lower, long upper) {if (node null) return true;if (node.val lower || node.val upper) return false;return isValidBST(node.left, lower, node.val) isValidBST(node.right, node.val, upper);
}四、排序与搜索
7. 快速排序
public void quickSort(int[] arr, int low, int high) {if (low high) {int pi partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi 1, high);}
}private int partition(int[] arr, int low, int high) {int pivot arr[high];int i low - 1;for (int j low; j high; j) {if (arr[j] pivot) {i;swap(arr, i, j);}}swap(arr, i 1, high);return i 1;
}private void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;
}8. 二分查找
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;if (nums[mid] target) left mid 1;else right mid - 1;}return -1;
}五、动态规划
9. 爬楼梯
public int climbStairs(int n) {if (n 1) return 1;int[] dp new int[n 1];dp[1] 1;dp[2] 2;for (int i 3; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];
}10. 最长递增子序列
public int lengthOfLIS(int[] nums) {int[] dp new int[nums.length];Arrays.fill(dp, 1);int max 1;for (int i 1; i nums.length; i) {for (int j 0; j i; j) {if (nums[i] nums[j]) {dp[i] Math.max(dp[i], dp[j] 1);}}max Math.max(max, dp[i]);}return max;
}六、回溯算法
11. 全排列
public ListListInteger permute(int[] nums) {ListListInteger res new ArrayList();backtrack(res, new ArrayList(), nums);return res;
}private void backtrack(ListListInteger res, ListInteger temp, int[] nums) {if (temp.size() nums.length) {res.add(new ArrayList(temp));} else {for (int i 0; i nums.length; i) {if (temp.contains(nums[i])) continue;temp.add(nums[i]);backtrack(res, temp, nums);temp.remove(temp.size() - 1);}}
}12. 组合总和
public ListListInteger combinationSum(int[] candidates, int target) {ListListInteger res new ArrayList();Arrays.sort(candidates);backtrack(res, new ArrayList(), candidates, target, 0);return res;
}private void backtrack(ListListInteger res, ListInteger temp, int[] candidates, int remain, int start) {if (remain 0) return;if (remain 0) {res.add(new ArrayList(temp));return;}for (int i start; i candidates.length; i) {temp.add(candidates[i]);backtrack(res, temp, candidates, remain - candidates[i], i);temp.remove(temp.size() - 1);}
}七、其他重要算法
13. LRU缓存机制
class LRUCache {class DLinkedNode {int key;int value;DLinkedNode prev;DLinkedNode next;}private MapInteger, DLinkedNode cache new HashMap();private int size;private int capacity;private DLinkedNode head, tail;public LRUCache(int capacity) {this.size 0;this.capacity capacity;head new DLinkedNode();tail new DLinkedNode();head.next tail;tail.prev head;}public int get(int key) {DLinkedNode node cache.get(key);if (node null) return -1;moveToHead(node);return node.value;}public void put(int key, int value) {DLinkedNode node cache.get(key);if (node null) {DLinkedNode newNode new DLinkedNode();newNode.key key;newNode.value value;cache.put(key, newNode);addNode(newNode);size;if (size capacity) {DLinkedNode tail popTail();cache.remove(tail.key);size--;}} else {node.value value;moveToHead(node);}}private void addNode(DLinkedNode node) {node.prev head;node.next head.next;head.next.prev node;head.next node;}private void removeNode(DLinkedNode node) {DLinkedNode prev node.prev;DLinkedNode next node.next;prev.next next;next.prev prev;}private void moveToHead(DLinkedNode node) {removeNode(node);addNode(node);}private DLinkedNode popTail() {DLinkedNode res tail.prev;removeNode(res);return res;}
}14. 实现Trie(前缀树)
class Trie {class TrieNode {TrieNode[] children new TrieNode[26];boolean isEnd;}private TrieNode root;public Trie() {root new TrieNode();}public void insert(String word) {TrieNode node root;for (char c : word.toCharArray()) {if (node.children[c - a] null) {node.children[c - a] new TrieNode();}node node.children[c - a];}node.isEnd true;}public boolean search(String word) {TrieNode node searchPrefix(word);return node ! null node.isEnd;}public boolean startsWith(String prefix) {return searchPrefix(prefix) ! null;}private TrieNode searchPrefix(String prefix) {TrieNode node root;for (char c : prefix.toCharArray()) {if (node.children[c - a] null) return null;node node.children[c - a];}return node;}
}这些算法题目覆盖了Java面试中最常见的数据结构和算法问题。建议不仅要理解这些解决方案还要能够分析它们的时间复杂度和空间复杂度并思考可能的优化方法。
