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 (Medium)

Q:

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

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

 

Example 1:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

Example 2:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]

Example 3:

Input: l1 = [0], l2 = [0]
Output: [0]

 

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

 

Follow up: Could you solve it without reversing the input lists?

A:

用vector保存，方便取最后一位

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode() : val(0), next(nullptr) {}

* ListNode(int x) : val(x), next(nullptr) {}

* ListNode(int x, ListNode *next) : val(x), next(next) {}

* };

*/

class Solution {

public:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

vector<int> V1, V2;

while (l1) {

V1.push_back(l1->val);

l1 = l1->next;

}

while (l2) {

V2.push_back(l2->val);

l2 = l2->next;

}

ListNode header;

int carry = 0;

while (!(V1.empty() && V2.empty()) || carry) {

int a = 0, b = 0;

if (!V1.empty()) {

a = V1.back();

V1.pop_back();

}

if (!V2.empty()) {

b = V2.back();

V2.pop_back();

}

int sum = a + b + carry;

ListNode* tmp = new ListNode(sum % 10, header.next);

header.next = tmp;

carry = sum / 10;

}

return header.next;

}

};

Errors:

1: ListNode* tmp = new ListNode(sum % 10, header.next);

new的结果必须是 指针

2:   need also check       carry != 0

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 ()  )  哎，