“ARTS” is a learning punch card activity, the initiator is ashes level programmer Chen Hao, net name left ear mouse. The task is to do a LeetCode Algorithm, read and comment on an English technical article, learn a technical Tip, or Share an opinion and thinking technical article. All of these are deliberate exercises based on learning and thinking.

‘

A bitter and happy phase refining, refining extremely and into blessing, its blessing began for a long time; A doubt and a letter can be surveyed, and a knowledgeable person can know only true knowledge. — Vegetable Root Tan

Algorithm

Before we talk about the algorithm, let’s add one more point: the time and space complexity of the algorithm

We evaluate the advantages and disadvantages of an algorithm mainly from two dimensions:

  • Time dimension: Refers to the time taken to execute the current algorithm, which is usually described by “time complexity”.

  • Spatial dimension: Refers to the amount of memory required to perform the current algorithm, which is usually described as “spatial complexity”.

1. Time complexity

Representation of time complexity: big O notation, i.e. T(n)=O(f(n))

This formula is called the asymptotic time complexity of the algorithm

F (n) represents the sum of the number of times each line of code is executed, while O represents direct proportion. Let’s take a concrete example:

for (int i = 0; i < n; i++) {
    j = i;
    j++;
}
Copy the code

There are four lines of code above, and we assume that the execution time of each line is the same, represented by a grain of time.

Execution time of the first line of code: N particle time execution time of the second line of code: N particle time Execution time of the third line of code: N particle time Execution time of the fourth line of code: Yes symbol, temporarily ignored

Total time: T(n) = 3n * particle time. It can be seen from this time that the total execution time changes with the change of n. Therefore, we can simplify the expression of the time complexity of this algorithm: T(n) = O(n).

This is simplified because the big O notation is not used to represent the actual execution time of the algorithm, but rather to represent the increasing and changing trend of the code execution time.

Common time complexity levels are:

  • Constant order O (1)
  • The logarithmic order O (logN)
  • Linear order O (n)
  • Linear log order O(nlogN)
  • Order squared O(n2n^2n2)
  • Cubic order O(n3n^ 3N3)
  • Order NKN to the KNK.
  • Exponential order (2n2^n2n)

As the time complexity from top to bottom increases, the execution becomes less and less efficient.

2. Space complexity

If you understand the time complexity, then the space complexity is similar. Space complexity is also not used to calculate how much space the program actually takes up.

Space complexity is a measure of the amount of storage space temporarily occupied by an algorithm. It also reflects a trend.

Space complexity is commonly used: O(1), O(n), O(n²)

Let’s look at two examples:

int i = 1;
int j = 2;
int sum = i + j;
Copy the code

The space allocated by I and j in code does not vary with the amount of data processed, so its spatial complexity is S(n) = O(1).

Second example:

int[] m = new int[n];
for (int i = 0; i < n; i++) {
    j = i;
    j++;
}
Copy the code

In the first line of code, an array is created by the new keyword, and the size of array M is N. The second to fifth lines of code are a loop, but no new space is allocated. Therefore, the space complexity of the above code is: S(n) = O(n).

This algorithm

Given an integer array nums and an integer target value target, find the two integers in the array and the target values and return their array subscripts.

You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer. You can return the answers in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9 output: [0,1]Copy the code

Example 2:

Input: nums = [3,2,4], target = 6Copy the code

Example 3:

Input: nums = [3,3], target = 6Copy the code

Their thinking

The most direct method is to use the violence enumeration method, using two for loops to iterate over the sum of two numbers, equal to target returns the subscript of two numbers, code as follows:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j}; }}}return new int[0]; }}Copy the code

Complexity analysis

  • Time complexity: O(N2N^2N2)

  • Space complexity: O(1)

Method two: hash table

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[0]; }}Copy the code

Start by creating a HashMap to hold the iterated elements. A for loop is then used to iterate over the array, internally determining whether target-x is included in the HashMap, returning the subscript if it is, and storing the element in the HashMap with the element’s value as key and the subscript as value if it is not.

Complexity analysis

  • Time complexity: O(N). Where N is the number of elements in the array. For each element x, we can look O(1) for target-x.

  • Space complexity: O(1)

Review

This article is from Medium.

These 10 Flutter Widgets Every Developer Should Know

This article focuses on the 10 basic widgets used in Flutter development.

  1. SafeArea
  2. Expanded
  3. Wrap
  4. Opacity
  5. FutureBuilder
  6. FloatingActionButton
  7. PageView
  8. Table
  9. FadeInImage
  10. StreamBuilder

The 10 widgets selected by the author are very practical for actual development. Each Widget can solve some specific problems, and is simple and stable in actual use.

Of course, in a real project, there would be more than these 10 widgets, but as the author writes in the opening paragraph: Programming is a field that you should practice or get to know something about daily.

Using these 10 widgets as a foundation, we can continue to grow our knowledge base by learning something new every day.

Tip

Use two techniques for Dart

1.Use the call Method To Make Classes Callable Like a Function

Use the call method to make a class callable like a function

Define a class:

class CallMethodDemo {
  // Defining call method
  String call(String name) => 'hello $name';
}
Copy the code

Use:

void main() { 
  var call_input = CallMethodDemo(); 
  // Calling the class through its instance 
  var call_output = call_input('jack');    
  print(call_output); 
}
Copy the code

This class, which lets instances be called directly as functions, is called a Callable class.

Note: only one call method is allowed for a class

2.Use entries To Iterate Through a Map

Use entries to traverse the Map collection

for (var entry in moneySpent.entries) {
  // do something with keys and values
  print('${entry.key}: ${entry.value}');
}
Copy the code

Ensure air safety.

Share

Flutter State Management for Minimalists

State management has always been a hot topic in responsive programming. Flutter currently has many frameworks for state management, such as Provider, Bloc, Redux, MobX, and so on.

The purpose of this article is not to compare the strengths and weaknesses of each framework, but to try to explain what state management is.

It should be useful to follow this article to understand the various state management frameworks.