网站模板下载百度云链接怎么做,陈木胜谢霆锋,室内设计在线网站,电气工程WordPress模板二分查找
69. x 的平方根
给你一个非负整数 x #xff0c;计算并返回 x 的 算术平方根 。 由于返回类型是整数#xff0c;结果只保留 整数部分 #xff0c;小数部分将被 舍去 。 注意#xff1a;不允许使用任何内置指数函数和算符#xff0c;例如 pow(x, 0.5) 或者 x **…二分查找
69. x 的平方根
给你一个非负整数 x 计算并返回 x 的 算术平方根 。 由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。 注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1 输入x 4 输出2 示例 2 输入x 8 输出2 解释8 的算术平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。 提示
0 x 231 - 1
class Solution {
public:int mySqrt(int x) {int l 0, r x, ans -1;while (lr) {int mid l (r-l)/2;if ((long long) mid * mid x) {ans mid;l mid 1;} else {r mid - 1;}}return ans;}
};4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (mn)) 。 示例 1 输入nums1 [1,3], nums2 [2] 输出2.00000 解释合并数组 [1,2,3] 中位数 2 示例 2 输入nums1 [1,2], nums2 [3,4] 输出2.50000 解释合并数组 [1,2,3,4] 中位数 (2 3) / 2 2.5
class Solution {
public:int getKthElement(const vectorint nums1, const vectorint nums2, int k) {int m nums1.size();int n nums2.size();int index1 0, index2 0;while (true) {// 边界情况if (index1 m) {return nums2[index2 k - 1];}if (index2 n) {return nums1[index1 k - 1];}if (k 1) {return min(nums1[index1], nums2[index2]);}// 正常情况int newIndex1 min(index1 k / 2 - 1, m - 1);int newIndex2 min(index2 k / 2 - 1, n - 1);int pivot1 nums1[newIndex1];int pivot2 nums2[newIndex2];if (pivot1 pivot2) {k - newIndex1 - index1 1;index1 newIndex1 1;}else {k - newIndex2 - index2 1;index2 newIndex2 1;}}}double findMedianSortedArrays(vectorint nums1, vectorint nums2) {int totalLength nums1.size() nums2.size();if (totalLength % 2 1) {return getKthElement(nums1, nums2, (totalLength 1) / 2);}else {return (getKthElement(nums1, nums2, totalLength / 2) getKthElement(nums1, nums2, totalLength / 2 1)) / 2.0;}}
};611. 有效三角形的个数
给定一个包含非负整数的数组 nums 返回其中可以组成三角形三条边的三元组个数。 示例 1: 输入: nums [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3 示例 2: 输入: nums [4,2,3,4] 输出: 4
class Solution {
public:int triangleNumber(vectorint nums) {int n nums.size();sort(nums.begin(), nums.end());int ans 0;for (int i 0; i n - 2; i) {for (int j i1; j n-1; j) {int l j1, r n-1, kj;while (l r) {int mid (r-l)/2 l;if (nums[mid] nums[i] nums[j]) {k mid;l mid 1;}else {r mid - 1;}}ans k-j;}}return ans;}
};
