Space-Filling Curves

wiki：https://en.wikipedia.org/wiki/Space-filling_curve

1.Space-Filling Curve

2.Z-curve

致谢：https://www.docin.com/p-830484046.html

归并排序

    public void merge(int[] a, int low, int mid, int high) {
        int[] b = Arrays.copyOf(a, a.length);
        int i, j, k;
        for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
            if (b[i] < b[j])
                a[k] = b[i++];
            else
                a[k] = b[j++];
        }
        while (i <= mid)
            a[k++] = b[i++];
        while (j <= high)
            a[k++] = b[j++];
    }

    public void mergesort(int[] a, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            mergesort(a, low, mid);
            mergesort(a, mid + 1, high);
            merge(a, low, mid, high);
        }
    }

public void merge(int[] a, int low, int mid, int high) {

int[] b = Arrays.copyOf(a, a.length);

int i, j, k;

for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {

if (b[i] < b[j])

a[k] = b[i++];

else

a[k] = b[j++];

}

while (i <= mid)

a[k++] = b[i++];

while (j <= high)

a[k++] = b[j++];

}

public void mergesort(int[] a, int low, int high) {

if (low < high) {

int mid = (low + high) / 2;

mergesort(a, low, mid);

mergesort(a, mid + 1, high);

merge(a, low, mid, high);

}

快速排序快排

 public void quicksort(int []a,int low,int high){
        if(low<high){
            int pivot=partition(a,low,high);
            quicksort(a,low,pivot-1);
            quicksort(a,pivot+1,high);
        }
    }
    
    public int partition(int []a,int low,int high){
        int pivot=a[low];
        while(low<high){
            while(low<high && a[high]>=pivot)
                high--;
            a[low]=a[high];
            while(low<high && a[low]<=pivot)
                low++;
        a[high]=a[low];
        }
        a[low]=pivot;
        return low;
    }

public void quicksort(int []a,int low,int high){

if(low<high){

int pivot=partition(a,low,high);

quicksort(a,low,pivot-1);

quicksort(a,pivot+1,high);

}

public int partition(int []a,int low,int high){

int pivot=a[low];

while(low<high){

while(low<high && a[high]>=pivot)

high--;

a[low]=a[high];

while(low<high && a[low]<=pivot)

low++;

a[high]=a[low];

}

a[low]=pivot;

return low;

}

215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2

输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4

输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

package gongel_first;

import java.util.PriorityQueue;

public class Twohundred_fifteen {
    /**
     * 快排、快速排序
     */
    public int paritition(int[] nums, int low, int high) {
        int pivot = nums[low];
        while (low < high) {//下面顺序不能交换， 因为pivot首先保存的是low
            while (low < high && nums[high] >= pivot)
                high--;
            nums[low] = nums[high];
            while (low < high && nums[low] <= pivot)
                low++;
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }

    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length)
            return -1;
        k = nums.length - k;//如果不进行此操作，则是找到数组中第k小的元素;例如4/5/6/7/8,第四大元素对应的下标为5-4=1
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int pivoit_pos = paritition(nums, low, high);
            if (pivoit_pos == k)
                return nums[pivoit_pos];
            else if (pivoit_pos > k)
                high = pivoit_pos - 1;
            else
                low = pivoit_pos + 1;
        }
        return nums[k];
    }

    /**
     * 优先队列实现小根堆
     */
    public int findKthLargest2(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int val : nums) {
            pq.add(val);
            if (pq.size() > k)//相当于nums.length-k；从nums中丢弃前nums.length-(k+1)+1=nums.length-k个最小的元素
                pq.poll();
        }
        return pq.peek();
    }
}

package gongel_first;

import java.util.PriorityQueue;

public class Twohundred_fifteen {

/**

* 快排、快速排序

public int paritition(int[] nums, int low, int high) {

int pivot = nums[low];

while (low < high) {//下面顺序不能交换，因为pivot首先保存的是low

while (low < high && nums[high] >= pivot)

high--;

nums[low] = nums[high];

while (low < high && nums[low] <= pivot)

low++;

nums[high] = nums[low];

}

nums[low] = pivot;

return low;

}

public int findKthLargest(int[] nums, int k) {

if (nums == null || nums.length == 0 || k <= 0 || k > nums.length)

return -1;

k = nums.length - k;//如果不进行此操作，则是找到数组中第k小的元素;例如4/5/6/7/8,第四大元素对应的下标为5-4=1

int low = 0, high = nums.length - 1;

while (low < high) {

int pivoit_pos = paritition(nums, low, high);

if (pivoit_pos == k)

return nums[pivoit_pos];

else if (pivoit_pos > k)

high = pivoit_pos - 1;

else

low = pivoit_pos + 1;

}

return nums[k];

}

/**

* 优先队列实现小根堆

public int findKthLargest2(int[] nums, int k) {

PriorityQueue<Integer> pq = new PriorityQueue<>();

for (int val : nums) {

pq.add(val);

if (pq.size() > k)//相当于nums.length-k；从nums中丢弃前nums.length-(k+1)+1=nums.length-k个最小的元素

pq.poll();

}

return pq.peek();

}

FLAG！

算法题一年内至少刷三遍！！！

LeetCode中国官方题库。

算法题临阵磨枪真的不行。

Coding Record

厚积薄发！

New Flag(20190828–): 看对话系统paper, 7:30左右起床看。

Paper Experience

编辑距离

72. 编辑距离

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符
示例 1:

输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2:

输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符

删除一个字符

替换一个字符

示例 1:

输入: word1 = "horse", word2 = "ros"

输出: 3

解释:

horse -> rorse (将 'h' 替换为 'r')

rorse -> rose (删除 'r')

rose -> ros (删除 'e')

示例 2:

输入: word1 = "intention", word2 = "execution"

输出: 5

解释:

intention -> inention (删除 't')

inention -> enention (将 'i' 替换为 'e')

enention -> exention (将 'n' 替换为 'x')

exention -> exection (将 'n' 替换为 'c')

exection -> execution (插入 'u')

package gongel_first;

public class Seventy_two {
    /**
     * dp[i][j]表示word1.sub(0,i)转到word2.sub(0,j)需要的步数
     */
    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null)
            return -1;
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 1; i <= word1.length(); i++)
            dp[i][0] = i;
        for (int j = 1; j <= word2.length(); j++)
            dp[0][j] = j;
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];//当前字符相等，不需要转换，看前面的转换就好了
                else
                    //dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作，+1表示动作执行
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

package gongel_first;

public class Seventy_two {

/**

* dp[i][j]表示word1.sub(0,i)转到word2.sub(0,j)需要的步数

public int minDistance(String word1, String word2) {

if (word1 == null || word2 == null)

return -1;

int[][] dp = new int[word1.length() + 1][word2.length() + 1];

for (int i = 1; i <= word1.length(); i++)

dp[i][0] = i;

for (int j = 1; j <= word2.length(); j++)

dp[0][j] = j;

for (int i = 1; i <= word1.length(); i++) {

for (int j = 1; j <= word2.length(); j++) {

if (word1.charAt(i - 1) == word2.charAt(j - 1))

dp[i][j] = dp[i - 1][j - 1];//当前字符相等，不需要转换，看前面的转换就好了

else

//dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作，+1表示动作执行

dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;

}

return dp[word1.length()][word2.length()];

}

编辑距离（非求两个字符串的编辑距离）

一	二	三	四	五	六	日
« 1月				3月 »
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28