• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode665.非递减数列|Non-decreasingArray

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10492254.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array. 

Example 2:

Input: [4,2,1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element. 

Note: The n belongs to [1, 10,000].


给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的: 对于数组中所有的 i (1 <= i < n),满足 array[i] <= array[i + 1]

示例 1:

输入: [4,2,3]
输出: True
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。

示例 2:

输入: [4,2,1]
输出: False
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

说明:  n 的范围为 [1, 10,000]。


44ms

 1 class Solution {
 2     func checkPossibility(_ nums: [Int]) -> Bool {
 3         var i = 0
 4         var j = nums.count - 1
 5         while i < j && nums[i] <= nums[i+1] {
 6             i += 1
 7         }
 8         while i < j && nums[j] >= nums[j-1] {
 9             j -= 1
10         }
11         let head = (i == 0) ? Int.min : nums[i-1]
12         let next = (j == nums.count - 1) ? Int.max : nums[j+1]
13         
14         if j - i <= 1 && (head < nums[j] || nums[i] < next) {
15             return true
16         } else {
17             return false
18         }
19     }
20 }

188ms

 1 class Solution {
 2     func checkPossibility(_ nums: [Int]) -> Bool {
 3         
 4         if nums.count < 3 {
 5             return true
 6         }
 7         
 8         var i = 0
 9         
10         while i <= nums.count - 2, nums[i] <= nums[i + 1] {
11             i += 1
12         }
13         
14         var j = nums.count - 1
15         
16         if i >= j - 1 {
17             return true
18         }
19         
20         while 1 <= j, nums[j - 1] <= nums[j] {
21             j -= 1
22         }
23         
24         if j <= 1  {
25             return true
26         }
27         
28         return ((j - i == 2) && (nums[i] <= nums[j])) 
29                || 
30                ((j - i == 1) 
31                    && 
32                    ((0 < i) && (nums[i - 1] <= nums[j])
33                    || ((j < nums.count - 1) && (nums[i] <= nums[j + 1]))))
34     }
35 }

Runtime: 192 ms
Memory Usage: 19.5 MB
 1 class Solution {
 2     func checkPossibility(_ nums: [Int]) -> Bool {
 3         var nums = nums
 4         var cnt:Int = 1
 5         var n:Int = nums.count
 6         for i in 1..<n
 7         {
 8             if nums[i] < nums[i - 1]
 9             {
10                 if cnt == 0 {return false}
11                 if i == 1 || nums[i] >= nums[i - 2]
12                 {
13                     nums[i - 1] = nums[i]
14                 }
15                 else
16                 {
17                     nums[i] = nums[i - 1]
18                 }
19                 cnt -= 1
20             }
21         }
22         return true
23     }
24 }

196ms

 1 class Solution {
 2     func checkPossibility(_ nums: [Int]) -> Bool {
 3             var c = 0
 4             var nums = [-Int.max] + nums
 5             var low = nums[0]
 6         
 7         for (i, n) in nums.enumerated().dropFirst() {
 8             if n < nums[i-1] {
 9                 if n >= low {
10                     nums[i-1] = low
11                 } else {
12                     nums[i] = nums[i-1]
13                 }
14                 c += 1
15                 if c > 1 {
16                     return false
17                 }
18             }
19             if i > 1 {
20                 low = nums[i-1]
21             }
22         }
23         
24         return true
25     }
26 }

200ms

 1 class Solution {
 2     func checkPossibility(_ nums: [Int]) -> Bool {
 3         var newNums = nums
 4         if newNums.count <= 2 {
 5             return true
 6         }
 7         
 8         var i = 1
 9         var j = 2
10         var noOfChange = 0
11         
12         if (newNums[i] < newNums[i-1]) {
13             newNums[i-1] = newNums[i]
14             noOfChange = noOfChange + 1
15         }
16         
17         while j <= newNums.count - 1 {
18             if (newNums[i] > newNums[j]) {
19                 //if [j] > [i-1], change value of [i] -> [i-1] 
20                 if (newNums[j] > newNums[i-1]) {
21                     newNums[i] = newNums[i-1]
22                 } 
23                 //else, change [j] -> [i]
24                 else { 
25                     newNums[j] = newNums[i]
26                 }
27                 
28                 noOfChange = noOfChange + 1
29             }
30             j = j + 1
31             i = i + 1
32         }
33         
34         return noOfChange <= 1
35     }
36 }

208ms

 1 class Solution {
 2     func checkPossibility(_ nums: [Int]) -> Bool {
 3         
 4         if nums.count < 3 {
 5             return true
 6         }
 7         
 8         var index = -1
 9         
10         for i in 0 ..< (nums.count - 1) {
11             if nums[i] > nums[i+1] {
12                 if index != -1 { return false }
13                 index = i
14             }
15         }
16         
17         return ((index == -1)
18             || (index == 0)
19             || (index == nums.count - 2)
20             || (nums[index+1] - nums[index-1] > 0)
21             || (nums[index+2] - nums[index] > 0))
22     }
23 }

284ms

 1 class Solution {
 2     func checkPossibility(_ nums: [Int]) -> Bool {
 3         guard nums.count > 1 && nums.count <= 10000 else {
 4             return nums.count == 1
 5         }
 6         var array = nums
 7         var modified = false
 8         for i in 0 ..< array.count - 1 {
 9             if array[i] > array[i + 1] {
10                 if modified {
11                     return false
12                 }
13                 if i > 0 && array[i - 1] > array[i + 1] {
14                     array[i + 1] = array[i]
15                 }
16                 modified = true
17             }
18         }
19         return true
20     }
21 }

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift学习字符串、数组、字典发布时间:2022-07-13
下一篇:
[Swift]LeetCode678.有效的括号字符串|ValidParenthesisString发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap