374. Guess Number Higher or Lower

Q:

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!

Example:

n = 10, I pick 6.

Return 6.

A:

没什么想的，就是取中间值，然后对比

/* The guess API is defined in the parent class GuessGame.
   @param num, your guess
   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
      int guess(int num); */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        return helper(1,n);
    }
    private int helper(int a, int b){
        if(a==b)
            return a;
        int mid = a + (b-a)/2;
        int res = guess(mid);
        if(res == 0)
            return mid;
        if(res == 1)
            return helper(mid+1,b);
        // res == 1, mine is bigger
        return helper(a,mid-1);
    }
}
 

Learned:

1：  guess(int num) return -1, mean my target number is lower than your given num这个是题意理解反了。
2：  求mid的时候，  以前还记得，刚刚忘了（主要是LC一直没考虑这种情况）， 要写成
int mid = a + (b-a)/2;

372. Super Pow

Q:

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

a = 2
b = [3]

Result: 8

Example2:

a = 2
b = [1,0]

Result: 1024

A:

就是记录下每一位的模，然后逐步相乘即可

public class Solution {
    public int superPow(int a, int[] b) {
        if(b.length==0)
            return 1;
        int n = b.length;
        int [] C = new int[ n ]; // 10^i of a/1337
        Arrays.fill(C,1);
        C[n-1] = a % 1337;
        for(int i =n-2;i>=0;i--){
            // for each position , loop 10 times
            for(int j = 0;j<10;j++){
                C[i] = (C[i] * C[i+1]) % 1337;
            }
        }
        int res = 1;
        for(int i =0;i<n;i++){
            for(int j = 0;j<b[i];j++){
                res = (res*C[i] ) % 1337;
            }
        }
        return res;
    }
}
 

Errors :

因为b[0]是最高位，  因此C的最高位也应该是C[0]   ---- 自己一开始写习惯了，把C【0】写成最低位了

352. Data Stream as Disjoint Intervals

Q:

Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:

[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

Follow up:
What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size?

A:-----也可以用TreeMap 

思路很直接：  就是用Set记录每个插入的。如果有重复的，就直接忽略
用List记录结果。
用Map记录   每个上下界 对应的interval，没加入一个新的数字，则 检查和修改map和list

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class SummaryRanges {
    List<Interval> list ;
    Map<Integer, Interval> map;   // record start and end only 
    Set<Integer> set; // all found numbers
    /** Initialize your data structure here. */
    public SummaryRanges() {
        list = new LinkedList<>();
        map = new HashMap<>();
        set = new HashSet<>();
    }
    
    public void addNum(int val) {
        if(set.contains(val))
            return;
        set.add(val);
        // check val+1
        if(map.containsKey(val+1)){
            Interval after = map.get(val+1);
            after.start = val;
            map.put(val, after);
            if(after.end != val+1)
                map.remove(val+1);
            if(map.containsKey(val-1)){
                Interval before = map.get(val-1);
                list.remove(before);
                after.start = before.start;
                map.put(after.start, after);
                if(before.start != val -1 )
                    map.remove(val-1);
            }
            return;
        }
        // check val -1 
        if(map.containsKey(val-1)){  // cannot contains upper
            Interval before = map.get(val-1);
            before.end = val;
            if(before.start != val -1)
                map.remove(val-1);
            map.put(val,before);
            return;
        }
        // add a new interval, linearly
        Interval tmp = new Interval(val, val);
        for(int i = 0;i< list.size();i++){
            if(list.get(i).start > val){
                map.put(val,tmp);
                list.add(i,tmp);
                return;
            }
        }
        map.put(val, tmp);
        list.add(tmp);
    }
    
    public List<Interval> getIntervals() {
        return list;
    }
}

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(val);
 * List<Interval> param_2 = obj.getIntervals();
 */
 

Errors：

记得remove from Map 的时候，需要小心start == end的情况

451. Sort Characters By Frequency

Q:

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

A:

就是放到PriorityQueue里再取出来。

public class Solution {
    public String frequencySort(String s) {
        if(s==null || s.length()==0)
            return "";
        // put to HashMap
        Map<Character,Integer> map = new HashMap();
        for(char ch : s.toCharArray()){
            map.put(ch, (map.containsKey(ch))? map.get(ch)+1: 1);
        }
        PriorityQueue<Obj> maxQueue = new PriorityQueue<>(map.size(), (A,B)->B.count - A.count);
        //from HashMap, put to priorityQueue
        for(char ch : map.keySet()){
            Obj obj = new Obj(ch, map.get(ch));
            maxQueue.add(obj);
        }
        //build result from PriorityQueue
        StringBuffer buf = new StringBuffer();
        while( ! maxQueue.isEmpty()) {
            Obj node = maxQueue.poll();
            for(int i =0;i<node.count;i++)
                buf.append(node.ch);
        }
        return buf.toString();
    }
    class Obj{
        char ch ='a';
        int count = 0;
        public Obj(char c, int cc){
            ch = c;
            count = cc;
        }
    }
}

Errors：

由于PriorityQueue需要的初始capaity 不能小于1。
因此，我们需要开始检查s是否为0.

434. Number of Segments in a String

Q:

Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.

Please note that the string does not contain any non-printable characters.

Example:

Input: "Hello, my name is John"
Output: 5

A:

public class Solution {
    public int countSegments(String s) {
        // if s contains only emptySpace
        s = s.trim();
        if(s.length()==0)
            return 0;
        int res =0, pre =-1;
        while(true){
            int i = s.indexOf(' ',pre+1);
            if(i<0)
                break;
            if(i==pre+1){// adjacent space
                pre++;
            }else{
                res++;
                pre = i;
            }
        }
        return res+1;
    }
}

Errors：

要记得先trim()

Move Zeroes

Q;

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

A:
********记录最新的非0 的位置 **********  先走一遍，再在后半部分置零************

public class Solution {
    public void moveZeroes(int[] nums) {
        int nonZero = 0;
        for(int i=0 ;i<nums.length;i++)
            if(nums[i] != 0)
                nums[nonZero++] = nums[i];
        
        for(;nonZero<nums.length;nonZero++)
            nums[nonZero] = 0;        
    }
} 

******** 只走一遍， 记录第一个0 的位置,每次分情况展开************

public class Solution {
    public void moveZeroes(int[] nums) {
        int i0 = -1;
        for(int i =0; i<nums.length; i++){
            if(nums[i] == 0){
                if(i0<0)
                    i0 = i;
            }else{
                if(i0 >=0){
                    nums[i0] = nums[i];
                    nums[i] = 0;
                    i0++;//update i0 to the next position
                    while(i0<=i && nums[i0]!=0)
                        i0++;
                }
            }
        }
    }
}

Note:

405. Convert a Number to Hexadecimal

Q:

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

1. All letters in hexadecimal (a-f) must be in lowercase.
2. The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character '0'; otherwise, the first character in the hexadecimal string will not be the zero character.
3. The given number is guaranteed to fit within the range of a 32-bit signed integer.
4. You must not use any method provided by the library which converts/formats the number to hex directly.

Example 1:

Input:
26

Output:
"1a"

Example 2:

Input:
-1

Output:
"ffffffff"

A:

就是递归右移 >>>

public class Solution {
    public String toHex(int num) {
        int cur = num & 15;
        num = num>>>4;
        return (   (num==0)?"":toHex(num)   ) + (   (cur<=9)?(char)(cur+'0'):(char)(cur-10 + 'a')   );
    }
} 

Errors：

由于3目运算符的优先级比较低，因此要尽量把它们括号起来用。