321. Create Maximum Number My Submissions Question

Q:

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]

A:
就是每个寻找最大的（如果相同，则看下一位-----为了省事儿，我们先用递归的方式）

public class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] res = new int[k];
        int i1=0, i2=0;// valid position
        for(int i =0;i<k;i++){
            // k - i is how many we need to find,  (num2.length-i2) is how many others can provide
            int maxIndex1 = getMaxIndex(nums1,i1, k - i - (nums2.length - i2) );
            int maxIndex2 = getMaxIndex(nums2,i2, k - i - (nums1.length - i1)  );
            if(maxIndex1<0){
                res[i] = nums2[maxIndex2];
                i2 = maxIndex2+1;
                continue;
            }
            if(maxIndex2<0){
                res[i] = nums1[maxIndex1] ;
                i1 = maxIndex1+1;
                continue;
            }
            int max1 = nums1[maxIndex1], max2 = nums2[maxIndex2];
            if( max1 > max2){
                res[i] = max1 ;
                i1 = maxIndex1+1;
            }else if(max1 < max2){
                res[i] = max2;
                i2 = maxIndex2+1;
            }else{ // max1 == max2
                res[i] = max1;
                // try to move the maxIndex1 by 1
                int[] res1 = maxNumber(Arrays.copyOfRange(nums1, maxIndex1+1,nums1.length ),
                        Arrays.copyOfRange(nums2, i2, nums2.length ),
                        k-i-1);
                // try the case that move the maxIndex2 forward
                int[] res2 = maxNumber(Arrays.copyOfRange(nums1, i1,nums1.length ),
                        Arrays.copyOfRange(nums2, maxIndex2+1, nums2.length ),
                        k-i-1);
                if(isFirstArrayBigger(res1,res2)){
                    for(int t  = 0; t<res1.length; t++){ // might use the arrayCopyOfRange()
                        res[i+1+t] = res1[t];
                    }
                }else{
                    for(int t  = 0; t<res2.length; t++){ // might use the arrayCopyOfRange()
                        res[i+1+t] = res2[t];
                    }
                }
                break;
            }
        }
        return res;
    }
    private int getMaxIndex(int[] A, int start,int leastNumberOfElementWeNeed){
        if(A.length==0)
            return -1;
        int maxIndex = -1, maxValue = Integer.MIN_VALUE;
        for(int i =start; i<= Math.min(A.length-1, A.length - leastNumberOfElementWeNeed); i++ ){
            if(A[i]>maxValue){
                maxIndex = i;
                maxValue = A[i];
            }
        }
        return maxIndex;
    }

    private boolean isFirstArrayBigger(int[] A,   int B[]){// A and B are the same size
        for(int i =0;i<A.length; i++){
            if(A[i]>B[i])
                return true;
            if(A[i]<B[i])
                return false;
        }
        return true;
    }
}

上面的超时了，  问题出在，如果相同的话，我们会实验两遍。因此不好看。
有没有更好的方法呢？？？？？

再想想~~~~~~~~~~~~~~~~~
嗯，利用这样一个特性：
0~~~~9 是确定的。因此我们可以把每个地址都记录下来。这样我们就不用一遍遍copy数组了。




Mistakes:
1： 编码的时候，忘记了，如果相同，则看下

445. Add Two Numbers II

Q:

You are given two linked lists representing two non-negative numbers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

A:

把长的先取下后面相同长度的那一段， 对其后，用recursive加起来计算。
同样的思路，处理进位

public class Solution {
    private int carry = 0;
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // l1 , l2 != null
        int len1 = getLen(l1), len2= getLen(l2);
        if(len1<len2)
            return addTwoNumbers(l2,l1);
        ListNode header = new ListNode(0);
        header.next = l1;
        ListNode pre = header;
        carry = 0;
        for(int i =0;i<len1-len2;i++)
            pre = pre.next;
        
