Leetcode 3. Longest Substring Without Repeating Characters

继续做把第三题的解题思路放上来。第三题的目的是求字符串内最长的不重复子串,两个要求非常清晰。下面是题目的描述:

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

思路:

假设子串的初始下标为 i,结束下标为 j。i 和 j 的初始值均为 0。j 开始一次往后遍历,如果这个字符串没有重复字符,那么 j 会一直走到最后,此时最长子串就是字符串本身。实际情况没有那么理想,我们主要分析这类场景。当处于 j 位置的字符和子串之前的字符重复(假设位置为 k),那么就应该停下,并且更新最长子串的长度(假设最长长度为 max),j 继续往后走,同时 i 的位置需要挪到重复字符之后,即 k+1 处。直到遍历到字符串的最后。

比如用第一个例子作为说明,初始状态 i = j = 0,最长子串长度 max = 0:

  1. j=0 处的字符是 a,无重复,当前子串长度为 1;
  2. j=1 处的字符是 b,无重复,当前子串长度为 2;
  3. j=2 处的字符是 b,无重复,当前子串长度为 3;
  4. j=3 处的字符是 a,发现重复,更新 max = 3,i = 0+1,当前子串长度为 3;
  5. j=4 处的字符是 b,发现重复,max 不变,i = 1+1,当前子串长度为 3;
  6. j=5 处的字符是 c,发现重复,max 不变,i = 2+1,当前子串长度为 3;
  7. j=6 处的字符是 b,发现重复,max 不变,i = 4+1,当前子串长度为 2;
  8. j=7 处的字符是 b,发现重复,max 不变,i = 6+1,当前子串长度为 1;

因此,"abcabcbb" 的最长子串长度是 3。

接下来我们写上代码:

func lengthOfLongestSubstring(s string) int {
	n := len(s)

	if n <= 1 {
		return n
	}

	tbl := make(map[byte]int, n)
	lo, longest, curr := 0, 0, 0

	for hi := 0; hi < n; hi++ {
		if k, ok := tbl[s[hi]]; ok && k >= lo {
			lo = k + 1
		}

		tbl[s[hi]] = hi
		curr = hi - lo + 1

		if curr > longest {
			longest = curr
		}
	}

	return longest
}

完整的代码参见这里,以及测试代码

LeetCode Problem 2 - Add Two Numbers

继续第二道题目,下面是问题描述:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

这个问题比较简单,基本上解题思路是比较清晰的。输入是两个链表,链表的元素都是单个数字(0-9),要求将两个列表的相应节点数字相加,并作为结果链表返回。

这个题咋看可以马上开始解答,但是在此之前还是有一些需要注意的地方。第一点是,题目并没有说明链表的长度,所以 A 和 B 两个链表可能不一定相同长度,那么如果一个链表更长,那么相加怎么处理呢?这里就考虑直接返回即可,相当于+0。第二点是,如果相加溢出怎么处理,其实题目的例子里面已经很清晰了,溢出会发生进位,依次向后处理。第三点是,如果最后一位发生进位呢,这点容易被遗忘,需要新增一个节点。

下面是具体的代码:

// Problem 2. Add Two Numbers
// URL: https://leetcode.com/problems/add-two-numbers/tabs/description

// ListNode defines a singly-linked list
type ListNode struct {
	Val  int
	Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	head := &ListNode{0, nil} // sentinel node
	carry := 0                // carray bit

	for tail := head; l1 != nil || l2 != nil || carry != 0; tail = tail.Next {
		sum := carry

		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}

		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}

		tail.Next, carry = &ListNode{sum % 10, nil}, sum/10
	}

	return head.Next // discard sentinel node
}

这里在链表加了一个哨兵节点,主要是为了处理方便。完整的代码参见这里,以及测试代码

LeetCode Problem 1 - Two Sum

最近开始在 LeetCode 网站上刷题,准备练练脑子。因为经常不动脑,感觉快生锈了。这个是第一题,比较简单。所有的解题代码都放在 Github 上。

