算法_初级算法

前言

日期：2020-04-24

1. 初始内容：常见算法题

一、字符串

1. KMP算法

• 概念：对字符串进行切割分组（前缀、后缀），按顺序匹配时，利用分组子串提高匹配效率
• 作用：解决字符串查找的问题
• 时间复杂度O(m+n) 空间复杂度O(m)
• 延伸
  • 暴力匹配算法：每次匹配失败，都重新回溯（匹配不到，索引回到上一次匹配到的位置，再+1继续从第一个开始匹配）

2. 替换空格

题目：将给定的字符串中的空格全部替换为233

• 常规方法：遍历，查找到空格的字符串索引位置，再进行添加
• API： string.replaceAll(“\s”,”233”);

3. 最长公共前缀

题目：查找给定字符串数组中的最长公共前缀

• 特别的技巧思路：先排序

// 不使用排序则需要嵌套循环
private static void getPrefix(String[] ss) {
        String str = new String();
        A:
        for (int i = 0; i < ss[0].length() ; i++) {
            String prefix = ss[0].substring(0,i+1);
            B:
            for (int j = 1; j < ss.length  ; j++) {
                if(ss[j] .startsWith(prefix)){
                    // 全部比中
                    if(j == ss.length-1){
                        str = prefix;
                    }
                }else {
                    System.out.println(str);
                    break A;
                }
            }

        }
    }

4. 回文串

题目：给定字符串（区分大小写），构造出最长的回文串（正读、反读一致），返回长度

private static int getLengthOfHw(String s) {
        int len = 0;
        // 1.奇数、偶数字符数量
        int oddCount = 0;
        int evenCount = 0;
        // 2.计算各个字符的特征
        String temp = new String(s);
        while (temp.length() > 0) {
            int beforeLength = temp.length();
            System.out.println("[Param:beforeLength]" + beforeLength);
            String single = temp.charAt(0) + "";
            temp = temp.replaceAll(single, "");
            int afterLength = temp.length();
            System.out.println("[Param:afterLength]" + afterLength);
            int count = beforeLength - afterLength;
            if ((count & 1) != 1) {
                // 2.1偶数累加
                evenCount = evenCount + count;
            } else if ((count & 1) == 1) {
                // 2.2奇数保存最长的
                if (oddCount < count) {
                    oddCount = count;
                }
            }

        }
        // 3.计算总数：奇数+偶数
        len = oddCount + evenCount;
        return len;
    }

---

题目：验证回文串，忽略空格，大小写

• 技巧：判断字符是否为子母或数字 Character.isLetterOrDigit()

private static boolean vertifyHw(String s, int frontIndex, int endIndex){
        boolean flag = false;
        // 1.判断完毕
        if (frontIndex >= endIndex) {
            flag = true;
        }
        System.out.println("[Method:vertifyHw][Params:frontIndex/endIndex]" + frontIndex + "-" + endIndex);

        // 2.逐个判断
        char front = s.charAt(frontIndex++);
        char end = s.charAt(endIndex--);
        System.out.println("[Method:vertifyHw][Params:front/end]" + front + "-" + end);

        // 3.判断
        if(Objects.equals(front,end)){
            flag = true;
        }

        // 4.递归
        if(flag){
            return vertifyHw(s,frontIndex,endIndex);
        }
        
        return flag;
    }

    private static boolean vertifyHw2(String s, int frontIndex, int endIndex) {
        // 1.判断完毕
        if (frontIndex >= endIndex) {
            return true;
        }
        System.out.println("[Method:vertifyHw][Params:frontIndex/endIndex]" + frontIndex + "-" + endIndex);

        // 2.逐个判断
        char front = s.charAt(frontIndex++);
        char end = s.charAt(endIndex--);
        System.out.println("[Method:vertifyHw][Params:front/end]" + front + "-" + end);

        // 3.判断
        if (!Objects.equals(front, end)) {
            return false;
        }

        // 4.递归
        return vertifyHw2(s, frontIndex, endIndex);
    }

---

题目：给定字符串，找出其中最长的回文子串

• 技巧：中心扩展法

