如果k个相同的k进制数进行无进位相加，相加的结果一定是每一位上都是0的k进制数。  所有的数都是32位整型，讲所有数都转为二进制数，计算所有数在32位每一位的和。如果该位可以被k整除，则表示那个只出现一次的数在该位为0；如果该位整除不为0， 则表示那个只出现一次的数在该位为1。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param arr intvector * @param k int * @return int */ int foundOnceNumber(vector<int...

最简单的做法：先不进位，把各个位的数算出来，同一位置累加，最后再做进位操作。 以6789 x 8976为例：  class Solution { public: void str2num(string& s, vector<int>& num){ for(char c: s){ num.push_back(c - '0'); } reverse(num.begin(), num.end()); } /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param s string字符串 第一个整数 * @param t st...

1. 递归 每次递归，当前位置的数字可以选择或者不选择。 class Solution { public: vector<vector<int> > res; void dfs(vector<int>& S, vector<int> tmp, int start){ res.push_back(tmp); if(start == S.size()){ return; } for(size_t i = start; i < S.size(); i++){ tmp.push_back(S[i]); dfs(S, tmp, i + 1);...

class Solution { public: const string IPV4 = "IPv4"; const string IPV6 = "IPv6"; const string NEITHER = "Neither"; const char IP4_SEP = '.'; const char IP6_SEP = ':'; /** * 验证IP地址 * @param IP string字符串 一个IP地址字符串 * @return string字符串 */ string solve(string IP) { // write code here if(contains_dot(IP) ...

1. 先序遍历解法 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: const char SEP = '&'; const char NULL_NODE = '#'; char* Serialize(TreeNode *root) { if(!root){ return nullptr; } stack<Tr...

1.栈 用栈保存最近未匹配括号的下标，将栈初始化为{-1}。 只有当前字符s[i]为')'且未匹配括号为'('时，弹出栈顶元素，并更新匹配括号子串的最大长度。 否则就将当前括号的下标进栈。 class Solution { public: /** * * @param s string字符串 * @return int整型 */ int longestValidParentheses(string s) { // write code here if(s.empty()) return 0; int n = s.size(); stack<int> st; st.push(-1);...

c++双端队列  参考精华解答，时间复杂度O(n)，空间复杂度O(n)，记录一下，熟悉解题思路  用双端队列保存数组元素下标。队列中数组下标对应元素应当是递减的，这是为了通过下标保存当前这个window下，最大、第二大、第三大……的元素。最大元素的下标始终在队头。  如果队列为空，或者当前元素小于队尾对应的元素，把当前元素的下标加入队尾。 否则，循环判断，如果当前元素大于队尾对应的元素，则队尾出队列，直至小于队尾对应的元素或队列为空。 如果队头元素，即最大元素在window最左边，弹出队头。 如果window已形成，则把队头元素加入队列。  class Solution { public: v...

class Solution { public: vector<string> res; string src_str; int str_len; string trans(vector<string> str_vec){ string res; for(auto s: str_vec){ res += s; res.push_back('.'); } res.pop_back(); return res; } bool is_legal_num(string num_str){ if(num_str.size()>= 2 && num_str[0...

经典动态规划的方程为： dp[i][j] = dp[i][j-1] + dp[i-1][j] 因为只要求解总路径数，dp[i][j]只与左边和上边的状态有关，不需要保存中间状态。 因而可以只用一个数组来保存。当前需要更新的黄色的dp[j]为：刚更新的dp[j-1] 与 旧的dp[j]值之和。  class Solution { public: /** * * @param m int整型 * @param n int整型 * @return int整型 */ int uniquePaths(int m, int n) { // write code here int less = m >...

1.经典动态规划解法 设s[k]为s[0...k]的子串，那么cost[i][j]为从s1[i]编辑为s2[j]的代价。  如果s1[i] == s2[j]， 那么cost[i][j] = cost[i-1][j-1]; 否则有三种方法可以完成这一次编辑:：   用cost[i-1][j-1]的代价将s1[i-1]编辑为s2[j-1],再将s1[i]替换为s[j]，即cost[i][j-1] + rc;   用cost[i][j-1]的代价将s1[i]编辑为s2[j-1],再插入一个s2[j]字符, 即cost[i][j-1] + ic;   用cost[i-1][j]的代价将s1[i-1]编...

通过一快一慢两个指针fast和slow，fast走两步，slow走一步，遍历链表，寻找链表中点，翻转后半链表部分。完成翻转后，首尾同时向中间走，同时判断对应位置是否对应相等。 遍历结束时，如果是奇数个结点，fast指向尾结点，slow指向中间结点，从slow->next开始翻转；如果是偶数个结点，fast指向null，slow指向后半部分的第一个结点，从slow开始翻转。所以只需判断fast为null即可确定从哪个结点mid开始翻转。 翻转后得到后半部分链表的头结点end，此时mid->next已经为null了。end、head同时前进，判断结点值是否相等，或直至end为null。...

新建一个头节点，一个指示当前结点的cur指针，一个指示前一个结点的pre指针。 对链表进行遍历：  ①如果当前节点和下一个结点的值相等，则记录该值，在while中判断之后结点的值是否也等于该值，是则指针前移, 直至走出重复段； ②如果不相等，则把pre指向cur, 更新pre为cur, cur前移。   如果输入为{1，2，2}，只进行到①，没走到过②。运行完， pre->val == 1, cur == nullptr，pre后面还连着两个结点，所以需要断链pre->next == nullptr.  /** * struct ListNode { * int val; * st...