15道使用频率极高的基础算法题

1、合并排序，将两个已经排序的数组合并成一个数组，其中一个数组能容下两个数组的所有元素;

public static int[] merge(int[] a,int [] b) {

        int[] c = new int[a.length+b.length];
        //i用于标记数组a
        int i=0;
        //j用于标记数组b
        int j=0;
        //用于标记数组c
        int k=0;

        //a，b数组都有元素时
        while(i<a.length && j<b.length) {
            if(a[i]<b[j]) {
                c[k++] = a[i++];
            }else {
                c[k++] = b[j++];
            }
        }

        //若a有剩余
        while(i<a.length) {
            c[k++] = a[i++];
        }

        //若b有剩余
        while(j<b.length) {
            c[k++] = b[j++];
        }

        return c;

    }

2、合并两个已经排序的单链表;
3、倒序打印一个单链表;

/**
     * 递归方法逆序打印单链表
     * @param head
     */
    public static void printListReverse1(ListNode head)
    {
        if(head!=null)
        {
            if(head.next!=null)
            {
                printListReverse1(head.next);
            }
        }
        System.out.println(head.val);
    }
    /**
     * 使用栈逆序打印单链表
     * @param head
     */
    public static void printListReverse2(ListNode head)
    {
         Stack<Integer> stack=new Stack<Integer>();
        while(head!=null)
        {
            stack.push(head.val);
            head=head.next;     
        }
        while(!stack.isEmpty())
        {
            System.out.println(stack.pop());
        }
    }

4、给定一个单链表的头指针和一个指定节点的指针，在O(1)时间删除该节点;
5、找到链表倒数第K个节点;
6、反转单链表;
7、通过两个栈实现一个队列;
8、二分查找;
9、快速排序;
10、获得一个int型的数中二进制中的个数;
11、输入一个数组，实现一个函数，让所有奇数都在偶数前面;

public static void reorderOddEven(int[] array){
        if(array==null||array.length<=0)
            throw new RuntimeException("invalid array");
        int begin=0;
        int end=array.length-1;
        while(begin<end){
            while(begin<end&&(array[begin]&1)!=0)
                begin++;
            while(begin<end&&(array[end]&1)==0)
                end--;
            if(begin<end){
                int temp=array[end];
                array[end]=array[begin];
                array[begin]=temp;
            }
        }
    }

12、判断一个字符串是否是另一个字符串的子串;

public static void main(String[] args) {
        String test = "This is test for string";
        System.out.println(test.indexOf("This")); //0
        System.out.println(test.indexOf("is")); //2
        System.out.println(test.indexOf("test")); //8
        System.out.println(test.indexOf("for")); //13
        System.out.println(test.indexOf("for string       "));//-1
        
        if (test.indexOf("This")!=-1){
            //"只要test.indexOf('This')返回的值不是-1说明test字符串中包含字符串'This',相反如果包含返回的值必定是-1"
            System.out.println("存在包含关系，因为返回的值不等于-1");
            
        }else{
            
            System.out.println("不存在包含关系，因为返回的值等于-1");
        }
        
        
        if (test.indexOf("this")!=-1){
            //"只要test.indexOf('this')返回的值不是-1说明test字符串中包含字符串'this',相反如果包含返回的值必定是-1"
            System.out.println("存在包含关系，因为返回的值不等于-1");
            
        }else{
            
            System.out.println("不存在包含关系，因为返回的值等于-1");
        }
        

    }

13、把一个int型数组中的数字拼成一个串，这个串代表的数字最小;

public String PrintMinNumber(int [] numbers) {
   int n;
   String s="";
   ArrayList<Integer> list= new ArrayList<Integer>();
   n=numbers.length;
   for(int i=0;i<n;i++){
      list.add(numbers[i]);
   
   }
   Collections.sort(list, new Comparator<Integer>(){
      public int compare(Integer str1,Integer str2){
         String s1=str1+""+str2;
         String s2=str2+""+str1;
         return s1.compareTo(s2);
      }
   });
   for(int j:list){
      s+=j;
   }
   return s;
}

14、输入一颗二叉树，输出它的镜像（每个节点的左右子节点交换位置）;
15、输入两个链表，找到它们第一个公共节点;