ARTS-8

Algorithm

引言

按照之前没有完成的题目顺序往下找的。

Description

题目

38. Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

大意

count-and-say (数-说)序列大意是这样的, 给出一个数字, 数数连续数字有几个, 然后写出 count-num , 例如 1 就是 1个1, 那么, 写作 11, 它是2个1, 那么下一项为21, 再下一项为1个2和1一个1, 即为1211 .... 如此这般。

思路

这种问题思路就很清晰了, 有一个起始条件, 每一个后续项都依赖于前一项, 典型的递归解决思路, 稍复杂就用DP, (最高效的方式应该是按照索引找规律, 到那时这个题目我没找到什么明显规律) 那么, 这个题目甚简单, 就直接简单递归即可。

Code

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

class Solution {
public:
    string countAndSay(int n) {
        if (n==1) 
            return "1";
        
        string res = "";
        string r = countAndSay(n-1);
        char lastC = r[0];
        int remainSize = 0;
        for (auto c : r) {
            if (lastC==c) {
                remainSize += 1;
            } else {
                res.append(1, (char)(remainSize+'0'));
                res.append(1, lastC);
                lastC = c;
                remainSize = 1;
            }
        }
        res.append(1, (char)(remainSize+'0'));
        res.append(1, lastC);
        return res;
    }
};

Result

Success Details 

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Count and Say.

Memory Usage: 9.1 MB, less than 38.74% of C++ online submissions for Count and Say.

Review

暂缺

Tips

暂缺

Share

引言

本次内容是我自己写的, 因为前几天生病,这次准备仓促,还只是写了一半, 后面一半还没写出来, 先发一半吧, 下次把后面一半补上

Synchronized

End

ARTS-7

Algorithm

Sudoku Solver

引言

上回, ARTS-5 做了一个验证sudoku是否有效的题目, 本题是它的后续。

Description

37. Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. Empty cells are indicated by the character '.'.

A sudoku puzzle...

...and its solution numbers marked in red.

Note:

The given board contain only digits 1-9 and the character '.'. You may assume that the given Sudoku puzzle will have a single unique solution. The given board size is always 9x9

大意

前面的分享已经介绍过数独游戏, 本次题目提供一个未完成的数组, 其中未填充的数字使用字符.来填充。

我们的解决方案需要替换原数组中的., 使数独结构成立, 假设题目给出的数组都只有唯一解。

思路

首先最容易想到的就是最简单直接的解法, 本科阶段学习数据接口课程, 对于栈和递归这两个章节都拿数独举过例子。数独的解法和迷宫一样, 都是一个简单直接的栈结构, 一个个放入尝试, 如果成立则递归解下一个单元格, 否则则退回上一步重新放置一个上一步的数字再试。

解法 1

这里先使用了最直接的解法, 我实现了cpp和java两个版本的方案, 这里贴出一个java版本的方案, 因为后面还继续讨论一下jvm对于这个情况的优化。

第一段代码

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
32
33
34
35
36

public class Solution {
    public void solveSudoku(char[][] board) {
        solveNext(board);
    }
    
