算法

剑指Offer和Leetcode数据结构与算法实现。

1.反转链表(JZ15)

// 链表类
class LinkListedNode {
    int val;
    LinkListedNode next;

    LinkListedNode(int val) {
        this.val = val;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public LinkListedNode getNext() {
        return next;
    }

    public void setNext(LinkListedNode next) {
        this.next = next;
    }
}
//反转类
public class ReverseLinkListed {

    /*
    * 1->2->3->null
    * 递归入栈
    * null
    * 3
    * 2
    * 1
    * 栈先进后出，所以null先出，此时3.next=null, reNode=3
    * linkListedNode.getNext().setNext(linkListedNode);-->将3设置在null上
    * linkListedNode.setNext(null);-->此时是这样一种状态 3->null
    * return reNode = 3;
    *
    * 3出栈，
    * linkListedNode.getNext().setNext(linkListedNode);--> 3->2
    * linkListedNode.setNext(null);-->3->2->null
    * reNode=3
    *
    * 2出栈
    *linkListedNode.getNext().setNext(linkListedNode);--> 3->2->1
    * linkListedNode.setNext(null);-->3->2->1->null
    * reNode=3
    *
    * 1出栈
     *linkListedNode.getNext().setNext(linkListedNode);--> 3->2->1->null
     * linkListedNode.setNext(null);-->3->2->1->null
     * reNode=3
    * */
    public static LinkListedNode reverse(LinkListedNode linkListedNode) {
        if(linkListedNode == null || linkListedNode.getNext() ==null) {
            return linkListedNode;
        }

        LinkListedNode reNode = reverse(linkListedNode.getNext());
        linkListedNode.getNext().setNext(linkListedNode);
        linkListedNode.setNext(null);

        return reNode;
    }

    public static LinkListedNode reverse2(LinkListedNode linkListedNode) {
        if (linkListedNode == null || linkListedNode.getNext() ==null) {
            return linkListedNode;
        }

        LinkListedNode pre = linkListedNode; //1
        LinkListedNode cur = linkListedNode.getNext(); //2
        LinkListedNode tmp = null;

        while (cur !=null) {
            tmp = cur.getNext(); //3
            cur.setNext(pre); // 2->1

            pre = cur; // pre=2
            cur = tmp; // cur=3
        }

        linkListedNode.setNext(null);

        return pre;
    }

    public static void main(String[] args) {
        LinkListedNode a = new LinkListedNode(1);
        LinkListedNode b = new LinkListedNode(2);
        LinkListedNode c = new LinkListedNode(3);

        a.setNext(b);
        b.setNext(c);

//        while (a != null) {
//            System.out.println(a.val);
//            a=a.getNext();
//        }
        LinkListedNode d = reverse2(a);
        while (d != null) {
            System.out.println(d.val);
            d=d.getNext();
        }
    }
}

二叉树中和为target的路径(JZ24)

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

// 二叉树类
class BinaryTree {
    int val;
    BinaryTree leftChild;
    BinaryTree rightChild;

    public BinaryTree(int val) {
        this.val = val;
    }
}

public class BinaryTreeRoad {
    ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> findPath(BinaryTree root, int target) {
        if (root == null) {
            return list;
        }
        target -= root.val;
        path.add(root.val);
        if (target == 0 && root.leftChild == null && root.rightChild == null) {
            list.add(new ArrayList<Integer>(path));
        }
        findPath(root.leftChild, target);
        findPath(root.rightChild, target);
        path.remove(path.size() - 1);

        return list;

    }
}

回文链表(LC234)

public boolean isPalindrome(ListNode head) {
        ArrayList<Integer> arrayList = new ArrayList<>();

        while(head != null) {
            arrayList.add(head.val);
            head=head.next;
        }
        StringBuffer tmpA = new StringBuffer();
        for (Integer a : arrayList) {
            tmpA.append(a);
        }
        StringBuffer tmpB = tmpA.reverse();

        return tmpA.equals(tmpB);


    }

寻找两个正数数组的中位数(LC4)

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length==0&&nums2.length==0){
            return 0;
        }
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i : nums1) {
            arrayList.add(i);
        }
        for (int i : nums2) {
            arrayList.add(i);
        }
        ArrayList<Integer> tmp = sort(arrayList);
        double res = 0;
        if(tmp.size()%2==1) {
            res = arrayList.get(tmp.size()/2);
        }else {
            res = ((double)(arrayList.get(tmp.size()/2-1)+arrayList.get(tmp.size()/2)))/2;
        }

        return res;

    }
    public ArrayList<Integer> sort(ArrayList<Integer> arrayList) {
        int tmp = 0;
        for(int i=0; i<arrayList.size()-1;i++) {
            for (int j = 0; j<arrayList.size()-i-1;j++){
                if(arrayList.get(j)>arrayList.get(j+1)) {
                    tmp = arrayList.get(j+1);
                    arrayList.remove(j+1);
                    arrayList.add(j+1,arrayList.get(j));
                    arrayList.remove(j);
                    arrayList.add(j,tmp);
                }
            }
        }
        return arrayList;
    }

赏

Thank you,么么哒

支付宝

微信