专栏首页算法工程师之路二分问题-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

本文分享自微信公众号 - 算法工程师之路(Zleopard7319538),作者:TeddyZhang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • gcd,哈希问题-LeetCode 357、355、365、367、380

    给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n 。

    算法工程师之路
  • 最大堆,DP问题-LeetCode 373 374 376 377 605(DP,最大堆)

    给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。 定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums...

    算法工程师之路
  • 数字问题-LeetCode 524、525、526、528、530、537、539、540

    LeetCode # 524 525 526 528 530 537 539 540

    算法工程师之路
  • 洛谷P3355 骑士共存问题

    题目描述 在一个 n*n个方格的国际象棋棋盘上,马(骑士)可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍,骑士不得进入 ? 对于给定的 n*n 个方格的国...

    attack
  • 二分查找总结

    二分查找是在每次匹配后,将查找的空间一分为二的算法,二分查找应该是有序的数组进行查找.

    用户7625070
  • 洛谷P4632 [APIO2018] New Home 新家(动态开节点线段树 二分答案 扫描线 set)

    问题转化为对于所有\(a_i \leqslant y_i \leqslant b_i\)的商店,\((x - mid, x + mid)\)内是否所有类型的商店...

    attack
  • Java常用排序算法/程序员必须掌握的8大排序算法

    1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基数排序)

    哲洛不闹
  • 程序员必知的8大排序(java实现)

    8种排序之间的关系: ?  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要...

    小帅丶
  • 序列比对(九)从掷骰子说起HMM

    前面八篇文章介绍了动态规划在序列比对中的基础应用。从本文开始,开始介绍HMM(隐马尔可夫模型)。为什么要介绍它呢?因为该模型在发现Motif、预测CpG岛等多方...

    一只羊
  • 挑战程序竞赛系列(79):4.3 2-SAT(3)

    挑战程序竞赛系列(79):4.3 2-SAT(3) 传送门:POJ 2723: Get Luffy Out 题意: 题目意思有点坑,实际上给出每一对钥匙,如...

    用户1147447

扫码关注云+社区

领取腾讯云代金券