// 获取给定字符串中，最长的回文子串
    private static String getLongestHw(String s) {

        String longestHw = "";
        // 2.遍历所有回文子串
        for (int i = 1; i < s.length() - 1; i++) {
            String hw = getLongestHw(s, i);
            // 3.保存最长
            if(longestHw.length()<hw.length()){
                longestHw = hw;
            }
        }

        return longestHw;
    }

    // 根据字符串和索引，获取以该索引为中心的最大回文串
    private static String getLongestHw(String s, int midIndex) {

        int len = s.length();
        if (midIndex == 0 || midIndex == len) {
            return "";
        }
        // 1.左右延伸
        int endIndex = midIndex + 1;
        int startIndex = midIndex - 1;
        String hw = "";
        // 2.判断
        while (startIndex >= 0 && endIndex <= len - 1) {
            System.out.println("[Method:even][Datas:endIndex/startIndex]" + endIndex + "/" + startIndex);
            // 2.1字符
            char start = s.charAt(startIndex);
            char end = s.charAt(endIndex);
            // 2.2回文
            if (Objects.equals(start, end)) {
                hw = s.substring(startIndex, endIndex + 1);
                System.out.println("[Description:回文][Data:halfEndHw]" + hw);
            } else {
            }
            ++endIndex;
            --startIndex;
        }

        return hw;
    }


// LeetCode答案
static class Solution {
        private int index, len;

        // 遍历获取最长回文子串
        public String longestPalindrome(String s) {
            if (s.length() < 2)
                return s;
            for (int i = 0; i < s.length() - 1; i++) {
                PalindromeHelper(s, i, i);  // 以i为中心，向左右两边延伸-奇数
                PalindromeHelper(s, i, i + 1);   // 以i，i+1两个为中心，向左右延伸-偶数
            }
            return s.substring(index, index + len);
        }
        // 计算起始索引和长度，得出最长回文串： 以l、r为中心，向左右两边延伸。注：若l = r，则以l为中心，
        public void PalindromeHelper(String s, int l, int r) {
            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
                l--;
                r++;
            }
            //替换最长的回文
            if (len < r - l - 1) {
                index = l + 1;
                len = r - l - 1;
            }
        }
    }

---

题目：获取字符串中最长的回文子序列

5. 括号匹配深度

题目：给定一个合法的括号序列，获取其深度

• 思路：从第一个字符往后遍历，遇到 ( 则count++，否则 count–;每次循环保存max值，max 保存每次循环中max和count的最大值

// 获取括号的深度
    private static int getDepthOfBracket(String s) {
        // 1.记录每轮的最大值
        int max = 0;
        int count = 0;
        // 2.遍历所有字符
        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i);
            if (Objects.equals(a, '(')) {
                ++count;
            } else {
                --count;
            }
            System.out.println("[Method:getDepthOfBracket-for][Datas:count/max]" + count + "/" + max);
            max = Math.max(max, count);
        }
        return max;
    }

6. 字符串转化为整数

题目：将字符串转化为整数，不合法的则返回0

• 思路：类型转化，将每个字符通过加法计算出来。
• 注意点：char转化int，是通过ascii码。

private static int stringToInt(String s) {
        int value = 0;
        // 1.判断是否含有正负字符

        // 2.循环计算
        for (int i = 0; i < s.length(); i++) {

            char temp = s.charAt(i);
            if (Character.isDigit(temp)) {
                // 2.1 ASCII码的加减，减去'0' 即可获取到与int相等的值
                int g = temp - '0';
                value = value * 10 + g;
                System.out.println("[Method:stringToInt-for][Datas:g/value]" + g + "/" + value);
            } else {
                return 0;
            }
        }
        return value;
    }

二、简单排序算法

1.冒泡排序

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。【维基百科】

• 思路：第一个字符开始，从头到尾依次相邻比较，大的放后面；循环此步骤
• 空间复杂度：O(1)
• 时间复杂度
  • 最好：O(1)
  • 最坏：O(n^2)
  • 平均：O(n^2)

