损失函数

一.常见损失函数

  • 二分类交叉熵

 

  • 多分类交叉熵

 

二. 常见问题

  • 为什么分类选用交叉熵而不是均方差?

交叉熵损失函数一般用来代替均方差损失函数与sigmoid激活函数组合

      • 均方差对参数的偏导的结果都乘了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];
}

归并

21. 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例:

输入: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;
        }
    }
};

88. 合并两个有序数组

给定两个有序整数数组 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--];
        }
    }
};

return the last

快速排序 快排 TOPK

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);
        }
    }
}

1.TOPK

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 ≤ 数组的长度。
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;
    }
};

2.三路快排

75. 颜色分类

给定一个包含红色、白色和蓝色,一共 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;
    }
};

return the last