    public boolean solveNext(char[][] board){
        for(int row = 0; row < 9; row++){
            for(int col = 0; col < 9; col++){
                if(board[row][col] == '.'){
                    for(char c = '1'; c <= '9'; c++){
                        if(!canSet(board, row, col, c)) continue;   //check if can set c
                        board[row][col] = c; 
                        if(!solveNext(board))
                            board[row][col] = '.';  //rollback if failed
                        else
                            return true; 
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean canSet(char[][] board, int row, int col, char c){
        int brow = row /3 * 3;
        int bcol = col /3 * 3;  // recaculate the block's begin position
        for(int i = 0; i < 9; i++) {
            if(board[i][col] != '.' && board[i][col] == c) return false; 
            if(board[row][i] != '.' && board[row][i] == c) return false; 
            if(board[brow + i / 3][ bcol + i % 3] != '.' && 
                board[brow + i / 3][bcol + i % 3] == c) return false; 
        }
        return true;
    }
}

第二段代码

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
32
33
34
35
36
37
38

public class Solution {
    public void solveSudoku(char[][] board) {
        solveNext(board, 0, 0);
    }
    
    private boolean solveNext(char[][] board, int row, int col){
        for(; row < 9; row++){
            for(; col < 9; col++){
                if(board[row][col] == '.'){
                    for(char c = '1'; c <= '9'; c++){
                        if(!canSet(board, row, col, c)) continue;
                        board[row][col] = c; 
                        if(!solveNext(board, row, col))
                            board[row][col] = '.'; 
                        else
                            return true; 
                    }
                    return false;
                }
            }
            col = 0;
        }
        return true;
    }
    
    private boolean canSet(char[][] board, int row, int col, char c){
        int brow = row /3 * 3;
        int bcol = col /3 * 3;
        for(int i = 0; i < 9; i++) {
            if(board[i][col] != '.' && board[i][col] == c) return false; 
            if(board[row][i] != '.' && board[row][i] == c) return false; 
            if(board[brow + i / 3][ bcol + i % 3] != '.' && 
                board[brow + i / 3][bcol + i % 3] == c) return false; 
        }
        return true;
    }
}

贴出一个c++的代码对比

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
32
33
34
35
36
37
38

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solveNextStep(board);
    }
    
private:  
    bool solveNextStep(vector<vector<char>>& board) {
      for (int row = 0; row < 9; ++row) {
        for (int column = 0; column < 9; ++column) {
          if (board[row][column] != '.') continue;
          for (char iv = '1'; iv <= '9'; ++iv) {
            if (isValid(board, row, column, iv)) {
              board[row][column] = iv;
              if (solveNextStep(board))
                return true;
              else
                board[row][column] = '.';
            }
          }
          return false;
        }
      }
      return true;
    }
  
    static bool isValid(const vector<vector<char>>& board, int row, int col, char c) {
      int brow = row/3*3;
      int bcol = col/3*3;
      for (int i=0; i<9; ++i) {
        if (board[row][i]!='.' && board[row][i]==c) return false;
        if (board[i][col]!='.' && board[i][col]==c) return false;
        if (board[brow + i/3][bcol + i%3] !='.' && board[brow + i/3][bcol + i%3]==c) return false;
      }
      return true;
    }
};

Result 1

其中, 第一行结果对应上面代码的第二段。 第二行结果对应上面结果的第一段。我本来是想稍微进行一点优化(虽然我知道这个"优化"聊胜于无), 反而结果更糟糕了, 下面我会分享一下我的猜想。

C++ 代码上在内存用量上完胜(这个应该是由于java基于jvm, 额外消耗了更多内存吧), 但是在执行时间上cpp代码完败, 猜想应该是由于cpp的标准vector类的实现问题, 和无法基于profiling 做编译时优化而造成的劣势。 针对cpp代码, 我也做了同样的传递行列参数的优化, 但是执行时间上和未优化的版本完全一致。

分析总结

我虽然提供了可以AC的答案, 但是这个答案应该是最基础的, 跟"好答案"相去甚远, 这个解法真的是对不起"Hard"这个难度。至于更优秀的解决方案, 后面我去看看讨论区大佬有什么精彩解法。

这里, 我只讨论我这两段代码, 为什么"优化"后的代码反而表现更差。 看上面的贴图相差无几, 也许可能纯粹认为是偶发的误差导致的, 但是, 我在本地机器上使用JMH反复做了测试, 结果依然如此。

猜想

这里可能涉及到一个jvm层面的优化, 可能jvm针对固定的计数循环使用了"循环展开"和"向量化"的优化技术。(这里我参考了循环优化和向量化), 由于第二种方法,我通过参数设置了循环开始条件,破坏了固定的循环计数, 导致即时编译器无法采用优化, 反而导致了运行效率更低。

对比cpp代码的两个方案, 两个代码执行时间基本一致, 所以我觉得这个java代码的差异应该就是由于编译时的优化失败导致的。

Review

JavaScript Fundamental: Prototypal Inheritance

JavaScript 基本规则 : 原型式继承

引言

本周的review内容依然来自于Medium Daily Digest, 就随缘吧, 哪天我开始写review了, 就直接使用哪天的digest了, 当然, 我绝对不是每周只读这一篇。 然后, 本篇较短。

内容

JavaScript的原型式继承

首先, 我写JavaScript并不多, 偶尔写两句。

作为JavaScript开发者, 理解JavaScript的继承的工作原理是必备知识, 面试尤其得心应手, 今天, 我来说道说道JavaScript实现的继承的优缺点。

下面的内容为原文翻译 原文链接

What is an inheritance?

什么是继承?

继承是面向对象编程的四个基本概念之一, (四个概念是: 抽象, 封装, 继承, 多态), 继承可以使一个对象获取另一个已存在的对象的属性。

Does JavaScript have inheritance?

JavaScript支持继承吗?

当然, JavaScript使用一个叫做原型式继承的类型, 它与类似Java语言的经典继承模型有很大差别。

What is prototypal inheritance?

什么是原型继承?

要搞明白原型继承, 我们先要搞明白原型链, 原型链是每个对象与其原型之间的一系列联系，它以某种方式充当“父对象”(通过原型)，直到链到达null的引用。 此外，可以使用__proto__手动设置对象的原型。举个栗子:

1
2
3
4
5
6
7
8
9
10

const vehicle = {
    numWheels: 4
}
const car = {
    numDoors: 4
}
// Setting vehicle as car object's prototype
car.__proto__ = vehicle
console.log(car.numWheels)
=> 4

card对象本身不包含numWheels属性, 但是, 当我们设置vehicle对象作为它的prototype属性, car.numWheels 取值为4, 在原型式继承中, 如果一个属性在原对象中不存在, JavaScript(执行引擎)将会通过原对象的prototype属性开始递归的搜索目标属性,直到找到目标属性,或者对象的prototype属性为null为止。

Good or bad?

优缺点

• Good 优点
  1. 简单直接
  2. 更适合JavaScript的动态特性本质
  3. 代码冗余度低 (ps. 我表示并没有低的明显)
• Bad 缺点
  1. 习惯于经典继承模型的人难以掌握(例如Java)
  2. JavaScript的原型继承使用构造函数模式，对象继承自另一个对象的构造函数，而不是整个对象类型，我(作者)认为它更符合原型继承试图实现的目标。
  “I was under marketing orders to make it look like Java but not make it too big for its britches. It’s just this sort of silly little brother language, right? The sidekick to Java.” -- Brandan Eich (Creator of JavaScript)

Tips

在生产环境的机器上,尤其是低配置机器,不要尝试去打开查看或者处理大文件

引言

本次Tips特别简单,真的, 它是一个警告, 只有一句话。如上

讲个故事

基于我国国情, 每一个通过域名可以访问的国内服务器(80和8080端口)都必须经过备案, 否则不可能访问通, 所以, 我购买了一个处于国外机房的vps(对, 我从不通过它访问谷歌, 那是违法的)。

本着钻研和学习的精神, 我在上面运行了一个 ss 进程, 用它来搭建代理, 提供我公司研发网络的穿透, 以便我可以在下班忘记打卡的时候可以在家里打卡下班(对, 不用来翻墙, 那样做违法)。

某天, 我又回到了家, 熟练的打开了teamviewer, 连上工位的机器, 签退页面打开, 看看还差五分钟就又满一小时了(多工作没有加班费, 我就是贱), 想着再等我分钟退吧。

正好某视频网站源码被我clone了一份在这个vps上, 而且压了一个压缩包准备下到本地, 然后手贱了一个view命令给到了压缩包上。

然后teamviewer熟练的断开了, 一查, 果然ss进程被oom关闭了, 工位上的机器teamviewer只会重试一次, 果然我没能在这个时间内重启, 于是, 考勤异常了。

相关知识

Linux的内存管理机制, 当linux内核发现可用内存不足时, 会通过3种途径来回收内存

• 基于 LRU（Least Recently Used）算法, 回收缓存
• 基于 Swap 机制，回收不常访问的匿名页
• 基于 OOM（Out of Memory）机制，杀掉占用大量内存的进程。

我的故事里, ss 进程被杀死就是第三种途径在产生效果。

第三种方式，OOM 机制按照 oom_score 给进程排序。oom_score 越大，进程就越容易被系统杀死。

当然了，如果你不希望应用程序被 OOM 杀死，可以调整进程的 oom_score_adj，减小 OOM分值，进而降低被杀死的概率。

或者，你还可以开启内存的 overcommit，允许进程申请超过物理内存的虚拟内存（这儿实际上假设的是，进程不会用光申请到的虚拟内存）。

上面机制的内容引自倪朋飞发表在极客时间的课程, 版权文章, 阅读完成版可能需要付费。

Share

微软最爽命令行工具发布！引诱开发者叛逃Mac，开源六小时冲上GitHub第二

我竟然分享的是一篇软文, 没错, 它击中了部分我对ide和开发环境的幻想, 即使它是一篇软文, 我仍旧期待。在此分享, 给所有ide洁癖者。

End

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

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语法介绍

RTS-3 第三周

Review an introduction of to principles of Functional Programming

函数式编程规约简介

标题如是，这是一篇关于函数式编程的入门级别的简介文章。作者同样提供了一篇基于JavaScript的解说。

回顾

长时间使用面向对象的编程语言工作和学习后，是时候用几个步骤来回顾一下系统复杂度了。

复杂性是软件难遇理解和维护的全部原因。

函数式编程是什么

函数式编程是一种编程范式，一种构建计算机程序和元素的风格，它将计算视为数学上函数，并避免了状态变化和可变数据。-- wiki 

纯函数

纯函数是函数式编程中第一个重要概念，那么。 #### 纯函数是什么

纯函数首先是一个函数，它具有两个基本特征： 1. 多次执行，给定相同的参数必然得到相同的结果。 2. 执行中，不会带来可以观察到的副作用状态改变。

纯函数的优势

纯函数易于测试，它的特征决定了对于这类程序的测试简单有效。

不变性

不变性是函数式编程的又一重要特性，很直观。数据一旦创建就永不可更改。 对于多年沉浸面向对象变成的程序员易于理解，就是所有的数据都是const数据，同时感到不可思议。

如文中提到的，一旦数据创建后不可变，那么，像非函数式语言中的for each 循环该如何实现呢？ 在函数式编程范式中，循环使用递归来实现。这里不展开讲述。

引用透明性

基本上，如果一个函数对相同的输入始终产生相同的结果，那么它就是引用透明的。

pure functions + immutable data = referential transparency

在这个前提下, 许多类似 (+3(+ 5 8)) 一类的表达式, 就会直接优化为它的常量结果, 因为他们总是不变的。

函数式一等公民

函数式编程范式中, 函数不止作为函数, 它也被视为一个值, 当做一个数据来用。(个人认为类似于C语言中的函数, 实际上函数指针也可以这么用, 只是在语言和语法层面是体现的不明显)

高阶函数

什么是高阶函数

高阶函数首先要是一个函数, 其次, 得满足两个特点至少其中之一: 1. 参数列表中至少含有一个函数类型的形参。 2. 它的返回值是一个函数。

When we talk about higher-order functions, we mean a function that either: 1.takes one or more functions as arguments, or
2.returns a function as its result

未尽之言

以上可能我自己也摸不着头脑,但是我已经把大意总结了一下, 剩下的未尽之言都是作者写了一些琐碎处的细节, 举例子贴代码来阐明的自己的观点, 这个我不好总结, 总之, 大意如此, 这是一篇函数式编程的入门文章, 浅显易懂, 深入浅出, 从未接触过函数式编程语言的我读后收益匪浅, 确实的开阔了眼界和思维。

Algorithm: First Bad Version

引言

本周就做了两道leetcode题目, 要分享的这个题目来源于Leetcode的Weekly Digest, 它试一次邮件推送。 easy难度, 给我个easy的题目,大概是leetcode都认为我比较水。

原始邮件:

Hi earneet,

We have an easy question that we thought you might be interested in solving:

First Bad Version
Solved 211443 times
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of...

First Bad Version

Description

278. First Bad Version
Easy

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version. 

假设我是一个项目管理, 正在领导一个开发团队做一个新产品, 不幸的是我的项目出了问题, 但不知道是哪个版本, 我的版本号管理是从1开始的自增升序, 我有个验证api isBadVersion(version)来验证当前版本是好的还是坏的, 问: 通过最少次的验证来找到第一个坏掉的版本, 应该怎么做。

思路

这是一个数组的查找问题, 从一堆版本号构成的数组[1,2,3,4 ... n]中,找到第一个符合要求的索引。 这个情况非常熟悉了, 如果这个数组是关于索引有规律的, 那么我们可以通过哈希计算获得位置, 如果是有顺序的,也可以通过二分查找来加快搜索。 乍一看, 这个数组符合第二个情况, 但是, 版本号并不是我们直接要找的目标值,它需要经过一次api调用的转换来达到目标数组。

好在, 这个题目还有个隐含的条件, 在某一个出错版本, 也就是我们的目标之前的所有版本, 都是正确的, 在这个版本之后, 都是错误的, 我可以映射好版本结果为0,而坏版本结果为1,那么原数组就被转换为了 [0, ... m, 1 ... n] 其中 m >= 0 且 m <= n。 至此已经完成了升序数组的转换。

这个题目与一般查找稍有差异, 它当中存在了大量的重复元素(它本来就只有两种元素), 我需要找到目标元素的第一次出现的位置。这里,基本可以确定是二分法查找没错了, 继续分析如何进行二分。

1. middle位置的结果为0。 此种情况下, 数组部分应为如 [...,0, 0, 0, 1, 1 ...], 粗体位置为middle,红色元素分别为left和right, 这种情况下, 应把left指针右移。使 left从当前middle的下一个元素迭代。
2. middle位置的结果为1。 此种情况下, 数组部分应为[...,0, 0,1, 1, 1, 1 ...], 粗体位置为middle,红色元素分别为left和right, 这种情况下, 应当将right指针左移,从当前middle元素位置开始迭代。

如此, 二分的迭代规则已经明确了, 剩下的问题就是代码实现了。

Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        register int min = 1;
        while (min <= n) {
          register int middle = min + (n-min)/2;
          if (isBadVersion(middle)){
            n = middle - 1;
          } else {
            min = middle + 1;
          }
        }
        return min > n ? min : n;
    }
};

当我写这个篇文的时候才发现, 可能以上代码虽然被AC了, 但是可能是错误的, 简略先记一下我发现的问题, 后面会更正本文。

为了更快速地迭代,我在指针移动时, 指针略过已经试过的当前middle元素, 如果是左移,则使 right = middle - 1, 若为右移, 则使 left = middle + 1, 若如此做, 一个尴尬的问题就来了, 这样可能恰好错过了目标解, 就如 [...,0, 0, 0, 1, 1, 1, 1 ...] 这种情况, right指针左移时, 下次的位置应为左侧第二个0, 现在, 目标解已经脱出了我们的 left和right指针范围!!

以上这段, 使我写本文时才发现, 夜深了, 先记在这里, 明后天想明白了之后再更正。

Tip 尽早失败,短流程优先

引言

本次分享的尽早失败是我在乐天派工作的时候, 项目组杨老师传授给我的经验,在后面的工作中屡试不爽, 特作一个分享, 完整的技巧不止于此, 在本篇中, 只分享其中的一个小点, 在条件语句中优先失败。这个技巧在很多的IDE中应该都会有提示, 但是项目代码里还是常见不遵循这个的代码, 我并不是说不这么写一定不好, 但是个人还是倾向于尽早失败, 让代码结构更加清晰。

尽早失败

不管新手还是老鸟, 在项目中总会看到如下面这样的代码

1
2
3
4
5
6
7
8
9
10
11
12
13

function () {
    // do something pre
    if (checkcondition1) {
        // do something 1
        if (checkcondition2) {
            // do something 2
            if (checkcondition3) {
                // do something3
            }
        }
    }
    return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

function () {
    // do something pre
    if (checkcondition0){
        for () {
            if (checkcondition1) {
                // do something 1
                if (checkcondition2) {
                    // do something 2
                    if (checkcondition3) {
                        // do something3
                    }
                }
            }
        }
    }
    return result;
}

这里我针对第二个代码, 做一个"尽早失败"的风格修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

function () {
    // do something pre
    if (not checkcondition0)
        return;
    for () {
        if (not checkcondition1) 
            continue;
        // do something 1
        if (not checkcondition2) 
            continue;
        // do something 2
        if (not checkcondition3)
            continue;
        // do something3
    }
    return result;
}

这个写法, 使的原先代码尾部一连串难以搞懂层级的}不见了, 缩进层级由6层, 缩减到了3层, 整个代码都条理了。

这就是杨老师传授的所谓的"尽早失败"技巧的其中一个应用, 在编写条件分支时,尽量不使用但条件的 if (true) dosomething 这样的分支, 而是使用 if (not true) return; dosometing 这样的分支, 这样会大大的减少代码的缩进层级。

短流程优先

还是不管新手还是老鸟, 在项目中总会看到如下面这样的代码

1
2
3
4
5
6
7
8
9
10
11
12
13

if (condition) {
    // do operation 1
    // do operation 2
    if (condition2) {
        // do operation 3
    } else {
        // do operation 4
    }
    // do operation 5
} else {
    // log a message 
    return;
}

这种情况下, 单单使用上面说的尽早失败进行修改虽然也可以, 但是牵扯到了其他分支内也有有用操作, 貌似还是差点意思。所以, 这里倾向于"短流程优先", 即写为:

1
2
3
4
5
6
7
8
9
10
11
12

if (not condition) {
    // log a message 
    return;
} 
// do operation 1
// do operation 2
if (condition2) {
    // do operation 3
} else {
    // do operation 4
}
// do operation 5

杨老师传授加上我自己琢磨的针对这个的技巧不止如上, 本篇先分享这一些, 后面再分享时将剩下一些总结一下补充来。

Share

引言

本来预计的分享又又又又又未能完成。

本次的分享源于我打算做的一个东西, 我之前有一块某米品牌的安卓平板, 由于我已经更新换代了设备,这个旧设备已经很久不用, 所以我打算把它改为一个便携显示器用来接ps4玩游戏, 所以ps4主机是比较封闭的, 输出我能够接入的只有hdmi接口, 要么我选择采购昂贵的视频采集卡来做,要么我只好研究下hdmi传输标准, 看看能不能做个硬件来做一下信号转换, 把hdmi信号编解码, 通过usb或者wifi传输给平板, 再在平板上解码输出, 于是,我翻阅了不少hdmi资料, 特分享一则讲的比较浅显的前辈的文。 ### 内容 HDMI协议

Flag

我个人做java开发比较多, 之前就想写一篇文来讲明白jvm中synchonize和volatile的实现,但是各种原因一直未能成行, 再次立一个Flag, 在劳动节前ARTS中, share分享部分我要分享我的这篇文, 我一定要在期限内完成。

这是第三周的ARTS篇

Algorithm

引子

本周这篇算法是一个Medium难度的Leetcode题目, 我从之前没有做的题目中随机选了一道题目。无特别原因, 其中的规律考虑了半个小时之后才发现, 中间有事情耽搁,大概从看题目到AC经过了两天。 题目 Next Permutation。

先展示下成果

Success
Details 
Runtime: 8 ms, faster than 100.00% of C++ online submissions for Next Permutation.
Memory Usage: 8.6 MB, less than 100.00% of C++ online submissions for Next Permutation.

Description

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

即为, 给定一个整数数列, 看做一个排列, 求出比它大的下一个字典序的排列。如果它已经是最大的了, 那么就给出最小的字典序序列。 题目里给出了几个例子, 比较通俗好懂。

思路

这个题目的点应该是找规律, 如何排列才是下一个大的字典序列。

这里, 分两种情况讨论:

• 给出的序列已经是最大字典序列了:
  这种情况很好理解, 要满足这个条件,那么给出的序列中的单值最大的数字一定占最高位(就是最前面), 次大的数字占据次高位 ... 依次递推, 很容易判断是否是最大的序列, 而这个特点也使的处理这种情况简单高效, 只需要翻转序列即可。所以,这种情况不再讨论。
• 给出的序列不是最大的字典序列。依照上一点, 如果一个序列不是最大序列,那么从高位开始遍历它时, 则必然会出现后值大于前值的情况, 即 a[i] < a[i+1], 若交换这两个值,那么字典序必然变大。

那么, 思路转换为将后面更大的值前移, 这样只是保证了字典序变大, 而如何使之为 变大的幅度最小 这个目标实现, 需要再分析。

我考虑一下权重影响, 高位自然权重更大, 不管低位怎么变化, 只要高位变动, 低位的变动就不影响结果了, 所以, 这个调节, 应该从低位开始。就如 我有序列 12345, 如果我调节高位,编程 21345 肯定比调节低位 12354 变化更大, 所以, 从低位开始着手准没错。

正常是顺序序列应该是从最低位往最高位依次单值递减的, 那么如果出现有低位比高位单值低的情况, 这个位置就应该是突破点, 在这个位置上换上一个比这个值稍微大一点的值, 序列的字典序就变大了!!! 问题依旧在,这个操作之后, 不能保证恰好就能是比前一个字典序刚好大一点的值, 这个时候, 得对这个位之后的序列进行重排, 使它是升序的,这样就是满足条件最小的了。总结一下: 从后往前看, 在出现后值小于前值的点, 交换一个这个点后面的比当前值大的最小值, 然后重排这个位置之后的序列。 依照这个规则,写一个代码实现:

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
32
33
34

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if (nums.size()==1)
          return ;
        const int size = nums.size();
        int i=size-2;
        for (; i>=0; i--) {
          if (nums[i] < nums[i+1]) {
            break;
          }
        }
        int chIndex = i;
        int chValue = nums[i];
        if (i<0) {
          std::reverse(nums.begin(), nums.end());
          return ;
        }
        int minCanChange = nums[chIndex + 1];
        int minCanIndex = chIndex;
        for (i = chIndex + 1; i < size; ++i) {
          if (nums[i] > chValue && nums[i] <= minCanChange) {
            minCanChange = nums[i];
            minCanIndex = i;
          }
        }
      