问题描述:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

题目描述的很清楚了,就是要从整数列表里面找出符合需求的两个数字,他们之和等于给定的目标值。输入是整数列表,输出是两个数字下标的列表。从给的例子上看,我们可以假设返回的列表,下标小的放在前面,比如是 [0, 1] 而不是 [1, 0]。那假如没有找到符合要求的数字呢,应该返回什么呢?题目里面没有明确说明,我自己觉得这里应该返回一个空值。

思路一

首先,我们可以想到一种最简单的方法,就是遍历所有组合,这种方法比较暴力也很有效。下面的代码用 go 语言编写:

func twoSum(nums []int, target int) []int {
	n := len(nums)

	if n < 2 {
		return nil
	}

	for i := 0; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			if nums[i]+nums[j] == target {
				return []int{i, j}
			}
		}
	}

	return nil
}

这个方法没什么好解释的,它的时间复杂度是O(n^2)

思路二

如果我们要降低时间复杂度,就必须减少迭代的次数。可以想到的一个优化思路是,针对数组进行排序,然后定义两个指针,分别从头和尾两个方向逼近,看起来有点像快速排序。如果指针指向的两个数之和大于目标值,则右边的指针左移。反之,左边的指针右移。直到找到符合需求的两个数。因为排序的最佳时间复杂度可以达到O(nlogn),接下来只遍历一次,时间复杂度是O(n),所以总的时间复杂度为 O(nlogn)。

这是一个不错的思路,但是这道题目要返回数字的下标,但是如果我们先排序会导致顺序就和初始状态不一样,所以还得想办法记录,所以这个思路最终实现也挺别扭的,就放弃了。

思路三

回到题目,我们要求出 a+b=target,反过来看,如果我们当前遍历的数字是 a,也就是我们要看 target - a 这个结果在数组里面是否存在。为了加快查找的效率,我们可以用额外的空间换时间效率,哈希表是一个很好的策略。在遍历的时候我们把每个数字和它对应的坐标保存到一个哈希表中。相应的代码如下:

func twoSum(nums []int, target int) []int {
	tbl := make(map[int]int, len(nums))

	for i, v := range nums {
		if j, ok := tbl[target-v]; ok {
			return []int{j, i}
		}

		tbl[v] = i
	}

	return nil
}

完整代码

完整的代码参见这里,以及测试代码

Bash function 还能这么玩

今天看到一篇讲 Bash function 的有意思的文章,原文在这里

在 Bash 中一般我们这么定义一个函数:

function name () {
  ...
}

这是非常常见的写法,包括我自己在内,一直把他当做类似 Python、C 等语言一样的函数定义语法。实际上这里{ ... }并不代表函数体或者函数的作用域。它只是代表里面的内容是一组命令的集合。了解这点之后,接下来就有一些比较好玩的写法了。

比如下面的函数作用是测试文件是否存在,这里就没用大括号:

function fileExists () [[ -f $1 ]]

或者

function isEven () (( $1 % 2 == 0 ))

还有下面的用法:

function name () (
  ...
)

这里用小括号,当执行函数的时候,会 fork 一个子进程来执行里面的命令。子进程对环境的修改不会影响到外面的父进程,也就不需要保存现场或者恢复现场的操作了。比如设置一些参数:

function caseInsensitiveMatch () (
    shopt -s nocasematch
    ....
)

除了上面的写法,这个用法的前提是函数体仅包含一行命令,或复杂或简单,比如 while、for、if、case 等结构都是可以的:

function sleep1 () while :; do "$@"; sleep 1; done

我也开始理财了

2016 年结束的时候,我突发好奇地开始算过去一年的开销。那个下午我拉出银行卡和支付宝的消费记录,大额支付都一一核对,触目惊心啊,不知不觉一年竟然花了那么多的钱,几乎每个月都没什么节制。以前从来没有记账的习惯,日积月累,很多钱都是花在没啥用的地方。所以,年初我就开始在网上找一些理财投资的渠道,也关注了一些公众号。

