[Swift]LeetCode611. 有效三角形的个数 | Valid Triangle Number

概述Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle. Example 1: I

Given an array consists of non-negative integers,your task is to count the number of triplets chosen from the array that can make triangles if we take them as sIDe lengths of a triangle.

Example 1:

input: [2,2,3,4]Output: 3Explanation:ValID combinations are: 2,4 (using the first 2)2,4 (using the second 2)2,3 

Note:

The length of the given array won‘t exceed 1000. The integers in the given array are in the range of [0,1000].

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

示例 1:

输入: [2,4]输出: 3解释:有效的组合是: 2,4 (使用第一个 2)2,4 (使用第二个 2)2,3

注意:

数组长度不超过1000。 数组里整数的范围为 [0,1000]。 Runtime: 36 ms Memory Usage: 19.4 MB

 1 class Solution { 2     func triangleNumber(_ nums: [Int]) -> Int { 3         var nums = nums 4         var res:Int = 0 5         var n:Int  = nums.count 6         nums.sort() 7         for i in strIDe(from:n - 1,through:2,by:-1) 8         { 9             var left:Int = 010             var right:Int = i - 111             while (left < right)12             {13                 if nums[left] + nums[right] > nums[i]14                 {15                     res += (right - left)16                     right -= 117                 }18                 else19                 {20                     left += 121                 }22             }23         }24         return res25     }26 }

76ms

 1 class Solution { 2     func triangleNumber(_ nums: [Int]) -> Int { 3         var result = 0 4         guard nums.count >= 3 else { 5             return 0 6         } 7         var nums = nums.sorted() 8         for i in 0...nums.count - 2 { 9             let longest = nums[i]10             var fast = i + 211             var slow = i + 112             while fast < nums.count {13                 while slow < fast && nums[i] + nums[slow] <= nums[fast] {14                     slow += 115                 }16                 result += fast - slow17                 fast += 118             }19         }20         return result21     }22 }

124ms

 1 class Solution { 2     func triangleNumber(_ nums: [Int]) -> Int { 3         guard nums.count >= 3 else { return 0 } 4         let sortednums = nums.sorted { 5             return $0 < $1 6         } 7         var count = 0 8         let last = sortednums.count - 1 9         print(sortednums)10         for i in 0..<last {11             if sortednums[i] == 0 {12                 continue13             }14             var k = i + 115             for j in i+1...last {16                 if sortednums[j] == 0 {17                     continue18                 }19                 let sum = sortednums[i] + sortednums[j]20                 while k < sortednums.count && sortednums[k] < sum {21                     k += 122                 }23                 count += (k - j - 1)24             }25         }26         return count27     }28 }

128ms

 1 class Solution { 2     func triangleNumber(_ nums: [Int]) -> Int { 3         let n = nums.sorted() 4         var ans = 0 5         for i in 0..<n.count { 6             var k = i + 1 7             for j in i + 1..<n.count { 8                 while k + 1 < n.count && n[k + 1] < n[i] + n[j] { 9                     k += 110                 }11                 if n[k] < n[i] + n[j] {12                     ans += max(0,k - j)13                 }14             }15         }16         return ans17     }18 }

232ms

 1 class Solution { 2     // return the last index of a biggest number <= target 3     func binarySearch(_ nums: [Int],_ target: Int,_ start: Int,_ end: Int) -> Int { 4         var i = start,j = end 5         while i < j { 6             let m = (i + j) / 2 7             if nums[m] > target { j = m } 8             else { i = m + 1 } 9         }10         return i-111     }12     13    14     func triangleNumber(_ nums: [Int]) -> Int {15         guard nums.count > 2 else { return 0 }16         let nums = nums.sorted()17         var res = 018         for i in 0..<(nums.count - 2) {19             for j in i+1..<(nums.count - 1) {20                 res += binarySearch(nums,nums[i] + nums[j] - 1,j+1,nums.count) - j21             }22         }23         return res24     }25 }

248ms

 1 class Solution { 2     func triangleNumber(_ nums: [Int]) -> Int { 3         if nums.count < 3 { return 0 } 4         var res = 0 5         let nums = nums.sorted() 6         for i in 1..<nums.count - 1 { 7             var k = nums.count - 1 8             for j in (0..<i).reversed() { 9                 let s = nums[j] + nums[i]10                 while k > i && nums[k] >= s { k -= 1 }11                 res += k - i12             }13         }14         return res15     }16 }

1180ms、18948kb

 1 class Solution { 2     func triangleNumber(_ nums: [Int]) -> Int { 3     if nums.count < 3 { 4       return 0 5     } 6     var count = 0 7     let nums_sorted = nums.sorted() 8     let maxnum = nums_sorted.last! 9     for i in 0..<nums_sorted.count {10      11       for j in i+1..<nums_sorted.count {12         let sIDe1 = nums_sorted[i]13         let sIDe2 = nums_sorted[j]14         var numOfValIDThrIDNums = 015         for k in j+1..<nums_sorted.count {    16           if nums_sorted[k] < sIDe1 + sIDe2 {17             numOfValIDThrIDNums = numOfValIDThrIDNums + 118           } else {19             break;20           }21         }22         count = count + numOfValIDThrIDNums23       }24     }25     return count26   }27 }

1584ms 

 1 class Solution { 2     func triangleNumber(_ nums: [Int]) -> Int { 3          4         var n = 0 5         let nums = nums.sorted() 6         for i in 0..<nums.count { 7             for j in i + 1..<nums.count { 8                 for k in j + 1..<nums.count { 9                     if nums[k] < nums[i] + nums[j] {10                         n += 111                     } else {12                         break13                     }14                 }15             }16         }17         return n18     }19 }

2332ms

 1 class Solution { 2     func triangleNumber(_ nums: [Int]) -> Int { 3         let ct = nums.count 4         if ct < 3 { 5             return 0 6         } 7         var nums = nums.sorted { $0 > $1 } 8         var ans = 0 9         for i in 0..<ct-2 {10             for j in (i+1)..<ct-1 {11                 for k in (j+1)..<ct {12                     if vailIDTriangle(nums[i],nums[j],nums[k]) {13                         ans += 114                     }else{15                         break16                     }17                 }18             }19         }20         return ans21     }22 23     func vailIDTriangle(_ a: Int,_ b: Int,_ c: Int) -> Bool {24         return (b+c>a)25     }26 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode611. 有效三角形的个数 | Valid Triangle Number全部内容，希望文章能够帮你解决[Swift]LeetCode611. 有效三角形的个数 | Valid Triangle Number所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。