我要分享技术
0%

ARTS-4

发表于 更新于 分类于

RTS第四周

Algorithm

Search in Rotated Sorted Array ### 引言 本周leetcode的推送又是一道easy难度的题目, 还是一个使用二分查找来解决的简单猜数问题, 本着要进步的想法, 做完了那道题, 但是感觉没什么可分享的点, 于是顺延之前解决的问题的顺序做了本题。

Description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

有一个已经升序排列的数组, 从其中一个元素的位置给他截断, 然后移动拼接, 成为新的数组, 就是按照元素为单位对数组进行循环移位。

思路

一看到这个题目, 二分搜索马上出现在脑海里, 后来一分析, 貌似行不通, 因为一般的二分搜索只能处理单调的数组(这个位置我被自己蠢哭了)。

这个问题的关键是, 第一次进行取mid操作时, mid落在哪个区间, 如图 (sorry, oos 到期了, 待更换):

  • 当 mid 落于左半边时, 记它为midl,否则,记为midr。若v[mid]恰等于target, 则查找结束。
  • 当 mid = midl , 此时mid落于左半边, 典型特征为 v[mid] > v[left] 此时, 再以一般的二分法判断该如何移动left和right指针即可, 此时, 若目标小于v[mid] 且大于v[left] 则 right指针左移, 否则left指针右移。
  • 当 mid = midr, 此时mid落于右半边, 典型特征为 v[mid] < v[left] 此时, 以一般二分判断移动指针, 若target < v[mid]且target < v[right] 则左移right 否则, 右移left。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0, right=nums.size()-1;
        while(left<=right){
            int mid=(left+right)/2;
            if (nums[mid]==target) return mid;
            if (nums[mid]>=nums[left]) {    // mid is midl
                if (target>=nums[left]&&target<=nums[mid]) {
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }else{                          // mid is midr
                if (target>=nums[mid]&&target<=nums[right]){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }
        }
        return -1;
    }
};

Result

Status Runtime Memory Language
Accepted 4 ms 8.6 MB cpp

Review

引言

本周review文章来自medium的一次每日推送, 高亮文章为 "被你所不知道的追踪器填满的手机App", 我平时使用手机也比较洁癖, 一个app如果要求我授权一个我认为它不需要的权限我是坚决不给的, 我宁可不用这个app, 这里就不得不说各政府部门外包给三流公司做的官方app了, 各种权限要求一大堆, 包括位置、电话短信、通讯录 什么的, 我就纳闷了,你一个公积金管理的app要这些权限干啥!!!

所以, 当我第一眼看见这个题目的时候, 确认过眼神, 就是它了。 Your Smartphone Apps Are Filled With Trackers You Know Nothing About

文章主旨

  • 我们使用手机App大多收集了各种各样的传感器数据和用户行为数据。
  • 手机app的崩溃日志可能带有大量其他的信息。
  • 即使开发者无意使用和收集这些数据,但是他们继承的各种SDK无时无刻不在做这些工作。

Tips

Lua的代理模型

引言

最新一个资料片要上一个跨服的好友功能, 之前我们已经有一个本服务器的好友功能了, 其实现是在玩家进行登录的时候将所有好友信息推送给客户端, 每当添加一个好友时,也将好友信息推送给客户端保存, 这样, 客户端可以即时的展示好友的界面和功能。 新的功能要求玩家可以跨服务器添加好友, 这样一来, 如果要做到在玩家登陆时推送好友信息, 那么玩家所属服务器或者中心服务器必须去各个服务器拉取好友信息,然后统一推送给玩家, 但是这个方案很复杂, 涉及到很多的拉取同步问题。

所以, 我设计新的方案, 在玩家登陆时, 只发送玩家的好友id和服务器id给客户端, 当客户端需要展示ui的时候再去目标服务器拉取, 然后展示。

之前思虑不周, 等新的好友模块都做完了, 才发现, 一些其他的模块对好友模块的数据有依赖, 它们没有去拉取再显示, 而是直接从好友模块中去取数据, 所以, 报空异常了。 稍微统计了一下, 这样的ui有很多很多, 单靠我挨个去改动是忙不完的。

此时, 一个牛逼的同事提出了他的解决方案(实际上之前他就说过, 但是我没在意), 使用一个代理的模式, 其他模块拿去数据的时候返回给他一个代理的包装对象, 此时好友模块再去动态的拉取信息, 响应回来后, 再去使用事件机制更新ui。

本技巧, 就是这个方案的实现。

原方案伪代码

1
2
3
4
5
--[[
    这是最早的代码, 本地缓存了好友数据, 所以, 可以直接拉取到好友数据, 用以UI显示
]]
    local friendinfo = friendmodule.getFriendInfo(friendid)
    ui.panelXXX:Show(friendinfo)

基于之前的功能需求,这样做无可厚非, 也是最简易的做法, 但是这个方案给后面功能的拓展埋下了坑,再增加跨服支持的时候需要修改大量的内容。

我改过后好友模块相关ui的实现伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
--[[
    修改后的代码, 尝试去从好友模块获取数据, 若存在,则跟之前一样用, 若不存在, 那么去请求数据, 然后在回调中重新渲染ui
]]

    local friendinfo = friendmodule.getFriendInfo(friendid)
    if friendinfo then
        ui.panelXXX:Show(friendinfo)
    else 
        friendmodule.queryFriendFromServer(friendid, function() -- callback function
            friendinfo = friendmodule.getFriendInfo(friendid)
            ui.panelXXX:Show(friendinfo)
        end)
    end

这个做法基本实现了新的功能要求, 而且基于懒加载节省了大多数时候不必要的内存消耗(实际游戏中, 玩家大多数的时候整个游戏过程都不会开好友ui), 但是, 这个修改需要改动的位置非常多, 几乎所有涉及到好友数据的ui都需这么改, 几乎无可避免会出现遗漏。

代理方案

1
2
3
4
5
--[[
    这是最早的代码, 本地缓存了好友数据, 所以, 可以直接拉取到好友数据, 用以UI显示
]]
    local friendinfo = friendmodule.getFriendInfo(friendid)
    ui.panelXXX:Show(friendinfo)

简单从上面伪代码看来,我们并没有做任何的更改。 确实, 因为这个方案就是为了减少我第二个方案的复杂度来做的。 实际上friendmodule.getFriendInfo这个函数的实现做了修改, 它所返回的不再是一个 "rawdata"了, 而是一个代理对象wrapper。

原先的实现: 

1
2
3
friendmodule.getFreindInfo = function(friend)
    return data[friend]
end

修改后的实现

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
wrapper = { data = {}}
wrapper.new = function(id) 
    local instance = { __data={}}
    setmetatable(instance, {__index = function(table, key)
        local res = instance.__data[key]
        if res then
            return res;
        end
        return rawget(table, key)
    end})
    friendmodule.queryFriendFromServer(id, function(callbackdata) -- callback 
            instance.__data = callbackdata
            eventsystem.redraw()
        end)
    return instance
end

friendmodule.getFreindInfo = function(friend)
    local friendinfo = data[friend]
    if not friendinfo then
        local res = warpper.new(friend)
        data[friend] = res
        return res
    end
    return friendinfo
end

Share

引言

本次本来想分享我自己写的关于java语言的锁同步的一些总结, 但是在写另一篇博文的时候, 我尝试向博文里添加几个流程图, 我使用draw.io画好了图, 但是同事告诉我markdown本身可以画流程图, 没想到它这么强大, 临时改成本次分享一篇半官方的帮助指南, 介绍markdown的各种特性和功能。

正文

MarkDown语法介绍