        ListNode res = helper(pre.next, l2);
        // recursive to add carry to the front
        add1Recursive(header.next, len1-len2);
        if(carry == 1){
            ListNode newHead = new ListNode(1);
            newHead.next = header.next;
            header.next = newHead;
        }
        return header.next;
    }
    private void add1Recursive(ListNode cur, int k){// k nodes after header
        if(carry == 0 || k == 0)
            return ;
        add1Recursive(cur.next, k-1);
        // add carry , regardless its value
        int sum = cur.val + carry;
        carry = sum/10;
        cur.val = sum %10;
    }
    private ListNode helper(ListNode l1, ListNode l2){
        // l1 and l2 are the same length
        if(l1.next == null){
            int sum = l1.val + l2.val + carry;
            carry = sum/10;
            l1.val = sum %10;
        }else{
            l1.next = helper(l1.next, l2.next);
            int sum = l1.val + l2.val + carry;
            carry = sum/10;
            l1.val = sum %10;
        }
        return l1;
    }

    private int getLen(ListNode head){
        int len = 0;
        while(head != null){
            head = head.next;
            len++;
        }
        return len;
    }
}
 

Errors:

371. Sum of Two Integers

Q:

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

A:

就是按位亦或，再把进位右移，继续运算

public class Solution {
    public int getSum(int a, int b) {
        if(b==0)
            return a;
        int carry = a & b;
        a = a^b;
        return getSum(a, carry<<1);
    }
}

Errors:

384. Shuffle an Array

Q:

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

A:

***********首先要有个nums的备份， 然后每次返回的时候，要一个shuffle的备份 *******

public class Solution {
    private static int[] A;
    private int[] B;
    public Solution(int[] nums) {
        A = nums;
        B = new int[A.length];
        for(int i = 0;i<A.length;i++)
            B[i] = A[i];
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        for(int i = 0;i<A.length;i++)
            B[i] = A[i];
        return B;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        for(int i =B.length-1;i>0;i--){
            int j = (int)(Math.random()*(i+1));
            int tmp = B[i];
            B[i] = B[j];
            B[j] = tmp;
        }
        return B;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */ 

Errors:

380. Insert Delete GetRandom O(1)

Q:

Design a data structure that supports all following operations in average O(1) time.

1. insert(val): Inserts an item val to the set if not already present.
2. remove(val): Removes an item val from the set if present.
3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 1 is the only number in the set, getRandom always return 1.

A:

思路是：   

1：   首先，我们肯定要用Set， 

2：  若想 要 处理getRandom， 需要找到一个数据结构，满足 O(1) 来做getRandom .-----必须要用数组。 （这里我们取巧，用了ArrayList. 如果真用数组的话，就得自己处理resize的问题）  

3:   那么问题来了。   如何处理删掉的呢/？？？------> 通过检查Set来帮助

       如何处理新增的呢？ ----------》  直接加到末尾。

  那么，删除的空间如何利用起来呢？    -------->  Sol 1:   用list保持可以利用的地址。   Sol 2:  每次删掉tail， 把删掉的值，放到该位置。  （这里很容易犯个错，😀，想想是什么？）

            

public class RandomizedSet {
    Set<Integer> set ;
    ArrayList<Integer> posArray ;// use Array to save the values, whenever we find a non-esisting value, we swap with the tail
    /** Initialize your data structure here. */
    public RandomizedSet() {
        set = new HashSet<>();
        posArray = new ArrayList();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(set.contains(val))
            return false;
        set.add(val);
        posArray.add(val); // append at the tail 
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(set.contains(val)){
            set.remove(val);
            return true;
        }
        return false;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        int index = (int) (Math.random()*posArray.size());
        if( set.contains(posArray.get(index)) ){
            return posArray.get(index);
        }else{ // release this position by swap with the tail
            int tailValue = posArray.remove(posArray.size()-1);
            if(index < posArray.size())// index might already be the tail
                posArray.set(index, tailValue);
            return getRandom();
        }
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

Errors:

由于思路的转换，  临时决定要交换tail， （那么，如果index就是tail呢？？？？）  就出现问题了，哈哈

449. Serialize and Deserialize BST ----M ~~~~~~!!!!!

Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

 

Example 1:

Input: root = [2,1,3]
Output: [2,1,3]

Example 2:

Input: root = []
Output: []

 

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• 0 <= Node.val <= 104
• The input tree is guaranteed to be a binary search tree.

A:

就是类似于递归的写法。然而不是最优的。 没有利用BST这个性质。

我还是多加了 ",#" 来代表  nullptr。 然而其实并不需要

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res = helper(root);
        // remove the last ',' and '#'
        int end = res.size()-1;
        while(end>=0 && not isdigit(res[end])){
            end--;
        }
        return res.substr(0,end+1);
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<string> tokens;
        // stringstream class check1 
        stringstream check1(data); 
        string tmp; 
        // Tokenizing w.r.t.  ',' 
        while(getline(check1, tmp, ',')) { 
            tokens.push_back(tmp); 
        }
        reverse(tokens.begin(), tokens.end());
        return helper2(tokens);
    }
private:
    string helper(TreeNode* root){
        if(root == nullptr)
            return "#";
        string res = to_string(root->val);
        string left = helper(root->left);
        string right = helper(root->right);
        res+= ","+left + ","+right;
        return res;
    }
    TreeNode* helper2(vector<string>& tokens){
        if(tokens.empty()){
            return nullptr;
        }
        string str = tokens.back();
        tokens.pop_back();
        if(str=="#"){
            return nullptr;
        }
        TreeNode* root = new TreeNode(stoi(str));
        root->left = helper2(tokens);
        root->right = helper2(tokens);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec* ser = new Codec();
// Codec* deser = new Codec();
// string tree = ser->serialize(root);
// TreeNode* ans = deser->deserialize(tree);
// return ans;

上面的不是最优的，因此，我们这里改了一下， 利用了  BST

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(not root){
            return "";
        }
        string res = to_string(root->val);
        if(root->left){
            res+= " "+serialize(root->left);
        }
        if(root->right){
            res += " "+serialize(root->right);
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<int> tokens;
        // stringstream class check1 
        stringstream check1(data); 
        string tmp; 
        // Tokenizing w.r.t.  ' ' 
        while(getline(check1, tmp, ' ')) { 
            tokens.push_back(stoi(tmp)); 
        }
        reverse(tokens.begin(), tokens.end());
        return helper(tokens);
    }
private:
    TreeNode* helper(vector<int>& tokens){
        if(tokens.size() == 0){
            return nullptr;
        }
        TreeNode* root = new TreeNode(tokens.back());
        tokens.pop_back();
        vector<int> sLeft;
        while(not tokens.empty() && tokens.back() < root->val){
            sLeft.push_back(tokens.back());
            tokens.pop_back();
        }
        reverse(sLeft.begin(), sLeft.end()); // need to make to reverse again
        root->left = helper(sLeft);
        root->right = helper(tokens);
        return root;
    }
};

Errors:

忘了这一句：     reverse(sLeft.begin(), sLeft.end()); // need to make to reverse again

How to make the encoded string as compact as possible

This question is similar to the Google interview question discussed last week.

To serialize a binary tree means to

• Encode tree structure.

• Encode node values.

• Choose delimiters to separate the values in the encoded string.

Hence there are three axes of optimisation here.

---

Approach 1: Postorder traversal to optimise space for the tree structure.

Intuition

Let's use here the fact that BST could be constructed from preorder or postorder traversal only. Please check this article for the detailed discussion. In brief, it's a consequence of two facts:

• Binary tree could be constructed from preorder/postorder and inorder traversal.

• Inorder traversal of BST is an array sorted in the ascending order: inorder = sorted(preorder).

That means that BST structure is already encoded in the preorder or postorder traversal and hence they are both suitable for the compact serialization.

Serialization could be easily implemented with both strategies, but for optimal deserialization better to choose the postorder traversal because member/global/static variables are not allowed here.

Implementation

Approach 2: Convert int to 4-bytes string to optimize space for node values.

Intuition

Approach 1 works fine with the small node values but starts to consume more and more space in the case of large ones.

For example, the tree [2,null,3,null,4] is encoded as a string "4 3 2" which uses 5 bytes to store the values and delimiters, 1 byte per value or delimiter. So far everything is fine.

Let's consider now the tree [12345,null,12346,null,12347] which is encoded as "12347 12346 12345" and consumes 17 bytes to store 3 integers and 2 delimiters, 15 bytes for node values only. At the same time it's known that 4 bytes is enough to store an int value, i.e. 12 bytes should be enough for 3 integers. 15 > 12 and hence the storage of values could be optimised.

How to do it? Convert each integer into 4-bytes string.

Implementation

441. Arranging Coins

Q:

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2:

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

A:

求根公式呀

public class Solution {
    public int arrangeCoins(int n) {
        return  (int)( Math.sqrt(2.0*n+0.25) - 0.5);
    }
} 

Errors:

412. Fizz Buzz

Q:

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:

n = 15,

Return:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

A:

public class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> res = new LinkedList<>();
        for(int i =1;i<=n;i++){
            if(i%3 !=0 && i%5 != 0){
                res.add(""+i);
            }else{
                String ss = "";
                if(i%3==0)
                    ss+="Fizz";
                
                if(i%5==0)
                    ss+="Buzz";
                res.add(ss);
            }
        }
        return res;
    }
}
 

345. Reverse Vowels of a String

Q:

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = "hello", return "holle".

Example 2:
Given s = "leetcode", return "leotcede".

Note:
The vowels does not include the letter "y".

A:

就是两个指针互相交换

public class Solution {
    public String reverseVowels(String s) {
        StringBuffer buf = new StringBuffer(s);
        int i =0, j = buf.length()-1;
        Set<Character> set = new HashSet<>();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');
        set.add('A');
        set.add('E');
        set.add('I');
        set.add('O');
        set.add('U');
        while(i<j){
            while(i<j && set.contains(buf.charAt(i))==false)
                i++;
            while(i<j && set.contains(buf.charAt(j))==false)
                j--;
            if(i<j){
                char ch = buf.charAt(i);
                buf.setCharAt(i,buf.charAt(j));
                buf.setCharAt(j,ch);
                i++;
                j--;
            }
        }
        return buf.toString();
    }
} 

Errors:

忘了考虑大写字母的情况

410. Split Array Largest Sum ---H !~~~~~~

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

 

Example 1:

Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Example 2:

Input: nums = [1,2,3,4,5], m = 2
Output: 9

Example 3:

Input: nums = [1,4,4], m = 3
Output: 4

 

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 106
• 1 <= m <= min(50, nums.length)

A:

首先，试图计算平均值，再每次尽量均分。

