LeetCode – 697. Degree of an Array

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

Input: [1, 2, 2, 3, 1]
Output: 2
Explanation: 
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.

Example 2:

Input: [1,2,2,3,1,4,2]
Output: 6

Note:

 

  • nums.length will be between 1 and 50,000.
  • nums[i] will be an integer between 0 and 49,999.

 

Idea: use a hash map to store number elements as key and indices as value, then the length of the value is frequency of a specific number element, and difference between first and last indices in the value is the potential minimum length of the sub-array which has the degree as the input array.

 

Code:

def findShortestSubArray1(self, nums):
    """
    :type nums: List[int]
    :rtype: int

    https://leetcode.com/problems/degree-of-an-array/discuss/108647/Python-O(n)-concise-with-explanation-(two-approaches)

    Firstly, group each num and collect the index it appears into a list. The list with the longest length will be
    the degree of the array.

    Next loop through each of the lists, only those lists with the same length as the degree will qualify.
    We simply take difference between the first and last value of each qualifying lists to find the length of such
    a possible subarray.

    For example if we have [1, 1, 2, 2, 2, 3, 1], after grouping by value:

    [1, 1, 2, 2, 2, 3, 1] => { 1: [0, 1, 6], 2: [2, 3, 4], 3: [4] }, degree: 3

    Only have to consider values where the length == degree:

    1: [0, 1, 6] => subarray length: (6 - 0) + 1 = 7
    2: [2, 3, 4] => subarray length: (4 - 2) + 1 = 3 (Winner!)

    beats 27.26%
    """
    nums_map, deg, min_len = collections.defaultdict(list), 0, float('inf')
    for index, num in enumerate(nums):
        nums_map[num].append(index)
        deg = max(deg, len(nums_map[num]))
    for num, indices in nums_map.items():
        if len(indices) == deg:
            min_len = min(min_len, indices[-1] - indices[0] + 1)
    return min_len

def findShortestSubArray2(self, nums):
    """
    :type nums: List[int]
    :rtype: int

    nums_map: k as num, v as indices of num in the array
    deg: degree of array (maximum frequency of any one of its elements)
    min_len: minimum length to hold the continuous sub-array which has the degree

    difference between first and last indices of an element is the degree and potential min length for the num

    beats 52.72%
    """
    nums_map, deg, min_len = collections.defaultdict(list), 0, float('inf')
    for index, num in enumerate(nums):
        nums_map[num].append(index)
        if len(nums_map[num]) == deg:
            min_len = min(min_len, nums_map[num][-1] - nums_map[num][0] + 1)
        elif len(nums_map[num]) > deg:
            deg = len(nums_map[num])
            min_len = nums_map[num][-1] - nums_map[num][0] + 1
    return min_len

Donate $5 to me for a coffee with PayPal and read more professional and interesting technical blog articles about web and mobile development. Feel free to visit my web app, WhizWallet, to apply for credit, store or gift cards, DealsPlus to browse daily deals and store coupons to save money, BlackFriday.fm to check latest news, ads and sales in BlackFriday shopping season.

Follow me @Yaoli0615 at Twitter to get latest tech updates.

Resources:

Core Java Volume I–Fundamentals (10th Edition) (Core Series)

Core Java, Volume II–Advanced Features (10th Edition) (Core Series)

Test-Driven Java Development

Java Concurrency in Practice

Java: An Introduction to Problem Solving and Programming (7th Edition)

Java 9 for Programmers (Deitel Developer Series)

Java SE8 for the Really Impatient: A Short Course on the Basics (Java Series)

Core Java for the Impatient

Java: The Beginners Guide for every non-programmer which will attend you trough your learning process

Java Deep Learning Essentials

Machine Learning in Java

Learning Reactive Programming With Java 8

Java 9 Programming By Example

Thinking in Java (4th Edition)

The Java EE Architect’s Handbook, Second Edition: How to be a successful application architect for Java EE applications

Java Artificial Intelligence: Made Easy, w/ Java Programming

 

Advertisements
Posted in Algorithm&DataStructure, Uncategorized | Tagged , , , | Leave a comment

