算法day1 两数之和 两数相加 冒泡排序 快速排序

        两数之和

        最简单的思维方式肯定是去凑两个数，两个数的和是目标值就ok。这里两遍for循环解决。

 

          两数相加

                        敲了一晚上哈哈，结果超过int范围捏，难受捏。

public class Test2 {
    public static void main(String[] args) {
//        ListNode l1 = new ListNode(2);
//        l1.next = new ListNode(4);
//        l1.next.next = new ListNode(3);
//
//        ListNode l2 = new ListNode(5);
//        l2.next = new ListNode(6);
//        l2.next.next = new ListNode(4);

        ListNode l1 = new ListNode(5);
        ListNode l2 = new ListNode(5);


        ListNode listNode = new Test2().addTwoNumbers(l1, l2);
        System.out.println("l = " + listNode.val);
        System.out.println("l = " + listNode.next.val);
//        System.out.println("l = " + listNode.next.next.val);


//        for (int i = 0; ; i++) {
//            ListNode l = listNode.next;
//            if (l.next != null) {
//                System.out.println("l = " + l.val);
//            }else return;
//        }
    }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//            Map map = new HashMap();
//            map.put("l1",l1.val+l1.next.val+l1.next.next.val)
        int num1 = l1.val;
        System.out.println("num1 = " + num1);
        int num2 = l2.val;
        ListNode l = l1.next;
        ListNode ll = l2.next;
        for (int i = 1; ; i++) {
            if ( l != null && l.next != null  ){
                num1 += l.val*Math.pow(10,i);
                l =  l.next;
            } else{
                if ( l != null  ){
                    num1 +=  l.val*Math.pow(10,i);
                }
                System.out.println("num1 = " + num1);
                for (int j = 1; ; j++) {
                    if (ll != null && ll.next != null){
                        num2 += ll.val*Math.pow(10,j);
                        ll =  ll.next;
                    }else{
                        if (ll != null ){
                            num2 += ll.val*Math.pow(10,j);
                        }
                        System.out.println("num2 = " + num2);
                        int temp = num1 +num2;
                        System.out.println("temp = " + temp);
                        int digit;
                        int place = 1;  //位数
                        ListNode lll = new ListNode();

                        int count = 0;
                        while (temp != 0) {
                            temp = temp / 10;
                            ++count;
                        }



                        temp = num1 +num2;
                        if (temp == 0)count=1;
                        ListNode listNode = new ListNode();
                        Map<String, ListNode> map =null;
                        for (int i1 = 0; i1 < count; i1++) {
                            digit = temp % 10;
                            temp = temp / 10;
                            System.out.println("Digit at place " + place + " is: " + digit);
//                            lll.val = digit;
//                             lll = lll.next;
                            if (i1 == 0){
                                lll.val = digit;
                                if (count!=1){
                                    lll.next =   listNode;
                                }
                            }else if (i1 == 1){
                                map = new HashMap<>();
                                map.put("listNode"+i1,new ListNode());
                                listNode.val = digit;
                                if (count==2)return lll;
                                listNode.next = map.get("listNode"+i1);
                                System.out.println("map.get(\"listNode111\"+i1).val = " + map.get("listNode"+i1).val);
                            } else{
                               map.get("listNode"+(i1-1)).val = digit;
                                if (i1==count-1)return lll;
                                map.put("listNode"+i1,new ListNode());
                                map.get("listNode"+(i1-1)).next = map.get("listNode"+i1);
                                System.out.println("map.get(\"listNode222\"+i1).val = " + map.get("listNode"+i1).val);
                            }
                            place *= 10;
                        }
                        return lll;
                    }
                }
            }
        }
    }


}

//两数求和
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next;}
}

        冒泡排序  

        有这样一个数组：[ 6,1,2,4,6,2  ]  冒泡排序是将相邻两个元素比大小转换位置最终实现从小到大或者从大到小排序的过程。

        首先关注第一个元素6：

                6和1比转换位置

                6和2比转换位置

                6和4比转换位置

                6和6比不动。

                6和2比转换位置

        再然后第二个元素到最后一个元素。这样每一个元素都找到他们对应的位置。

public static void sort1(int[] data){
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data.length - i - 1; j++) {
                if (data[j] > data[j + 1]){
                    int k = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = k;
                }
            }
        }
    }

        快速排序

排序——快速排序（Quick sort）-CSDN博客    快速排序底层是递归的思想。

        有这样一个数组：[ 6,1,2,4,6,2  ] ，快速排序是有左右两个数组的下标指针，一个基准数。

一开始 ：

                左指针指向最左边  

                右指针指向最右边

                基准数默认初始值为  最左边

                左指针负责挑出大于基准值的，右指针负责挑出小于基准值的。当左右指针相遇时，将数组分为左右两个以基准值为界限的小数组和大数组。

                然后左右两个数组递归。

        从右指针开始比，2比基准数6小就和左指针交换位置，同时左指针的值6赋给基准值6.

        这时，左指针位置下移到1

        再从左指针开始比，1比基准值6小，2比基准值6小，4比基准值6小，6比基准值6不大

        左右指针相遇时 将基准值6赋给右【2，1，2，4，6 ，6】

        这个时候的小数组是【2，1，2，4，6】 大数组【6】再重新进行快速排序。

​​​​​​​