时光博客

题目如下

一个数除以7，不能用除法，乘法以及模运算，写出算法并实现

解题思路

既然不能用常规的函数，那么我们就像想别的办法，最容易想到的，当然还是位运算，关于位运算，leetcode上有一道题，属于经典的位运算题目，我博客之前也做过分析，猛击这里阅读「 Single Number II 」

首先假设这个数为N，这个数可以表示为 N = 8 * A + B，为什么要用8，是因为8是最靠近7的，且可以通过二级制位移来产生的数字，例如：A >> 3 = A * 2 ^ 3 = A * 8

有了上面的结论后，那么就有了下面的递归

从上面的公式中很容易看出来递归，那么A、B究竟该怎么表示呢？回到公式 N = 8 * A + B，不难看出，

A = N / 8  且 B = N & 7

A = N / 8 很好理解，可以看做8是被除数，N是商

B = N & 7 这个又回到了，我们的位运算的与运算上，因为B < 8，所以要获得B 只需要获取 N 的二级制最小位开始的后三位即可，所以这里是 & 0111，直接返回后3位的值

上面的理解了，程序就很容易写出来了

代码如下

#include <stdio.h>
int div7(int n) {
    if(n < 8)
    {
        return (n + 1) >> 3; //此处+1是为了处理n为7的情况
    }
    else
    {
        return (n >> 3) + div7((n >> 3) + n & 7);
    }
}
int main(){
    int n = 14;
    int x;
    x = div7(n);
    printf("%d div 7 is : %d\n", n, x);
} 

编译之后运行 14 div 7 is : 2

这里留一道地考题，如何求 任意数正整数对7求余，同样不利用乘法、除法、取模

编写PHP的C扩展，有三种方式：

1、External Modules：外部模块，也就是编译成共享库，用dl()函数动态加载

好处：

(1)不需要重新编译PHP
(2)PHP体积小，因为不需要编译进PHP

缺点：

(1)每次*.php脚本执行都需要用dl()去加载，效率较低
(2)每次都要调用dl()

2、Built-in Modules：编译进PHP

好处：

(1)不需要动态加载，模块在php脚本里面可以直接使用
(2)不需要将模块编译成.so共享库，因为直接编译进PHP

缺点：

(1)对模块的改变都需要重新编译PHP
(2)因为编译进PHP，所以PHP二进制文件较大，而且多占点内存

3、The Zend Engine：Zend核心里实现（略……有兴趣的话可以看Zend API）

Note：推荐用第2种方式，直接编译进PHP，但是在下面示例里，我们编译成外部模块，因为，外部模块不需要重新编译PHP，所以在测试阶段先编译成共享库，测试完后再用第2种方式重新编译进PHP。

什么是AOP

下面是Wikipedia的描述

In computing, aspect-oriented programming (AOP) is a patented[1] programming paradigm that aims to increase modularity by allowing the separation of cross-cutting concerns. It does so by adding additional behavior to existing code (an advice) without modifying the code itself, instead separately specifying which code is modified via a "pointcut" specification, such as "log all function calls when the function's name begins with 'set'". This allows behaviors that are not central to the business logic (such as logging) to be added to a program without cluttering the code core to the functionality. AOP forms a basis for aspect-oriented software development.

AOP为Aspect Oriented Programming的缩写，意为：面向切面编程（也叫面向方面），可以通过预编译方式和运行期动态代理实现在不修改源代码的情况下给程序动态统一添加功能的一种技术。AOP实际是GoF设计模式的延续，设计模式孜孜不倦追求的是调用者和被调用者之间的解耦，AOP可以说也是这种目标的一种实现。

Given an array of integers, every element appears three times except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

问题：给一个数组，里面只有一个数字一次，其它数字都出现3次，找出这个出现一次的数字，要求时间复杂度为O(n)，空间复杂度为O(1)。

解题思路：

这里我们需要用到的知识为二进制、位计算。这里需要思考数字在计算机是怎么存储的。考虑全部用二进制表示，如果我们把第i个位置上所有数字的和对3取余，那么只会有两个结果 0 或 1 (根据题意，3个0或3个1相加余数都为0).

AC代码如下：

#include <stdio.h>
int singleNumber(int A[], int n) {
    int count[32] = {0};
    int result = 0;
    for (int i = 0; i < 32; i++) {
        for (int j = 0; j < n; j++) {
            //判断A[J]的第i位的奇偶，奇数才加，偶数为0不加
            if ((A[j] >> i) & 1) {
                count[i]++;
            }
        }
        // 计算第i位的和，然后计算其对应的10进制，再通过与运算求和（其实加法求和也可以）
        result |= ((count[i] % 3) << i);
    }
    return result;
}

我们可以用一组CASE来测试一下 {12, 1, 12, 3, 12, 1, 1,15, 3, 3}

最后依次统计各位上的和如下

依次为 4447，高位为0直接省略。最后求余之后为 为 1111，转换为2进制则为 8+4+2+1 = 15

算法中值得注意的是：

通过位运算 (A[j] >> i) & 1 来判断奇偶

因为此题又看了一下位运算，感觉CS的世界博大精深

应游戏朋友要求做了个抽奖程序，还是拿C#做的，$MS大法好 ：）

游戏可以设定抽奖类型和跑马灯效果，做这个跑马灯效果的时候，还是很有趣的。

一般抽奖中，会用到类似于转盘的效果，最后停在某个地方，因为转盘是原型的，我们可以根据角度来判断精确到哪个区域，所以我采取了步进carry的方式，来处理方块类似于圆盘区域的显示。下面是跑马灯的状态：

跑马灯静止 -> 加速 -> 匀速 -> 递减 -> 静止

题目如下：

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

这基本就是水题，求最长不重复子串长度。关键在于考察处理边界情况的能力，主要是碰到相同字母，起始位置重新计算这个细节需要注意

代码如下：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(!s) return 0;
    var n = 0;
    var l = s.length;
    var _s = "";
    var _t = 0;
    for (var i = 0;i < l;i++) {
        var flag = _s.indexOf(s[i]);
        if(flag != -1){
            _s = _s.substr(++flag, _s.length) + s[i];
            _t = _s.length;
        } else {
            _s += s[i];
            _t++;
        }
        n = _t > n ? _t : n;
    }
    return n;
};