Java版手撕算法

╰半橙微兮° 2022-03-02 15:56 183阅读 0赞

自己写的手撕算法练习

1.归并排序：

public static void merge(int []a,int l,int r,int mid)
        {
            int []temp=new int[r-l+1];
            int i=l;
            int j=mid+1;
            int k=0;
            while(i<=mid&&j<=r)
            {
                if(a[i]<=a[j])
                {
                    temp[k]=a[i];
                    i++;
                }
                else
                {
                    temp[k]=a[j];
                    j++;
                }
                k++;
            }
            while(i<=mid)
            {
                temp[k]=a[i];
                i++;
                k++;
            }
            while(j<=r)
            {
                temp[k]=a[j];
                j++;
                k++;
            }
            for(i=0,j=l;j<=r;j++,i++)
            {
                a[j]=temp[i];
            }
        }
        public static void ksort(int []a,int l,int r)
        {
            if(r-l>=1)
            {
                int mid=(l+r)/2;
                ksort(a,l,mid);
                ksort(a,mid+1,r);
                merge(a,l,r,mid);
            }
        }
        public static void main(String []args)
        {
            int []a={5,6,2,3,4,8,9};
            ksort(a,0,a.length-1);
            for(int i=0;i<a.length;i++)
                System.out.print(a[i]+",");
        }

2.快速排序

public static void qsort(int []a,int l,int r)
        {
            if(l>=r)
                return;
            int i=l,j=r;
            int t,temp=a[l];
            while(i<j)
            {
                while(i<j&&a[j]>=temp)//先从右往左找
                {
                    j--;
                }
                while(i<j&&a[i]<=temp)
                {
                    i++;
                }
                if(i<j)
                {
                    t=a[i];
                    a[i]=a[j];
                    a[j]=t;
                }
            }
            a[l]=a[i];
            a[i]=temp;
            qsort(a,l,i-1);
            qsort(a,i+1,r);
        }
        public static void main(String []args)
        {
            int []a={5,6,2,3,4,8,9};
            qsort(a,0,a.length-1);
            for(int i=0;i<a.length;i++)
                System.out.print(a[i]+",");
        }

3.双端链表

public class DeList {
        private class Node{
            private Node pre;
            private Node next;
            private int v;
            public Node(int v)
            {
                this.v=v;
                pre=null;
                next=null;
            }
    
            @Override
            public String toString() {
                return ""+v;
            }
        }
        private Node head;
        private Node tail;
        public DeList()
        {
            head=null;
            tail=null;
        }
        public void add(int v)//往链表尾部添加元素
        {
            Node node=new Node(v);
            if(head==null)
            {
                head=node;
            }
            else
            {
                node.pre=tail;
                tail.next=node;
            }
            tail=node;
        }
        public Node pollFirst()//拿到链表首部元素并弹出
        {
            if(head!=null) {
                Node node = head;
                head = head.next;
                if (head == null)
                    tail = null;
                else
                {
                    head.pre=null;
                }
                return node;
            }
            else
            {
                return null;
            }
        }
        public Node pollLast()//拿到链表尾部元素并弹出
        {
            if(tail==null)
                return null;
            Node node=tail;
            if(tail.pre!=null)
            {
                tail=tail.pre;
            }
            else {
                tail=null;
                head=null;
            }
            return node;
        }
        public boolean isEmpty()
        {
            if(head==null)
                return true;
            return false;
        }
        public static void main(String []args)
        {
            DeList l=new DeList();
            l.add(1);
            l.add(2);
            l.add(3);
            while(!l.isEmpty())
            {
                System.out.println(l.pollFirst());
            }
            l.add(4);
            l.add(5);
            l.add(6);
            while(!l.isEmpty())
            {
                System.out.println(l.pollLast());
            }
        }
    }

4.生产者消费者模型

public class Model {
        public static volatile boolean isRun=true;
        public static class Entity{
            String name;
            public Entity(String name){
                this.name=name;
            }
        }
        public static class Producer{
            BlockingQueue<Entity>buffer;
            public Producer(BlockingQueue<Entity>buffer)
            {
                this.buffer=buffer;
            }
            public void create()throws Exception
            {
                    Random random = new Random();
                    String name;
                    switch (random.nextInt(3) + 1) {
                        case 1:
                            name = "苹果";
                            break;
                        case 2:
                            name = "香蕉";
                            break;
                        case 3:
                            name = "梨";
                            break;
                        case 4:
                            name = "橘子";
                            break;
                        default:
                            name = "出错";
                    }
                    buffer.put(new Entity(name));
                    System.out.println("生产了一个"+name);
                }
            }
           public static class Consumer{
                BlockingQueue<Model.Entity>buffer;
                public Consumer(BlockingQueue<Model.Entity>buffer)
                {
                    this.buffer=buffer;
                }
                void eat()throws Exception
                {
                    Model.Entity entity=buffer.take();
                    System.out.println("我吃了"+entity.name);
                }
            }
    
