【小Y學演算法】??每日LeetCode打卡??——49.匯總區間

📢前言

• 🌲 每天打卡一道演算法題，既是一個學習程序，又是一個分享的程序😜
• 🌲 提示：本專欄解題 編程語言一律使用 C# 和 Java 兩種進行解題
• 🌲 要保持一個每天都在學習的狀態，讓我們一起努力成為演算法大神吧🧐！
• 🌲 今天是力扣演算法題持續打卡第49天🎈！

🌲原題樣例：匯總區間

給定一個無重復元素的有序整數陣列 nums，

回傳 恰好覆寫陣列中所有數字 的 最小有序 區間范圍串列，也就是說，nums的每個元素都恰好被某個區間范圍所覆寫，并且不存在屬于某個范圍但不屬于 nums 的數字 x ，

串列中的每個區間范圍 [a,b] 應該按如下格式輸出：

• “a->b” ，如果 a != b
• “a” ，如果 a == b

示例 1：

輸入：nums = [0,1,2,4,5,7]
輸出：["0->2","4->5","7"]
解釋：區間范圍是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/summary-ranges
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

示例 2：

輸入：nums = [0,2,3,4,6,8,9]
輸出：["0","2->4","6","8->9"]
解釋：區間范圍是：
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

示例 3：

輸入：nums = []
輸出：[]

示例 4：

輸入：nums = [-1]
輸出：["-1"]

示例 5：

輸入：nums = [0]
輸出：["0"]

提示：

• 0 <= nums.length <= 20
• -231 <= nums[i] <= 231 - 1
• nums 中的所有值都 互不相同
• nums 按升序排列

🌻C#方法：深度優先搜索

1. 本質上就是回圈陣列，判斷當前位置和上一位置（或者是當前位置和下一位置）相比，是不是相差1，是的話繼續，不是的話就加入的list中
2. 往list中添加，也有兩種情況，
   a. 連續值超過1 超過1 用 x->y 格式
   b. 連續值等于1 不超過1 用 x 格式

代碼：

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;
        }
        return res;
    }
}

執行結果

通過
執行用時：232 ms，在所有 C# 提交中擊敗了69.77%的用戶
記憶體消耗：30 MB，在所有 C# 提交中擊敗了74.42%的用戶

🌻Java 方法一：一次遍歷

思路決議

我們從陣列的位置 00 出發，向右遍歷，每次遇到相鄰元素之間的差值大于 11 時，我們就找到了一個區間，遍歷完陣列之后，就能得到一系列的區間的串列，

在遍歷程序中，維護下標low 和 high 分別記錄區間的起點和終點，對于任何區間都有 low≤high，當得到一個區間時，根據low 和 high 的值生成區間的字串表示，

• 當 low<high 時，區間的字串表示為 ‘‘low→high"；
• 當 low=high 時，區間的字串表示為 ‘‘low"，

代碼：

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());
        }
        return ret;
    }
}

執行結果

通過
執行用時：0 ms，在所有 Java  提交中擊敗了100.00%的用戶
記憶體消耗：36.5 MB，在所有 Java 提交中擊敗了65.23%的用戶

復雜度分析

時間復雜度：O( n )
空間復雜度：O( 1 )

💬總結

• 今天是力扣演算法題打卡的第四十九天！
• 文章采用 C#和 Java 兩種編程語言進行解題
• 一些方法也是參考力扣大神寫的，也是邊學習邊分享，再次感謝演算法大佬們
• 那今天的演算法題分享到此結束啦，明天再見！
  

🚀往期優質文章分享

• ??Unity零基礎到入門 | 游戲引擎 Unity 從0到1的 系統學習 路線【全面總結-建議收藏】！
• 🧡花一天時間做一個高質量飛機大戰游戲，過萬字Unity完整教程！漂亮學妹看了直呼666！
• 💛回憶童年和小伙伴一起玩過的經典游戲【炸彈人小游戲】制作程序+決議
• 💚通宵一晚做出來的一款類似CS的第一人稱射擊游戲Demo！原來做游戲也不是很難
• 🤍爆肝整整一個周末寫一款類似 皇室戰爭 的 即時戰斗類 游戲Demo！兩萬多字游戲制作程序+決議！
• 💙一款類似“恐龍快打”的 橫版街機格斗游戲 該如何制作？| 一起來學習 順便送原始碼【碼文不易，建議收藏學習】
• 💜【超實用技巧】| 提高寫文的質量 和 速率必學技能： Typora 圖床配置 詳細說明