All posts by shiji

Leetcode

884. Uncommon Words from Two Sentences

We are given two sentences A and B.  (A sentence is a string of space separated words.  Each word consists only of lowercase letters.)

A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.

Return a list of all uncommon words.

You may return the list in any order.

 

Example 1:

Input: A = "this apple is sweet", B = "this apple is sour"
Output: ["sweet","sour"]

Example 2:

Input: A = "apple apple", B = "banana"
Output: ["banana"]

 

Note:

  1. 0 <= A.length <= 200
  2. 0 <= B.length <= 200
  3. A and B both contain only spaces and lowercase letters.
Runtime: 8 ms
Memory Usage: 14.9 MB
class Solution {

    /**
     * @param String $A
     * @param String $B
     * @return String[]
     */
    function uncommonFromSentences($A, $B) {
        $x = []; $y = [];
        foreach(explode(' ',$A) as $aa) {
            $this->add($x, $aa);
        }
        foreach(explode(' ',$B) as $bb) {
            $this->add($y, $bb);
        }
        $this->rmCommon($x, $y);
        $x = array_keys($x);
        $y = array_keys($y);
        return array_merge(array_diff($x,$y), array_diff($y, $x));
    }
    
    function add(&$arr, $v){
        if(isset($arr[$v])){
            $arr[$v] ++;
        } else {
            $arr[$v] = 1;
        }
    }
                
    function rmCommon(&$a,&$b){
        foreach($a as $k => $v){
            if ($v > 1){
                unset ($a[$k]);
                unset ($b[$k]);
            }
        }
        foreach($b as $k => $v){
            if ($v > 1){
                unset ($b[$k]);
                unset ($a[$k]);
            }
        }
    }
}

 

 

Leetcode

994. Rotting Oranges

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:

Input: [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.

24 ms 38.6 MB

class Solution {
    public int orangesRotting(int[][] grid) {
        if(this.nothing(grid)){
            return 0;
        }
        if(this.neverR(grid)){
            return -1;
        }
        
        int count = 0;
        while(!this.isAllR(grid)){
            grid = this.infect(grid);

            count ++;
            if(count > grid.length * grid[0].length){
                return -1;
            }
        }
        return count;
    }
    
    public int[][] infect(int[][] grid){
        int[][] next = new int[grid.length][grid[0].length];
        for(int x  = 0; x < grid.length; x ++){
            for(int y = 0; y < grid[0].length; y++){
                next[x][y] = grid[x][y];
            }
        }
        for(int x  = 0; x < grid.length; x ++){
            for(int y = 0; y < grid[0].length; y++){
                if(grid[x][y] == 2){
                    if(x>0 && next[x-1][y] > 0){
                        next[x-1][y] = 2;
                    }
                    if(y>0 && next[x][y-1] > 0){
                        next[x][y-1] = 2;
                    }
                    if(x< grid.length-1 && next[x+1][y] > 0){
                        next[x+1][y] = 2;
                    }
                    if(y < grid[0].length - 1 && next[x][y+1] > 0){
                        next[x][y+1] = 2;
                    }
                }
            }
        }
        return next;
    }
    
    public boolean isAllR(int[][] grid){
        boolean allR = true;
        for (int[] col : grid){
            for (int c : col){
                if(c == 1){
                    allR = false;
                }
            }
        }
        return allR;
    }
    
    public boolean neverR(int[][] grid){
        boolean allFresh = true;
        for(int x  = 0; x < grid.length; x ++){
            for(int y = 0; y < grid[0].length; y++){

                if(grid[x][y] == 2){
                    allFresh = false;
                }
                
                if(grid[x][y] == 1){
                    
                    boolean alone = true;
                    if(x>0 && grid[x-1][y] != 0){
                        alone = false;
                    }
                    if(y>0 && grid[x][y-1] != 0){
                        alone = false;
                    }
                    if(x< grid.length-1 && grid[x+1][y] != 0){
                        alone = false;
                    }
                    if(y < grid[0].length - 1 && grid[x][y+1] != 0){
                        alone = false;
                    }
                    System.out.println(alone);
                    if(alone){
                        return true;
                    }
                }
            }
        }
        return allFresh;
    }
    
    
    public boolean nothing(int[][] grid){
        boolean nothing = true;
        for(int x  = 0; x < grid.length; x ++){
            for(int y = 0; y < grid[0].length; y++){

                if(grid[x][y] > 0){
                    nothing = false;
                }

            }
        }
        return nothing;
    }
}

 

Leetcode

996. Number of Squareful Arrays

Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful. Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].

Example 1:

Output: 2
Explanation: 
[1,8,17] and [17,8,1] are the valid permutations.

Example 2:

Input: [2,2,2]
Output: 1

Note:

1 <= A.length <= 12
0 <= A[i] <= 1e9

Solved this with PHP.

  1. Go through the input and construct array ‘peers’
    1. peers holds an array of pointers pointing to all possible ‘partners’ in the input.
    2. For example, [1 => [8=>ref(8)], 8 => [1=>ref(1), 17=>ref(17)], 17 => [8=>ref(8)]]
  2. Meanwhile, another array stat collect all numbers and its occurrence.
  3. Then peers is recursive. so it’s like a tree, with infinite depth.
  4. Starting from the root of peers, if found any number in ‘stat’, update (-1) stat, and move on to peers’ children
    1. if cannot find any match at some points, break;
    2. since stat is finite, the recursive func will run forever
  5. Calculate the sum.

Works well with even larger input length.

16ms runtime w/ 14.7M RAM

Class Solution {

    /**
     * @param Integer[] $ls
     * @return Integer
     */
    function numSquarefulPerms($ls) {
        
        if(count($ls) <= 1){
            return 0;
        }
        
        $peers = [];
        $stat = [];
        
        for($i = 0; $i < count($ls); $i++){
            // Insert/Update stat
            if(!isset($stat[$ls[$i]])){
                $stat[$ls[$i]] = 1;
            } else {
                $stat[$ls[$i]] ++;
            }
            
            for($j = $i + 1; $j < count($ls); $j++){

                $value_i = $ls[$i];
                $value_j = $ls[$j];
                
                if(!isset($peers[$value_i])){
                    $peers[$value_i] = [];
                }
                if(!isset($peers[$value_j])){
                    $peers[$value_j] = [];
                }
                if($this -> isPerfectSquare($ls[$i] + $ls[$j])){
                    $peers[$value_i][$value_j] = &$peers[$value_j];
                    if($ls[$j] !== $ls[$i]){
                        $peers[$value_j][$value_i] = &$peers[$value_i];
                    }
                }
            }
        }
        // If any number has no partner
        foreach($peers as $p){
            if($p === []){
                return 0;
            }
        }
        return $this->traversal($stat, $peers, count($ls));
    }
    
    // Check if number is perfect square w/ small optimization
    function isPerfectSquare($num){
        $last_digit = $num % 10;
        if($last_digit == 2 ||
            $last_digit == 3 ||
            $last_digit == 7 ||
            $last_digit == 8 
          ) 
            return false;
        
        $sqrt = sqrt($num);
        return $sqrt == floor($sqrt);
    }
    
    function traversal($nums, &$tree, $max){
        $count = 0;
        var_dump($nums);
        if(empty($nums)){
            echo "Add\r\n";
            return 1;
        }
        foreach($tree as $k => $v){
            // Make a copy
            $nums_copy = $nums;
            if(isset($nums_copy[$k])){
                // If exist decrease, if last remove
                if($nums[$k] > 1){
                    $nums_copy[$k] --;
                } else {
                    unset($nums_copy[$k]);
                }
                // move on to children
                $count += $this -> traversal($nums_copy, $v, $max - 1); 
            }     
        }
        return $count;
    }
}
Leetcode

6. ZigZag Conversion

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: “PAHNAPLSIIGYIR”

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I


/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    var data = new Array(numRows);
    var up = false; // up or down? used in-between tops and bottoms
    
    for(var i = 0, j = 0; i < s.length; i ++){
        // init arr elems
        if(data[j] === undefined){
            data[j] = "";
        }
        // append cur char
        data[j] += s.charAt(i);
        
        
        if(j == 0){
            // On top
            up = false; // Change direction
            j ++;
        } else if(j == numRows-1){
            // On bottom
            up = true;  // Then go up
            j --;
        } // in-between, follow prev direction
        else if(up){
            j --;
        } else {
            j ++;
        }
    }
    // Join/concat arr of str to single arr 
    return data.join("");
};
Leetcode

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {\
    // palindromic str for single round
    var o = ""; 
    // Longest palindromic str
    var max = "";
    for (var i = 0; i < s.length; i ++){
        var x = i;
        var y = i;
        // Include current char
            o = s[i];
            
            // Collect Same letters on the right
        while(s[y+1] == s[y]){
            y ++; i ++;
            // append same char on the right to p_str
            o += s[i];
        } 
        
        // Then check both sides one by one
        // Make sure x & y in range, then compare both ends
        while(x > 0 
                && y < s.length-1 
                && s[x-1] == s[y+1]){
            o = s[x-1] + o + s[y+1];
            // Separate x & y for one more step
            x--; y++;
        }
        
        // Save, if longer than current max record
        if(o.length > max.length){
            max = o;
        }
        
    }
    
    return max;
};
Leetcode

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

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

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5


