LeetCode训练|LeetCode初级算法训练-排序和搜索(完成) LeetCode训练|Java

简介
上一篇 : LeetCode初级算法训练-树
下一篇 : LeetCode初级算法训练-动态规划
本来想重初中级和企业面试算法开始的，但是最后还是选择从基础的开始，因为我们并不是为了刷题而刷题，而是在刷题过程中锻炼一种算法思维，在大量的训练之后形成一种对算法的独特见解，培养那种对算法的的敏感度，看到题目，大脑中可以浮现一个解题蓝图，而且从初级开始慢慢建立信心，而且这也是在为后边复杂算法的解题思路打基础。
LeetCode初级算法简介
如果你也想训练自己的算法思维，也可以加入我，从初级算法开始，开启你的算法之旅：初级算法。
自己的一些思考：不要在看完题目后直接就看答案，然后去背题，这样行成的算法记忆是不牢固的，一定要有自己的思考；而且不要一开始就在IDEA上边去写，一定试着自己在leetCode提供的白板上边写一遍最后在放到IDEA上边去执行看有什么问题，以便巩固你的基础API的使用和熟练度；还有一点就是大胆些，不是面试我们试错成本低，尽可能把我们的想法融入到代码中
因篇幅问题，博客中只列出示例和自己的解题答案，详细可以直接点击题目查看。
合并两个有序数组给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
这边
第一种方式比较容易想到但是时间复杂度比较慢。没有利用两个数据有序的特点。

class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { System.arraycopy(nums2, 0, nums1, m, n); Arrays.sort(nums1); } }

第二种方式是创建一个新数组把nums1的数据移到nums3中，用双指针比对两个数组中的数据插入到nums1中，最后把剩下的数据copy到nums1中。

class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int[] nums3 = new int[m]; System.arraycopy(nums1, 0, nums3, 0, m); int p = 0; int p1 = 0, p2 = 0; while (p1 < m && p2 < n) { nums1[p++] = nums3[p1] <= nums2[p2] ? nums3[p1++] : nums2[p2++]; }if (p1 < m) System.arraycopy(nums3, p1, nums1, p1 + p2, m + n - p1 - p2); if (p2 < n) System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2); } }

第一个错误的版本第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 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 left = 1; int right = n; while(left < right) { int mid = left + (right - left) / 2; if(isBadVersion(mid)){ right = mid; } else{ left = mid + 1; } } return left; }}

22 / 22 个通过测试用例
状态：通过
执行用时：16 ms
内存消耗：36.6 MB
【LeetCode训练|LeetCode初级算法训练-排序和搜索(完成)】二分都用了 16ms更何况从头开始遍历。