面试题汇总（算法）
Merge Sorted Array（Java实现）
如何快速判断某 URL 是否在 20 亿的网址 URL 集合中？
剑指 offer 第一题： 二维数组中的查找
图解剑指 offer 第二题： 替换空格
图解剑指 offer 第三题： 从尾到头打印链表
public void printListFromTailToHead(List<String> list, int idx) {
int nextIdx = idx + 1;
if (list.size() >= nextIdx) {
printListFromTailToHead(list, nextIdx);
System.out.println(list.get(idx));
}
}
@Test
public void testPrintList() {
final List<String> list = Lists.newArrayList("0", "1", "2", "3", "4", "5");
printListFromTailToHead(list, 0);
}
如何在 1000 万个整数中快速查找某个整数？
这个问题并不难。我们的内存限制是 100MB ，每个数据大小是 8 字节，最简单的办法就是将数据存储在数组中，内存占用差不多是 今天讲的内容，我们可以先对这 1000 万数据从小到大排序，然后再利用二分查找算法，就可以快速地查找想要的数据了。 看起来这个问题并不难，很轻松就能解决。实际上，它暗藏了 “ 玄机 ” 。如果你对数据结构和算法有一定了解，知道散列表、二叉树这些支持快速查找的动态数据 结构。你可能会觉得，用散列表和二叉树也可以解决这个问题。实际上是不行的。 虽然大部分情况下，用二分查找可以解决的问题，用散列表、二叉树都可以解决。但是，不管是散列表还是二叉树，都会需要比较多的额外的内 存空间。如果用散列表或者二叉树来存储这 1000 万的数据，用 100MB 的内存肯定是存不下的。而二分查找底层依赖的是数组，除了数据本身之外，不需要额外存 储其他信息，是最省内存空间的存储方式，所以刚好能在限定的内存大小下解决这个问题。
分段的链表翻转
给定正整数k ，一个链表 头指针
实现k个元素分为一组，组之间是翻转的，组内是保持原来的顺序。
示例：
k= 2
A B C D E F G => G E F C D A B
@Data
@NoArgsConstructor
@AllArgsConstructor
public class ListNode {
private ListNode next;
private char value;
}
@Data
@NoArgsConstructor
@AllArgsConstructor
public class MyList {
private ListNode head;
private int size;
}
public ListNode reverse(ListNode head, ListNode lastGroupHead, int groupSize) {
if(head == null) {
return null;
}
ListNode currentNode = head;
ListNode next = head.getNext();
for(int idx=1; idx <= groupSize; idx++) {
next = currentNode.getNext();
if(idx == groupSize || next == null) {
// next 指向 lastGroupHead
currentNode.setNext(lastGroupHead);
if(next == null) {
return head;
}
}
currentNode = next;
}
// 返回当前分组的head
return reverse(next, head, groupSize);
}
输出字符数组中不包含字符b、也不包含连续的ac子串
代码：
输入：一个字符数组。
输出：使得输出字符数组中不包含字符b、也不包含连续的ac子串。
以下是3个case：
case1：
输入：mmaxcbd
输出：mmaxcd
case2：
输入：abbcdef
输出：def
case3：
输入：fexaaccd
输出：fexd
public String format(String rawStr) {
int length = rawStr.length();
StringBuilder sb = new StringBuilder();
for(int idx=0; idx<length; idx++) {
// 遍历字符串
char c = rawStr.charAt(idx);
// 如果遇到 b， 直接忽略
if(c == 'b'){
continue;
}else if(sb.length() == 0){
// 如果 StringBuilder 为空，直接插入
sb.append(c);
}else if(c == 'c'){
// 如果遇到 c，且 StringBuilder 中的最后一个字符为 a，则将a和c同时删除
Character pChar = sb.charAt(sb.length() - 1);
if(pChar == 'a') {
sb.deleteCharAt(sb.length() - 1);
} else {
sb.append(c);
}
} else {
sb.append(c);
}
}
return sb.toString();
}
