第 97 期：洛克忠告

@Author : Lewis Tian ([e-mail])

@Link : github.com/taseikyo

@Range : 2025-01-12 - 2025-01-18

Weekly #97

readme | previous | next

本文总字数 9606 个，阅读时长约： 12 分 04 秒，统计数据来自：算筹字数统计。

*Photo by Andrey Zvyagintsev on Unsplash

Table of Contents

• algorithm

  • 字母异位词分组

  • 最长连续序列

• review

  • live 图原理介绍

  • 双因子认证解决方案

• tip
• share

  • 洛克忠告

algorithm 🔝

1. 49. 字母异位词分组

题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]] 示例 2:

输入: strs = [""] 输出: [[""]] 示例 3:

输入: strs = ["a"] 输出: [["a"]]

提示：

• 1 <= strs.length <= 104

• 0 <= strs[i].length <= 100

• strs[i] 仅包含小写字母

解法

49.group-anagrams.go

func groupAnagrams(strs []string) [][]string {
    if len(strs) == 1 {
        return [][]string{strs}
    }

    maps := make(map[string][]string, 0)
    for _, str := range strs {
        bytes := []byte(str)
        sort.Slice(bytes, func(i, j int) bool {
            return bytes[i] < bytes[j]
        })

        newStr := string(bytes)
        maps[newStr] = append(maps[newStr], str)
    }

    res := make([][]string, 0)
    for _, v := range maps {
        res = append(res, v)
    }

    return res
}

数据：8ms 70.07%; 9.23MB 82.70%

2. 128. 最长连续序列

题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9 示例 3：

输入：nums = [1,0,1,2] 输出：3

提示：

• 0 <= nums.length <= 105

• -109 <= nums[i] <= 109

解答

解题思路：https://leetcode.cn/problems/longest-consecutive-sequence/description/comments/2436490/

假设题目没有要O(n)的时间复杂度的话，肯定就是先将数组排序后在遍历数组计算最长的连续序列。

那么该如何只用O(n)的时间复杂度来完成这道题呢?

排序的目的是为了让连续的数字在物理层面紧挨在一起，不排序的话，现在让它们逻辑上挨在一起就行了。我们可以利用哈希表来实现数字在逻辑方面挨在一起。哈希表的key就是数字，value则为包含key的最长连续序列的长度。 那么现在的问题就变成的如何用value表示包含key的最长连续序列的长度。 遍历数组，将第i位元素num插入哈希表，就存在3种情况：

• 仅num在哈希表中。

• num-1或者num+1也在哈希表中。

• num-1和num+1都在哈希表中。

因为哈希表的value存的是长度，当有新数字插入时，与其相邻的数字长度也需要改变。但是我们不需要把这个连续序列全部都修改，只需要修改这个连续序列的边缘数字，因为连续序列内的数字改变没有意义，我们不会把数字插入到连续序列内

128.longest-consecutive-sequence.go

func longestConsecutive(nums []int) int {
    dict := make(map[int]int)
    for _, num := range nums {
        if _, ok := dict[num]; !ok {
            prev := dict[num-1]
            next := dict[num+1]

            dict[num] += prev+next+1
            dict[num-prev] = dict[num]
            dict[num+next] = dict[num]
        }
    }

    res := 0
    for _, v := range dict {
        if v > res {
            res = v
        }
    }
    return res
}

数据：63ms 10.11%; 13.98MB 10.99%

速度最快的解法如下，先排序然后遍历计数：

func longestConsecutive(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	sort.Ints(nums)
	res := 1
	cur := 1
	for j := 1; j < len(nums); j++ {
		switch nums[j] - nums[j-1] {
		case 1:
			cur++
			res = max(res, cur)
		case 0:
		default:
			cur = 1
		}
	}
	return res
}

review 🔝

1. live 图原理介绍

图片拥有属性，对于大多数图像文件格式，使用 CGImageSource 类型可以有效地读取数据。可以使用 The Photo Investigator 应用查看照片中的所有 Metadata：

拍摄照片时，Apple 相机会自动为照片添加不同种类的 Metadata。大多数元数据都很好理解，如位置存储在 GPS Metadata 中、相机信息位于 EXIF Metadata 中。

