448. Find All Numbers Disappeared in an Array

Q:

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

A:

public class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        // keeps swaping untill we found or is marked at -1
        for(int i =0;i<nums.length;i++){
            int val = nums[i];
            if(val<0)
                continue;
            if(val != i+1){// 
                if( val == nums[val-1]){
                    nums[i] = -1;
                }else{
                    swap(nums,i, val-1);
                    i--;
                }
            }
        }
        List<Integer> res = new LinkedList<>();
        for(int i =0;i<nums.length;i++)
            if(nums[i]<0)
                res.add(i+1);
        return res;
    }
    private void swap(int[] nums,int i ,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
 

Errors：

392. Is Subsequence

Q:

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:
s = "abc", t = "ahbgdc"

Return true.

Example 2:
s = "axc", t = "ahbgdc"

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

A:

就是一个个地数，发现就行。

public class Solution {
    public boolean isSubsequence(String s, String t) {
        int k =0; // index for t
        for(int i =0;i<s.length();i++){
            char ch = s.charAt(i);
            while(k<t.length() && t.charAt(k) != ch){
                k++;
            }
            if( k >=t.length())
                return false;
            k++;  
        }
        return true;
    }
}
 

Follow up的情况，就是把 t 预先处理，  save the position of each character
为了更speed up ， 我们搜索的时候，把当前搜索到的位置，也保存下来。

public class Solution {
    public boolean isSubsequence(String s, String t) {
        //init :  record the location for each char
        List<List<Integer>> all = new ArrayList<>();
        for(char ch = 'a'; ch<= 'z'; ch++ ){
            List<Integer> list = new ArrayList<>();
            all.add(list);
        }
        for(int i =0;i<t.length(); i++){
            char ch = t.charAt(i);
            int index = ch -'a';
            all.get(index).add(i);
        }
        // now test the case for S_k
        int[] A = new int[26]; // all S_k starting from the first position
        int mostLeftIndex = -1;// before this position(inclusive), string is tested valid
        for(int i =0;i< s.length();i++){
            char ch = s.charAt(i);
            List<Integer> list = all.get(ch-'a');
            while( A[ch-'a'] < list.size() && list.get(A[ch-'a']) <= mostLeftIndex){
                A[ch-'a'] ++;
            }
            if(A[ch-'a']  == list.size() )
                return false;
            mostLeftIndex = list.get(A[ch-'a']);
            
        }
        return true;
        
    }
}
 

Errors：

Follow up 情况的时候，由于 mostLeftIndex定义的变化， 做比较的时候，忘了加上  <=

475. Heaters

Q:

Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

So, your input will be the positions of houses and heaters separately, and your expected output will be the minimum radius standard of heaters.

Note:

1. Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
2. Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
3. As long as a house is in the heaters' warm radius range, it can be warmed.
4. All the heaters follow your radius standard and the warm radius will the same.

Example 1:

Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use 

the radius 1 standard, then all the houses can be warmed.

Example 2:

Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. 

We need to use radius 1 standard, then all the houses can be warmed.

A:

对于每个house，找到他应该最近的heater

public class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int res= 0, i = 0 , n = heaters.length;
        for(int val : houses){// each house found its closest heater
            // if val is on left of i
            if(val <= heaters[i]){
                res = Math.max(res, heaters[i]  - val);
                continue;
            }
            // Now val > heaters[i]
            while(i+1<n && val > heaters[i+1])// move val in the middle of the closes heater
                i++;
            int rLeft = val - heaters[i];
            int rRight = i+1 < n ? heaters[i+1]-val : Integer.MAX_VALUE;
            res = Math.max(res, Math.min(rLeft, rRight));
        }
        return res;
    }
}

*******精简后的版本， 思路同上. ************ 

public class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int res= 0, i = 0 ;
        for(int val : houses){// each house found its closest heater
            while(i+1<heaters.length && val > heaters[i+1])//move val in the middle of the closes heater
                i++;
            int rLeft = Math.abs(val - heaters[i]);
            int rRight = i+1 < heaters.length ? Math.abs(heaters[i+1]-val) : Integer.MAX_VALUE;
            res = Math.max(res, Math.min(rLeft, rRight));
        }
        return res;
    }
}

Errors:1：  没有考虑，可能一下子跳过很多heater ,house 直接跑到遥远的最后面  的情况。 （因此才要用while 来update index
2：  艹        原来默认的两个数组已经排序好， 是不成立的。  自己其实也一直在找，是不是已经排序好了。