 但这样， 会有一种情况

average = 100,   m = 

1,2,4,5,6 99,99, 10, 9 ,8 , 7, .....    这样的情况，还是需要把两个99 分开。 那样左

这样结束后， 需要 左右挪动 每个位置，  这样就会互相影响。

因此，这个应该是行不通的。

-------》  考虑分而治之的思想 , 再考虑， m的情况，可以分为 a+b = m的两种情况，因此我们试着考虑DP 算法

首先我考虑的是2维的DP，就是对于index (a,b) inclusive, 可以分成的最小的情况。

但是由于 m == 14,000，因此可能空间太大了。

因此考虑1维的， 由此变成，每次取下最前面的一个（或者几个），然后再分后面的till the end of nums array。

由此，数组就变成了 n * m的了。

这个题目比普通DP 困难之处是：

每次m 增加一个，  那么之前的所有的index 从  a 到  b, 都需要重新update. 而不是规定于某一个index

状态转移方程不好写。

那么我用 HashMap 来存储。

那么，我们对于每一个从 [ a, b]  ---> minSum with  k subarray.

再想一下，其实 a 永远都是0 的，

所以，我们就可以有了DP 的方式。

每行 从k = 1...m   然后每个DP[k][end] 的值是从 [0, end] 被分为k 个subarray的minSum

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Solution { public: int splitArray(vector<int>& nums, int m) { int n = nums.size(); vector<int> total = nums; // get the total sum for m == 1 (per each ending index) for(int i= 1; i<n;i++){ total[i] += total[i-1]; } vector<int> DP = total; // DP[i] stands for [0,i] the minSum of k_split subarray for(int k = 2; k<=m; k++){ vector<int> newDP(n, INT_MAX); for(int cur = k-1; cur < n; cur++){ for(int preLast = k-2; preLast<cur; preLast++){ int minSplitSum = DP[preLast]; int curLastSum = total[cur]-total[preLast]; newDP[cur] = min(newDP[cur], max( minSplitSum, curLastSum)); if(curLastSum<=minSplitSum){ // no need to shrink break; } } } DP = newDP; } return DP[n-1]; } };

这个题的改善是可以在line 15的for loop, 写成 binary search.  

Error:

Line 18,  一开始糊涂， 写成了  min(  ,  min ()  )  哎，

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：  艹        原来默认的两个数组已经排序好， 是不成立的。  自己其实也一直在找，是不是已经排序好了。