其中 kCGImagePropertyMakerAppleDictionary 是 Apple 相机拍摄的照片的键值对字典。“17” 是 Maker Apple 中的 LivePhotoVideoIndex，是 Live Photo 的 Identifier Key，完整列表可以参考 Apple Tags。

Live Photo 需要有特殊 Metadata 的 JPEG 图像：

[kCGImagePropertyMakerAppleDictionary : [17 : <Identifier>]]

[!NOTE] 作者还介绍了如何 将 Live Photo 分解为照片和视频 以及 使用照片和视频创建 Live Photo

2. 双因子认证解决方案

什么叫双因子认证？

通俗的讲，一般的认证方式都是用户名 / 密码的方式，也就是只有密码这一个因子来作认证，双因子无非是增加一个因子，增强认证的安全性。

常见解决方案

• 短信方式

• 邮件方式

• 电话语音方式

• TOTP 解决方案

前三种方案，其实都大同小异。Server 端通过某种算法生成一段随机密码，通过短信、邮件或者电话的方式传递给用户，用户把随机密码作为登录的凭证传递给 Server，Server 验证通过之后，就完成了一次双因子认证。但是短信和电话语音对于运营公司是有一定的成本的，除此之外有些非互联网的应用可能并不通公网，这种情况下，TOTP 不失为一种好的双因子认证的解决方案。

什么是 TOTP？

是 Time-based One-Time Password 的简写，表示基于时间戳算法的一次性密码。

如果大家玩过梦幻西游的话，那么对将军令应该不陌生，这个就是基于 TOTP 的一个产物。

OTP

介绍 TOTP 之前，先介绍下OTP

One-Time Password 的简写，表示一次性密码。

OTP(K,C) = Truncate(HMAC-SHA-1(K,C))

其中，K 代表密钥串；C 是一个数字，表示随机数；HMAC-SHA-1 表示用 SHA-1 做 HMAC；

Truncate 是一个函数，用于截取加密后的串，并取加密后串的一些字段组成一个数字。

对 HMAC-SHA-1 方式加密来说，Truncate 实现如下：

• HMAC-SHA-1 加密后的长度得到一个 20 字节的密串；

• 取这个 20 字节的密串的最后一个字节，取这字节的低 4 位，作为截取加密串的下标偏移量；

• 按照下标偏移量开始，获取 4 个字节，以大端（把高位字节放在低位地址）的方式组成一个整数；

• 截取这个整数的后 6 位或者 8 位转成字符串返回。

public static String generateOTP(String K, String C, String returnDigits, String crypto) {
	int codeDigits = Integer.decode(returnDigits).intValue();
	String result = null;

	// K是密码
	// C是产生的随机数
	// crypto是加密算法 HMAC-SHA-1
	byte[] hash = hmac_sha(crypto, K, C);
	// hash为20字节的字符串

	// put selected bytes into result int
	// 获取hash最后一个字节的低4位，作为选择结果的开始下标偏移
	int offset = hash[hash.length - 1] & 0xf;

	// 获取4个字节组成一个整数，其中第一个字节最高位为符号位，不获取，使用0x7f
	int binary = ((hash[offset] & 0x7f) << 24) | ((hash[offset + 1] & 0xff) << 16) | ((hash[offset + 2] & 0xff) << 8) | (hash[offset + 3] & 0xff);
	// 获取这个整数的后6位（可以根据需要取后8位）
	int otp = binary % 1000000;
	// 将数字转成字符串，不够6位前面补0
	result = Integer.toString(otp);
	while (result.length() < codeDigits) {
		result = "0" + result;
	}
	return result;
}

返回的结果就是看到一个数字的动态密码。

HOTP

知道了 OTP 的基本原理，HOTP 只是将其中的参数 C 变成了随机数

公式修改一下

HOTP(K,C) = Truncate(HMAC-SHA-1(K,C))

HOTP： Generates the OTP for the given count

即：C 作为一个参数，获取动态密码。

一般规定 HOTP 的散列函数使用 SHA2，即：基于 SHA-256 or SHA-512 [SHA2] 的散列函数做事件同步验证；

TOTP 详解

TOTP 只是将其中的参数 C 变成了由时间戳产生的数字。

