排序算法

排序算法

• 快速排序

    /**
     * 快速排序
     * <p>
     * 核心的思路是取第一个元素（或者最后一个元素）作为分界点，把整个数组分成左右两侧，左边的元素小于或者等于分界点元素，
     * 而右边的元素大于分界点元素，然后把分界点移到中间位置，对左右子数组分别进行递归，最后就能得到一个排序完成的数组。
     * 当子数组只有一个或者没有元素的时候就结束这个递归过程。
     */
    public static void quickSort(int[] nums, int left, int right) {
        if (left > right) return;
        int key = nums[left];
        int l = left;
        int r = right;
        while (l < r) {
            while (nums[r] >= key && l < r)
                r--;
            while (nums[l] <= key && l < r)
                l++;
            if (l < r)
                swap(nums, r, l);
        }

        nums[left] = nums[r];
        nums[r] = key;

        quickSort(nums, left, r - 1);
        quickSort(nums, r + 1, right);
    }

• 归并排序

• 冒泡排序

    /**
     * 冒泡排序
     * 冒泡排序从左到右依次比较两个相邻的元素，如果前一个元素比较大，就把前一个元素和后一个元素交换位置，
     * 完成一趟循环后保证了最大的元素在最后一位。接下来进行第二趟排序，第二趟排序完成后第二大的元素在倒数第二位。
     * 依次遍历直至整个数组排序完成。
     * <p>
     * 冒泡排序的时间复杂度是O(n2),空间复杂度为
     *
     * @param nums
     * @return
     */
    public static void bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }

查找算法

字符串

• LeetCode 125. 验证回文串

 public static boolean isPalindrome(String s) {
    int right = s.length() - 1;
    int left = 0;
    while (left < right) {
      char leftChar = s.charAt(left);
      while (!Character.isLetterOrDigit(leftChar) && left < right) {
        leftChar = s.charAt(++left);
      }
      char rightChar = s.charAt(right);
      while (!Character.isLetterOrDigit(rightChar) && left < right) {
        rightChar = s.charAt(--right);
      }
      if (Character.toLowerCase(leftChar) != Character.toLowerCase(rightChar)) {
        return false;
      }
      left++;
      right--;
    }
    return true;
  }

数组相关

• LeetCode 1. 两数之和

  public static int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
      int result = target - nums[i];
      for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] == result) {
          return new int[] { i, j };
        }
      }
    }
    return null;
  }

 public static int[] twoSum1(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
      if (map.containsKey(target - nums[i])) {
        return new int[] { map.get(target - nums[i]), i };
      }
      map.put(nums[i], i);
    }
    return null;
  }

• 303. 区域和检索 - 数组不可变

// 解法1
class NumArray {
    private final int[] nums;
    public NumArray(int[] nums) {
       this.nums=nums;
    }
    
    public int sumRange(int left, int right) {
        if(nums==null){
            return 0;
        }
        int sum = 0;
        for(;left<=right;left++){
            sum += nums[left];
        }
        return sum;
    }
}

// 解法2
public class NumArray {
    private final int[] sums;

    public NumArray(int[] nums) {
        int n = nums.length;
        sums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + sums[i + 1];
        }
    }

    public int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
}

• 643. 子数组最大平均数 I

  public double findMaxAverage(int[] nums, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) {
      sum += nums[i];
    }
    if (nums.length == k) {
      return (double) sum / k;
    }
    int maxSum = sum;
    if (k == 1) {
      for (int i = 1; i < nums.length - 1; i++) {
        maxSum = Math.max(maxSum, nums[i]);
      }
      return maxSum;
    }
    for (int i = 0; i < nums.length - k; i++) {
      sum = sum - nums[i] + nums[i + k];
      maxSum = Math.max(maxSum, sum);
    }
    return (double) maxSum / k;
  }

链表相关

二叉树

递归