二分问题-LeetCode 69、167、92（二分，牛顿法，双指针）
二分问题-LeetCode 69、167、92（二分，牛顿法，双指针）
二分，牛顿法：LeetCode #69 167 92
1
编程题
【LeetCode #69】x 的平方根
实现 int sqrt(int x) 函数。 计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1: 输入: 4 输出: 2
牛顿法： 首先对f(x)进行二阶泰勒展开，即f(x)=f(x0)+f'(x0)(x-xo), 在求解平方根问题时，f(x)=x^2-a. 接着令f(x)=0, 从而得到 x = (x0+a/x0)/2, 一直循环迭代即可！ 二分法： 略略略
（牛顿迭代法）
class Solution {
public:
int mySqrt(int x) {
long r = x;
while(r*r > x){
r = (r + x/r) / 2;
}
return r;
}
};（二分法）
class Solution{
public:
int mySqrt(int x){
return binary(0, x, x);
}
int binary(long left, long right, int x){
long mid;
while(left <= right){
mid = left + (right - left) / 2;
if(mid * mid > x)
right = mid - 1;
else if(mid * mid < x)
left = mid + 1;
else
return mid;
}
if(left * left <= x)
return left;
else
return left - 1;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sqrtx
【LeetCode #167】两数之和 II - 输入有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。 说明:
- 返回的下标值（index1 和 index2）不是从零开始的。
- 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例: 输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
解题思路：
双指针的问题，从数组两端开始向中间查找！很简单的思路！
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int l = 0, r = numbers.size()-1;
vector<int> res(2, 0);
while(l < r){
int sum = numbers[l] + numbers[r];
if(sum == target){
res[0] = l + 1;
res[1] = r + 1;
break;
}else if(sum < target){
l++;
}else{
r--;
}
}
return res;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
【LeetCode #92】反转链表 II
反转从位置 m 到 n 的链表。 说明: 1 ≤ m ≤ n ≤ 链表长度。
示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL
解题思路：
一个数值序列的反转可以使用堆栈很轻松的实现，因此可以从链表头部开始遍历，并记录遍历个数，当个数在[m, n]范围内时，将对应链表的节点的val值压入到堆栈中，然后再重新从头遍历结点，修改对应范围的值即可！
一次遍历的方法有点绕，这里就不说了！！！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
stack<int> sta;
long i = 0;
ListNode *tmp = head;
while(tmp != nullptr){
i++;
if(m <= i && i <= n)
sta.push(tmp->val);
tmp = tmp->next;
}
i = 0;
tmp = head;
while(tmp != nullptr){
i++;
if (m <= i && i <= n){
tmp->val = sta.top();
sta.pop();
}
tmp = tmp->next;
}
return head;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
腾讯云开发者
