[TOC]
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
class Solution {
public int mySqrt(int x) {
if (x <= 1) {
return x;
}
int low = 0, high = x;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (mid > x / mid) {
high = mid - 1;
} else {
if ((mid + 1) > x / (mid + 1)) {
return mid;
} else {
low = mid + 1;
}
}
}
return low;
}
}给定一个只包含小写字母的有序数组letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。
数组里字母的顺序是循环的。举个例子，如果目标字母target = 'z' 并且有序数组为 letters = ['a', 'b']，则答案返回 'a'。
示例:
输入:
letters = ["c", "f", "j"]
target = "a"
输出: "c"
输入:
letters = ["c", "f", "j"]
target = "c"
输出: "f"
输入:
letters = ["c", "f", "j"]
target = "d"
输出: "f"
输入:
letters = ["c", "f", "j"]
target = "g"
输出: "j"
输入:
letters = ["c", "f", "j"]
target = "j"
输出: "c"
输入:
letters = ["c", "f", "j"]
target = "k"
输出: "c"
注:
letters长度范围在[2, 10000]区间内。
letters 仅由小写字母组成，最少包含两个不同的字母。
目标字母target 是一个小写字母。
class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int low = 0, high = letters.length - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (letters[mid] > target) {
if (mid == 0 || letters[mid - 1] <= target) {
return letters[mid];
} else {
high = mid - 1;
}
} else {
low = mid + 1;
}
}
return letters[0];
}
}给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:
输入: [1,1,2,3,3,4,4,8,8] 输出: 2 示例 2:
输入: [3,3,7,7,10,11,11] 输出: 10 注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
class Solution {
public int singleNonDuplicate(int[] nums) {
int low = 0, high = nums.length - 1;
int n = nums.length;
for (int i = 0; i < n; ) {
if (i != n - 1 && nums[i] == nums[i + 1]) {
i = i + 2;
} else {
return nums[i];
}
}
return 0;
}
}class Solution {
public int singleNonDuplicate(int[] nums) {
int low = 0, high = nums.length - 1;
while (low < high) {
int mid = low + ((high - low) >> 1);
if (mid % 2 == 1) {
mid--;
}
if (nums[mid] == nums[mid + 1]) {
low = mid + 2;
} else {
high = mid;
}
}
return nums[low];
}
}你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int low = 1, high = n;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (isBadVersion(mid)) {
if (isBadVersion(mid - 1)) {
high = mid - 1;
} else {
return mid;
}
} else {
low = mid + 1;
}
}
return 0;
}
}把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2] 输出：1 示例 2：
输入：[2,2,2,0,1] 输出：0
class Solution {
public int minArray(int[] numbers) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (numbers[mid] < numbers[right]) {
right = mid;
} else if (numbers[mid] > numbers[right]) {
left = mid + 1;
} else {
right--;
}
}
return numbers[left];
}
}给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
先二分查找找到第一个等于target，然后直接遍历找最后一个位置
class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return new int[]{-1, -1};
}
int n = nums.length;
int low = 0, high = n - 1;
while (low < high) {
int mid = low + ((high - low) >> 1);
if (nums[mid] > target) {
high = mid - 1;
} else if (nums[mid] == target) {
high = mid;
} else {
low = mid + 1;
}
}
int first = low;
int second = first;
if (nums[first] != target) {
return new int[]{-1, -1};
}
if (first == n - 1) {
return new int[]{first, first};
}
for (int i = first + 1; i < n; i++) {
if (nums[i] == nums[first]) {
second = i;
} else {
break;
}
}
return new int[]{first, second};
}
}还有一种方式，分别二分查找到第一个位置和最后一个位置，代码类似，不再写啦。