经典的动态规划。dp[i][j]代表着从i开始到j为止的子串是不是回文串, l代表回文串长度。状态转移方程：dp[i][j] = 1, l == 1dp[i][j] = A[i] == A[j], l == 2 or l == 3dp[i][j] = dp[i + 1][j - 1] && A[i] == A[j], else class Solution { public: int getLongestPalindrome(string A, int n) { int dp[n][n], j, max = 0; for(int l = 1; l <= n; l++) {...

最简单的动态规划了 class Solution { public: int Fibonacci(int n) { if(n == 0 || n == 1) return n; int a = 0, b = 1, c; for(int i = 0; i <= n - 2; i++) { c = a + b; a = b; b = c; } return c; } };

leetcode上能过，但是在这里就过不了，不知道为啥段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起 class Solution { public: vector<int> spiralOrder(vector<vector<int> > &matrix) { int direction[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int x = 0, y = 0, m = matrix.size(), n = matrix[0].size(), index = ...

直接反转就行。 class Solution { public: /** * 反转字符串 * @param str string字符串 * @return string字符串 */ string solve(string str) { int len = str.length(); for(int i = 0 ; i < len / 2 ;i++) { swap(str[i],str[len-1-i]); } return str; } };

用DFS如果root->val等于o1或者o2，就返回o1或者o2。如果左右子树一个返回o1一个返回o2，那就返回当前节点的val，因为这就是要找的节点。如果左右子树中有某一个返回了不是-1也不是o1或o2，那就说明那底下有要找的节点，直接返回他返回的值。如果都不是就返回-1。 class Solution { public: int dfs(TreeNode* root, int o1, int o2) { int left = -1, right = -1; if(root->val == o1) return o1; if(root->val == o2) return...

先反转链表，然后逐个加和并计算进位，最后再反转回来。 class Solution { public: ListNode* reverse(ListNode* head) { ListNode *pre = nullptr, *cur = head, *next = nullptr; while(cur != nullptr) { next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; } ListNode* addInList(ListNode* head1, ListNode* head2)...

两个指针分别把两个链表a,b各走一遍，因为len(a + b) = len(b + a)，所以相遇的时候就是第一个公共节点了。 class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { ListNode *ta = pHead1, *tb = pHead2; while (ta != tb) { ta = ta ? ta->next : pHead2; tb = tb ? tb->next : pHead1; } return ta; } };

经典的动态规划题目。dp[i][j]表示以字符串str1 i位置结尾，以字符串str2 j位置结尾的公共字串的长度。状态转移方程：dp[i][j] = dp[i -1][j - 1] + 1, str1[i] == str2[j]dp[i][j] = 0, str1[i] != str2[j] class Solution { public: string LCS(string str1, string str2) { int len1 = str1.size(), len2 = str2.size(), max = 0, endpos = 0; int dp[len1][len2]; mem...

同样是用队列维护，但是多用了一个栈用来反转。 class Solution { public: vector<vector<int> > zigzagLevelOrder(TreeNode* root) { vector<vector<int> > vec; if(root == nullptr) return vec; queue<TreeNode*> que; int flag = 0; que.push(root); while(!que.empty()) { int len = que.size(); vector<in...

维护一个进位和一个当前位，从后往前迭代就行。注意补0. class Solution { public: string solve(string s, string t) { int slen = s.size(), tlen = t.size(); stack<char> stks, stkt, stk; int len = max(slen, tlen); if(slen > tlen) for(int i = 0; i < slen - tlen; i++) stkt.push('0'); else for(int i = 0; i < tlen - sle...

先便利一遍查数，然后再走一遍删节点。 class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { int count = 0; ListNode *pHead = head; while(head != nullptr) { head = head->next; count++; } if(n == count) return pHead->next; ListNode *pre = nullptr, *now = pHead; for(int i = 1; i < count - ...

用快慢指针，分别从两指针相遇位置和头指针位置出发两个相同速度的指针，相遇的位置就是环开始的位置。 class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *fast = head, *slow = head, *pos = nullptr; while(fast != nullptr && fast->next != nullptr) { fast = fast->next->next; slow = slow->next; if(fast == slow) { ...

用一个栈维护。 class Solution { public: bool isValid(string s) { stack<int> stk; int len = s.size(); for(int i = 0; i < len; i++) { if(s[i] == '(' || s[i] == '[' || s[i] == '{') stk.push(s[i]); else { if(s[i] == ')') if(stk.empty() || stk.top() != '(') return false; else stk.pop(); if(s[i] == ']')...

从后往前看，依次添加到A数组的末尾。 class Solution { public: void merge(int A[], int m, int B[], int n) { int i = m - 1, j = n - 1, index = m + n - 1; while(i >= 0 && j >= 0) { if(A[i] > B[j]) { A[index] = A[i]; i--; } else { A[index] = B[j]; j--; } index--; } if(j >= 0) for(int k = 0; k <= j;...