TOTP(K,C) = HOTP(K,C) = Truncate(HMAC-SHA-1(K,C))

不同点是 TOTP 中的 C 是时间戳计算得出。

C = (T - T0) / X;

T 表示当前 Unix 时间戳

T0 一般取值为 0.

X 表示时间步数，也就是说多长时间产生一个动态密码，这个时间间隔就是时间步数 X，系统默认是 30 秒；

例如:

T0 = 0;

X = 30;

T = 30 ~ 59, C = 1; 表示 30 ~ 59 这 30 秒内的动态密码一致。

T = 60 ~ 89, C = 2; 表示 30 ~ 59 这 30 秒内的动态密码一致。

不同厂家使用的时间步数不同;

• 阿里巴巴的身份宝使用的时间步数是 60 秒；

• 宁盾令牌使用的时间步数是 60 秒；

• Google 的 身份验证器的时间步数是 30 秒；
• 腾讯的 Token 时间步数是 60 秒；

应用

客户端的实现有很多，上面已经列出来了。而服务端的实现库比较少，貌似也都是非官方的实现。这里推荐一个 JAVA 的实现库, 这是一个私人的库, 介意的朋友只能自己撸轮子了。

这里基于上述的实现库，给出一段 demo 代码，仅供参考。

package com.github.chenqimiao.util;

import java.text.MessageFormat;

import com.warrenstrange.googleauth.GoogleAuthenticator;
import com.warrenstrange.googleauth.GoogleAuthenticatorConfig;
import com.warrenstrange.googleauth.GoogleAuthenticatorConfig.GoogleAuthenticatorConfigBuilder;
import com.warrenstrange.googleauth.GoogleAuthenticatorKey;

import lombok.SneakyThrows;
import lombok.extern.slf4j.Slf4j;

/**
 * @Auther: chenqimiao
 * @Date: 2019/8/26 22:58
 * @Description: refer https://github.com/wstrange/GoogleAuth
 */
@Slf4j
public class GoogleAuthenticatorUtils {
	// 前缀
	private static final String DEFAULT_USER_PREFIX = "TOTP_USER:";
	// 用户名|密钥|发行者
	public static final String QRCODE_TEMPLATE = "otpauth://totp/" + DEFAULT_USER_PREFIX + "{0}?secret={1}&issuer={2}";
	// 默认的发行者
	public static final String DEFAULT_ISSUER = "DAS_TOTP";

	private static final GoogleAuthenticatorConfig DEFAULT_CONFIG;

	static {
		GoogleAuthenticatorConfigBuilder builder = new GoogleAuthenticatorConfigBuilder();

		// Do something here if you want to set config for GoogleAuthenticator

		DEFAULT_CONFIG = builder.build();
	}

	public static String createQrCodeContent(String username, String secret) {
		return createQrCodeContent(username, secret, DEFAULT_ISSUER);
	}

	public static String createQrCodeContent(String username, String secret, String issuer) {
		return MessageFormat.format(QRCODE_TEMPLATE, username, secret, issuer);
	}

	public static String createSecret() {
		return createSecret(DEFAULT_CONFIG);
	}

	public static String createSecret(GoogleAuthenticatorConfig config) {
		GoogleAuthenticator gAuth = new GoogleAuthenticator(config);
		final GoogleAuthenticatorKey key = gAuth.createCredentials();
		return key.getKey();
	}

	public static boolean verify(Integer totpPwd, String secret) {

		return verify(totpPwd, secret, DEFAULT_CONFIG);
	}

	public static boolean verify(Integer totpPwd, String secret, GoogleAuthenticatorConfig config) {
		GoogleAuthenticator gAuth = new GoogleAuthenticator(config);
		return gAuth.authorize(secret, totpPwd);
	}

	public static Integer getTotpPassword(String secret) {
		return getTotpPassword(secret, DEFAULT_CONFIG);
	}

	public static Integer getTotpPassword(String secret, GoogleAuthenticatorConfig config) {
		GoogleAuthenticator gAuth = new GoogleAuthenticator(config);
		return gAuth.getTotpPassword(secret);
	}

