算法（一）

下面罗列几个简单的算法来活跃一下思维。

题目一

计算两个非负整数 x 和 y 的最大公约数:若 x 是 0，则最大公约数为 y。否则，将 x 除以 y得到余数m，x和y的最大公约数即为y和 m 的最大公约数。

解析：ax+by=kz
xy为非负整数,ab是倍数,k也是整数
z为最大公约数,能够被xy都整除
x=ny+m,m为余数
证明:m能够被最大公约数整除
m = x-ny = 整数倍*z,因为xy都是z的整数倍,所以余数肯定是最大公约数的整数倍
(a,b)=z (b,r)=z
所以下面的例子就比较好解释了:这样一直相除下去,如果余数为零,那么就说明传入的a就是最大公约数

- (int)test1:(int)a B:(int)b {
    if (b == 0) {
        return a;
    }
    
    int r = a % b;
    return [self test1:b B:r];
}

题目二

已知整数数组及目标数target，求数组中某两个数相加等于目标数的角标
举个例子：[2,4,5,3,8] 目标数为9，那么4+5= 9，返回这两个数的角标为1，2

说明：在看到这个题的时候，我们会很自然地想到用for循环遍历，只要获取到nums[n]+nums[m]=target，我们就可以返回n,m，如下：

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

但是我看到了另一种解法，也是想当不错的

func twoSum(_ nums:[Int], _ target:Int) -> [Int]? {
        //键值对,字典
        var d = [Int:Int]()
        //index1表示顺序 num表示值
        for (index1, num) in nums.enumerated(){

            //在这里判断target-nums的值是否有值,如果有值,说明之前已经添加了一个角标与其相加等于9的,此时index2是当前值的key
            if let index2 = d[target - num] {
                return [index2, index1]
            }else{
                //将角标作为d的值,将值作为d的角标
                d[num] = index1
            }
        }
        return nil
     
    }

题目三

反转数字，例如：将2456反转后得到6542

- (int)reverse:(int)num {
    int t = 0;
    /*
     第一次对数字进行取模，获取到的这个数即时反转后的最高位，之后对原数字除以10，看能除多少次，才为零（只要最后的数字不大于10，除以10即为0，还有余数），这样最高位要乘10的多少次方，
     之后按照这个流程走，即可获取到反转的数字，但这样做有个缺点，当尾数是0是时，反转后会没有这个0，因为这是数学算法，并不是反转文本
     */
    while (num != 0) {
        if (t > INT_MAX / 10 || t < INT_MIN / 10) {
            return 0;
        }
        
        t = t * 10 + num % 10;
        num /= 10;
        NSLog(@"t*10 = %d -- num = %d",t * 10,num);
    }
    return t;
}

以后还会不定时更新算法，锻炼自己。