一、278题：第一个错误的版本，难度：简单
1、题目描述
/**
* 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
*
* 假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
*
* 你可以通过调用bool isBadVersion(version)接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
* 示例 1：
*
* 输入：n = 5, bad = 4
* 输出：4
* 解释：
* 调用 isBadVersion(3) -> false
* 调用 isBadVersion(5)-> true
* 调用 isBadVersion(4)-> true
* 所以，4 是第一个错误的版本。
*
* 来源：力扣（LeetCode）
* 链接：https://leetcode.cn/problems/first-bad-version
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
2、个人解法
二分查找法
执行用时：21 ms, 在所有 Java 提交中击败了14.02%的用户
内存消耗：38 MB, 在所有 Java 提交中击败了89.85%的用户
public int firstBadVersion(int n) {
int low=1,high=n;
while (low<=high){
int mid=low+(high-low)/2;
System.out.println("low:"+low+",mid:"+mid+",high:"+high+","+isBadVersion(mid));
if (isBadVersion(mid)){
high=mid-1;
}else if (!isBadVersion(mid)){
low=mid+1;
}
}
return low;
}
public boolean isBadVersion(int version){
return version >= 2;
}
3、官方解法
public int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) { // 循环直至区间左右端点相同
int mid = left + (right - left) / 2; // 防止计算时溢出
if (isBadVersion(mid)) {
right = mid; // 答案在区间 [left, mid] 中
} else {
left = mid + 1; // 答案在区间 [mid+1, right] 中
}
}
// 此时有 left == right，区间缩为一个点，即为答案
return left;
}
public boolean isBadVersion(int version){
return version >= 2;
}
二、744题：寻找比目标字母大的最小字母，难度：简单
1、题目描述
/**
* 给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母target，请你寻找在这一有序列表里比目标字母大的最小字母。
*
* 在比较时，字母是依序循环出现的。举个例子：
*
* 如果目标字母 target = 'z' 并且字符列表为letters = ['a', 'b']，则答案返回'a'
*
* 示例 1：
*
* 输入: letters = ["c", "f", "j"]，target = "a"
* 输出: "c"
* 示例 2:
*
* 输入: letters = ["c","f","j"], target = "c"
* 输出: "f"
* 示例 3:
*
* 输入: letters = ["c","f","j"], target = "d"
* 输出: "f"
*
* 来源：力扣（LeetCode）
* 链接：https://leetcode.cn/problems/find-smallest-letter-greater-than-target
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
2、个人解法
二分查找法-右边界问题
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.7 MB, 在所有 Java 提交中击败了68.05%的用户
public char nextGreatestLetter(char[] letters, char target) {
int low = 0, high = letters.length - 1;
if (letters[high] <= target) {
return letters[0];
}
while (low < high) {
int mid = low + (high - low) / 2;
System.out.println(low + "," + mid + "," + high + "," + letters[mid]);
if (letters[mid] <= target) {
low = mid + 1;
} else if (letters[mid] > target) {
high = mid;
}
}
return letters[high];
}
3、官方解法
三、第350题：两个数组的交集||，难度：简单
1、题目描述
/**
* 给你两个整数数组nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
*
* 示例 1：
*
* 输入：nums1 = [1,2,2,1], nums2 = [2,2]
* 输出：[2,2]
* 示例 2:
*
* 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
* 输出：[4,9]
*
* 来源：力扣（LeetCode）
* 链接：https://leetcode.cn/problems/intersection-of-two-arrays-ii
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
2、个人解法
暴力解法，双层循环
执行用时：2 ms, 在所有 Java 提交中击败了95.12%的用户
内存消耗：41.3 MB, 在所有 Java 提交中击败了83.00%的用户
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
int len1 = nums1.length, len2 = nums2.length;
List<Integer> list = new ArrayList<>();
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
if (nums1[i] == nums2[j]) {
list.add(nums1[i]);
nums1[i] = -1;
nums2[j] = -1;
break;
}
}
}
int[] nums = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
nums[i] = list.get(i);
}
return nums;
}
}
3、官方解法
解法1：哈希表法
解法2：排序后双指针（快慢指针）法
四、第367题：有效的完全平方根，难度：简单
1、题目描述
/**
* 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
*
* 进阶：不要 使用任何内置的库函数，如sqrt 。
*
* 示例 1：
*
* 输入：num = 16
* 输出：true
* 示例 2：
*
* 输入：num = 14
* 输出：false
*
* 来源：力扣（LeetCode）
* 链接：https://leetcode.cn/problems/valid-perfect-square
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
2、个人解法
二分查找法
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.2 MB, 在所有 Java 提交中击败了64.12%的用户
public boolean isPerfectSquare(int num) throws InterruptedException {
if (num == 1) {
return true;
}
int low = 1, high = num;
while (low < high) {
int mid = low + (high - low) / 2;
if (mid > 46340 || mid * mid > num) {//num为int，因此不会大于2^31，它的平方根不会大于46340
high = mid;
} else if (mid * mid < num) {
low = mid + 1;
} else {
return true;
}
System.out.println(mid);
}
return false;
}
3、官方解法
解法1：平方根函数
解法2：暴力解法
解法3：二分查找法
大于等于2,147,395,600的时候，个人解法二分查找更有优势，小于它的时候，一样
public boolean isPerfectSquare(int num) {
int left = 0, right = num;
while (left <= right) {
int mid = (right - left) / 2 + left;
long square = (long) mid * mid;
if (square < num) {
left = mid + 1;
} else if (square > num) {
right = mid - 1;
} else {
return true;
}
}
return false;
}
解法4：牛顿迭代法
public boolean isPerfectSquare(int num) {
double x0 = num;
while (true) {
double x1 = (x0 + num / x0) / 2;
if (x0 - x1 < 1e-6) {
break;
}
x0 = x1;
}
int x = (int) x0;
return x * x == num;
}
五、第704题：二分查找，难度：简单
1、题目描述
/**
* 给定一个n个元素有序的（升序）整型数组nums 和一个目标值target ，写一个函数搜索nums中的 target，如果目标值存在返回下标，否则返回 -1。
*
*
* 示例 1:
*
* 输入: nums = [-1,0,3,5,9,12], target = 9
* 输出: 4
* 解释: 9 出现在 nums 中并且下标为 4
* 示例2:
*
* 输入: nums = [-1,0,3,5,9,12], target = 2
* 输出: -1
* 解释: 2 不存在 nums 中因此返回 -1
*
* 来源：力扣（LeetCode）
* 链接：https://leetcode.cn/problems/binary-search
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
2、个人解法
二分查找
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.9 MB, 在所有 Java 提交中击败了72.94%的用户
class Solution {
public int search(int[] nums, int target) {
int len=nums.length;
int low=0,high=len;
while(low<high){
int mid=low+(high-low)/2;
if(target==nums[mid]){
return mid;
}else if(target<nums[mid]){
high=mid;
}else{
low=mid+1;
}
}
return -1;
}
}
3、官方解法
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
int num = nums[mid];
if (num == target) {
return mid;
} else if (num > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
六、第441题：排列硬币，难度：简单
1、题目描述
2、个人解法
解法1：暴力解法
执行用时：12 ms, 在所有 Java 提交中击败了7.52%的用户
内存消耗：39.3 MB, 在所有 Java 提交中击败了7.22%的用户
class Solution {
public int arrangeCoins(int n) {
int s=0;
for(int i=1;i<=n;i++){
s=s+i;
if(s>n||s<0){
return i-1;
}else if(s==n){
return i;
}
}
return 0;
}
}
3、官方解法
