常见算法

谁践踏了优雅 2022-11-05 12:59 124阅读 0赞

## 常见排序算法 ##

### 冒泡排序 ###

public class BubbleSort implements IArraySort { 
    
        @Override
        public int[] sort(int[] sourceArray) throws Exception { 
            // 对 arr 进行拷贝，不改变参数内容
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    
            for (int i = 1; i < arr.length; i++) { 
                // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
                boolean flag = true;
    
                for (int j = 0; j < arr.length - i; j++) { 
                    if (arr[j] > arr[j + 1]) { 
                        int tmp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = tmp;
    
                        flag = false;
                    }
                }
    
                if (flag) { 
                    break;
                }
            }
            return arr;
        }
    }

### 选择排序 ###

public class SelectionSort implements IArraySort { 
    
        @Override
        public int[] sort(int[] sourceArray) throws Exception { 
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    
            // 总共要经过 N-1 轮比较
            for (int i = 0; i < arr.length - 1; i++) { 
                int min = i;
    
                // 每轮需要比较的次数 N-i
                for (int j = i + 1; j < arr.length; j++) { 
                    if (arr[j] < arr[min]) { 
                        // 记录目前能找到的最小值元素的下标
                        min = j;
                    }
                }
    
                // 将找到的最小值和i位置所在的值进行交换
                if (i != min) { 
                    int tmp = arr[i];
                    arr[i] = arr[min];
                    arr[min] = tmp;
                }
    
            }
            return arr;
        }
    }

### 插入排序 ###

public class InsertSort implements IArraySort { 
    
        @Override
        public int[] sort(int[] sourceArray) throws Exception { 
            // 对 arr 进行拷贝，不改变参数内容
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    
            // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
            for (int i = 1; i < arr.length; i++) { 
    
                // 记录要插入的数据
                int tmp = arr[i];
    
                // 从已经排序的序列最右边的开始比较，找到比其小的数
                int j = i;
                while (j > 0 && tmp < arr[j - 1]) { 
                    arr[j] = arr[j - 1];
                    j--;
                }
    
                // 存在比其小的数，插入
                if (j != i) { 
                    arr[j] = tmp;
                }
    
            }
            return arr;
        }
    }

### 快速排序 ###

###### 实现一 ######

public class QuickSort implements IArraySort { 
    
        @Override
        public int[] sort(int[] sourceArray) throws Exception { 
            // 对 arr 进行拷贝，不改变参数内容
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    
            return quickSort(arr, 0, arr.length - 1);
        }
    
        private int[] quickSort(int[] arr, int left, int right) { 
            if (left < right) { 
                int partitionIndex = partition(arr, left, right);
                quickSort(arr, left, partitionIndex - 1);
                quickSort(arr, partitionIndex + 1, right);
            }
            return arr;
        }
    
        private int partition(int[] arr, int left, int right) { 
            // 设定基准值（pivot）
            int pivot = left;
            int index = pivot + 1;
            for (int i = index; i <= right; i++) { 
                if (arr[i] < arr[pivot]) { 
                    swap(arr, i, index);
                    index++;
                }
            }
            swap(arr, pivot, index - 1);
            return index - 1;
        }
    
        private void swap(int[] arr, int i, int j) { 
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
    }

###### 实现二 ######

public static int[] qsort(int arr[],int start,int end) {         
        int pivot = arr[start];        
        int i = start;        
        int j = end;        
        while (i<j) {             
            while ((i<j)&&(arr[j]>pivot)) {                 
                j--;            
            }            
            while ((i<j)&&(arr[i]<pivot)) {                 
                i++;            
            }            
            if ((arr[i]==arr[j])&&(i<j)) {                 
                i++;            
            } else {                 
                int temp = arr[i];                
                arr[i] = arr[j];                
                arr[j] = temp;            
            }        
        }        
        if (i-1>start) arr=qsort(arr,start,i-1);        
        if (j+1<end) arr=qsort(arr,j+1,end);        
        return (arr);    
    }    
     
    public static void main(String[] args) {         
        int arr[] = new int[]{ 3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};        
        int len = arr.length-1;        
        arr=qsort(arr,0,len);        
        for (int i:arr) {             
            System.out.print(i+"\t");        
        }    
    }
     