网上说理财的文章和人很多,很多都是给你灌输一堆概念,比如“人不理财,才不理你”,也有反面的说法是“最好的理财就是投资你自己”。说的都是对的,个人秉持的原则是,通过理财建立金钱管理的体系,管理好自己的钱,同时理财不应该占用太多个人的时间,尤其是工作时间,她只是锦上添花的事情。理财让个人财富保值、增值。之前看理财文章了解到一个很好的概念,这些都是日常中被大家忽略的非常简单的东西,比如月结余。假设你个人月收入一万块钱,每月平均开销 2000,那么 8000 块就是你的月结余,如果你多花 3000,月结余就是 5000,月光族的月结余就是 0 。显然,理财就是要去提高月结余,合理消费。

宝宝类理财

最简单的理财方式,就是把你工资的所有钱都存入到余额宝。余额宝本质上是属于货币基金,是属于低风险(基本上也可以认为无风险)的投资品种。货币基金的理财收益比起银行活期和定期的收益高多了,最近货币资金紧张,余额宝等互联网宝宝类的年化利率已经超过 4% 了。推荐网商银行的余利宝,和余额宝同出一门,最近的年化保持在 4.1% 的水平。差不多投资一万,每天的收益 1.1 元左右。我自己有大部分的资金都是放在网商银行。

下面是招商银行存款利息和余利宝的对比,高下立见:

说起招行,招商银行 APP 上的朝朝盈也不错,年化和余利宝差不多,但是缺点是一个人最多只能投资五万。宝宝类理财的优点是可以随时取用、低风险,缺点是转入后下一个基金交易日才开始计算收益。节假日、周末就比较尴尬了。

再不济也不要把钱躺在银行卡了,活期的利率几乎可以忽略。

网贷投资

如果你不满足宝宝类理财的收益,那么想要更高的收益就需要承担额外的风险了。金融投资就是和风险搏斗,风险越大收益越高,本金损失的概率也越大。往低看,银行定存、货币基金、国债(没具体了解过)的风险较低,因此利息也相对较低,如上面所说,银行定存最低。往高看,网贷(P2P 理财)刚刚兴起的时候,大平台的投资收益都有 20% 多,但是出现了很多不合规的危险平台,过去几年跑路的平台也非常多,本金追回的概率也就非常小了。一般来说,国债的利息是理财的标尺,低于国债利率的风险就比较低,高于国债利率的风险就随之变大。

查看全文

优雅部署 Google Adsense 广告代码

去年就曾经申请过 Google Adsense 的广告,但是貌似审核没通过,一直留有遗憾(没有尝试过好奇)。今年突然起了兴致重新申请,审核持续了将近一周,意外地竟然通过了。

在申请之前,需要在页面上加上一段代码。最好加到 head 里面,因为 Google Adsense 的代码片段加了 async 属性会后台异步加载,不会影响页面渲染。代码例如:

<script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
<script>
  (adsbygoogle = window.adsbygoogle || []).push({
    google_ad_client: "ca-pub-xxxxxxxx",
    enable_page_level_ads: true
  });
</script>

其中 "ca-pub-xxxxxxxx" 是你的 publisher id(Adsense 账户里面看到的是没有 ca- 前缀的,搞不懂区别是什么)。

审核通过之后就是可以再 Adsense 网站创建广告单元,然后复制代码到你自己的网站上,不出意外很快就可以显示广告了。广告代码大概是这样子的:

<script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
<!-- 侧栏自适应2 -->
<ins class="adsbygoogle"
     style="display:block"
     data-ad-client="ca-pub-xxxxx"
     data-ad-slot="yyyyy"
     data-ad-format="horizontal"></ins>
<script>
(adsbygoogle = window.adsbygoogle || []).push({});
</script>

查看全文

非插件实现面包屑导航功能

