STL利用erase和remove_if实现filterremove_if是STL中的一个函数，这个函数的作用是遍历一个容器并筛选要删除的元素，接受一个自定义函数，这个自定义函数返回true则代表删除此元素，remove_if会将要删除的元素移动到容器尾部，以此类推，最终remove_if返回的是要删除的所有元素的第一个的位置。 #include<bits/stdc++.h> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param trees int整型vector * @re...

好久不见高精度相关的题目了 #include <iterator> #include <string> #include<cctype> class Solution { public: // 高精 // 此题没有涉及到正负号的问题 string solve(string s, string t) { string res = ""; int n = s.size(); int m = t.size(); // 反转 reverse(s.begin(), s.end()); reverse(t.begin(), t.end()); int...

STL真的好用！！STL中没有split()函数，需要自己手动实现（这一点差评）！ #include <algorithm> #include <cctype> class Solution { public: // 自定义转换规则 static char myfun(char ch){ if(isalpha(ch)){ // 是字母 if(islower(ch)){ ch = toupper(ch); }else{ ch = tolower(ch); } } return ch; } // 字符串分割 vector<string> split(string...

与最长公共子序列相似，只不过修改迭代条件即可，因为子串是连续额的，所以我们可以使用两个变量就可以截取出最长公共子串：maxLen，记录最大公共子串长度lastIdx，最长公共子串的结尾位置 class Solution { public: string LCS(string str1, string str2) { int n = str1.size(), m = str2.size(); vector<vector<int>> dp(n + 1, vector<int>(m + 1)); int maxLen = 0; int lastIdx = -1; ...

与01 背包不同的是，一个物品可以无限次放入。我们可以在本次物品的基础上继续放入，而不是在前一个物品的基础上放入，因此我们只需要在01背包的代码上稍作修改即可。例题：P1616 疯狂的采药二维数组 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ f[i][j]=f[i-1][j]; if(j>=v[i]){ // 此处不再是 i-1，而是i，在本次物品的基础上再放入 f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]); } } } 一维滚动数组优化在01背包中，一维数组逆序是为了防止重复放入，而完全背包正好...

每个物品只有放入、不放入两种情况，而且每个物品只能取一次，取背包的最大价值例题:P1048 [NOIP2005 普及组] 采药P1734 最大约数和P1060 [NOIP2006 普及组] 开心的金明二维数组模版 int n, m; cin >> n >> m; // w[i] 第i个物品的重量 // v[i] 第i个物品的价值 for(int i = 1; i <= n; i ++) cin >> w[i] >> v[i]; // dp[i][j] 前i个物品放入容量为j的背包的最大价值 // 当前背包容量是j,要考虑当前物品能否放入?是...

前序遍历我们利用栈的特性，先将根节点压栈，每次都是从栈中弹出一个，然后将这个节点的右、左孩子压栈。注意：压栈时，一定要先压右孩子，然后是左孩子 public int[] preorderTraversal (TreeNode root) { if(root == null){ return new int[]{}; } Stack<TreeNode> st = new Stack<TreeNode>(); List<Integer> list = new ArrayList<>(); st.push(root); while(!st.isEmpt...

import java.util.*; public class Solution { public ListNode ReverseList (ListNode head) { ListNode prev = null; ListNode curr = head; ListNode next = null; while (curr != null) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } }

反常但是巨好用的一种二分的写法！不再直接找目标索引，而是找分界线。不再考虑left < right还是left <= right ，以及不用考虑left = mid + 1 还是left = mid可以看这个视频[为什么二分总是写错？这种写法不再考虑边界问题] import java.util.*; public class Solution { public int searchInsert (int[] labels, int target) { int left = -1; int right = labels.length; int mid = -1; // 找到 >...

思路：用两个栈来记录，第一个栈s用来保存真实的牛的重量，第二个栈 `maxStack` 用来记录当前数据到栈底的最大值，那么`maxStack`的栈顶值就是当前所有数据的最大值。这样在获取最大值时，直接返回maxStack的栈顶元素，就是`O(1)` 的时间复杂度画个图：push时，第一个普通栈直接压栈，第二个栈maxStack需要判断当前元素到栈底的最大值，将最大值压栈。此时maxStack中栈顶元素就是所有牛的最大重量。pop时，对两个栈都出栈top时，对第一个栈S返回栈顶元素即可getMax时，第二个栈maxStack的栈顶元素就是当前普通栈中栈顶元素对应的最大值。 import jav...

思路：如果是数字，则压栈如果是操作符，则出栈两个操作数，将运算结果继续压栈最终的栈中只会有一个数字，就是结果 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param tokens string字符串一维数组 * @return int整型 */ public int calculatePostfix (String[] tokens) { Stack<Integer> s = new Stack<>(); // write co...