    /*//方式二*/
    更高效点的代码：(TextendsComparable和SortUtil都是自己封装的类，里面重写和实现了compareTo和swap方法)
    public <TextendsComparable<?superT>>
    T[] quickSort(T[] targetArr,int start,int end)
    { 
    inti=start+1,j=end;
    T key=targetArr[start];
    SortUtil<T> sUtil=new SortUtil<T>();
     
    if(start==end)return(targetArr);
     
     
    /*从i++和j--两个方向搜索不满足条件的值并交换 * *条件为：i++方向小于key，j--方向大于key */
    while(true)
    { 
    while(targetArr[j].compareTo(key)>0)j--;
    while(targetArr[i].compareTo(key)<0&&i<j)i++;
    if(i>=j)break;
    sUtil.swap(targetArr,i,j);
    if(targetArr[i]==key)
    { 
    j--;
    }else{ 
    i++;
    }
    }
     
    /*关键数据放到‘中间’*/
    sUtil.swap(targetArr,start,j);
     
    if(start<i-1)
    { 
    this.quickSort(targetArr,start,i-1);
    }
    if(j+1<end)
    { 
    this.quickSort(targetArr,j+1,end);
    }
     
    returntargetArr;
    }
     
     
    /*//方式三：减少交换次数，提高效率/*/
    private<TextendsComparable<?superT>>
    voidquickSort(T[]targetArr,intstart,intend)
    { 
    inti=start,j=end;
    Tkey=targetArr[start];
     
    while(i<j)
    { 
    /*按j--方向遍历目标数组，直到比key小的值为止*/
    while(j>i&&targetArr[j].compareTo(key)>=0)
    { 
    j--;
    }
    if(i<j)
    { 
    /*targetArr[i]已经保存在key中，可将后面的数填入*/
    targetArr[i]=targetArr[j];
    i++;
    }
    /*按i++方向遍历目标数组，直到比key大的值为止*/
    while(i<j&&targetArr[i].compareTo(key)<=0)
    /*此处一定要小于等于零，假设数组之内有一亿个1，0交替出现的话，而key的值又恰巧是1的话，那么这个小于等于的作用就会使下面的if语句少执行一亿次。*/
    { 
    i++;
    }
    if(i<j)
    { 
    /*targetArr[j]已保存在targetArr[i]中，可将前面的值填入*/
    targetArr[j]=targetArr[i];
    j--;
    }
    }
    /*此时i==j*/
    targetArr[i]=key;//应加判断
     
    /*递归调用，把key前面的完成排序*/
    this.quickSort(targetArr,start,i-1);
     
     
    /*递归调用，把key后面的完成排序*/
    this.quickSort(targetArr,j+1,end);
    //两个递归应加判断
    }

## 常见链表问题 ##

### 删除链表倒数第N个元素，并返回头结点 ###

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
    class Solution { 
        public ListNode removeNthFromEnd(ListNode head, int n) { 
    
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        // Advances first pointer so that the gap between first and second is n nodes apart
        for (int i = 1; i <= n + 1; i++) { 
            first = first.next;
        }
        // Move first to the end, maintaining the gap
        while (first != null) { 
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    
        }
    }

### 环形链表 ###

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
    public class Solution { 
        public boolean hasCycle(ListNode head) { 
            
            if (head == null || head.next == null) { 
                return false;
            }
            ListNode slow = head;
            ListNode fast = head.next;
            while (slow != fast) { 
                if (fast == null || fast.next == null) { 
                    return false;
                }
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
        }
    }

## 二叉树 ##

### 二叉树的最大深度 ###

> 本题思路：采用递归+广度优先搜索的方式进行求解。  
> 步骤一：构建递归函数（局部变量存储每一层的节点list）  
> 步骤二：依取list的值，将新的子节点的值添加到newlist中，并返回+1.  
> 步骤三：开始新的递归函数（newlist）,直到newlist为空，则返回总计数。

public class Solution { 
    	public int maxDepth(TreeNode root) { 
    	  if(root == null) { 
    	   return 0;
    	   }
    	List<TreeNode> list = new ArrayList<TreeNode>();
    	list.add(root);
    	int result = tree(list);
    	return result;
      }
    	public int tree(List<TreeNode> list) { 
    	    if(list.size() == 0) { 
    	        return 0;
    	    }
    	    
    	    List<TreeNode> dataList = new ArrayList<TreeNode>();
    	    for(int i = 0;i < list.size();i++) { 
    	        TreeNode tempNode = list.get(i);
    	        if(tempNode.left != null) { 
    	            dataList.add(tempNode.left);
    	        }
    	        if(tempNode.right != null) { 
    	            dataList.add(tempNode.right);
    	        }
    	    }
    	    return tree(dataList) + 1;
    	    
      }
    }

## 滑动窗口 ##

### 无重复字符的字长子串 ###

public class Solution { 
        public static int lengthOfLongestSubstring(String s) { 
            int n = s.length();
            Set<Character> set = new HashSet<>();
            int result = 0, index = 0, move = 0;
            while (index < n && move < n) { 
                //charAt：返回指定位置处的字符
                if (!set.contains(s.charAt(move))) { 
                    set.add(s.charAt(move));
                    j++;
                    result = Math.max(result, move - index);
                } else { 
                    set.remove(s.charAt(index));
                    index++;
                }
            }
            return result;
        }
    }