ARTS 第一周打卡

Algorithm : 做一个 leetcode 的算法题

1.只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

思路：线性时间复杂度(O(n) –> 排除简单的双重for循环！！！)

不使用额外的空间(O(1) –> 排序hash、数组下标等做法！！！ )

解题思路一：除了某个元素只出现一次以外，其余每个元素均出现两次；根据这条特性，可以想到 ^= 算法(相同为假，不同为真)！

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int iRes = ;
        for(int i = ; i < nums.size(); i++)
        {
            iRes ^= nums[i];
        }        return iRes;
    }
};

解题思路二：先排序，然后比较步长为2之间的元素

class Solution {
public:
    int singleNumber(vector<int>& nums) {        //方法一：这里算不算用额外的空间
        std::sort(nums.begin(), nums.end());
        for(int i = ; i < nums.size(); i += )
        {
            if(i +  >= nums.size() || nums[i] != nums[i + ])
            {
                return nums[i];
            }
        }
        return ;
    }
};

Review : 阅读并点评一篇英文技术文章

原文地址：https://redis.io/

Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache and message broker.

Redis是一个开源(BSD许可)的内存数据结构存储，用作数据库、缓存和消息代理；

It supports data structures such as strings, hashes, lists, sets, sorted sets with range queries, bitmaps, hyperloglogs, geospatial indexes with radius queries and streams.

它支持诸如字符串、hash散列表、集合、带范围查询的排序集合、位图、hyperloglogs、带半径查询和流的地理空间索引等数据结构。

Redis has built-in replication, Lua scripting, LRU eviction, transactions and different levels of on-disk persistence, and provides high availability via

Redis Sentinel and automatic partitioning with Redis Cluster. Learn more →

Redis具有内置的复制、Lua脚本、LRU清除、事务和不同级别的磁盘持久性、和通过Redis Sentinel(哨兵)和Redis CLuster(Redis 集群)的自动分区提供高可用性。

备注：

1.hyperloglogs：

1.1 原文链接：https://redis.io/topics/data-types-intro

HyperLogLogs

A HyperLogLog is a probabilistic data structure used in order to count unique things (technically this is referred to estimating the cardinality of a set).

HyperLogLog 是一种概率数据结构，用于计算唯一的东西(技术上这是指估算集合的基数)；

Usually counting unique items requires using an amount of memory proportional to the number of items you want to count, because you need to remember the elements you have already seen in the past in order to avoid counting them multiple times.

通常计算唯一项要求使用与要计算的项数成比例的内存，因为需要记住在过去已经见过的元素以避免重复计算；

However there is a set of algorithms that trade memory for precision: you end with

an estimated measure with a standard error, which in the case of the Redis implementation is less than 1%.

然而这里有一种内存换精度的算法：你以一个标准误差的估计度量结束，在redis实现中，标准误差小于1%；

The magic of this algorithm is that you no longer need to use an amount of memory proportional to the number of items counted, and instead can use a constant amount of memory! 12k bytes in the worst case, or a lot less if your HyperLogLog (We’ll just call them HLL from now) has seen very few elements.

这个算法的神奇之处在于：不在需要与计算项等比例的内存，可以使用固定的内存，最坏的情况下是12k byte,然后HLL会看到少了很多元素；

HLLs in Redis, while technically a different data structure, are encoded as a Redis string, so you can call GET to serialize a HLL, and SET to deserialize it back to the

server.

在Redis中， HLLs虽然在技术上是一种不同的数据结构，但是它被编码为redis string,所以你可以使用GET 序列化HLL，使用SET反序列化到服务器上；

2.LRU清除:

什么是LRU算法？ LRU是Least Recently Used的缩写，即最近最少使用，常用于页面置换算法，是为虚拟页式存储管理服务的。

LRU原理和Redis实现：https://zhuanlan.zhihu.com/p/34133067