《数据结构与算法之美》16～20笔记

2019-10-15  本文已影响0人  太阳骑士索拉尔

关于我的仓库

前言

16讲二分查找（下）：如何快速定位IP对应的省份地址

变体一：查找第一个值等于给定值的元素

503c572dd0f9d734b55f1bd12765c4f8 
// 变体一：查找第一个值等于给定值的元素[hard]
int BinarySearchXH(vector<int> &arr, int value) {
    
    int len = arr.size();
    int left = 0;
    int right = len - 1;
    int mid = left + ((right - left) >> 1);
    while (left <= right) {
        mid = left + ((right - left) >> 1);
        if (arr[mid] >= value) {
            right = mid - 1;
        } else {
            left = mid + 1;
        } 
    }
    
    if (left < len && arr[left] == value) {
        return left;
    } else {
        return -1;
    }
}
// 其实这种做法也没有那么难理解，只是对arr[mid] = value的情况将它视作没找到，继续进行二分
// 就和上一章总结的那样，如果出现的是return right会返回最接近那个，这里使用的是return left返回的就是第一个了

// 变体一：查找第一个值等于给定值的元素[easy]
int BinarySearchXE(vector<int> &arr, int value) {
    
    int len = arr.size();
    int left = 0;
    int right = len - 1;
    int mid = left + ((right - left) >> 1);
    while (left <= right) {
        mid = left + ((right - left) >> 1);
        if (arr[mid] > value) {
            right = mid - 1;
        } else if (arr[mid] < value) {
            left = mid + 1;
        } else {
            if ((mid == 0) || (arr[mid - 1] != value)) {
                return mid;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}

// 没啥好说的，很简单就是对与找到的mid不一定是第一个，遥往前找
// 这里其实找到一个一直往前推也可以，当然这样慢了，没有二分的优越性了

变体二：查找最后一个值等于给定值的元素

// 变体二：查找最后一个值等于给定值的元素
int BinarySearchY(vector<int> &arr, int value) {
    
    int len = arr.size();
    int left = 0;
    int right = len - 1;
    int mid = left + ((right - left) >> 1);
    while (left <= right) {
        mid = left + ((right - left) >> 1);
        if (arr[mid] > value) {
            right = mid - 1;
        } else if (arr[mid] < value) {
            left = mid + 1;
        } else {
            if ((mid == len - 1) || (arr[mid + 1] != value)) {
                return mid;
            } else {
                left = mid + 1;
            }
        }
    }
    
    return -1;
}

变体三：查找第一个大于等于给定值的元素

// 变体三：查找第一个大于等于给定值的元素
int BinarySearchZ(vector<int> &arr, int value) {
    
    int len = arr.size();
    int left = 0;
    int right = len - 1;
    int mid = left + ((right - left) >> 1);
    while (left <= right) {
        mid = left + ((right - left) >> 1);
        if (arr[mid] >= value) {
            if ((mid == 0) || (arr[mid - 1] < value)) {
                return mid;
            } else {
                right = mid - 1;
            }
        } else {
            left = mid + 1;
        }
    }   
    return -1;
}

变体四：查找最后一个小于等于给定值的元素

// 变体四：查找最后一个小于等于给定值的元素
int BinarySearchZA(vector<int> &arr, int value) {
    
    int len = arr.size();
    int left = 0;
    int right = len - 1;
    int mid = left + ((right - left) >> 1);
    while (left <= right) {
        mid = left + ((right - left) >> 1);
        if (arr[mid] > value) {
            right = mid - 1;
        } else {
            if ((mid == len - 1) || (arr[mid + 1] > value)) {
                return mid;
            } else {
                left = mid + 1;
            }
        }
    }
    
    return -1;
}

开篇题目：如何快速定位出一个IP地址的归属地？

[202.102.133.0, 202.102.133.255]  山东东营市 
[202.102.135.0, 202.102.136.255]  山东烟台 
[202.102.156.34, 202.102.157.255] 山东青岛 
[202.102.48.0, 202.102.48.255] 江苏宿迁 
[202.102.49.15, 202.102.51.251] 江苏泰州 
[202.102.56.0, 202.102.56.255] 江苏连云港

课后题：LeetCode 33 搜索旋转有序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < nums[right]) {
                if (nums[mid] < target && nums[right] >= target) left = mid + 1;
                else right = mid - 1;
            } else {
                if (nums[left] <= target && nums[mid] > target) right = mid - 1;
                else left = mid + 1;
            }
        }
        return -1;
    }
};

17讲跳表：为什么Redis一定要用跳表来实现有序集合

理解跳表

e18303fcedc068e5a168de04df956f6d 14753c824a5ee4a976ea799727adc78e 492206afe5e2fef9f683c7cff83afa65 46d283cd82c987153b3fe0c76dfba8a9

跳表的优越性

d03bef9a64a0368e6a0d23ace8bd450c

跳表的操作

65379f0651bc3a7cfd13ab8694c4d26c a861445d0b53fc842f38919365b004a7

解答开篇：为什么Redis中的有序集合是通过跳表来实现的

课后题：在今天的内容中，对于跳表的时间复杂度分析，我分析了每两个结点提取一个结点作为索引的时间复杂度。如果每三个或者五个结点提取一个结点作为上级索引，对应的在跳表中查询数据的时间复杂度是多少呢？

18讲散列表（上）：Word文档中的单词拼写检查功能是如何实现的

92c89a57e21f49d2f14f4424343a2773

散列函数

散列冲突

开放寻址法

5c31a3127cbc00f0c63409bbe1fbd0d5 9126b0d33476777e7371b96e676e90ff fe7482ba09670cbe05a9dfe4dd49bd1d

链表法

a4b77d593e4cb76acb2b0689294ec17f

解答开篇：Word文档中单词拼写检查功能是如何实现的？

课后题

假设我们有10万条URL访问日志，如何按照访问次数给URL排序？

有两个字符串数组，每个数组大约有10万条字符串，如何快速找出两个数组中相同的字符串？

19讲散列表（中）：如何打造一个工业级水平的散列表

散列函数设计

装载因子过大

67d12e07a7d673a9c1d14354ad029443 6d6736f986ec4b75dabc5472965fb9cb

解决冲突的方法

103b84d7173277c5565607b413c40129

以Java中的HashMap为例看工业级别的散列表实现

20讲散列表（下）：为什么散列表和链表经常会一起使用

LRU缓存淘汰算法

eaefd5f4028cc7d4cfbb56b24ce8ae6e

Redis有序集合

Java LinkedHashMap

17ac41d9dac454e454dcb289100bf198 fe313ed327bcf234c73ba738d975b18c

课后题

今天讲的几个散列表和链表结合使用的例子里，我们用的都是双向链表。如果把双向链表改成单链表，还能否正常工作呢？为什么呢？

猎头系统设计

上一篇 下一篇

猜你喜欢

热点阅读