LeetCode – 308. Range Sum Query 2D – Mutable


Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
update(3, 2, 2)
sumRegion(2, 1, 4, 3) -> 10

Note:

  1. The matrix is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRegion function is distributed evenly.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.

 

Idea: it should come out some way to store the computed results of sums and get region sum based on the pre-computed results. “Range Sum” is a good idea in this case, because every element in the matrix stores the sum of all previous elements in this row and it can get the range sum by difference of end element and previous element of start point.

 

Similar problems:

LC 303. Range Sum Query – Immutable

 

Code:

class NumMatrix(object):
    """
    Your NumMatrix object will be instantiated and called as such:
    obj = NumMatrix(matrix)
    obj.update(row,col,val)
    param_2 = obj.sumRegion(row1,col1,row2,col2)

    https://leetcode.com/problems/range-sum-query-2d-mutable/discuss/75872/Python-94.5-Simple-sum-array-on-one-dimension-O(n)-for-both-update-and-sum

    beats 83.86%
    """

    def __init__(self, matrix):
        """
        :type matrix: List[List[int]]

        element m[i][j] in self.matrix means sum of previous elements in this row,
        namely sum(m[i][0] + m[i][1] + ... + m[i][j])
        """
        for row in matrix:
            for col in range(1, len(row)):
                row[col] += row[col - 1]
        self.matrix = matrix

    def update(self, row, col, val):
        """
        :type row: int
        :type col: int
        :type val: int
        :rtype: void

        original means the single element value in original matrix
        """
        original = self.matrix[row][col]
        if col != 0:
            original -= self.matrix[row][col - 1]

        diff = original - val

        for y in range(col, len(self.matrix[0])):  # update elements in the row
            self.matrix[row][y] -= diff

    def sumRegion(self, row1, col1, row2, col2):
        """
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int

        region sum is the sum of range sum in every row from row1 to row2
        as the above definition of self.matrix
        each range sum could be calculated as (m[row][col2] - m[row][col1 - 1])
        """
        region_sum = 0
        for x in range(row1, row2 + 1):
            region_sum += self.matrix[x][col2]
            if col1 != 0:
                region_sum -= self.matrix[x][col1 - 1]
        return region_sum
Posted in Algorithm&DataStructure, Uncategorized | Tagged | Leave a comment

Dynamic Programming Notes

wpid-Programming-Wallpaper-3

Dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler sub-problems, solving each of those sub-problems just once, and storing their solutions. The next time the same sub-problem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space.

 

Solution:

Figure out a way to break the problem into sub-problems:

The original problem can be solved relatively easily once solutions to the sub-problems are available and these sub-problem solutions are cached.

 

4 key factors:

1. function definition and meaning (f[n] in Fibonacci Numbers)

2. transition function (f[n] = f[n-1] + f[n-2])

3. base case and initial condition (f[0] = 0, f[1] = 1)

4. result (f[n])

Refer:

Divide and Conquer Summary

Dynamic Programming – From Novice to Advanced

 

Donate $5 to me for a coffee with PayPal and read more professional and interesting technical blog articles about web and mobile development. Feel free to visit my web app, WhizWallet, to apply for credit, store or gift cards, DealsPlus to browse daily deals and store coupons to save money, BlackFriday.fm to check latest news, ads and sales in BlackFriday shopping season.

Follow me @Yaoli0615 at Twitter to get latest tech updates.

Resources:

Core Java Volume I–Fundamentals (10th Edition) (Core Series)

Core Java, Volume II–Advanced Features (10th Edition) (Core Series)

Test-Driven Java Development

Java Concurrency in Practice

Java: An Introduction to Problem Solving and Programming (7th Edition)

Java 9 for Programmers (Deitel Developer Series)

Java SE8 for the Really Impatient: A Short Course on the Basics (Java Series)

Core Java for the Impatient

Java: The Beginners Guide for every non-programmer which will attend you trough your learning process

Java Deep Learning Essentials

Machine Learning in Java

Learning Reactive Programming With Java 8

Java 9 Programming By Example

