计算机编程 类目

学会编程我们能够和计算机沟通

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

优雅部署 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 --

CPython 源码中整数加法的实现

最近突然涌起兴趣去阅读 CPython 源码,网上也看了不少解析的文章,后来网上看到《Python源码剖析》评价不错,可惜现在已经绝版,只能从豆瓣阅读购买了一本电子书观摩 。

我从网上下载的是最新的 Python 2.7 源码,这本书配套的解说代码是 Python 2.5 的,这是一个遗憾,但是大体上相差不大,刚好昨天遇到一处。

昨天看到 Python int 实现的原理,这里不详细表述,有兴趣的可以去看看书。其中整数加法 (int_add) 的实现,虽然代码只有几行,但是其中隐藏的知识点还是非常多的,花了点时间回顾了一些基础知识,在这里也简单总结下。

以下是 2.5 里面加法的实现,也是书中提供的例子,这里直接引用过来作为参考对比,注释是作者加入的。

static PyObject* int_add(PyIntObject *v, PyIntObject *w)
{
    register long a, b, x;
    CONVERT_TO_LONG(v, a);
    CONVERT_TO_LONG(w, b);
    x = a + b;
    //[1] : 检查加法结果是否溢出
    if ((x^a) >= 0 || (x^b) >= 0)
        return PyInt_FromLong(x);
    return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
}

下面是 2.7 中的代码对比,大体都没有变化:

static PyObject *
int_add(PyIntObject *v, PyIntObject *w)
{
    register long a, b, x;
    CONVERT_TO_LONG(v, a);
    CONVERT_TO_LONG(w, b);
    /* casts in the line below avoid undefined behaviour on overflow */
    x = (long)((unsigned long)a + b);
    if ((x^a) >= 0 || (x^b) >= 0)
        return PyInt_FromLong(x);
    return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
}

在此之前,先简单介绍下上面的逻辑:
1)首先 int_add 函数是 Python 中 int 加法的实现函数,参数是两个 Python 整数对象,PyIntObject;
2)接着使用预先定义好的宏(不是重点,这里不具体展开),从整数对象中取出 value,这个value就是整数的值,类型是 long;
3)接下来做整数加法,判断是否溢出,如果没有发生溢出,则将新建一个整数对象,最后结果返回;
4)如果加法过程中发生溢出,则使用更长的类型(PyLong_Type)来做这个加法运算;

这个函数的精髓在与加法的处理,不是简单求和返回,可以看出 2.5 和 2.7代码的区别:

// 2.5
x = a + b;

// 2.7
x = (long)((unsigned long)a + b);

为什么 2.7 要搞得怎么复杂,又是转换成 unsigned long 最后又转换为 long,实际上原因是因为一个历史包袱,在C语言的定义中有符号数(signed)的加法溢出是 undefined behavior,所以这里先变成无符号数的加法,如果溢出就是简单做个截断(取模)。注意,无符号数和有符号数运算,有符号数会隐式转换成无符号数。

接下来我们看对溢出额判断,(x^a) >= 0 || (x^b) >= 0,为什么使用异或来判断。这里先梳理下,什么情况下会发生加法溢出:
1)如果两个不同符号的数字相加,不会发生溢出,比如 5 + (-128);
2)如果两个相同符号的数字相加,可能会发生溢出,比如正正相加溢出后变成负数,负负相加后变成整数;
这里实际上就是利用了这两点来作为判断依据,如果加法运算结果和原来的任意一个数字符号一致就没有溢出,使用异或来判断性能更好。关于溢出的判断还有其他方法,网上也有不少小伙伴提供了更多思路

这里还有一个隐含的点,在 Python 里整数对象是不可变的,这个要注意,相加之后是返回一个新的对象:

>>> a = 1
>>> id(a)
38821992L
>>> a += 1
>>> id(a)
38821968L

继续看书。

WordPress 文章内嵌 Gist 代码

WordPress 内嵌 Gist 链接的方法很简单,将以下代码添加到当前主题的 functions.php 文件中:

/*
 * Embed gists with a URL in post article
 */
function dangopress_embed_gist($matches, $attr, $url, $rawattr)
{
    $embed = sprintf(
        '<script src="https://gist.github.com/%1$s.js%2$s"></script>',
        esc_attr($matches[1]),
        esc_attr($matches[2])
    );

    return apply_filters('dangopress_embed_gist', $embed, $matches, $attr, $url, $rawattr);
}
wp_embed_register_handler('gist', '#https?://gist\.github\.com(?:/[a-z0-9-]+)?/([a-z0-9]+)(\?file=.*)?#i', 'dangopress_embed_gist');

在上面的代码中,我们注册了 Gist 链接的处理方法 dangopress_embed_gist。当我们拷贝 Gist 链接到编辑框时,会调用改方法生成内嵌内容。

Gist 链接是通过注册过程中,指定的正则表达式匹配的:

#https?://gist\.github\.com(?:/[a-z0-9-]+)?/([a-z0-9]+)(\?file=.*)?#i

它可以匹配下面的任意一种形式:

https://gist.github.com/dangoakachan/443ca6efa9622deb3131   # a full gist url example
https://gist.github.com/443ca6efa9622deb3131                # but user name is optional

# If the gist contains multiple file, use "?file=youfile" to embed only one 
https://gist.github.com/e59891e80652bb209f8e?file=moderate.list  # embed moderate.list only

查看全文