最近开始整理 WordPress 的插件,发现有些插件功能越来越重,比如 Yoast SEO 的插件,出于个人洁癖就把他删除了。但是目前网站原来的 Breadcrumbs 导航功能是这个插件提供的,所以就开始查找替换方案。网上搜索发现一片文章介绍的比较具体 --- 《WordPress实现面包屑导航的方法》,博主其实也是参考了国外网友的非插件实现

以下代码都是基于 Dimox 的原创,我只是在他基础上做了微调,改动不大:

/*
 * Show breadcrumb by Dimox
 * URL: http://dimox.net/wordpress-breadcrumbs-without-a-plugin/
 * Version: 2017.21.01
 * License: MIT
 */
function dangopress_breadcrumb()
{
    /* === OPTIONS === */
    $text['home']     = '首页'; // text for the 'Home' link
    $text['category'] = '%s'; // text for a category page
    $text['search']   = '"%s" 的搜索结果'; // text for a search results page
    $text['tag']      = '包含标签 "%s" 的文章'; // text for a tag page
    $text['404']      = '页面未到到'; // text for the 404 page
    $text['page']     = 'Page %s'; // text 'Page N'
    $text['cpage']    = 'Comment Page %s'; // text 'Comment Page N'

    $prefix         = '<i class="icon-windows"></i>'; // Prefix the breadcrumb
    $wrap_before    = '<div class="breadcrumbs" id="site-breadcrumbs" itemscope itemtype="http://schema.org/BreadcrumbList">'; // the opening wrapper tag
    $wrap_after     = '</div><!-- .breadcrumbs -->'; // the closing wrapper tag
    $sep            = '<i class="icon-caret-right"></i>'; // separator between crumbs
    $sep_before     = '<span class="sep">'; // tag before separator
    $sep_after      = '</span>'; // tag after separator
    $show_home_link = 0; // 1 - show the 'Home' link, 0 - don't show
    $show_current   = 1; // 1 - show current page title, 0 - don't show
    $before         = '<h1 class="current-crumb">'; // tag before the current crumb
    $after          = '</h1>'; // tag after the current crumb
    /* === END OF OPTIONS === */

    global $post;
    $home_url       = home_url('/');

    $link_before    = '<span itemprop="itemListElement" itemscope itemtype="http://schema.org/ListItem">';
    $link_after     = '</span>';
    $link_attr      = ' itemprop="item"';
    $link_in_before = '<span itemprop="name">';
    $link_in_after  = '</span>';
    $link           = $link_before . '<a href="%1$s"' . $link_attr . '>' . $link_in_before . '%2$s' . $link_in_after . '</a>' . $link_after;

    $frontpage_id   = get_option('page_on_front');
    $parent_id      = ($post) ? $post->post_parent : '';
    $sep            = ' ' . $sep_before . $sep . $sep_after . ' ';
    $home_link      = $link_before . '<a rel="nofollow" href="' . $home_url . '"' . $link_attr . ' class="home">' . $link_in_before . $text['home'] . $link_in_after . '</a>' . $link_after;

    if (is_home() || is_front_page()) {
        return;
    } else {
        echo $wrap_before . $prefix;
        if ($show_home_link) echo $home_link;

        if ( is_category() ) {
            $cat = get_category(get_query_var('cat'), false);
            if ($cat->parent != 0) {
                $cats = get_category_parents($cat->parent, TRUE, $sep);
                $cats = preg_replace("#^(.+)$sep$#", "$1", $cats);
                $cats = preg_replace('#<a([^>]+)>([^<]+)<\/a>#', $link_before . '<a$1' . $link_attr .'>' . $link_in_before . '$2' . $link_in_after .'</a>' . $link_after, $cats);
                if ($show_home_link) echo $sep;
                echo $cats;
            }
            if ( get_query_var('paged') ) {
                $cat = $cat->cat_ID;
                echo $sep . sprintf($link, get_category_link($cat), get_cat_name($cat)) . $sep . $before . sprintf($text['page'], get_query_var('paged')) . $after;
            } else {
                if ($show_current) echo $sep . $before . sprintf($text['category'], single_cat_title('', false)) . $after;
            }
        } elseif ( is_search() ) {
            if (have_posts()) {
                if ($show_home_link && $show_current) echo $sep;
                if ($show_current) echo $before . sprintf($text['search'], get_search_query()) . $after;
            } else {
                if ($show_home_link) echo $sep;
                echo $before . sprintf($text['search'], get_search_query()) . $after;
            }
        } elseif ( is_day() ) {
            if ($show_home_link) echo $sep;
            echo sprintf($link, get_year_link(get_the_time('Y')), get_the_time('Y')) . $sep;
            echo sprintf($link, get_month_link(get_the_time('Y'), get_the_time('m')), get_the_time('F'));
            if ($show_current) echo $sep . $before . get_the_time('d') . $after;
        } elseif ( is_month() ) {
            if ($show_home_link) echo $sep;
            echo sprintf($link, get_year_link(get_the_time('Y')), get_the_time('Y'));
            if ($show_current) echo $sep . $before . get_the_time('F') . $after;
        } elseif ( is_year() ) {
            if ($show_home_link && $show_current) echo $sep;
            if ($show_current) echo $before . get_the_time('Y') . $after;
        } elseif ( is_single() && !is_attachment() ) {
            if ($show_home_link) echo $sep;
            if ( get_post_type() != 'post' ) {
                $post_type = get_post_type_object(get_post_type());
                $slug = $post_type->rewrite;
                printf($link, $home_url . $slug['slug'] . '/', $post_type->labels->singular_name);
                if ($show_current) echo $sep . $before . get_the_title() . $after;
            } else {
                $cat = get_the_category(); $cat = $cat[0];
                $cats = get_category_parents($cat, TRUE, $sep);
                if (!$show_current || get_query_var('cpage')) $cats = preg_replace("#^(.+)$sep$#", "$1", $cats);
                $cats = preg_replace('#<a([^>]+)>([^<]+)<\/a>#', $link_before . '<a$1' . $link_attr .'>' . $link_in_before . '$2' . $link_in_after .'</a>' . $link_after, $cats);
                echo $cats;
                if ( get_query_var('cpage') ) {
                    echo $sep . sprintf($link, get_permalink(), get_the_title()) . $sep . $before . sprintf($text['cpage'], get_query_var('cpage')) . $after;
                } else {
                    if ($show_current) echo $before . get_the_title() . $after;
                }
            }
        // custom post type
        } elseif ( !is_single() && !is_page() && get_post_type() != 'post' && !is_404() ) {
            $post_type = get_post_type_object(get_post_type());
            if ( get_query_var('paged') ) {
                echo $sep . sprintf($link, get_post_type_archive_link($post_type->name), $post_type->label) . $sep . $before . sprintf($text['page'], get_query_var('paged')) . $after;
            } else {
                if ($show_current) echo $sep . $before . $post_type->label . $after;
            }
        } elseif ( is_attachment() ) {
            if ($show_home_link) echo $sep;
            $parent = get_post($parent_id);
            $cat = get_the_category($parent->ID); $cat = $cat[0];
            if ($cat) {
                $cats = get_category_parents($cat, TRUE, $sep);
                $cats = preg_replace('#<a([^>]+)>([^<]+)<\/a>#', $link_before . '<a$1' . $link_attr .'>' . $link_in_before . '$2' . $link_in_after .'</a>' . $link_after, $cats);
                echo $cats;
            }
            printf($link, get_permalink($parent), $parent->post_title);
            if ($show_current) echo $sep . $before . get_the_title() . $after;
        } elseif ( is_page() && !$parent_id ) {
            if ($show_current) echo $sep . $before . get_the_title() . $after;
        } elseif ( is_page() && $parent_id ) {
            if ($show_home_link) echo $sep;
            if ($parent_id != $frontpage_id) {
                $breadcrumbs = array();
                while ($parent_id) {
                    $page = get_page($parent_id);
                    if ($parent_id != $frontpage_id) {
                        $breadcrumbs[] = sprintf($link, get_permalink($page->ID), get_the_title($page->ID));
                    }
                    $parent_id = $page->post_parent;
                }
                $breadcrumbs = array_reverse($breadcrumbs);
                for ($i = 0; $i < count($breadcrumbs); $i++) {
                    echo $breadcrumbs[$i];
                    if ($i != count($breadcrumbs)-1) echo $sep;
                }
            }
            if ($show_current) echo $sep . $before . get_the_title() . $after;
        } elseif ( is_tag() ) {
            if ( get_query_var('paged') ) {
                $tag_id = get_queried_object_id();
                $tag = get_tag($tag_id);
                echo $sep . sprintf($link, get_tag_link($tag_id), $tag->name) . $sep . $before . sprintf($text['page'], get_query_var('paged')) . $after;
            } else {
                if ($show_current) echo $sep . $before . sprintf($text['tag'], single_tag_title('', false)) . $after;
            }
        } elseif ( is_404() ) {
            if ($show_home_link && $show_current) echo $sep;
            if ($show_current) echo $before . $text['404'] . $after;
        } elseif ( has_post_format() && !is_singular() ) {
            if ($show_home_link) echo $sep;
            echo get_post_format_string( get_post_format() );
        }
        echo $wrap_after;
    }
}

