#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010;
int f[N];

int main(void) {
    int n, m;
    scanf("%d %d", &n, &m);
    memset(f, 0, sizeof(f));
    int v, w, s;

    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &v, &w, &s);
        if (s != 0) {            // 是多重背包 / 01背包（多重背包特殊情况）
            if (s == -1)
                s = 1;           // 多重背包特殊情况 s = 1
            int num = min(s, m / v);   //节省1
            for (int k = 1; num > 0; k <<= 1) {  // <<=是左移操作
                if (k > num)
                    k = num;   // 注意这里和for循环的结束条件，可以减少代码量
                num -= k;
                for (int j = m; j >= v * k; j--) {       //从大到小枚举
                    f[j] = max(f[j], f[j - v * k] + w * k);
                }
            }
        }
        else {           // 完全背包，需要从小到大枚举
            for (int j = v; j <= m; j++) {
                f[j] = max(f[j], f[j - v] + w);
            }
        }

    }
    printf("%d\n", f[m]);
    return 0;
}

也是二进制拆分 可能更简单一些

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 25000;
int f[N];
//int v[20001] = { 0 }, w[20001] = { 0 }, s[1001] = { 0 };

int main(void) {
    int n, m;
    scanf("%d %d", &n, &m);
    memset(f, 0, sizeof(f));
    int v, w, s;

    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &v, &w, &s);
        int num = min(s, m / v);   //节省1
        for (int k = 1; num > 0; k <<= 1) {  //节省2  <<=是左移操作
            if (k > num)
                k = num;   //注意这里和for循环的结束条件
            num -= k;
            for (int j = m; j >= v * k; j--) {
                f[j] = max(f[j], f[j - v * k] + w * k);
            }
        }

    }
    printf("%d\n", f[m]);
    return 0;
}

算法

(DP) $O(nm)$

dp方程：

dp[i][j]表示s中前$i$个字符和p的前$j$个字符是否匹配成功，如果匹配成功则为$true$，否则为$false$

初始条件：

• s，p为空串时，能匹配成功，所以

$dp[0][0]=true$

• s为空串，p只为*时，*也能替换成空串，所以

$dp[0][i]=true$ (p串从$1$到$i$均是*号)，如果有除*号以外的字符就匹配不上了

C++ 代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int sLen = s.size();
        int pLen = p.size();
        //为了空出边界条件dp[0][0] 我们dp数组从下标为1开始使用
        // dp[i][j]表示s中前i个字符和p的前j个字符是否匹配成功，如果匹配成功则为true

        vector<vector<bool> > dp(sLen + 1, vector<bool>(pLen + 1, false));
        dp[0][0] = true;

        //s为空，*也可以替换成空串，则当s为空p为连续的*号时候也是匹配成功的
        for(int i = 1; i <= pLen; i++) {
            if(p[i - 1] == '*') {
                dp[0][i] = dp[0][i - 1];
            }
        }

        for(int i = 1; i <= sLen; i++) {
            for(int j = 1; j <= pLen; j++) {
                //p的第j个字符是*号，*号可以匹配任意串
                //所以无论是s的前i个字符和p的前j-1个字符匹配成功 将*号替换成空串
                //还是s的前i-1个字符和p的前j个字符匹配成功，*号替换的长度不限制，
                //所以可以将*号替换成的内容多加上s[i]
                // 这两种情况都能推出s的前i个字符和p的前j个字符匹配成功
                if(p[j - 1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }

                //p的第j个字符不是*号
                //如果dp[i-1][j-1]为false，
                //则s的前i-1个字符和p的前j-1个字符已经匹配失败了
                //这时候dp[i][j]只能为false了
                // 如果dp[i-1][j-1]为true，s的前i-1个字符和p的前j-1个字符已经匹配成功了
                //则要看s的第i个字符s[i] 和p的第j个字符p[j]是否匹配成功
                //s[i]和p[j]匹配成功有两种情况 1是两个字符相同，2是p[j]是？
                else {
                    if(dp[i - 1][j - 1] == true) {
                        if(s[i - 1] == p[j - 1] || p[j - 1] == '?') {
                            dp[i][j] = true;
                        }
                    }
                }
            }
        }
        return dp[sLen][pLen];
    }
};

KMP：

定义：Knuth-Morris-Pratt字符串查找算法，简称为“KMP算法”，常用于在一个文本串S内查找一个模式串P的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。

注：以下字符串起始下标均为1

引入概念：

• 前缀：指的是字符串的子串中从原串最前面开始的子串
  如abcdef的前缀有：a,ab,abc,abcd,abcde

