杰拉斯的博客
经典回溯算法问题:九宫格
杰拉斯 | 时间:2012-12-18, Tue | 22,388 views编程算法
九宫格是在81个格子中,要满足以下条件:(1)每个横行和竖列中的9个格子都包含数字1至9,不重复;(2)每个黑色粗实线围住的9个格子都包含数字1至9,不重复。如下表所示:
7 6 1 9 3 4 8 2 5 3 5 4 6 2 8 1 9 7 9 2 8 1 5 7 6 3 4 2 1 9 5 4 6 3 7 8 4 8 3 2 7 9 5 1 6 5 7 6 3 8 1 9 4 2 1 9 5 7 6 2 4 8 3 8 3 2 4 9 5 7 6 1 6 4 7 8 1 3 2 5 9
要求找出给定数字的九宫格。
【输入形式】
输入9行9列81个数字,其中0表示要填的数字。
【输出形式】
输出满足条件的九宫格。
【输入样例】
0 6 1 0 3 0 0 2 0 0 5 0 0 0 8 1 0 7 0 0 0 0 0 7 0 3 4 0 0 9 0 0 6 0 7 8 0 0 3 2 0 9 5 0 0 5 7 0 3 0 0 9 0 0 1 9 0 7 0 0 0 0 0 8 0 2 4 0 0 0 6 0 0 4 0 0 1 0 2 5 0
【输出样例】
7 6 1 9 3 4 8 2 5 3 5 4 6 2 8 1 9 7 9 2 8 1 5 7 6 3 4 2 1 9 5 4 6 3 7 8 4 8 3 2 7 9 5 1 6 5 7 6 3 8 1 9 4 2 1 9 5 7 6 2 4 8 3 8 3 2 4 9 5 7 6 1 6 4 7 8 1 3 2 5 9
代码及思路如下:
#include<stdio.h> bool canFill(int a[9][9], int k, int n){ int i, j, row = k / 9, col = k % 9; for(i = 0; i < 9; ++i){ if(a[i][col] == n){ return false; } } for(j = 0; j < 9; ++j){ if(a[row][j] == n){ return false; } } for(i = row - row % 3; i < row - row % 3 + 3; ++i){ for(j = col - col % 3; j < col - col % 3 + 3; ++j){ if(a[i][j] == n){ return false; } } } return true; } void fill(int a[9][9], int k = 0){ int i, j; if(k == 81){ for(i = 0; i < 9; ++i){ for(j = 0; j < 9; ++j){ printf("%d ", a[i][j]); } printf("\n"); } return; } int row = k / 9, col = k % 9; if(a[row][col] == 0){ for(i = 1; i <= 9; ++i){ if(canFill(a, k, i)){ a[row][col] = i; fill(a, k + 1); a[row][col] = 0; } } }else{ fill(a, k + 1); } } int main(){ int i, j, a[9][9]; for(i = 0; i < 9; ++i){ for(j = 0; j < 9; ++j){ scanf("%d", &a[i][j]); } } fill(a); return 0; }
2013年5月4日3点温习重写代码如下:
#include<stdio.h> int square[9][9]; int isEnabled(int k, int num){ int row = k / 9; int col = k % 9; for(int i = 0; i < 9; ++i){ if(square[row][i] == num || square[i][col] == num){ return false; } } int m = row - row % 3; int n = col - col % 3; for(int i = m; i < m + 3; ++i){ for(int j = n; j < n + 3; ++j){ if(square[i][j] == num){ return false; } } } return true; } void fill(int k = 0){ int row = k / 9; int col = k % 9; if(k >= 81){ for(int i = 0; i < 9; ++i){ for(int j = 0; j < 9; ++j){ printf("%d ", square[i][j]); } printf("\n"); } return; } if(square[row][col] > 0){ fill(k + 1); return; } for(int i = 1; i <= 9; ++i){ if(isEnabled(k, i)){ square[row][col] = i; fill(k + 1); square[row][col] = 0; } } } int main(){ for(int i = 0; i < 9; ++i){ for(int j = 0; j < 9; ++j){ scanf("%d", &square[i][j]); } } fill(); return 0; }
[转载]高性能网站需避免的7个错误
杰拉斯 | 时间:2012-12-14, Fri | 6,665 views前端开发
翻译是门体力活,最后一点内容实在没嚼头,有些捣糨糊,省了不少废话。
原文地址:http://www.sitepoint.com/seven-mistakes-that-make-websites-slow/
原文作者:Coach Wei
翻译编辑:zhangxinxu
假期临近(应该指感恩节和圣诞节),公司增加了SEM方面的花费,关注SEO,修改页面。然而,为了最大的销售额,这些时间、财力上的付出可能就是打水漂——如果假期增加了访问量让网站速度变慢甚至下去的话。
性能影响用户是毫无疑问的。网站速度直接影响反弹率、转化率、收入、用户满意度、搜索引擎优化(已知的如反映网站流行度的Page Rank)以及几乎所有值得追踪的业务。用户离开速度慢的网站,而且往往不会再回来。
还在不久前,用户离开一个网站的时间点是8秒。然而,很快就是6秒,然后4秒,然后现在是2秒。门槛一直在提高。
小小性能改变,大大影响发生
用户的耐心不是线性的。第1秒的时候基本上没有人会放弃这个站点。但是,1秒开外之后,如果没有适当的反馈的话(例如浏览器标头显示页面标题),用户开始以一个加速的比率离开。到3~4秒的时候,一般的站点会一半的潜在用户。当然,具体的阈值根据网站、用户行为和意图以及其他因素不同而有所不同……但万变不离其宗。
瓶颈
快速测试:当HTML载入浏览器之后,用户等待你页面加载的时间百分比是多少?如果你不是做web开发的,或是经常混迹于性能社区的话答案可能会让你大跌眼镜。一般超过90%,用户花在等待上的时间的90%实在页面HTML载入到浏览器之后。为什么会这样呢?
经典算法:整数划分问题
杰拉斯 | 时间:2012-12-12, Wed | 30,736 views编程算法
整数划分问题(算法分析与设计 P12):将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数和方案。例如正整数6有如下11种不同的划分:
6 5+1 4+2, 4+1+1 3+3, 3+2+1, 3+1+1+1 2+2+2, 2+2+1+1, 2+1+1+1+1 1+1+1+1+1+1
PHP中获取中英文混合字符串长度
杰拉斯 | 时间:2012-12-04, Tue | 35,338 views后台技术
今晚在写框架的表单验证类时,需要判断某个字符串长度是否在指定区间内,很自然地,想到了PHP中的strlen函数。
$str = 'Hello world!'; echo strlen($str); // 输出12
然而在PHP自带的函数中,strlen及mb_strlen都是通过计算字符串所占字节数来计算长度的,在不同的编码情况下,中文所占的字节数是不同的。在GBK/GB2312下,中文字符占2个字节,而在UTF-8下,中文字符占3个字节。
$str = '你好,世界!'; echo strlen($str); // GBK或GB2312下输出12,UTF-8下输出18
[转载]你真的已经搞懂JavaScript了吗?
杰拉斯 | 时间:2012-12-02, Sun | 18,308 views前端开发
昨天在著名前端架构师Baranovskiy的博客中看到一个帖子《So, you think you know JavaScript?》
题目一:
if (!("a" in window)) { var a = 1; } alert(a);
题目二:
var a = 1, b = function a(x) { x && a(--x); }; alert(a);
题目三:
function a(x) { return x * 2; } var a; alert(a);
题目四:
function b(x, y, a) { arguments[2] = 10; alert(a); } b(1, 2, 3);
题目五:
function a() { alert(this); } a.call(null);
请不要借助任何帮助工具,心算答案。答案在下面。