O比较简单,的所有行然后分别进行 binary search

作者: 编程  发布:2019-10-08

My code:

9159.com 1

9159.com 2

public class Solution { public int minSubArrayLen(int s, int[] nums) { if (nums == null || nums.length == 0) return 0; int head = 0; int end = 0; int sum = 0; boolean isForward = true; int minLen = Integer.MAX_VALUE; while (end < nums.length) { if (isForward) { sum += nums[end]; if (sum >= s) { minLen = Math.min(minLen, end - head + 1); isForward = false; } else { isForward = true; end++; } } else { sum = sum - nums[head]; head++; if (sum >= s) { minLen = Math.min(minLen, end - head + 1); isForward = false; } else { isForward = true; end++; } } } return minLen < Integer.MAX_VALUE ? minLen : 0; } public static void main(String[] args) { Solution test = new Solution(); int[] a = {2,3,1,2,4,3}; System.out.println(test.minSubArrayLen; }}

My code:

My code:

我自己的做法就是 sliding window, O比较简单。但是还有一种 O n log n 的做法。我没怎么搞懂。博文放在这里,有机会再研究。

public class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false; for (int i = 0; i < matrix.length; i++) { int begin = 0; int end = matrix[0].length - 1; while (begin <= end) { int middle = begin + (end - begin) / 2; if (matrix[i][middle] > target) { end = middle - 1; } else if (matrix[i][middle] < target) { begin = middle + 1; } else return true; } } return false; }}
public class Solution { public int[] searchRange(int[] nums, int target) { if (nums == null || nums.length == 0) return null; int[] result = new int[2]; int lo = 0; int hi = nums.length - 1; BinarySearch(lo, hi, target, nums, result); return result; } private void BinarySearch(int lo, int hi, int target, int[] nums, int[] result) { if (lo > hi) { result[0] = -1; result[1] = -1; return; } int mid =  / 2; if (target > nums[mid]) { while (mid + 1 < nums.length && nums[mid + 1] == nums[mid]) mid++; BinarySearch(mid + 1, hi, target, nums, result); } else if (target < nums[mid]) { while (mid - 1 >= 0 && nums[mid - 1] == nums[mid]) mid--; BinarySearch(lo, mid - 1, target, nums, result); } else { int i = mid; while (i + 1 < nums.length && nums[i + 1] == nums[i]) i++; result[1] = i; i = mid; while (i - 1 >= 0 && nums[i - 1] == nums[i]) i--; result[0] = i; } }}

**总结:sliding window**

我觉得这道题木就是每一行用一次binary seach,O, 没什么难的。

My test result:

Anyway, Good luck, Richardo!

Anyway, Good luck, Richardo!

9159.com 3

My code:

My code:

这道题目没什么大的难度。主要就是其中需要用 while循环过滤掉那些重复出现的数字,之前一道题目中出现过一种方法。具体忘了。

public class Solution { public int minSubArrayLen(int s, int[] nums) { if (nums == null || nums.length == 0) return 0; int min = Integer.MAX_VALUE; int begin = 0; int end = 0; int sum = 0; while (begin <= end && end < nums.length) { sum += nums[end]; if (sum >= s) { min = Math.min(min, end - begin + 1); sum -= nums[begin]; sum -= nums[end]; begin++; } else { end++; } } if (min == Integer.MAX_VALUE) return 0; else return min; }}
public class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return false; } int i = 0; int j = matrix[0].length - 1; while (i < matrix.length && j >= 0) { int curr = matrix[i][j]; if (curr == target) { return true; } else if (curr > target) { j--; } else { i++; } } return false; }}

**总结:binary search in range**

这道题木的思路就是 sliding window,但是奇怪的是,为什么时间复杂度是 O 呢?

reference:

Anyway, Good luck, Richardo!

programcreek 上面对这道题木的解释很直接简洁:

time complexity: O

原先的做法并不能保证严格的O.还是得用两次bianry search第一次,搜索 target 出现的左边界,相比于BS来说,变化在于,when nums[mid] == target:mid--;第二次,搜索target出现的右边界,相比于BS来说,变化在于:when nums[mid] == target:mid++;

We can use 2 points to mark the left and right boundaries of the sliding window. When the sum is greater than the target, shift the left pointer; when the sum is less than the target, shift the right pointer.

这个做法,并没有很好地利用 binary search

而且,最后给ret赋值的时候,得注意判断,begin是否 <nums.lengthend时候 >= 0

参考网址:

然后 binary search 通俗的做法是下面这个链接:

Anyway, Good luck, Richardo9159.com ,! -- 09/03/2016

当然,这道题目还有一种 nlogn的解法,就是以一侧为开头,比如nums[i],新开一个数组一次记录元素的和。然后每次用binary search 找最接近target + sum[i]的index,然后求出长度。具体看之前的网页链接。

复杂度是 O(row * log具体思路就是,先找到 <= target 的所有行然后分别进行 binary search

My code:

Anyway, Good luck, Richardo!

然后看了下我以前的做法,直接对所有行进行 Binary search,其实在时间复杂度上没有区别。

public class Solution { public int[] searchRange(int[] nums, int target) { if (nums == null || nums.length == 0) { return new int[]{-1, -1}; } int[] ret = new int[2]; int start = 0; int end = nums.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (nums[mid] == target) { end = mid; } else if (nums[mid] < target) { start = mid; } else { end = mid; } } if (nums[start] == target) { ret[0] = start; } else if (nums[end] == target) { ret[0] = end; } else { ret[0] = -1; ret[1] = -1; return ret; } start = 0; end = nums.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (nums[mid] == target) { start = mid; } else if (nums[mid] > target) { end = mid; } else { start = mid; } } if (nums[end] == target) { ret[1] = end; } else if (nums[start] == target) { ret[1] = start; } else { ret[0] = -1; ret[1] = -1; return ret; } return ret; }}

Anyway, Good luck, Richardo! -- 09/21/2016

reference:

Anyway, Good luck, Richardo! -- 10/16/2016

本文由9159.com发布于编程,转载请注明出处:O比较简单,的所有行然后分别进行 binary search

关键词:

上一篇:没有了
下一篇:没有了