/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    // remove elements from both ends

    
    while ((nums1.length + nums2.length)/2 > 1){
        // If any of the arrays is empty, rm the other one
        if(nums1.length == 0){
            nums2.shift();
            nums2.pop();
        } else if(nums2.length == 0){
            nums1.shift();
            nums1.pop();
        } else {
            if(nums1[0] < nums2[0]){
                nums1.shift();
            } else {
                nums2.shift();
            }
            // if nums1 is empty 
            //   OR nums1's tail is less than nums2's, remove nums2
            if(nums1.length == 0 || 
               nums1[nums1.length -1] < nums2[nums2.length -1]){
                nums2.pop();
            } else {
                nums1.pop();
            }
        }
    }
    // only 1 or 2 elements remain now
    var r = nums1.concat(nums2);
    // send average for two
    if(r.length > 1){
        return (r[0]+r[1])/2;
    } else {
    // or just the last element
        return r[0];
    }
};
Leetcode

3. Longest Substring Without Repeating

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    var max = 0;
    var a = [];
    for (var i = 0; i < s.length; i ++){
        // If element exists, remove any other elements before it, 
        // and itself
        if(a.includes(s[i])){
            a.splice(0, a.indexOf(s[i]) + 1);
        }
        // Append new element
        a.push(s[i]);
        // Update result
        if(max < a.length){
            max = a.length;
        }
    }
    return max;
};
Experience

Getting started with eBay API Tokens (Oauth) with PHP

Official Guide: http://developer.ebay.com/devzone/rest/ebay-rest/content/oauth-gen-user-token.html

I’ll also cover some mistakes I made.

  1.  Signup at https://developer.ebay.com
  2. Create an App and get the App ID (Client ID) and Cert ID (Client Secret)
  3. Click ‘User Tokens‘ (either from sandbox or production, depend on you)
  4. Click “Get a Token from eBay via Your Application” then “Add eBay Redirect URL“
  5. Fill in the form, the only important thing is the “Your auth accepted URL“, it should be under your domain. (You should able to extract the auth code from the call back later, for example $_GET[‘code’] in PHP),  let’s assume this  https://yourdomain.com/accept.php
  6. Take down the value of “RuName (eBay Redirect URL name)” and “Your branded eBay Production Sign In (OAuth)“

So far, we’ve done our preparation at developer.ebay.com

Then, on you local developing environment or you production server,:

  1. Set user login you own website
  2. put a hyperlink pointing to the URL of “Your branded eBay Production Sign In (OAuth)“
  3. visitor click on that link, and login with their ebay account.
  4. ebay will make a callback redirect to “Your auth accepted URL” if success.

On the “Your auth accepted URL“, prepare a PHP script that get the value of $_GET[‘code’] and save it in sessions. It starts with ‘v%5E1’. this is called “Authorization Code”

Next, get an “Access Token” with this “Authorization Code” 

Craft a HTTP Request with whatever you like with PHP.

HTTP headers:
Content-Type = application/x-www-form-urlencoded
Authorization = Basic <B64-encoded-oauth-credentials>

HTTP method: POST

URL: https://api.sandbox.ebay.com/identity/v1/oauth2/token

Request body (wrapped for readability):
grant_type=authorization_code&
code=<authorization-code-value>&
redirect_uri=<redirect_URI>

We have three ‘Variables’ here.

<B64-encoded-oauth-credentials>: Use a Chrome Browser, Right click, Inspect, Console
Then type: btoa(‘APP_ID:CERT_ID‘);
We did take down these two values earlier. and there is a : between.
Hit ENTER, the value inside the double quotes is <B64-encoded-oauth-credentials>

<authorization-code>: the ‘Authorization Code‘ we got in the callback redirect.

<redirect_URI>: This is the tricky part. This can’t be ignored or filled with random things, it’s the value of “RuName (eBay Redirect URL name)”

Send the request, and you’ll get the access token and the refresh token.
Follow the official guide to refresh the token if expired.

We are basically finished here, If you wanna call an API, ‘List orders as a seller’ for instance:

GET https://api.ebay.com/sell/fulfillment/v1/order

Headers:
Authorization: Bearer <YOUR_ACCESS_TOKEN>
It’s Bearer this time :), don’t use Basic by mistake.