同时,我也把这个很棒的功能引入到 dangopress 主题 里面了,有兴趣的同学可以下载下来尝试下效果,这个主题接下来我还会继续维护。

我的网站效果:

面包屑导航效果

-- END --

最近的变化

好久没有写技术博客了,刚才看归档页面,15 年写了一篇,16 年也写了一篇,实在汗颜。不过这个博客对我来说是一个非常宝贵的财富,所以不出意外我会一直维护下去。争取今年可以继续写一些文章。

这两年博客写得少,主观原因确实是在技术上投入的精力减少了,虽然我也有在看一些技术文章,但是沉淀落实到纸面(博客)上的几乎没有。一方面原因是平时工作比较忙,非工作时间也更多开始陪伴家人(想想 Dota 也是大半年没玩了)。另外一方面是,大概两年前我开始带团队,这两年的时间我更多得在摸索怎么带好一只团队,纠结、彷徨、探索一路走来,更加关注团队同学的技术和个人能力的成长。最近忘记是知乎还是微博上看到一篇,关于一线工程师和技术经理的翻译文章,里面讲到一线工程师被提拔为主管后,很多东西会发生变化,细节的关注程度,技术方向的把握,工作规划的制定,团队之间的协作等等。个人感觉,有好有坏,确实带团队之后个人在细节的把握上比以前弱了不少,但是也因为带过团队思路和视野开阔不少。

最近谈得比较多的是 DevOps,国内基本上就是说研发具备运维能力,或者激进点就是干掉运维团队。运维团队是否没有存在的价值?未必,只能说传统的 Ops 运维不再有存在的价值,运维需要往更深领域去转型。运维工程师的关注点可能不再是一个变更或者一个具体的操作。

比较能想到的一个方向,是自动化运维,这也是近几年非常火的关键词。DevOps 的理念并非让研发来兼职完成运维的操作,而是需要将运维的经验通过代码的方式沉淀到自动化的平台,通过平台赋能帮助研发高效地完成运维工作。研发鼠标点点,填写几个表单选项就可以快速部署应用到各个环境,不再需要找运维同学去申请机器、申请域名、部署发布,容量不足了可以快速扩容,甚至设定规则弹性伸缩。但是我一般不看好(没有运维经验的)研发去做自动化平台,所以这也是为什么非常多研发组成的工具团队最终造出来的是一个难用的玩具的原因。

查看全文