编程珠玑

计算机编程充满乐趣。有时候,它是一门优雅的科学,有时候,它要去开发和使用新的软件工具。编程与人息息相关:客户实际想解决什么问题?

① 二维数组中的查找

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

解题思路:因为数组从左到右递增,从上到下递增,所以从左下角来看,从左到右递增,从下到上递减。(为什么不从左上角开始搜寻,左上角向右和向下都是递增,那么对于一个点,对于向右和向下会产生一个岔路;如果我们选择从左下角开始搜寻的话,如果大于就向右,如果小于就向上)

                  1  3  5  7
                  2  4  6  8
                  9  11 13 15

解题思路一代码:

public class Solution {
    public boolean Find(int [][] array,int target) {
        int i=0; //i表示列 array[0].length表示列数
        int len=array.length-1;//len表示横 array.length表示横数
        while((len>=0) && (i<array[0].length)){
        // 从左下角开始找,如果目标小于左下角数,就往上。
            if(array[len][i]>target){
                len--;
            }
         //如果目标大于左下角数,就往右
            else if(array[len][i]<target){
                i++;
            }
            else{
                return true;
            }
        }
        return false;
    }
}

解题思路二: 把每一行看成有序递增的数组,利用二分法查找,通过遍历每一行得到答案,时间复杂度 为nlogn。

代码为:

public class Solution {
    public boolean Find(int [][] array,int target) {

        for(int i=0;i<array.length;i++){
            int low=0;
            int high=array[i].length-1;
            while(low<=high){
                int mid=(low+high)/2;
                if(target>array[i][mid])
                    low=mid+1;
                else if(target<array[i][mid])
                    high=mid-1;
                else
                    return true;
            }
        }
        return false;

    }
}

② 用两个栈实现队列

题目描叙:用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

解题思路:有两个栈,栈1和栈2.当入栈的时候,我们将它全放进栈1中,当需要出栈的时候,我们将栈1出栈到栈2中,然后再将栈2依次出栈。所以入栈的时候,思路很简单,注意到要将int类型转为Integer类型,我们使用了new Integer(int);当需要出栈的时候,我们用API提供的方法while(stack1.isEmpty())来将所有栈1的元素压入栈2中,然后将栈2弹出就可以。这里又涉及到将Integer的类型转为int类型的方法Integer.intValue();实现代码如下:

用两个栈实现一个队列的功能?要求给出算法和思路!
<分析>:
入队:将元素进栈A
出队:判断栈B是否为空,如果为空,则将栈A中所有元素pop,并push进栈B,栈B出栈;
如果不为空,栈B直接出栈。
用两个队列实现一个栈的功能?要求给出算法和思路!
<分析>:
入栈:将元素进队列A
出栈:判断队列A中元素的个数是否为1,如果等于1,则出队列,否则将队列A中的元素 以此出队列并放入队列B,直到队列A中的元素留下一个,然后队列A出队列,再把 队列B中的元素出队列以此放入队列A中。

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(new Integer(node));
    }

    public int pop() {
    if(stack2.isEmpty()){
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
    }
       return  stack2.pop().intValue();
    }
}

  转载请注明: Hi 高虎 编程珠玑

 上一篇
数据结构之冒泡排序 数据结构之冒泡排序
冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。 走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来
下一篇 
java集合框架 java集合框架
java集合框架① 定义:集合(collection)就是一个存储一组对象的容器对象,一般将这些对象称为集合的元素(element),Java集合框架支持三种类型的集合:规则集(set),线性表(list)和图(map),他们分别定义在接口
2016-07-27
  目录