This is the 10th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continues to punch the card 43 days 🎈!
🚀 Algorithm 🚀

🌲 Example: Sum of two numbers II – Enter an ordered array

Given an array of integers in non-decreasing order numbers, find two numbers that add up to the target number.

The function should return the subscript values of these two numbers as an array of integers of length 2. The subscript of numbers starts at 1, so the answer array should be 1 <= answer[0] < answer[1] <= numbers. Length.

You can assume that each input corresponds to a unique answer, and you can’t reuse the same elements.

Example 1:

Enter: numbers = [2.7.11.15], target = 9Output:1.2] :2 与 7The sum is equal to the number of targets9. So the index1 =1, index2 = 2 。
Copy the code

Example 2:

Enter: numbers = [2.3.4], target = 6Output:1.3]
Copy the code

Example 3:

Enter: numbers = [- 1.0], target = - 1Output:1.2]
Copy the code

Tip:

  • 2 <= numbers.length <= 3 * 104
  • -1000 <= numbers[i] <= 1000
  • Numbers is arranged in non-decreasing order
  • -1000 <= target <= 1000
  • There is only one valid answer

🌻C# method: depth-first search

Since we’re solving for the minimum depth of a binary tree, let’s go through the entire binary tree and figure out the depth

Use depth-first search to traverse the entire tree and record the minimum depth.

For each non-leaf node, we only need to calculate the minimum leaf node depth of the left and right subtrees respectively.

This turns a big problem into a small problem that can be solved recursively.

Thinking analytical

Code:

public class Solution {
    public int MinDepth(TreeNode root) {
         if (root == null) return 0;
        else if (root.left == null) return MinDepth(root.right) + 1;
        else if (root.right == null) return MinDepth(root.left) + 1;
        else return Math.Min(MinDepth(root.left), MinDepth(root.right)) + 1; }}Copy the code

The execution result

By execution time:272Ms, in all CBeat 46.32% of users in # submitMemory consumption:50MB, in all CBeat 50.00% of users in submission
Copy the code

Complexity analysis

Time complexity: O(n), where N is the number of nodes in the tree Space complexity: O(H), where H is the height of the treeCopy the code

🌻Java method 1: binary search

Thinking analytical

To find two numbers in an array whose sum is equal to the target value, fix the first number and then find the second number, which is equal to the difference between the target value and the first number.

Using the ordered nature of array, we can find the second number by binary search.

To avoid double searches, only look to the right of the first number when looking for the second.

Code:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; ++i) {
            int low = i + 1, high = numbers.length - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (numbers[mid] == target - numbers[i]) {
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {
                    high = mid - 1;
                } else {
                    low = mid + 1; }}}return new int[] {-1, -1}; }}Copy the code

The execution result

By execution time:3Ms, beat out all Java commits26.14% user memory consumption:38.6MB, beat out all Java commits52.15% of the userCopy the code

Complexity analysis

Time: O(nlog n) Space: O(1 )
Copy the code

🌻Java Method 2: dual Pointers

Thinking analytical

Code:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int low = 0, high = numbers.length - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return new int[]{low + 1, high + 1};
            } else if (sum < target) {
                ++low;
            } else{ --high; }}return new int[] {-1, -1}; }}Copy the code

The execution result

By execution time:0Ms, beat out all Java commits100.00% user memory consumption:38.4MB, beat out all Java commits85.91% of the userCopy the code

Complexity analysis

Time: O(n) Space: O(1)
Copy the code

💬 summary

  • Today is the forty-third day of buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!

🚀 past quality articles to share

  • ❤ ️ Unity based to zero entry | the Unity game engine from 0 to 1 system study route suggest collection 】 【 comprehensive summary -!
  • 🧡 Spend a day making a high quality aircraft war game with over 10,000 word Unity complete tutorial! Beautiful school sister saw the call 666!
  • 💛 recall childhood and small partners played together the classic game [bomb people small game] production process + analysis
  • 💚 overnight a night to make a similar CS first person shooting game Demo! Turns out making games isn’t so hard
  • 🤍 blast liver a whole weekend to write a similar royal war real-time combat game Demo! More than 20,000 words game production process + analysis!
  • 💙 a similar “dinosaur kombat” horizontal version of the arcade fighting game how to make? | to learn together The way the source code suggest collect learning 】 【 code text is not easy,
  • 💜 super practical skills | 】 to improve writing quality and speed will learn skills: Typora figure bed configuration details