665. Non-decreasing Array

LeetCode medium original: C# #array #backtracking #csharp #leetcode #medium
Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.
LeetCode Static

Дан Array nums из n целых чисел. Ваша Aufgabe - проверить, можно ли сделать его неубывающим, изменив не более одного elementа.

Мы определяем Array как неубывающий, если для каждого i (индексация с 0), такого что 0 <= i <= n - 2, выполняется Beschreibung nums[i] <= nums[i + 1].

Beispiel

Input: nums = [4,2,3]

Output: true

Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

C# Lösung

zugeordnet/original 
public class Solution {
    public bool CheckPossibility(int[] nums) {
        int count = 0;
        
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] < nums[i - 1]) {
                if (count > 0) {
                    return false;
                }
                count++;
                if (i == 1 || nums[i] >= nums[i - 2]) {
                    nums[i - 1] = nums[i];
                } else {
                    nums[i] = nums[i - 1];
                }
            }
        }
        
        return true;
    }
}

C++ Lösung

Auto-Entwurf, vor dem Einreichen prüfen 
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool CheckPossibility(vector<int>& nums) {
        int count = 0;
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < nums[i - 1]) {
                if (count > 0) {
                    return false;
                }
                count++;
                if (i == 1 || nums[i] >= nums[i - 2]) {
                    nums[i - 1] = nums[i];
                } else {
                    nums[i] = nums[i - 1];
                }
            }
        }
        
        return true;
    }
}

Java Lösung

Auto-Entwurf, vor dem Einreichen prüfen 
import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public boolean CheckPossibility(int[] nums) {
        int count = 0;
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                if (count > 0) {
                    return false;
                }
                count++;
                if (i == 1 || nums[i] >= nums[i - 2]) {
                    nums[i - 1] = nums[i];
                } else {
                    nums[i] = nums[i - 1];
                }
            }
        }
        
        return true;
    }
}

Python Lösung

zugeordnet/original 
class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        count = 0
        
        for i in range(1, len(nums)):
            if nums[i] < nums[i - 1]:
                if count > 0:
                    return False
                count += 1
                if i == 1 or nums[i] >= nums[i - 2]:
                    nums[i - 1] = nums[i]
                else:
                    nums[i] = nums[i - 1]
        
        return True

Go Lösung

zugeordnet/original 
func checkPossibility(nums []int) bool {
    count := 0
    
    for i := 1; i < len(nums); i++ {
        if nums[i] < nums[i-1] {
            if count > 0 {
                return false
            }
            count++
            if i == 1 || nums[i] >= nums[i-2] {
                nums[i-1] = nums[i]
            } else {
                nums[i] = nums[i-1]
            }
        }
    }
    
    return true
}

Algorithm

Инициализация переменных:

Завести переменную count для подсчета числа изменений.

Проверить последовательность чисел в Arrayе nums.

Проверка условий:

Если nums[i] > nums[i + 1], то увеличиваем count.

Если count превышает 1, возвращаем false, так как больше одного изменения недопустимо.

Если nums[i - 1] > nums[i + 1] и nums[i] > nums[i + 2], то возвращаем false.

Возврат результата:

Если количество изменений не превышает 1, вернуть true.

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen
Es gibt noch keine aktiven Stellen.