        int t = nums[chIndex];
        nums[chIndex] = nums[minCanIndex];
        nums[minCanIndex] = t;
        std:sort(nums.begin()+chIndex+1, nums.end());
        return ;
    }
};

这个代码是初版, 看起来还有很多的优化的空间, 后面我会再优化一版。

Review

本次Review的内容是一篇叫做 The Mistakes I Made As a Beginner Programmer - Learn to identify them, make habits to avoid them (作为新手程序员我所犯的错)

引言

我是一个有着七年工作经验的"老"程序员了, 至少, 不能算是一个新人, 但是,有一些错误在工作和学习中还是"不可避免"的发生了,甚至,有一些错误是新人的常见错误, 所以,在Medium推送给我这么一篇文章的时候, 我觉得我被深深的吸引了,忍不住要把它发出来大家共勉。 也许这不是一篇规范review, 我打算把它的主旨简略翻出来, 以供警醒。

文章主旨

Let me make one thing clear first. If you are a beginner programmer, this article is not meant to make you feel bad about the mistakes that you might be making but rather to make you aware of them, teach you to spot signs of them, and remind you to avoid them.

I have made these mistakes in the past and learned from each and every one of them. I am happy to have formed coding habits to help me avoid them. You should do too.

译: 首先让我们搞清楚一件事情, 如果你是个新手程序员,本文并不是让你来觉得因犯这些错误而有不好的感觉,而是教你了解它们, 发现它们的迹象, 从而避免它们。