477. Total Hamming Distance

Q:

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:

Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Note:

1. Elements of the given array are in the range of 0 to 10^9
2. Length of the array will not exceed 10^4.

A:

首先实验brute Force算法，我是想或许通过调整# of ones可以通过，但是还是TLE了

public class Solution {
    public int totalHammingDistance(int[] nums) {
        int n = nums.length, res = 0;
        for(int i =0;i<n;i++){
            for(int j = i+1;j<n;j++){
                res+= nOnes(nums[i]^nums[j]);
            }
        }
        return res;
    }
    private int nOnes(int a){
        int res = 0;
        while(a!=0){
            res++;
            a = a&(a-1);
        }
        return res;
    }
}

--------因此，每一位开始比较，----------其实就是每一位的1的个数乘以0的个数--------

public class Solution {
    public int totalHammingDistance(int[] nums) {
        int n = nums.length, res = 0;
        for(int k =0;k<32;k++){
            int mask = 1<<k;
            int numOf1s = 0;
            for(int i =0;i<n;i++)
                if( (nums[i] & mask) !=0)
                    numOf1s ++;
            res += numOf1s * (n-numOf1s);
        }
        return res;
    }
}

Errors:

373. Find K Pairs with Smallest Sums

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.

Example 1:

Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3

Return: [1,2],[1,4],[1,6]

The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

Given nums1 = [1,1,2], nums2 = [1,2,3],  k = 2

Return: [1,1],[1,1]

The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

Given nums1 = [1,2], nums2 = [3],  k = 3 

Return: [1,3],[2,3]

All possible pairs are returned from the sequence:
[1,3],[2,3]

A:

自己看下面的解法有什么问题,啊哈哈

public class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> res = new LinkedList();
        int i = 0,j=0, m = nums1.length, n = nums2.length;
        k = Math.min(k,m*n);
        while(k-- >= 0){
            int[] tmp = {nums1[i],nums2[j]};
            res.add(tmp);
            if(i==m-1){
                j++;
            }else if(j==n-1){
                i++;
            }else{
                if(nums1[i+1]+nums2[j] < nums1[i]+nums2[j+1])
                    i++;
                else
                    j++;
            }
        }
        return res;
    }
}

-------Use priority heap----------

public class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> res = new LinkedList();
        int m = nums1.length, n = nums2.length;
        if(m==0 || n == 0 || k <=0)
            return res;
        int[] index = new int[m];// for nums1
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(m, (A, B) -> A[1] + A[2] - B[1] - B[2]);
        for(int i = 0;i<m;i++)  // put the initial values
            minHeap.offer(new int[]{i, nums1[i], nums2[0]});
        while( !minHeap.isEmpty() && k-- > 0){
            int[] top = minHeap.poll();
            res.add(new int[]{top[1], top[2]});
            int t = top[0]; // index of which element of nums1 is used.
            if(index[t] +1 < n)//if next move on nums2 is also valid,
                minHeap.add( new int[]{t, nums1[t], nums2[++index[t]]} );
        }
            return res;
        }
    }

Error:

没有考虑Example 3的情况，没有读完题意呀，😌

Java Lambda to write a comparator

clearly to understand how make a minHeap and maxHeap in the Compare method()

367. Valid Perfect Square

Q:

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16
Returns: True

Example 2:

Input: 14
Returns: False

A:

********** 在所有的可能的平方根里，进行二分查找**********

class Solution {
public:
    bool isPerfectSquare(int num) {
        if(num == 1)
            return true;
        int low = 2, up = num/2+1;
        while(low < up)
        {
            long mid = low + (up - low) /2;
            if(mid * mid == num)
                return true;
            if (mid * mid > num)
            {
                up = mid;
            }else{
                low = mid+1;
            }
        }
        return false;
    }
};

Mistakes:

if we declare:

int mid; 

mid * mid   would be an int,  but can overflow, thus need long.

315. Count of Smaller Numbers After Self

Q:

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

A:
*********首先意识到，这就是数组的插入排序啊。  n* log(n)  应该是足够快了
****嗯，就是找到需要插入的位置，再返回这个位置就可以了。********
******可是，反过来想，如果是数组的话，需要每次挪动啊。******？？？？

******sol： 不需要真的插入，只需要记录其后面有多少个就行。然后，记录其前面的。 不对，这样，还是需要记录进去，否则怎么查呢？ *******


Sol 2： 先排序，



Mistakes: