This is the 16th 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 49th day 🎈!
🚀 Algorithm 🚀

🌲 Example: Summary interval

Given an ordered array of integers with no repeating elements, nums.

Returns a list of minimum ordered ranges that cover exactly all the numbers in the array. That is, every element of NUMS is covered by exactly some range, and there is no number X that belongs to a range but is not numS.

Each interval range [a,b] in the list should be printed in the following format:

  • “A -> B”, if A! = b
  • “A”, if a is equal to b

Example 1:

Enter: nums = [0.1.2.4.5.7] output: ["0 - > 2"."4 - > 5"."Seven"] The interval range is: [0.2] --> "0 - > 2"
[4.5] --> "4 - > 5"
[7.7] --> "Seven"Source: LeetCode//leetcode-cn.com/problems/summary-rangesCopyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Example 2:

Enter: nums = [0.2.3.4.6.8.9] output: ["0"."2 - > 4"."6"."8 - > 9"] The interval range is: [0.0] --> "0"
[2.4] --> "2 - > 4"
[6.6] --> "6"
[8.9] --> "8 - > 9"

Copy the code

Example 3:

Nums = [] Output: []Copy the code

Example 4:

Enter: nums = [- 1] output: ["1"]
Copy the code

Example 5:

Enter: nums = [0] output: ["0"]
Copy the code

Tip:

  • 0 <= nums.length <= 20
  • -231 <= nums[i] <= 231 – 1
  • All values in NUMS are different
  • Nums are arranged in ascending order

🌻C# method: depth-first search

  1. This is essentially a loop array that checks whether the current position is 1 different from the previous position (or the current position is 1 different from the next position). If so, continue. If not, add to the list
  2. There are also two ways to add to a list.

A. Use x-> Y format for consecutive values greater than 1. Use X format for consecutive values equal to and less than 1

Code:

public class Solution {
    public IList<string> SummaryRanges(int[] nums) {
        List<string> res = new List<string> ();int i=0,j=0;

        while(j<nums.Length){
            //j==nums. length-1
            if(j==nums.Length- 1 || nums[j+1]-nums[j]! =1) {if(i==j) res.Add($"{nums[i]}");
                else res.Add($"{nums[i]}->{nums[j]}");
                i = j+1;
            }
            ++j;
        }
        returnres; }}Copy the code

The execution result

By execution time:232Ms, in all CDefeated 69.77% of users in # commitMemory consumption:30MB, in all C# beat 74.42% of users in submission
Copy the code

🌻Java Method 1: Iterate once

Thinking analytical

Let’s start at position 00 and iterate to the right. Every time we encounter a difference of more than 11 between adjacent elements, we find an interval. After iterating through the array, you get a list of intervals.

During the traversal process, the maintenance subscripts low and high record the starting point and end point of the interval respectively. For any interval, low≤high. When an interval is obtained, a string representation of the interval is generated based on the values of low and high.

  • When low
  • When low=high, the interval string is represented as’ low ‘.

Code:

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ret = new ArrayList<String>();
        int i = 0;
        int n = nums.length;
        while (i < n) {
            int low = i;
            i++;
            while (i < n && nums[i] == nums[i - 1] + 1) {
                i++;
            }
            int high = i - 1;
            StringBuffer temp = new StringBuffer(Integer.toString(nums[low]));
            if (low < high) {
                temp.append("- >");
                temp.append(Integer.toString(nums[high]));
            }
            ret.add(temp.toString());
        }
        returnret; }}Copy the code

The execution result

By execution time:0Ms, beat out all Java commits100.00% user memory consumption:36.5MB, beat out all Java commits65.23% of the userCopy the code

Complexity analysis

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

💬 summary

  • Today is the forty-ninth day of 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