我过去曾犯过这些错误,并且从它们每一个当中学到东西。我很高兴能形成编码习惯让我避免犯这些错, 希望你也能。

作者以上这个观点,同样是本文的观点。

These mistakes are not presented here in any particular order

以下错误并不以特定顺序呈现

没有计划的写代码

High-quality written content, in general, cannot be created easily. It requires careful thinking and research. High-quality programs are no exception.

高质量的写错内容通常不易创造, 它要求深思熟虑和仔细的验证, 高质量的程序亦然如此。

Writing quality programs is a process with a flow: 
** Think. Research. Plan. Write. Validate. Modify. **

编写高质量的程序是一个这样的流式的过程: 思考, 研究, 计划, 写, 验证, 修改。 但是并没有这样一个首字母的缩略词汇, 你需要自己去创建始终遵循这个活动的习惯。

作为新人我犯过的重要错误之一, 就是没有经过思考和调查就开始码代码, 这对于小程序还好, 但是对于大型的程序, 它有严重的负面影响。

写代码前计划太多

Yes. Planning before jumping into writing code is a good thing, but even good things can hurt you when you do too much of them. Too much water might poison you.

在开始码代码之前做计划是一件好事儿, 但是, 好事过量也可能伤害你, 就像喝水太多会中毒。

看起来这条跟第一条自相矛盾, 不过, 总结来说就是太多不好,太少也不好, 在每个功能点上进行计划, 不要对整体完整进行规划即可。 所谓的瀑布模型即如此。

