leetCode刷题记录-链表

发表于 分类于 ，

关于二分查找，可以看labuladong，或者是极客王铮的算法课15 16

王铮总结的左右边界 要比公众号好记的多

704.二分查找 基础题

最基础的一个二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

自己的代码,含有4个二分法变种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// 正常二分法
var search = function(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] < target) {
      left = mid + 1
    } else {
      return mid
    }
  }
  return -1
};
// 含有重复元素 找到第一个等于target的数
var search = function(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] < target) {
      left = mid + 1
    } else {
      if (mid === 0 || nums[mid - 1] !== target) {
        return mid
      }
      right = mid - 1
    }
  }
  return -1
};
// 含有重复元素 找到最后一个等于target的数
var search = function(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] < target) {
      left = mid + 1
    } else {
      if (mid === nums.length - 1 || nums[mid + 1] !== target) {
        return mid
      }
      left = mid + 1
    }
  }
  return -1
};
// 含有重复元素 查找第一个大于等于给定值的元素
var search = function(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] >= target) {
      if (mid === 0 || nums[mid - 1] < target) {
        return mid
      }
      right = mid - 1
    } else if (nums[mid] < target) {
      left = mid + 1
    }
  }
  return -1
};
// 含有重复元素 查找最后一个小于等于给定值的元素
var search = function(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] <= target) {
      if (mid === nums.length - 1 || nums[mid + 1] > target) {
        return mid
      }
      left = mid + 1
    }
  }
  return -1
};

33.搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

需要注意的细节很多很多，一般看着官方题解和代码，慢慢调试才写了出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
var search = function(nums, target) {
  let left = 0,right = nums.length - 1, n = nums.length;
  if (!n) {
    return -1;
  }
  if (n == 1) {
      return nums[0] == target ? 0 : -1;
  }
  while(left <= right){
    // 两种写法都能过
    const mid = (right + left) >> 1;
    const mid = left + ((right - left) >> 1);
    if(nums[mid] === target){
      return mid
    }else if(nums[left] <= nums[mid]){
      // 细节一，必须保证target 在左右区间
      // 普通二分法 只需要一个就够了，那是因为target 必然在有序的left-right之间
      // 细节二 小于等于 等于不能忘
      if(nums[mid] > target && nums[left] <= target){
        right = mid - 1
      }else{
        left = mid + 1
      }
    }else{
      if(nums[mid] < target && target <= nums[right]){
        left = mid + 1
      }else{
        right = mid - 1
      }
    }
      
  }
  return -1
};

167.两数之和 II - 输入有序数组

给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

自己的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var twoSum = function(numbers, target) {
  const l = numbers.length;
  for(let i = 0; i<l-1;i++){
    const result = getIndex(i+1, target - numbers[i]);
    if(result){
      return result
    }
  }
  function getIndex(i, target){
    let left = i, right = l - 1;
    while(left <= right){
      const mid = left + ((right - left) >> 1);
      if(numbers[mid] === target) {
        return [i, mid+1]
      }else if(numbers[mid]>target){
        right = mid - 1
      }else{
        left = mid +1
      }
    }
  } 
};

稍微优化了一下，把函数体放入循环里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var twoSum = function(numbers, target) {
  const l = numbers.length;
  for(let i = 0; i<l-1;i++){
    const result = target - numbers[i];
    let left = i+1, right = l - 1;
    while(left <= right){
      const mid = left + ((right - left) >> 1);
      if(numbers[mid] === result) {
        return [i+1, mid+1]
      }else if(numbers[mid]>result){
        right = mid - 1
      }else{
        left = mid +1
      }
    }
  }
};

​