算法训练1

1、在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

二维数组，思路就是利用二分查找法循环遍历二维数组

/// target:要查找的数， array：数组
public boolean Find(int target, int [] [] array) {
        for(int i=0; i<array.length; i++) {
                int low = 0;
                int hight = array[i].length - 1;
                while(low <= hight) {
                        int mid = (low + hight) / 2;
                        if (mid > array[i][mid]) {
                              low = mid+1;
                        }else if (mid < array[i][mid]) {
                              hight = mid-1;
                        }else {
                              return true;
                        }
                }
        }
        return false;
}

2、用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

队列为先进先出，栈为先进后出，所以使用两个栈，入栈stack1后，在出栈stack1，之后入栈stack2，出栈stack2，这样就形成了类似先进先出的序列。

#include <iostream>
class Queue
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
            count << stack2.top();
            stack2.pop();
        }else{
            count << stack2.top();
            stack2.pop();
        }
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

void test(){
    Queue<int> queue;
    queue.push(1); queue.push(2);  queue.push(3);
    queue.pop(); queue.pop(); queue.pop();
}

3、将www.baidu.zhidao.com字符串翻译为com/zhidao/baidu/www

OC思想为：按照.将文字分为4部分的数组，然后从数组的最后循环拼接为目标文字。

NSString *str = @"www.baidu.zhidao.com";
NSArray *arr = [str componentsSeparatedByString:@"."]    
NSString *string = arr.lastObject;
for (int i=[arr count]-2; i>=0; i--) {
   string =  [NSString stringWithFormat:@"%@/%@",string,arr[i]];    
}
NSLog(@"%@",string);

4、大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家 列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为 [兔子数列]，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果

public:
     int Fibonacci(int n) {
         if (n == 0) return 0;
         if (n == 1) return 1;
         int num1 = 0, num2 = 1;
         int countNum = 0;
         for (int i = 2; i<= n ; ++i) {
             countNum = num1 + num2;
             num1 = num2;
             num2 = countNum;
         }
         return countNum;
      }

类似题目：
1、A：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
B：我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

这就是一个斐波那契数列：
登上第一级台阶有一种登法；登上两级台阶，有两种登法；
登上三级台阶，有三种登法；登上四级台阶，有五种登法……
1，2，3，5，8，13……所以，登上十级，有89种走法
代码：
public:
    int jumpFloor(int number) {
        if(number <= 0) return 0;
        if(number == 1) return 1;
        if(number == 2) return 2;
        int num1 = 1, num2 = 2;
        int countNum = 0;
        for(int i=3; i<= number; ++i){
            countNum = num1 + num2;
            num1 = num2;
            num2 = countNum;
        }
        return countNum;
    }

2、兔子出生后2个月就有繁殖能力，每一对成年兔子一个月就可生下一对兔子，不考虑兔子死亡问题，一年之后一共有多少对兔子？

兔子繁殖问题.png

5、输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

看到这个题目，表示感觉蒙圈。

如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响.

举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

public:
     int  NumberOf1(int n) {
         int count = 0;
         while(n != 0){
             count ++;
             n = n & (n-1);      //n-1之后和原值进行‘与’运算
         }
         return count;
     }