低估了代码质量的重要性

If you can only focus on one aspect of the code that you write, it should be its readability. Unclear code is trash. It is not even recyclable.

如果你仅能关注你写的代码的其中一项, 那么它一定是代码可读性, 不清楚的代码就是垃圾, 它甚至不可回收。

不得不说, 作为一只工作多年的老鸟,这个错误我还是经常犯, 有自己的原因,但是更多是因为项目进度逼迫。国内环境常常是项目管理者将程序员的加班时长也计划在正常工作时间内来计划项目进度,而且并不能将出现问题而攻关的时间计算在内, 所以, 在一切管理者没有意料到的意外而产生的额外时间消费都只能由程序员买单, 这样导致了程序员在写完自己的功能时, 只要通过了测试就不再理会,更别说modify这个过程, 而通常, 业务变动, 程序员限于时间,都只能采用打补丁的方式解决, 导致了代码进一步不可读。 当然, 由于程序员个人的原因也是有的, 对代码质量的过分不重视, 导致程序员在完成测试后就认为工作已经结束,留下了质量低下的代码。

作者给出了自己的格言:

Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live.

总是要认为最终维护你代码的人是一个知道你住在哪里的精神病患者。

另一个简单的条目是过长行任何的超过80个字符的行将导致代码更难以阅读。许多类似的问题都可以通过工具来解决。

