LeetCode(114) -- 260, 264,

P260. Single Number III (Medium)

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

My Solution

class Solution {
    public int[] singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                set.remove(num);
            } else {
                set.add(num);
            }
        }
        int[] ans = new int[2];
        int i = 0;
        for (Integer integer : set) {
            ans[i] = integer;
            i++;
        }
        return ans; 
    }
}

43%

Solution

肯定应该用XOR，但是有两个数出现一次，所以仅用XOR是解决不了问题的。答案有一个重要的知识点。x & (-x) 可以得到最右边的一个1。刚才的两个数x XOR y 的结果，就是两个数不一样的地方。把这个diff取最右边一个1，那么在这一位上我们可以确定，x和y一定是不一样的。只有当这一位是1的时候，我们再做XOR累加，则必定可以过滤掉x, y中的其中一个。

class Solution {
    public int[] singleNumber(int[] nums) {
        int bitmask = 0;
        for (int num: nums) {
            bitmask ^= num;
        }
        int diff = bitmask & (-bitmask);
        int x = 0;
        for (int num : nums) {
            if ((num & diff) != 0) {
                x ^= num;
            }
        }
        return new int[]{x, bitmask ^ x};
    }
}

99%

P264. Ugly Number II (Medium)

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

My Solution

public class P264_UglyNumberII {
    public int nthUglyNumber(int n) {
        int candidate = 1;
        while (n > 0) {
            int test = candidate;
            while (test % 2 == 0) {
                test /= 2;
            }
            while (test % 3 == 0) {
                test /= 3;
            }
            while (test % 5 == 0) {
                test /= 5;
            }
            if (test == 1) {
                n--;
                if (n == 0) {
                    return candidate;
                }
            }
            candidate++;
        }
        return candidate;
    }
}

超时了。

Solution

方法一：Heap (PQ)

class Ugly {
    public int[] nums = new int[1690];
    Ugly() {
        HashSet<Long> seen = new HashSet();
        PriorityQueue<Long> heap = new PriorityQueue<Long>();
        seen.add(1L);
        heap.add(1L);

        long currUgly, newUgly;
        int[] primes = new int[]{2,3,5};
        for (int i = 0; i < 1690; i++) {
            currUgly = heap.poll();
            nums[i] = (int) currUgly;
            for (int j : primes) {
                newUgly = currUgly * j;
                if (!seen.contains(newUgly)) {
                    seen.add(newUgly);
                    heap.add(newUgly);
                }
            }
        }
    }
}

class Solution {
    public static Ugly u = new Ugly();
    public int nthUglyNumber(int n) {
        return u.nums[n - 1];
    }
}

方法二：DP

用三个指针分别记录乘以这三个数的结果，然后一步一步移动这三个指针，谁小就先加谁。

class Solution {
    static class Ugly {
        public int[] nums = new int[1690];
        Ugly() {
            nums[0] = 1;
            int ugly, i2 = 0, i3 = 0, i5 = 0;
            for (int i = 1; i < 1690; i++) {
                ugly = Math.min(Math.min(nums[i2] * 2, nums[i3] * 3), nums[i5] * 5);
                nums[i] = ugly;
                if (ugly == nums[i2] * 2) {
                    i2++;
                }
                if (ugly == nums[i3] * 3) {
                    i3++;
                }
                if (ugly == nums[i5] * 5) {
                    i5++;
                }
            }
        }
    }
    
    public static Ugly u = new Ugly();
    public int nthUglyNumber(int n) {
        return u.nums[n - 1];
    }
}

100%

P274. H-Index (Medium)

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

My Solution

class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        Arrays.sort(citations);
        int n = citations.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (citations[mid] >= n - mid) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return citations[l] >= n - l ? n - l : 0;
    }
}

100% 跟下一道题几乎一样，抄了那个答案。