wiki:https://en.wikipedia.org/wiki/Space-filling_curve
1.Space-Filling Curve
2.Z-curve
致谢:https://www.docin.com/p-830484046.html
0
wiki:https://en.wikipedia.org/wiki/Space-filling_curve
致谢:https://www.docin.com/p-830484046.html
交叉熵损失函数一般用来代替均方差损失函数与sigmoid激活函数组合
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]; }
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4
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; } } };
给定两个有序整数数组 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]
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--]; } } } }
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--]; } } };
int get_pivot_pos(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_pos(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_pos(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); } } }
在未排序的数组中找到第 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 ≤ 数组的长度。
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(); } }
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; } };
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意: 不能使用代码库中的排序函数来解决这道题。 示例: 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶: 一个直观的解决方案是使用计数排序的两趟扫描算法。 首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗?
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; } }
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; } };