选取最初的方案

新手程序员急于求成, 当遇到问题, 想到一个可能的解决方案时,立即投入编码, 一旦验证通过, 那么这几乎就是最终的方案了, 不会考虑到其中的风险利弊。

所以, 程序员当想出一个解决方案后,应该多想想其他的解决方案,从其中对比利弊, 选出"最简单"的方案来实现。这里最简单指的是, 在能够满足正确性和性能要求的前提下,尽可能的实现简单,可读性强,可维护性高。

不放弃

原文为"Not Quitting", 直译为"不戒烟", 对于这个错误上这是个非常形象贴切的词汇, 但是为了更加直接明了,我还是使用不放弃作为本错误的标题。

有时候, 在一个方案开始做了之后马上意识到它并不是"最简单"的防范, 也能相处一个更优秀的方案, 但是就是不愿意放弃它,还以老方案把它做完。 不放弃可能放到大多数地方都是一个好习惯,但是不适合在编程领域。编程领域的优秀习惯是尽快失败和经常失败。

不搜索

原文为"Not Googling", 鉴于国内的环境, 这个词在这里明显是不合适的, 改换为不搜索。 在寻找解决方案的时候,一味的蛮干, 浪费了太多的时间在这上面, 枉顾网上已经有很多成熟并且优秀的方案。 除非你做的是边缘技术, 否则都应该先搜索一下看看, 至少, 能从中受到启发和避免踩一些他人已经趟过的坑。

