给定一个字符串,找出不含有重复字符的最长子串的长度。
解决思路:
(相关资料图)
我们可以用滑动窗口来解决这个问题。我们用两个指针 i 和 j 来表示窗口的左右边界。每次移动右指针 j,同时用哈希表记录每个字符出现的位置。如果当前字符已经在哈希表中出现过了,那么就将左指针 i 移动到该字符上次出现的位置的下一个位置。每次更新最长子串的长度。
代码实现:
public int lengthOfLongestSubstring(String s) { int n = s.length(); int i = 0; int j = 0; int maxLen = 0; Map<Character, Integer> map = new HashMap<>(); while (j < n) { char c = s.charAt(j); if (map.containsKey(c)) { i = Math.max(i, map.get(c) + 1); } map.put(c, j); maxLen = Math.max(maxLen, j - i + 1); j++; } return maxLen;}
给定两个有序链表,将它们合并成一个新的有序链表并返回。
解决思路:
我们可以用递归的方法来解决这个问题。我们将两个链表的头节点进行比较,将较小的节点作为合并后链表的头节点,并将该节点的 next 指向递归合并后的链表。
代码实现:
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } if (l2 == null) { return l1; } if (l1.val <= l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; }}
设计一个支持 push、pop、top 和在常数时间内检索到最小元素的操作的栈。
解决思路:
我们可以用两个栈来实现这个问题。一个栈用来存储元素,另一个栈用来存储当前栈中的最小值。
具体来说,当一个元素被压入栈时,我们同时将该元素压入最小栈中,如果该元素比最小栈的栈顶元素小,则将该元素也压入最小栈中。当一个元素从栈中弹出时,我们同时将该元素从最小栈中弹出。当我们需要获取当前栈中的最小元素时,我们只需要查看最小栈的栈顶元素即可。
代码实现:
class MinStack { Stack<Integer> stack; Stack<Integer> minStack; public MinStack() { stack = new Stack<>(); minStack = new Stack<>();}public void push(int val) { stack.push(val); if (minStack.isEmpty() || val <= minStack.peek()) { minStack.push(val); }}public void pop() { if (stack.peek().equals(minStack.peek())) { minStack.pop(); } stack.pop();}public int top() { return stack.peek();}public int getMin() { return minStack.peek();}}
以上是关于常见算法题的解决思路、代码实现以及实际案例的详细讲解。对于互联网公司的校招来说,掌握这些算法题可以帮助我们更好地应对面试。当然,还需要多多练习,才能真正掌握这些算法。
标签: