知识点：字符串分析：给定一串信息 message 和一个关键词 keyword，找到关键词 keyword 第一次出现在信息 message 中的起始位置下标。如果关键词并未出现在信息中，返回 -1。遍历字符串，当message字符串出现和keyword字符串相同的首字母，则两个字符串开始比较匹配，如果匹配到了keyword，那么j在匹配结束后会增长到keyword字符串的长度，如果没有增长到keyword字符串的长度，那么久没有匹配到，则返回-1；编程语言：C++完整代码： int findKeyword(string message, string keyword) { ...

知识点：字符串/stringstream分析：去掉前置空格，后置空格，然后倒序遍历，将每个单词断开放入新的res字符串中编程语言：C++完整代码： string reverseWords(string s) { // write code here stringstream ss(s);//stringstream能去除空格，且自动去除前置和后置的空格 string tmp; vector<string> vs; while(ss >> tmp) { ...

知识点：字符串分析：从后往前遍历，遇到空格则终止，但是由于字符串结尾还有可能存在空格，需要进行处理。编程语言：C++完整代码： int lengthOfLastWord(string s) { // write code here int res = 0; int ans = 0; for (int i = s.length() - 1; i >= 0; i--) { if (s[i] != ' ') res++; else if (re...

知识点：动态规划/状态机模型分析：dp大家都做了好几百遍了，主要分析状态机模型。比DP更好理解。首先上图是一个状态转移图，其次再记住买入和卖出算一次买卖现在分析状态：状态表示：f[i][j][k]， k取0或1，0表示手中无货，1表示手中有货，f[i][j][0]：第i天，已经进行完j次交易后的最大利润f[i][j][1]：第i天，正在进行第j次交易（已经进行了j - 1次交易）后的最大利润一开始从手中无货开始，首先可以转移到手中有货状态，或者是手中无货状态。同理手中有货也有两种状态转移。手中无货—>手中无货，则f[i][j][0] = f[i-1][j][0]，直接等于前一天手中有货-...

知识点：动态规划/状态机模型分析：dp大家都做了好几百遍了，主要分析状态机模型。比DP更好理解。首先上图是一个状态转移图，其次再记住买入和卖出算一次买卖现在分析状态：状态表示：f[i][j][k]， k取0或1，0表示手中无货，1表示手中有货，f[i][j][0]：第i天，已经进行完j次交易后的最大利润f[i][j][1]：第i天，正在进行第j次交易（已经进行了j - 1次交易）后的最大利润一开始从手中无货开始，首先可以转移到手中有货状态，或者是手中无货状态。同理手中有货也有两种状态转移。手中无货—>手中无货，则f[i][j][0] = f[i-1][j][0]，直接等于前一天手中有货-...

知识点：动态规划/编辑距离分析：首先题目中给出两个字符串，有两种操作可以进行：1.在编号中插入一个字符2.删除编号中的一个字符使得a字符串变为字符串b，求变更的最小次数状态表示：状态表示：word1[1~i]变为word2[1~j]的操作次数的最小次数状态属性：min，求最小次数状态计算计算f[i][j]，依次考虑两种操作方式： 1) 删除操作：把word1[i]删掉之后word1[1~i]和word2[1~j]匹配，所以之前要先做到word1[1~(i-1)]和word2[1~j]匹配， f[i-1][j] + 1 2) 插入操作：插入之后word1[i]与wor...

知识点：动态规划分析：首先如果 s3 的长度不等于 s1 的长度 + s2 的长度，肯定返回 false如果两个指针分别指向 s1 和 s2，然后遍历 s3，如果 s3 对应的字符出现在 s1，指向 s1 的指针前进一位，反之指向 s1 的指针前进一位。用 f[i][j] 来表示 s1 的前 i 位和 s2 的前 j 位是否可以组成 s3 的前 i + j 位，那么如果 s3[i + j - 1] == s1[i - 1]，f[i][j] |= f[i - 1][j]如果 s3[i + j - 1] == s2[j - 1]，f[i][j] |= f[i][j - 1]如果 s3[i + j ...

知识点：动态规划分析：首先如果 s3 的长度不等于 s1 的长度 + s2 的长度，肯定返回 false如果两个指针分别指向 s1 和 s2，然后遍历 s3，如果 s3 对应的字符出现在 s1，指向 s1 的指针前进一位，反之指向 s1 的指针前进一位。用 f[i][j] 来表示 s1 的前 i 位和 s2 的前 j 位是否可以组成 s3 的前 i + j 位，那么如果 s3[i + j - 1] == s1[i - 1]，f[i][j] |= f[i - 1][j]如果 s3[i + j - 1] == s2[j - 1]，f[i][j] |= f[i][j - 1]如果 s3[i + j ...

知识点：哈希表/回溯/DFS分析：首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作。回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完生成器的所有数字，则已有的字母排列是不完整的）。该字符串初始为空。每次取生成器的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理生成器的后一位数字，直到处理完生成器中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。回溯法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不...

知识点：双指针/数组/原地分析：不额外增加数组，在原数组的基础上进行删除可以考虑使用双指针方法 首先使用两个指针指向数组的首元素，这里要清楚两个指针分别的作用是什么，i指针的作用是用来判断是否要进行元素删除，我们称为主指针，那么j指针，j指针就是辅助i指针完成移除操作的指针。在i指针进行遍历，从首元素遍历至尾元素，如果i指针指向的元素不是要删除的元素，那么将i指针指向的值赋给j指针，并让j指针往后移动一个，然后i指针也往后移动一个。当整个数组遍历结束，j指针指向的位置就是新数组的结尾，故返回它就是整个数组的长度编程语言：C++完整代码： int remove_cows(vector&l...

知识点：栈/字符串分析：两种方法：一、利用一个栈来匹配括号，首先将 s[i] == '('|| s[i] == '{'|| s[i] == '['这些情况都一一压栈，在循环中，如果遇到了“ ) ] } ”,就和栈顶元素进行匹配，成功则继续，有一个不匹配，则整个字符串不匹配。若是循环中都判断结束了，那么最后还需要对栈是否为空进行判断，因为最后成对的括号都要弹出。二、利用一个栈来匹配括号，但是这种方法的匹配与上面的方法不同，当出现 s[i] == '('|| s[i] == '{'|| s[i] == '['这些情况，将其对应的右半括号“ ) ] } ”压栈，在每一次循环中对当前字符进行判断，若是...

知识点：排序/堆排序分析：可以使用快速排序，各种排序方法，这里使用堆排序堆排序，重点理解：i为什么从n/2开始down？首先要明确要进行down操作时必须满足左儿子和右儿子已经是个堆。开始创建堆的时候，元素是随机插入的，所以不能从根节点开始down，而是要找到满足下面三个性质的结点：1.左右儿子满足堆的性质。2.下标最大（因为要往上遍历）3.不是叶结点（叶节点一定满足堆的性质）编程语言：C++完整代码： void down(int u, int s_h, int* heap) { int t = u; if (2 * u <= s_h &&...

知识点：DFS/剪枝/位运算分析：使用常规深度优先一层层搜索使用三个整形分别标记每一层哪些草场可以放置牛牛，这三个整形分别代表列、左斜下、右斜下（_col, ld, rd_），二进制位为 111 代表不能放置，000 代表可以放置两个位运算：x & -x 代表除最后一位 111 保留，其它位全部为 000x & (x - 1) 代表将最后一位 111 变成 000编程语言：C++完整代码： int res = 0; void dfs(int n, int row, int col, int ld, int rd) { if (row >= ...

知识点：字符串/动态规划分析：使用动态规划来解，还是先来定义状态，问题是确定字符串s是否可以被分割状态表示：字符串的前i个字符是否可以被分割。这样就可以去判断前1个字符是否可以被分割状态转移方程：f(i) = f(j) && s[j] ~ s[i - 1]是否可以被分割；初始状态：f(0) = true；返回结果：f(s.size())；编程语言：C++完整代码： bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> dict;...