// 1.冒泡排序，从小到大
public static int[] bubbleSort(int[] arr){

   for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (j + 1 == arr.length) {
                    break;
                }
                // 位移运算：一个数对另一个数位异或两次，该数不变
                if (arr[j] > arr[j + 1]) {
                    arr[j] = arr[j] ^ arr[j + 1];
                    arr[j + 1] = arr[j] ^ arr[j + 1];
                    arr[j] = arr[j] ^ arr[j + 1];
                }
            }
   }
   return arr;
}
// 2.冒泡排序，从小到大
public static int[] bubbleSort2(int[] arr) {
		// 1.总共几次循环
        for (int i = arr.length - 1; i > 0 ; i--) {
        	// 2.一次循环的比较
            for (int j = 0; j < i; j++) {
                // 2.1位移运算：一个数对另一个数位异或两次，该数不变
                if (arr[j] > arr[j + 1]) {
                    arr[j] = arr[j] ^ arr[j + 1];
                    arr[j + 1] = arr[j] ^ arr[j + 1];
                    arr[j] = arr[j] ^ arr[j + 1];
                }
            }
        }
        return arr;
    }

2.选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。【维基百科】

• 思路：从第一个字符开始往后比较，知道找到最值，交换位置；循环此步骤
• 空间复杂度：O(1)
• 时间复杂度
  • 最好：O(1)
  • 最坏：O(n^2)
  • 平均：O(n^2)

// 选择排序，从小到大
public static int[] selectionSort(int[] arr) {
        // 1.总共轮次
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            // 2.每轮比较次数
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            // 3.交换：自己本身是最值，则不用
            if (i != minIndex) {
                arr[i] = arr[i] ^ arr[minIndex];
                arr[minIndex] = arr[i] ^ arr[minIndex];
                arr[i] = arr[i] ^ arr[minIndex];
            }
        }
        return arr;
    }

3.插入排序

工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。【维基百科】

• 思路：从第一个字符开始，每次往后一个字符与前面（已经排好序）进行比较
• 空间复杂度：O(1)
• 时间复杂度
  • 最好：O(1)
  • 最坏：O(n^2)
  • 平均：O(n^2)

// 插入排序
public static int[] insertionSort(int[] arr){
	// 从左往右
    for (int i = 0; i < arr.length; i++) {
            // 新一个字符，逐个与前面字符的比较：从有望走
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > arr[j+1]) {
                    arr[j] = arr[j] ^ arr[j + 1];
                    arr[j + 1] = arr[j] ^ arr[j + 1];
                    arr[j] = arr[j] ^ arr[j + 1];
                }
            }
    }
    return arr;
}

4.希尔排序

也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。通过将比较的全部元素分为几个区域来提升插入排序的性能。【维基百科】

• 思路：先进行分组排序，再对每一组进行插入排序，每完成一次排序，都对分组数进行缩小

• 空间复杂度：O(1)

• 时间复杂度

  • 最好：O(1)
  • 最坏：O(n^2)

// 希尔排序
public static int[] shellSort(int[] arr) {
        // 1.获取小组数
        int count = arr.length / 2;
        int current;
        while (count > 0) {
            for (int i = count; i < arr.length; i++) {
                current = arr[i];
                int j = i - count;
                // 分组里的数据进行插入排序
                while (j >= 0 && current < arr[j]) {
                    arr[j + count] = arr[j];
                    j -= count;
                }
                arr[j + count] = current;
            }
            count /= 2;
        }
        return arr;
}

5.快速排序

又称分区交换排序），简称快排，是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。【百度百科】

• 思路：找到基准数字，每次分组（子序列）比较，递归排序
• 复杂度
  • 空间复杂度：O(log2n))
  • 时间复杂度：O(nlog2n)

// 快速排序
public static int[] quickSort(int[] arr){
    quickSort(arr, 0, arr.length - 1);
    return arr;
}

// 快速排序具体方法：递归
public static int[] quickSort(int[] arr,int left,int right){
    	// 1.结束
        if (left > right) {
            return;
        }
        // 基准数
        int i = left;
        int j = right;
        int base = arr[left];

        // 2.比较
        while (i != j) {
            // 1.右侧编号查找数字：比基准数小的索引
            while (j > i && arr[j] >= base) {
                j--;
            }
            // 2.左侧编号查找数字：比基准数大的索引
            while (j > i && arr[i] <= base) {
                i++;
            }
            // 3.数字交换：
            if (j > i) {
                arr[i] = arr[i] ^ arr[j];
                arr[j] = arr[i] ^ arr[j];
                arr[i] = arr[i] ^ arr[j];
            }
        }
        // 3.基准数字和left 位置数字交换
        arr[left] = arr[i];
        arr[i] = base;

        // 4.左、右侧数字再次排序
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
}