剑指Offer

4.1 哈希表(5)

2017-12-30  本文已影响3人  coderjiege

套路


注意点


目录


数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。

public boolean duplicate(int numbers[],int length,int [] duplication) {
    if (numbers == null || length == 0) {
        return false;
    }
    for (int i = 0; i < length; i++) {
        int val = numbers[i] % length;
        if (numbers[val] < length) {
            numbers[val] += length;
        } else {
            duplication[0] = val;
            return true;
        }
    }
    return false;
}

复杂链表的复制

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;
    RandomListNode(int label) {
        this.label = label;
    }
}
public RandomListNode Clone(RandomListNode pHead) {
    Map<RandomListNode, RandomListNode> map = new HashMap<>();
    // 创建复制链表的额外头结点,方便复制链表所有节点操作的统一处理
    RandomListNode cloneFront = new RandomListNode(0);
    RandomListNode p1 = pHead, p2 = cloneFront;
    while (p1 != null) {
        p2.next = new RandomListNode(p1.label);
        // 哈希表存放原节点和复制节点的双向键值对
        map.put(p2.next, p1);
        map.put(p1, p2.next);
        p2 = p2.next;
        p1 = p1.next;
    }
    p2 = cloneFront.next;
    while (p2 != null) {
        p2.random = map.get(map.get(p2).random);
        p2 = p2.next;
    }
    return cloneFront.next;
}

字符流中第一个不重复的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时,第一个只出现一次的字符是"l"。
输出描述:
如果当前字符流没有存在出现一次的字符,返回#字符。

// 核心代码:LinkedHashMap 是有序的 hashMap,可以找到出现一次的字符并且满足是第一个出现
private Map<Character, Integer> map = new LinkedHashMap<>();
public void Insert(char ch) {
    if (map.containsKey(ch)) {
        map.put(ch, 0);
    } else {
        map.put(ch, 1);
    }
}
public char FirstAppearingOnce() {
    for (Map.Entry<Character, Integer> en : map.entrySet()) {
        if (en.getValue() == 1) {
            return en.getKey();
        }
    }
    return '#';
}

数组中只出现一次的数字

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < array.length; i++) {
        int t = array[i];
        if (map.containsKey(t)) {
            map.put(t, 2);
        } else {
            map.put(t, 1);
        }
    }
    boolean flag = true;
    for (Map.Entry<Integer, Integer> en : map.entrySet()) {
        if (en.getValue() == 1) {
            if (flag) {
                num1[0] = en.getKey();
                flag = false;
            } else {
                num2[0] = en.getKey();
            }
        }
    }
}

第一个只出现一次的字符

在一个字符串(1<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置

public int FirstNotRepeatingChar(String str) {
    if (str == null || str.length() == 0) {
        return -1;
    }
    // 能放得下所有大小写字母即可
    int[] arr = new int['z' + 1];
    for (int i = 0; i < str.length(); i++) {
        arr[str.charAt(i)]++;
    }
    // 存放所有只出现一次的字母在字符串中的索引
    ArrayList<Integer> res = new ArrayList<>();
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == 1) {
            res.add(str.indexOf(i));
        }
    }
    int index = 9999;
    for (int i = 0; i < res.size(); i++) {
        if (res.get(i) < index) {
            index = res.get(i);
        }
    }
    return res.size() == 0 ? 0 : index;
}

上一篇下一篇

猜你喜欢

热点阅读