Thinking in Java (4th Edition)

The Java EE Architect’s Handbook, Second Edition: How to be a successful application architect for Java EE applications

Java Artificial Intelligence: Made Easy, w/ Java Programming

Posted in Algorithm&DataStructure, Uncategorized | Tagged , | Leave a comment

Startup Blogs

Flat designt business startup launch concept.

How to start a startup

Startup

Founders at Work

The Best Simple Business Models

Why I’m leaving silicon valley

未来世界的幸存者

Software and technology stack used by top companies

Do things that don’t scale

 

Donate $5 to me for a coffee with PayPal and read more professional and interesting technical blog articles about web and mobile development. Feel free to visit my web app, WhizWallet, to apply for credit, store or gift cards, DealsPlus to browse daily deals and store coupons to save money, BlackFriday.fm to check latest news, ads and sales in BlackFriday shopping season.

Follow me @Yaoli0615 at Twitter to get latest tech updates.

Posted in IT, startup, Uncategorized | Tagged , , | Leave a comment

Python Blogs

567828_67d0

Google’s Python Class

Dive into Python

A Python Reading List

Map, Filter, Reduce

Python Tutorial: Shallow and Deep Copy

Python Numpy Tutorial

PEP 8 — Style Guide for Python Code

Python Zen – FooFish Python之禅

The Hitchhiker’s Guide to Python

 

Donate $5 to me for a coffee with PayPal and read more professional and interesting technical blog articles about web and mobile development. Feel free to visit my web app, WhizWallet, to apply for credit, store or gift cards, DealsPlus to browse daily deals and store coupons to save money, BlackFriday.fm to check latest news, ads and sales in BlackFriday shopping season.

Follow me @Yaoli0615 at Twitter to get latest tech updates.

Posted in CS Research&Application, Uncategorized | Tagged | Leave a comment

Kwik Learning

20065291_791032531070507_9203537912241586176_n

1. Manage first hour and last hour.

 

2. 10 things to do in the morning:

1) remember your dream (i.e. business, ML/AI, 3 commas)

2) make your bed

3) drink lots of water

4) brush teeth with opposite hand

5) deep breath exercise (meditation)

6) drink brain tea

7) journaling (record daily plan and reflection)

8) 5 minute HIIT workout (to warm up)

9) drink brain power smoothie (blueberry, avocado, etc)

10) daily reading

 

3. Learn FAST

Forget: be hungry, be foolish

Active: take notes, concentrate

State: emotion influence learning effect

Teach: learn by teaching

 

4. Self talk is very important.

“As you think, so shall you become.” – Bruce Lee

 

5. “Education is ultimately much more than simply memorizing individual facts, or even learning individual concepts. [What] matters most: learning how to think, learning how to reason and learning how to learn.” – Vitalik Buterin

 

6. Ask questions, be dump for seconds, then wise ever after

 

Donate $5 to me for a coffee with PayPal and read more professional and interesting technical blog articles about web and mobile development. Feel free to visit my web app, WhizWallet, to apply for credit, store or gift cards, DealsPlus to browse daily deals and store coupons to save money, BlackFriday.fm to check latest news, ads and sales in BlackFriday shopping season.

Follow me @Yaoli0615 at Twitter to get latest tech updates.

Posted in Book/Movie/Music, Uncategorized | Tagged , , | Leave a comment

Favorite Chrome Extensions

best-chrome-extensions-670x335

Momentum: wallpaper, todo list, quotes

SimilarWeb: similar websites

Wappalyzer: website technology analysis

Google Optimize: A/B testing

AdBlock: block ads

 

Donate $5 to me for a coffee with PayPal and read more professional and interesting technical blog articles about web and mobile development. Feel free to visit my web app, WhizWallet, to apply for credit, store or gift cards, DealsPlus to browse daily deals and store coupons to save money, BlackFriday.fm to check latest news, ads and sales in BlackFriday shopping season.

Follow me @Yaoli0615 at Twitter to get latest tech updates.

Posted in CS Research&Application, Uncategorized | Tagged , | 2 Comments