wiki：https://en.wikipedia.org/wiki/Space-filling_curve
1.Space-Filling Curve
2.Z-curve
致谢：https://www.docin.com/p-830484046.html
月份：2019年2月
损失函数
一. 二分类交叉熵
二. 多分类交叉熵
updating….
归并排序
|
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 |
void merge_sort(vector<int> &nums, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; merge_sort(nums, left, mid); merge_sort(nums, mid + 1, right); merge(nums, left, mid, right); } } void merge(vector<int> &nums, int left, int mid, int right) { vector<int> temp; int i = left; int j = mid + 1; while (i <= mid && j <= right) { if (nums[i] > nums[j]) { temp.push_back(nums[j++]); } else temp.push_back(nums[i++]); } //下面两个循环只有一个会执行 while (i <= mid) temp.push_back(nums[i++]); while (j <= right) temp.push_back(nums[j++]); for (int i = 0; i < temp.size(); i++) nums[left + i] = temp[i]; } |
21. 合并两个有序链表
|
1 2 3 4 5 6 |
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 |
|
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { ListNode *dummy = new ListNode(0); ListNode *cur = dummy; while (l1 != nullptr && l2 != nullptr) { if (l1->val < l2->val) { cur->next = l1; cur = cur->next; l1 = l1->next; } else { cur->next = l2; cur = cur->next; l2 = l2->next; } } if (l1 != nullptr) cur->next = l1; if (l2 != nullptr) cur->next = l2; return dummy->next; } ListNode *mergeTwoLists2(ListNode *l1, ListNode *l2) { if (l1 == nullptr) return l2; if (l2 == nullptr) return l1; if (l1->val < l2->val) { l1->next = mergeTwoLists2(l1->next, l2); return l1; } else { l2->next = mergeTwoLists2(l1, l2->next); return l2; } } }; |
88. 合并两个有序数组
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 示例: 输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6] |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public class Eighty_eight { /** * 倒着合并 */ public void merge(int[] nums1, int m, int[] nums2, int n) { int index1 = m - 1; int index2 = n - 1; int indexNew = m + n - 1; while (index1 >= 0 || index2 >= 0) { if (index1 < 0) { nums1[indexNew--] = nums2[index2--]; } else if (index2 < 0) { nums1[indexNew--] = nums1[index1--]; } else if (nums1[index1] > nums2[index2]) { nums1[indexNew--] = nums1[index1--]; } else { nums1[indexNew--] = nums2[index2--]; } } } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public: void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) { int new_index = m + n - 1; int i = m - 1; int j = n - 1; while (i >= 0 && j >= 0) { if (nums1[i] > nums2[j]) { nums1[new_index--] = nums1[i--]; } else { nums1[new_index--] = nums2[j--]; } } while (i >= 0) { nums1[new_index--] = nums1[i--]; } while (j >= 0) { nums1[new_index--] = nums2[j--]; } } }; |
快速排序 快排 TOPK
|
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
int get_pivot(int left, int right, vector<int> &nums) { int pivot = nums[left]; while (left < right) { while (left < right && nums[right] >= pivot) right--; nums[left] = nums[right]; while (left < right && nums[left] <= pivot) left++; nums[right] = nums[left]; } nums[left] = pivot; return left; } //递归 void quick_sort(int left, int right, vector<int> &nums) { if (left < right) { int pivot = get_pivot(left, right, nums); quick_sort(left, pivot - 1, nums); quick_sort(pivot + 1, right, nums); } } //非递归 void quick_sort_no_recursion(int left, int right, vector<int> &nums) { if (left >= right) return; stack<int> s; s.push(left); s.push(right); while (!s.empty()) { int right = s.top(); s.pop(); int left = s.top(); s.pop(); int pivot = get_pivot(left, right, nums); if (pivot - 1 > left) {//保存左边 s.push(left); s.push(pivot - 1); } if (pivot + 1 < right) {//保存右边 s.push(pivot + 1); s.push(right); } } } |
1.TOPK
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
在未排序的数组中找到第 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 ≤ 数组的长度。 |
|
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
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(); } } |
|
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Solution { public: int findKthLargest(vector<int> &nums, int k) { if (nums.size() == 0) return -1; priority_queue<int, vector<int>, greater<int> > pq; for (auto num:nums) { pq.push(num); if (pq.size() > k) pq.pop(); } return pq.top(); } int findKthLargest2(vector<int> &nums, int k) { if (nums.size() == 0) return -1; k = nums.size() - k; int low = 0; int high = nums.size() - 1; while (low < high) { int pivot = paritition(low, high, nums); if (pivot == k) return nums[k]; else if (pivot > k) high = pivot - 1; else low = pivot + 1; } return nums[k]; } int paritition(int low, int high, vector<int> &nums) { int pivot = nums[low]; while (low < high) { 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; } }; |
2.三路快排
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意: 不能使用代码库中的排序函数来解决这道题。 示例: 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶： 一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗？ |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
public class Seventy_five { /** * 三路快排 */ public void sortColors(int[] nums) { int zero = -1, one = 0, two = nums.length; while (one < two) { if (nums[one] == 0) { swap(nums, ++zero, one++); } else if (nums[one] == 2) { swap(nums, --two, one); } else { ++one; } } } public void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public: void sortColors(vector<int> &nums) { int zero = -1; int one = 0;/指向不确定的颜色 int two = nums.size(); while (one < two) { if (nums[one] == 0) { swap(nums,++zero, one++);//左边已经扫过了，所以one++ } else if(nums[one]==2){ swap(nums,--two,one);//右边没有扫过，所以one暂停等着下一步来扫 } else{ one++; } } } void swap(vector<int> &nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }; |
FLAGs！
算法题一年内至少刷三遍！！！
厚积薄发！
New Flag(20190828起): 看paper, 7:30左右起床看。
进展(20200515⛽️)：skill++, paper++, but laziness++