不封装

这个错误不仅仅限于和针对面向对象编程, 在其他的范式下, 封装这个概念依然很有帮助, 不封装通常会导致系统难以维护。

为未知做计划

It is often tempting to think beyond the solution that you are writing. All sort of what-ifs will pop into your head with every line of code that you write. This is a good thing for testing edge cases, but it is just wrong to use as a driver for potential needs.

在你写作的时候，人们往往倾向于超越解决方案去思考。在你写的每一行代码中，所有的“如果”都会突然出现在你的脑海中。这对于测试边缘用例来说是一件好事，但是将它用作潜在需求的驱动程序是错误的。

这确实是一个我也犯过的严重的错误, 很多时候自己意识不到,或者并不承认是一个错误, 因为在写一个方案的时候,总认为考虑方方面面时候一件好事,然而恰恰是这个"好习惯"使我做了大量的无用功, 写了很多根本用不到的代码, 当时还安慰自己"如果需求变成这样", 而事实证明了, 百分之九十九的这些准备都用不上, 而他可能使我比预期多花了一倍的时间来完成。

使用不正确的数据结构

作者在这章的观点我无法全部赞同, 作者强调程序开发人员对于数据结构优缺点的掌握要生于对算法的掌握。我还未能达到作者的高度, 但我认为,这二者应该同等重要, 数据结构还是要配合算法来使用才是正道。

后面几节略过

因为作者针对这篇文章写了大量的内容, 一时吸收不了, 后面几节我将来补充。

后言

当我完成这篇读后感的时候, 本文内容已经被更新, 并已经收入作者新书中, 最新的内容我没有查阅, 还是仅以作者文章初版作为依据。最新内容在本文开始已经给出了链接, 诸位读着可自行查阅。

Tip

原打算写一个自己的心得技巧, 看本周的工作安排我知道我没有时间了, 所以, 再次分享一个之前学习并收录在笔记中的技巧吧。

sudo拾取上一条命令

sudo !!

很多时候, 命令行输入一条命令后, 提示权限不足无法执行, 这个时候需要用 sudo ${command} 来执行, 然而需要重新sudo 然后敲一遍上次的命令, 很繁琐。稍微改进一些, 按一下向上导航键显示上一条命令,然后光标移动到行首, 插入一个sudo 命令来执行, 还是稍显繁琐。

sudo 的一个小技巧可以解决这个问题, 使用 sudo !! , sudo !! 可以自动拾取上一条命令,并在前面补充sudo 重新执行。

Share

本周分享无助于学习, 纯属私人趣味, 也许大家都很熟悉了

996.ICU