马谦的博客 – 第 11 页

二分查找及扩展

2020 年 2 月 10 日作者马谦马谦马谦

一、二分查找

template<typename T>
int bin_search(const T data[], int left, int right, T target) {
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (data[mid] > target) {
            right = mid - 1;
        } else if (data[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

template<typename T>

int bin_search(const T data[], int left, int right, T target) {

int mid;

while (left <= right) {

mid = (left + right) / 2;

if (data[mid] > target) {

right = mid - 1;

} else if (data[mid] < target) {

left = mid + 1;

} else {

return mid;

}

return -1;

}

二、查找最后一个小于 n 的值

// 查找第一个大于目标的元素
template<typename T>
int bin_search_first_greater(const T data[], int left, int right, T target) {
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (data[mid] > target) {
            if (mid == left || data[mid - 1] < target)
                return mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

// 查找第一个大于目标的元素

template<typename T>

int bin_search_first_greater(const T data[], int left, int right, T target) {

int mid;

while (left <= right) {

mid = (left + right) / 2;

if (data[mid] > target) {

if (mid == left || data[mid - 1] < target)

return mid;

right = mid - 1;

} else {

left = mid + 1;

}

return -1;

}

三、查找第一个大于 n 的值

template<typename T>
int bin_search_last_less(const T *data, int left, int right, T target) {
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (data[mid] < target) {
            if (mid == right || data[mid + 1] > target)
                return mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

template<typename T>

int bin_search_last_less(const T *data, int left, int right, T target) {

int mid;

while (left <= right) {

mid = (left + right) / 2;

if (data[mid] < target) {

if (mid == right || data[mid + 1] > target)

return mid;

left = mid + 1;

} else {

right = mid - 1;

}

return -1;

}

四、查找第一个等于 n 的值 [cra ... 阅读更多

[leetcode]344-反转字符串

2020 年 2 月 10 日作者马谦马谦马谦

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-string 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。一、题目描述编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形 ... 阅读更多

[leetcode]7-整数反转

2020 年 2 月 10 日作者马谦马谦马谦

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-integer 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。一、题目描述给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。示例： ... 阅读更多

[leetcode]138-复制带随机指针的链表

2020 年 2 月 10 日2020 年 2 月 9 日作者马谦马谦马谦

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。一、题目描述给定一个链表，每个节点包含一个额外增加的随机指针，该 ... 阅读更多

《剑指 offer 》面试题 35：复杂链表的复制

2020 年 2 月 9 日作者马谦马谦马谦

一、题目描述请实现函数 complex_list_node *clone_list(complex_list_node *head)，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的随机节点或 nullptr 。节点的 C++定义如下： [ ... 阅读更多

[leetcode]19-删除链表的倒数第 N 个节点

2020 年 2 月 9 日作者马谦马谦马谦

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。一、题目描述给定一个链表，删除链表的倒数第 n 个节点，并 ... 阅读更多

《剑指 offer 》面试题 22：链表中的倒数第 k 个节点

2020 年 2 月 9 日作者马谦马谦马谦

一、题目输入一个链表，输出该链表中倒数第 k 个节点，为了符合大多数人的习惯，k 的序号从 1 开始，即链表的尾结点是倒数第一个节点。例如，如下链表中的倒数第 3 个节点是 3：二、解题思路使用快慢指针，快指针先走 n 步，然后快慢指针同时走，直到快指针为 null，慢指针就是倒数第 n 个节点。以上面的链表为例， ... 阅读更多

[leetcode]303-区域和检索（数组不可变）

2020 年 2 月 9 日作者马谦马谦马谦

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/range-sum-query-immutable 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。一、题目描述给定一个整数数组 nums，求出数组从索引 i 到 j (i ... 阅读更多

[leetcode]704-二分查找

2020 年 2 月 9 日作者马谦马谦马谦

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。一、题目描述给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜 ... 阅读更多

[leetcode]276-栅栏涂色

2020 年 2 月 9 日作者马谦马谦马谦

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/paint-fence 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。一、题目描述有 k 种颜色的涂料和一个包含 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