• 后缀：指的是字符串的子串中在原串结尾处结尾的子串
  如abcdef的后缀有：f,ef,def,cdef,bcdef

• Next[i]：满足 以1开始的前缀 和 以i结尾的后缀 相等条件的最大长度（长度≤i）

Next数组求解：
求解Next数组，只涉及模式串P，要将模式串作为文本串（即S=P）

• 边界：Next[1]=0;（由定义即可得到）

• 匹配状态：j + 1表示当前P要匹配的下标，i表示当前S串要匹配的下标
  若P[j+1]=S[i]，直接匹配成功，则Next[j]=Next[j-1]+1;
  若P[j+1]≠S[i]，匹配失败，需要根据Next[j]不断向前跳j，直到匹配成功或者j=0；
  while (j && S[i] != P[j + 1]) j = Next[j];
  

Next数组运用：
过程和求解基本一致，直接用原文本串即可。

不知道理解得对不对，请大佬指教

题目描述

有一块木板，长度为 n 个 单位。一些蚂蚁在木板上移动，每只蚂蚁都以 每秒一个单位 的速度移动。其中，一部分蚂蚁向 左 移动，其他蚂蚁向 右 移动。

当两只向 不同 方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。

而当蚂蚁在某一时刻 t 到达木板的一端时，它立即从木板上掉下来。

给你一个整数 n 和两个整数数组 left 以及 right。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。

样例

输入：n = 4, left = [4,3], right = [0,1]
输出：4
解释：如上图所示：
-下标 0 处的蚂蚁命名为 A 并向右移动。
-下标 1 处的蚂蚁命名为 B 并向右移动。
-下标 3 处的蚂蚁命名为 C 并向左移动。
-下标 4 处的蚂蚁命名为 D 并向左移动。
请注意，蚂蚁在木板上的最后时刻是 t = 4 秒，之后蚂蚁立即从木板上掉下来。
（也就是说在 t = 4.0000000001 时，木板上没有蚂蚁）。

输入：n = 7, left = [], right = [0,1,2,3,4,5,6,7]
输出：7
解释：所有蚂蚁都向右移动，下标为 0 的蚂蚁需要 7 秒才能从木板上掉落。

输入：n = 7, left = [0,1,2,3,4,5,6,7], right = []
输出：7
解释：所有蚂蚁都向左移动，下标为 7 的蚂蚁需要 7 秒才能从木板上掉落。

输入：n = 9, left = [5], right = [4]
输出：5
解释：t = 1 秒时，两只蚂蚁将回到初始位置，但移动方向与之前相反。

输入：n = 6, left = [6], right = [0]
输出：6

限制

• 1 <= n <= 10^4
• 0 <= left.length <= n + 1
• 0 <= left[i] <= n
• 0 <= right.length <= n + 1
• 0 <= right[i] <= n
• 1 <= left.length + right.length <= n + 1
• left 和 right 中的所有值都是唯一的，并且每个值 只能出现在二者之一 中。

算法

(模拟) $O(n)$

1. 两只蚂蚁相遇可以忽略，因为交换方向如果不考虑蚂蚁编号的话实际上等于没有交换。
2. 对于向左走的蚂蚁，需要的时间等于初始的位置；对于向右走的蚂蚁，需要的时间等于长度减去初始位置。

时间复杂度

• 分别遍历两个数组一次，时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int ans = 0;
        for (int x : left)
            ans = max(ans, x);

        for (int x : right)
            ans = max(ans, n - x);

        return ans;
    }
};

题目描述

You may recall that an array A is a mountain array if and only if:

A.length >= 3
There exists some i with 0 < i < A.length - 1 such that:
A[0] < A[1] < … A[i-1] < A[i]
A[i] > A[i+1] > … > A[A.length - 1]
Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target. If such an index doesn’t exist, return -1.

You can’t access the mountain array directly. You may only access the array using a MountainArray interface:

MountainArray.get(k) returns the element of the array at index k (0-indexed).
MountainArray.length() returns the length of the array.
Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

样例

Example 1:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.
Example 2:

Input: array = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in the array, so we return -1.

算法1

(二分) $O(logn)$

先二分找到peak，然后在左半部分和右半部分二分找target

时间复杂度

O(logn)
O(1)

参考文献

C++ 代码