        public static void main(String args[])
        {
            Model model=new Model();
            ExecutorService executorService=new ThreadPoolExecutor(10,20,60,TimeUnit.SECONDS,new LinkedBlockingDeque<Runnable>());
            BlockingQueue<Entity>buffer=new ArrayBlockingQueue<Entity>(3);
            Producer producer=new Producer(buffer);
            Consumer consumer=new Consumer(buffer);
            for(int i=0;i<5;i++)
            {
                executorService.execute(new Runnable() {
                    @Override
                    public void run() {
                        try {
                            while (isRun) {
                                producer.create();
                            }
                        }
                        catch (Exception e)
                        {
                            e.printStackTrace();
                        }
                        System.out.println("生产者关闭");
                    }
                });
            }
            for(int i=0;i<5;i++)
            {
                executorService.execute(new Runnable() {
                    @Override
                    public void run() {
                        try {
                            while(isRun) {
                                consumer.eat();
                            }
                        }
                        catch (Exception e)
                        {
                            e.printStackTrace();
                        }
                        System.out.println("消费者关闭");
                    }
                });
            }
            try {
                Thread.sleep(50);
            }
            catch (Exception e)
            {
                e.printStackTrace();
            }
            isRun=false;
            executorService.shutdown();
        }
    }

5.翻转链表

public ListNode ReverseList(ListNode head) {
            ListNode tail,pre;
            if(head==null||head.next==null)
                return head;
            pre=head.next;
            head.next=null;
            tail=head;
            head=pre;
            while(head.next!=null)
            {
                pre=head.next;
                head.next=tail;
                tail=head;
                head=pre;
            }
            head.next=tail;
            return head;
        }

6.前中序数组构建二叉树

public int index=1;
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
            if(in.length==0)
                return null;
            int mid,i;
            TreeNode root=new TreeNode(pre[0]);
            root.left=null;
            root.right=null;
            for(i=0;i<in.length;i++)
            {
                if(in[i]==pre[0])
                {
                    BuildTree(root,0,i-1,pre,in,0);
                    BuildTree(root,i+1,in.length-1,pre,in,1);
                    break;
                }
            }
            return root;
        }
        public void BuildTree(TreeNode t,int l,int r,int []pre,int []in,int state)
        {
            if(l>r||index>pre.length)
                return;
            int i;
            for(i=l;i<=r;i++)
            {
                if(in[i]==pre[index])
                {
                    if(state==0)
                    {
                        t.left=new TreeNode(pre[index]);
                        t.left.left=null;
                        t.left.right=null;
                        index++;
                        BuildTree(t.left,l,i-1,pre,in,0);
                        BuildTree(t.left,i+1,r,pre,in,1);
                    }
                    else
                    {
                        t.right=new TreeNode(pre[index]);
                        t.right.left=null;
                        t.right.right=null;
                        index++;
                        BuildTree(t.right,l,i-1,pre,in,0);
                        BuildTree(t.right,i+1,r,pre,in,1);
                    }
                    break;
                }
            }
        }

7.Arrays.sort按要求排序

题目:

[https://www.nowcoder.com/practice/8fecd3f8ba334add803bf2a06af1b993?tpId=13&tqId=11185&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_8fecd3f8ba334add803bf2a06af1b993_tpId_13_tqId_11185_tPage_2_rp_2_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Comparator;
    
    public class Solution {
        public String PrintMinNumber(int [] numbers) {
            Comparator cmp=new MyCmp();
            Integer nums[]=new Integer[numbers.length];
            for(int i=0;i<numbers.length;i++)
                nums[i]=numbers[i];
            Arrays.sort(nums,cmp);
            StringBuffer s=new StringBuffer();
            for(int i=0;i<nums.length;i++)
                s.append(nums[i]);
            String t=s.toString();
            return t;
        }
    }
    class MyCmp implements Comparator<Integer> {
        public int compare(Integer o1, Integer o2) {
            ArrayList<Integer>a1=new ArrayList<Integer>();
            ArrayList<Integer>a2=new ArrayList<Integer>();
            int t1=o1,t2=o2;
            while(t1!=0)
            {
                a1.add(t1%10);
                t1/=10;
            }
            while(t2!=0)
            {
                a2.add(t2%10);
                t2/=10;
            }
            int i=a1.size()-1,j=a2.size()-1;
            while(i>=0||j>=0)
            {
                if(i<0)
                {
                    t1=a1.get(0);
                }
                else
                {
                    t1=a1.get(i);
                }
                if(j<0)
                {
                    t2=a2.get(0);
                }
                else
                {
                    t2=a2.get(j);
                }
                if(t1<t2)
                {
                    return -1;
                }
                else if(t1>t2)
                {
                    return 1;
                }
                i--;
                j--;
            }
            return -1;
        }
    }

[https_www.nowcoder.com_practice_8fecd3f8ba334add803bf2a06af1b993_tpId_13_tqId_11185_tPage_2_rp_2_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/8fecd3f8ba334add803bf2a06af1b993?tpId=13&tqId=11185&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking