6-10 DSA

问题集

  • 如何编程实现“求一个数的平方根”?要求精确到小数点后 6 位
  • 搜索旋转排序数组 leetcode T33

问题1

如何编程实现“求一个数的平方根”?要求精确到小数点后 6 位

解答

采用二分法的思想

  • 将此数除2
  • 比较 余数相乘 和 原来的数
  • 继续除2…直到逼近精确度

问题2

搜索旋转排序数组 leetcode 第33题

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。

解答

思路:先拆分两个有序数组 依次进行二分查找
实现:

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
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.empty()) {
return -1;
}
int second_backup = 0, second = 0, low = 0, high = nums.size() - 1;
for (int i = 0; i < high; i++) {
if (nums[i] > nums[i+1]) {
second = second_backup = i+1;
break;
}
}
while (low <= second_backup) {
int mid = low + ((second_backup - low) >> 1);
if (nums[mid] > target) {
second_backup = mid - 1;
} else if (nums[mid] < target) {
low = mid + 1;
} else {
return mid;
}
}
while (second <= high) {
int mid = second + ((high - second) >> 1);
if (nums[mid] > target) {
high = mid -1;
} else if (nums[mid] < target) {
second = mid + 1;
} else {
return mid;
}
}
return -1;
}
};
# DSA

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×