面试算法题

1    

    /*
    * 
    *   [1,2,3,-2,-4,5,3,-2,4,1,-5,3]数组排序
    *  输出结果[1,2,3,5,3,4,1,3,-2,-4,-2,-5]
    * 要求:
    *1.正数在左，负数在右，
    *2.相对顺序不变，
    *3.空间复杂度O(1)
    *
    * 两种思路第二种好： 仔细看题，反方向考虑，既然小于0 的要放到最右边，所以只需要把大于0的往左边移动即可（往左冒泡）
    *
    */

    /* 解题思路1：
    * 1 首先找到小于0的
    * 2 从小与0的位置开始往后找大于0 的第一个数
    * 3 再使用冒泡，将大于0替换掉最前面那个小于0 的（判断条件: 小于0前面的数字是大于0 即可）
    */

public static void function1(int[] data){
        int temp=0;
        int index=0;
        for(int i=0;i<data.length;i++){
            if(data[i]<0){
                for(int j=i+1;j<data.length;j++){
                    if(data[j]>0){
                        //说明是第一次
                        if((j-1)==i){
                            temp=data[i];
                            data[i]=data[j];
                            data[j]=temp;
                            break;
                        }else{
                            while(index<(j-i)){
                                //交换
                                temp=data[j-index];
                                data[j-index]=data[j-1-index];
                                data[j-1-index]=temp;
                                ++index;
                            }
                        }
                        if(index>0) index=0;break;
                    }
                }
            }

        }
        for(int i=0;i<data.length;i++){
            System.out.println(data[i]);
        }
    }

 两种思路二： 反方向考虑，既然小于0 的要放到最右边，所以只需要把大于0的往左边移动即可（往左冒泡）

/*
    * 1 当data[i]大于0时进行向上冒泡
    * 2 条件： 从第二个元素开始，前面一个元素小于0
    * 3 冒泡交换值，交换后将 下标置0
    *  时间复杂度低
    **/
    public static void f2(int[] data) {
        int temp = 0;
        int index = 0;
        int loop=0;
        for (int i = 0; i < data.length; i++) {
            //如果当前data[i]大于0并且前面data[i-1]也是大于0 则不进行循环
            if (data[i] > 0 && i != 0 && data[i - 1] < 0) {
                //将大于0的网上冒泡，直到大于0的出现
               while (i-1-index>=0&&data[i-1-index]<0) {
                    //交换
                    temp = data[i - index];
                    data[i - index] = data[i - 1 - index];
                    data[i - 1 - index] = temp;
                    ++index;
                }
                 index=0;

        }
    }

//对方法2code review

public static void f2Review(int[] data) {
        int temp = 0;
        int currentIndex=0;
        for (int i = 0; i < data.length; i++) {
            //如果当前data[i]大于0并且前面data[i-1]也是大于0 则不进行循环
            if (data[i] > 0 && i != 0 && data[i - 1] < 0) {
                //将大于0的网上冒泡，直到大于0的出现
                currentIndex=i-1;

               while(currentIndex>=0&&data[currentIndex]<0){
                    //交换
                    temp = data[currentIndex+1];
                    data[currentIndex+1] = data[currentIndex];
                    data[currentIndex] = temp;
                    loop--;
                }

            }
        }
    }

掌握算法，以及思路，很多时候为了解决问题而陷阱到题目中去了，这样就会想方法1一样多写很多无用的代码，并且将题目想的复杂化了增加了出错的可能性，也降低的代码的可读性，所以很多时候我们做事不妨跳出当前的怪圈去思考问题，反方向，或者以另外一种视觉去看待问题，反而能有更好的解决方案

后续继续更新

2  考察的是 冒泡排序以及对String类的应用熟悉度，涉及到了字符串的比较

 /*
    *  给定一个非0数组组成一个最大的数字：
    *  [12,324,67,2]  ----->   67324212
    *  字符排序
    */
    public  static void getBigNum(String[] data){
        StringBuilder stringBuilder = new StringBuilder();
        List<String> list = Arrays.asList(data);
        //冒泡算法
        String temp;
        for(int i=0;i<data.length-1;i++){
            for(int j=i+1;j<data.length;j++){
                if(data[i].compareTo(data[j])>0){
                    temp=data[i];
                    data[i]=data[j];
                    data[j]=temp;
                }
            }
        }
        for(int i=data.length-1;i>0;i--){
           stringBuilder.append(data[i]);
        }

        System.out.println(stringBuilder.toString());
    }

3 链表反转

package com.算法;


public class SingleList {
     class Element {
        public  Element(Object value,Element next){
            this.value=value;
            this.next=next;
        }

         public  Element(){
         }

        public Object value = null;
        private Element next = null;
    }



    private Element head = null; //头结点

    /**
     * 初始化链表
     */
    void init() {
        head = new Element();
        head.value = null;
        head.next = null;
    }

    /**
     * 插入链表
     */
    void insertLinkList(Object o) {
        if (head==null) {
            //说明尚未初始化
            init();
        }
       Element element = head;
        while (element.next !=null) {
            //如果不是头
            element = element.next;
        }

        if(head.value==null){
            head.value=o;
            return;
        }
        Element addElement = new Element();
        addElement.value = o;
        //注释掉循环链表
        //addElement.next = head;
        element.next = addElement;
    }


    public  static void main(String[] args){
        SingleList circleLinkList=new SingleList();
        circleLinkList.insertLinkList("1");
        circleLinkList.insertLinkList("2");
        circleLinkList.insertLinkList("3");
        circleLinkList.insertLinkList("4");

        new SingleList().revser(circleLinkList);
    }

    public   void revser( SingleList circleLinkList){
        Element head = circleLinkList.head;
        Element currentElement=head.next;
        //用于存放反转后的上一个节点
        Element next=head;
        Element temp=null;
        while(currentElement!=null){
            temp=currentElement.next;
            //存放上一个
            currentElement.next=new Element(next.value,(currentElement==head.next)?null:next.next);
            //存放当前节点
            next=currentElement;
            //反转前的上一个节点
            currentElement=temp;
        }
        while (next!=null){
            System.out.println(next.value);
            next=next.next;
        }




    }
}

总结: 重点在于将当前节点的上一个节点作为当前节点的下一个节点，并且不能影响后面的链表反转

4 字符串反转： 首尾相互替换，如果为奇数中间的就不需要动

public static void main(String[] args){
    /*
    *  利用最少的空间将字符串反转
    */
    String data="0123456789";
    //计算出需要互换的次数
    int num=data.length()>>1;
    char[] chars = data.toCharArray();
    char before;
    char after;
    for(int i=0;i<num;i++){
         before=chars[i];
         after=chars[data.length()-1-i];
        chars[data.length()-1-i]=before;
        chars[i]=after;
    }
    System.out.println(new String(chars));
}