```
/*
* // This is the MountainArray’s API interface.
* // You should not implement it, or speculate about its implementation
* class MountainArray {
* public:
* int get(int index);
* int length();
* };
/

class Solution {
public:
int findInMountainArray(int target, MountainArray &mountainArr) {
int n=mountainArr.length();
int l=0, r=n-1;
while(l[HTML_REMOVED]target)
l=mid+1;
else
r=mid;
}
if(mountainArr.get(l)==target) return l;
return -1;
}
};

题目描述

给你一个数字数组 arr。

如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列。

如果可以重新排列数组形成等差数列，请返回 true；否则，返回 false。

样例

输入：arr = [3,5,1]
输出：true
解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1]，
任意相邻两项的差分别为 2 或 -2，可以形成等差数列。

输入：arr = [1,2,4]
输出：false
解释：无法通过重新排序得到等差数列。

限制

• 2 <= arr.length <= 1000
• -10^6 <= arr[i] <= 10^6

算法

(排序) $O(n \log n)$

1. 将原数组从小到大排序。
2. 判断任意相邻两个数字的差值是否一致。

时间复杂度

• 排序后遍历一次，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(), arr.end());

        int n = arr.size(), d = arr[1] - arr[0];

        for (int i = 2; i < n; i++)
            if (arr[i] - arr[i - 1] != d)
                return false;

        return true;
    }
};

单独开一章-附带归纳的算法类型 233

July 4th Explore Card 264 Ugly Number II

法1:全枚举算出来 然后排列

ugly = sorted(2**a * 3**b * 5**c for a in range(32) for b in range(20) for c in range(14))
def nthUglyNumber(self, n):
    return self.ugly[n-1]

法2: 三指针(每次循环得到三个, 把最小的加上去)

def nthUglyNumber(self, n):
    ugly = [1]
    i2, i3, i5 = 0, 0, 0
    while n > 1:
        u2, u3, u5 = 2 * ugly[i2], 3 * ugly[i3], 5 * ugly[i5]
        umin = min((u2, u3, u5))
        if umin == u2:
            i2 += 1
        if umin == u3:
            i3 += 1
        if umin == u5:
            i5 += 1
        ugly.append(umin)
        n -= 1
    return ugly[-1]

Seeing the description we can arrive at the observation that bigger ugly numbers can be generated by multiplying smaller ugly numbers by 2, 3 and 5. In order to be exhaustive, we have to multiply every ugly number by 2, 3, and 5 do make sure we don’t miss any. The problem with that if you run this method on the first few ugly numbers:

1 -> 2, 3, 5 … 2 -> 4, 6, 10 … 3 -> 6, 9, 15

The problem with this is that there are going to be duplicates and (unsorted)

Therefore the OP’s solution is having 3 pointers, namely i2, i3, and i5, they will keep track of which multiple of 2, 3, 5 of the smaller ugly number they are pointing to. At every loop, you get three multiples of 2, 3 and 5 and you pick the smallest one to append to the ugly number array, this will fix the problem with new ugly number being unsorted, and since we appended that smallest next ugly number, increment the pointer that generated that smallest ugly number so we can add the next bigger one in the future. Since the if-statements are parallel, this also prevent duplicates from being added to the ugly number array, since if two or three u2, u3, and u5 are the same, their corresponding pointer will all be incremented.
Therefore after n-1 loops has executed, we have generated n ugly numbers, and the last number ugly[-1] will indeed be our answer.

以下胡扯 手写的就先不上传了

python

$\underline{python}$ 下划线赛高
1. 基础类
1） 离散数学 高等数学 等math
2） Markov Process 最优化Optimisation 凸优化 等stats 哈哈感觉回到了大学
2. 计算理论 对模型评价 过拟合 点估计/区间估计 树模型 （随机森林 gbdt集成学习思想）

每类word2vector 神经网络语言模型

Java双栈

class MyQueue {

Stack<Integer>stack1;
Stack<Integer>stack2;
    /** Initialize your data structure here. */
    public MyQueue() {
         stack1=new Stack<>();
         stack2=new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
         stack1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
         if(stack2.isEmpty()){
              if(stack1.isEmpty()) return -1;
              while(!stack1.isEmpty()) stack2.push(stack1.pop());
         }
         return stack2.pop();
    }

    /** Get the front element. */
    public int peek() {
        if(stack2.isEmpty()){
            if(stack1.isEmpty()) return -1;
            while(!stack1.isEmpty()) stack2.push(stack1.pop());
        }
        return stack2.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
         return stack1.isEmpty()&&stack2.isEmpty();
    }
}

Java 详细注释

class Solution {
    public TreeNode inorderSuccessor(TreeNode p) {
    //如果有右孩子，那么后继为右孩子中的左孩子wang
           if(p.right!=null){
               p=p.right;
               while(p.left!=null) p=p.left;
               return p;
           }
           //如果没有右孩子，并且为父亲节点的右节点，那么就一直往上找
           while(p.father!=null&&p==p.father.right) p=p.father;
           return p.father;
    }
}