	@SneakyThrows
	public static void main(String args[]) {
		String secret = createSecret();
		String qrcodeContent = createQrCodeContent("chenqimiao", secret);
		System.out.println("qrcodeContent is " + qrcodeContent);

		Integer totpPwd = getTotpPassword(secret);
		System.out.println("Current totp password is " + totpPwd);

		boolean result = verify(totpPwd, secret);
		System.out.println("result is " + result);

	}

qrcodeContent 可以通过二维码工具生成二维码，使用 Google Authenticator 扫描该二维码之后，就相当于为用户绑定了一个认证器。

tip 🔝

share 🔝

1. 洛克忠告

洛克忠告：没有有效的监督，就不会有满意的工作绩效。明智的管理者会利用监督这把利剑，促使员工们既心有紧迫感，又满怀热情地投入到工作中去。

规定应该少定，一旦定下之后，便得严格遵守。

提出者：英国教育家洛克

点评：令出必行才能保证成功。

在管理中，把事情程序化、制度化，让各职能部门有章可循，员工按部就班，可以提高管理效率。要做到这些，制定各种各样的规定就不可避免。俗话说：没有规矩，不成方圆。如何制定规定，从而使企业能以最好的状态运转，是每个管理者都不能忽视的问题。过多的规定会使员工们无所适从，规定应该少定。少定规定会给员工们以较大的个人发展空间，在工作中充分发挥积极性和创造性，从而提高企业的产出效率。但是，规定要是不能严格得到执行，那就会比没有规定还差。适当的规定，然后严格的得到执行是成功的保证。

五种分粥的办法

把社会财富比做一锅粥，一群人来分粥，可能有五种分粥的办法：

一、指定一个人全权负责分粥。但很快大家就发现，这个人为自己分的粥最多。于是又换了一个人，结果还是一样，负责分粥的人碗里最多最好。

二、大家轮流坐庄，每人一天。每个人一周里总有一天胀得嘴歪眼斜，其余六天都是饥饿难耐。这种方法不仅不能消除不公平，还造成资源的巨大浪费。

三、大家选举一个信得过的人。开始这位品德高尚的人还能公平分粥，但不久他便给拍马溜须的人和自己多分，分粥又变得不公平了。

四、成立分粥委员会和监察委员会，形成分权和制约。这样，公平基本做到了，可是由于监察委员会经常提出种种质疑，分粥委员会又据理力争，等到粥分完毕，早就凉透了。

五、在没有精确计量的情况下，无论选择谁来分，都会有利己嫌疑。解决的方法就是第五种——分粥者最后喝粥，要等所有人把粥领走了，“分粥者”自己才能取剩下的那份。因为让分粥者最后领粥，就给分粥者提出了一个最起码的要求：每碗粥都要分得很均匀。道理明摆着——倘若分得不匀，最少的那碗肯定是自己的了。只有分得合理，自己才不至于吃亏。因此，分粥者即使只为自己着想，结果也是公正、公平的。

一些关系国计民生的社会公共行业的规矩，不仅要管社会公众，更要管住业内人，内外统一管理标准，社会生活才能有序而不致乱套。由于垄断着公共资源，“分粥者 ”就应当对行内外一视同仁，不得厚此薄彼。比如，每到春运和节假日，铁路售票窗口有时连一张票也买不到，但人们却可以很容易地从票贩子手里拿到高出票面价格一倍以上的票。票贩子的票有些就来自车站职工。“火车票就是我们的节日‘概念股票’，不搞白不搞。”一位铁路职工如是说。针对这种现象，我们的监督管理措施，就是让“分粥”者无权最先“领粥”。

上述五种分粥制度假设的前提是所有的“分粥者”个个都是自私鬼，没有一个是大公无私的。正因如此，他们一有机会便会“以权谋私”。美国《独立宣言》起草人之一托马斯·杰斐逊说：“自由的政府不是以信赖，而是以猜疑为基础建立起来的。因此，在权力问题上，不是建立在对人性的信赖上，而是要用法律加以约束，防止其行为不端。”所以制度至关重要，制度是人选择、交易的结果。好的制度清晰而精妙，既简洁又高效，令人为之感叹。

作为管理人员，我们更应该时时提醒自己，我们所制定的各种制度是否浑然一体，简洁高效，是否处在激励与制约之间的平衡点上。

readme | previous | next