//leetcode 28 KMP这个有少部分用例有问题 正在排查 别的都可以
#include <algorithm>
#include <iostream>
#include <time.h>
#include <vector>
#include <math.h>
#include <unordered_map>
#include <queue>
#include <string.h>
using namespace std;
struct TreeNode
{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x),left(NULL),right(NULL){}
TreeNode(int x,TreeNode* p1,TreeNode* p2) : val(x),left(p1),right(p2){}
};
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
ListNode(int x,ListNode* p) : val(x), next(p) {}
};
class Solution
{
public:
//leetcode 16
//Input: nums = [-1,2,1,-4], target = 1
//Output: 2
//Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
int threeSumClosest(vector<int>& nums, int target)
{
if(nums.size() < 3) return 0;
if(3 == nums.size()) return nums[0]+nums[1]+nums[2];
std::sort(nums.begin(),nums.end());
int curSum = nums[0]+nums[1]+nums[2];
for(int i=0;i<nums.size()-2;i++)
{
int j= i+1;
int k = nums.size()-1;
while (j<k)
{
curSum = abs(curSum - target) <= abs(nums[i]+nums[j]+nums[k] - target) ? curSum : (nums[i]+nums[j]+nums[k]);
if(nums[i]+nums[j]+nums[k] > target)
{
k--;
}
else if(nums[i]+nums[j]+nums[k] < target)
{
j++;
}
else
{
return target;
}
}
}
return curSum;
}
//leetcode 17
vector<string> letterCombinations(string digits)
{
vector<string> res;
if(0 == digits.size()) return res;
int fastIndex = digits[0] - '0';
unordered_map<int,string> numsTodigits;
numsTodigits[2] = "abc";
numsTodigits[3] = "def";
numsTodigits[4] = "ghi";
numsTodigits[5] = "jkl";
numsTodigits[6] = "mno";
numsTodigits[7] = "pqrs";
numsTodigits[8] = "tuv";
numsTodigits[9] = "wxyz";
vector<string> preString;
if(fastIndex >=2 && fastIndex<=9 && fastIndex != 7 && fastIndex != 9)
{
preString.push_back(numsTodigits[fastIndex].substr(0,1));
preString.push_back(numsTodigits[fastIndex].substr(1,1));
preString.push_back(numsTodigits[fastIndex].substr(2,1));
}
else if(7 == fastIndex || 9 == fastIndex)
{
preString.push_back(numsTodigits[fastIndex].substr(0,1));
preString.push_back(numsTodigits[fastIndex].substr(1,1));
preString.push_back(numsTodigits[fastIndex].substr(2,1));
preString.push_back(numsTodigits[fastIndex].substr(3,1));
}
int len = digits.size();
vector<string> curString;
for(int i=1;i<len;i++)
{
for(int k =0;k<preString.size();k++)
{
for(int j=0;j<numsTodigits[digits[i] - '0'].size();j++)
{
string tmpResString = preString[k] + numsTodigits[digits[i] - '0'][j];
cout<<"This tmp string is "<<tmpResString<<endl;
curString.push_back(tmpResString);
}
}
preString.clear();
preString.assign(curString.begin(),curString.end());
curString.clear();
}
return preString;
}
//leetcode 18 4sum
/*
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
*/
vector<vector<int>> fourSum(vector<int>& nums, int target) {
std::sort(nums.begin(),nums.end());
//cout<<"after sort this nums is ";
vector<vector<int>> res;
if(nums.size() < 4) return res;
int j = nums.size()-1;
for(int i=0;i<nums.size()-3 ;i++)
{
for(j=nums.size()-1;j>=3;j--)
{
vector<int> cur;
int newTarget = target - nums[i] - nums[j];
int k = i+1;
int m = j-1;
while (k < m)
{
//cout<<"k is "<<k<<" m is "<<m<<endl;
if(nums[k] + nums[m] > newTarget)
{
m--;
}
else if(nums[k] + nums[m] < newTarget)
{
k++;
}
else
{
cur.push_back(nums[i]);
cur.push_back(nums[k]);
cur.push_back(nums[m]);
cur.push_back(nums[j]);
res.push_back(cur);
cur.clear();
while (nums[k+1] == nums[k] && k<m) k++;
k++;
while (nums[m-1] == nums[m] && k<m) m--;
m--;
}
}
while (nums[j-1] == nums[j] && j>=3) j--;
}
while (nums[i+1] == nums[i] && i<(nums.size()-3)) i++;
}
return res;
}
//leetcode 19 Remove Nth Node From End of List
/*
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
*/
ListNode* removeNthFromEnd(ListNode* head, int n)
{
if(head == NULL || n <= 0) return NULL;
int len = 0;
ListNode* fast = head;
ListNode* slow = head;
while (fast != NULL && fast->next != NULL && fast->next->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
len++;
}
int realLen = 0;
if(fast->next == NULL)
{
realLen = len*2 + 1;
}
else if(fast->next->next == NULL)
{
realLen = (len+1) * 2;
}
if(n > realLen) return NULL;
slow = head;
ListNode* dumy = NULL;
if(realLen == n) return head->next;
for(int i=0;i<(realLen-n);i++)
{
dumy = slow;
slow = slow->next;
}
dumy->next = dumy->next->next;
return head;
}
void travelListNode(ListNode* head)
{
if(head == NULL) return;
cout<<"This val is "<<head->val<<endl;
travelListNode(head->next);
}
/*leetcode 20
Given a string containing just the characters '(', ')', '{', '}', '[' and ']',
Input: "{[]}"
Output: true
null is valid
"(([]){})" true
*/
bool isValid(string s)
{
if(s.size() == 0) return true;
int len = s.size();
int i = 0;
if(len%2 == 1) return false;
while (!(s[i] == '(' && s[i+1] == ')' || s[i] == '{' && s[i+1] == '}' || s[i] == '[' && s[i+1] == ']') && i < len-1)
{
i++;
}
if (i == len-1) return false;
string newStr = s.substr(0,i) + s.substr(i+2,s.size()-(i+2));
return isValid(newStr);
}
/*
leetcode 21
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
Merge two sorted linked lists and return it as a new sorted list.
The new list should be made by splicing together the nodes of the first two lists.
*/
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
if(l1 == NULL && l2 == NULL) return NULL;
if(l1 != NULL && l2 == NULL) return l1;
if(l1 == NULL && l2 != NULL) return l2;
ListNode* dumy = new ListNode(0);
ListNode* cur = NULL;
ListNode* pre = dumy;
while (l1 != NULL || l2 != NULL)
{
if(l1 == NULL && l2 != NULL)
{
pre->next = l2;
break;
}
else if(l2 == NULL && l1 != NULL)
{
pre->next = l1;
break;
}
else
{
if(l1->val <= l2->val)
{
ListNode* tmpNode = new ListNode(l1->val);
cur = tmpNode;
pre->next = cur;
pre = cur;
l1 = l1->next;
}
else
{
ListNode* tmpNode = new ListNode(l2->val);
cur = tmpNode;
pre->next = cur;
pre = cur;
l2 = l2->next;
}
}
}
return dumy->next;
}
ListNode* insertTail()
{
ListNode* dumy = new ListNode(0);
ListNode* pre = dumy;
ListNode* cur = NULL;
for(int i=0;i<5;i++)
{
ListNode* tmpNode = new ListNode(i+1);
cur = tmpNode;
pre->next = cur;
pre = cur;
}
return dumy->next;
}
ListNode* insertHead()
{
ListNode* dumy = new ListNode(0);
ListNode* pre = dumy;
ListNode* cur = NULL;
for(int i=0;i<5;i++)
{
ListNode* tmpNode = new ListNode((i+1)*(i+1));
pre = dumy;
cur = tmpNode;
cur->next = pre->next;
pre->next = cur;
}
return dumy->next;
}
void travelTreeNodeByFloor(TreeNode* root)
{
queue<TreeNode*> q;
if(root == NULL) return;
q.push(root);
while (!q.empty())
{
TreeNode* tmp = q.front();
cout<<"This val is "<<tmp->val<<endl;
q.pop();
if(tmp->left != NULL)
{
q.push(tmp->left);
}
if(tmp->right != NULL)
{
q.push(tmp->right);
}
}
}
vector<vector<int>> getAllPath(TreeNode* root)
{
vector<vector<int>> res;
if(NULL == root) return res;
vector<int> v;
helper(res,v,root);
}
//vector<int> v 这个入参好像真不能用vector<int>& v
void helper(vector<vector<int>>& res,vector<int> v,TreeNode* root)
{
if(root == NULL) return;
v.push_back(root->val);
if(root->left == NULL && root->right == NULL)
{
res.push_back(v);
}
helper(res,v,root->left);
helper(res,v,root->right);
}
/* leetcode 22
22. Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
*/
//回溯法 这道题真不会 leetcode22
vector<string> generateParenthesis(int n)
{
vector<string> res;
if(n <= 0) return res;
helperGeneratePatenthesis(res,"",0,0,n);
return res;
}
void helperGeneratePatenthesis(vector<string>& res,string cur,int left,int right,int n)
{
cout<<"This cur is "<<cur<<" This left is "<<left<<" This right is "<<right<<endl;
if(n == right)
{
res.push_back(cur);
}
if(left < n)
{
helperGeneratePatenthesis(res,cur+'(',left+1,right,n);
}
if(right < left)
{
helperGeneratePatenthesis(res,cur+')',left,right+1,n);
}
}
/*
leetcode 23
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
*/
ListNode* mergeKLists(vector<ListNode*>& lists)
{
if(lists.size() == 0) return NULL;
vector<int> nums;
for(int i=0;i<lists.size();i++)
{
while (lists[i] != NULL)
{
nums.push_back(lists[i]->val);
lists[i] = lists[i]->next;
}
}
std::sort(nums.begin(),nums.end());
ListNode* dumy = new ListNode(0);
ListNode* pre = dumy;
ListNode* cur = NULL;
for(int i=0;i<nums.size();i++)
{
cur = new ListNode(nums[i]);
pre->next = cur;
pre = cur;
}
return dumy->next;
}
/*
leetcode 24
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example://Given 1->2->3->4, you should return the list as 2->1->4->3.
*/
ListNode* swapPairs(ListNode* head)
{
if(head == NULL || (head != NULL && head->next == NULL)) return head;
ListNode* dumy = new ListNode(0);
ListNode* pre = dumy;
ListNode* cur = NULL;
while(head != NULL && head->next != NULL)
{
ListNode* curNext = new ListNode(head->next->val);
cur = new ListNode(head->val);
pre->next = curNext;
curNext->next = cur;
pre = cur;
head = head->next->next;
}
if(head != NULL && head->next == NULL)
{
ListNode* tmpNode = new ListNode(head->val);
pre->next = tmpNode;
}
return dumy->next;
}
/*
leetcode 25
//leetcode 25 Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than&nbs***bsp;equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Note:Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.
*/
ListNode* reverseKGroup(ListNode* head, int k)
{
if(head == NULL || k <=0) return NULL;
ListNode* dumy = new ListNode(0);
ListNode* pre = dumy;
ListNode* cur = NULL;
ListNode* next = NULL;
int count = 0;
bool flag = false;
while(count < k && head != NULL)
{
ListNode* tmp = head;
for(int i=0;i<k;i++)
{
if(tmp == NULL)
{
flag = true;
break;
}
tmp = tmp->next;
}
if(true == flag) break;
tmp = head;
int curRealVal = 0;
for(int i=0;i<(k - count -1) && tmp != NULL;i++)
{
tmp = tmp->next;
}
curRealVal = tmp->val;
cur = new ListNode(curRealVal);
next = head->next;
pre->next = cur;
pre = cur;
count++;
if(count == k)
{
count = 0;
for(int i=0;i<k;i++)
{
head = head->next;
}
}
}
ListNode* newHead = head;
while (newHead != NULL)
{
ListNode* tmp = newHead;
int count = 0;
for(int i =0;i<k;i++)
{
if(tmp != NULL)
{
count++;
tmp = tmp->next;
}
else
{
break;
}
}
if(count == k)
{
newHead = newHead->next->next->next;
}
else
{
break;
}
}
pre->next = newHead;
return dumy->next;
}
/*
//leetcode25
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.
*/
int removeDuplicates(vector<int>& nums)
{
if(nums.size() == 0) return 0;
int count = 0;
for(int i=0;i<nums.size();)
{
int j = i;
while((j < nums.size()-1) && nums[j] == nums[j+1]) j++;
nums.erase(nums.begin()+i,nums.begin()+j);
if(j > i)
{
count++;
i = count;
}
else
{
i++;
}
}
return nums.size();
}
/*
leetcode 27
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Given nums = [0,1,2,2,3,0,4,2], val = 2,
Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
*/
int removeElement(vector<int>& nums, int val)
{
if(nums.size() == 0) return 0;
for(int i=0;i<nums.size();i++)
{
if(nums[i] == val)
{
nums.erase(nums.begin()+i,nums.begin()+i+1);
i--;
}
}
return nums.size();
}
/*
leetcode 28 KMP
*/
int strStr(string s, string p)
{
if(s.size() == 0 && p.size() != 0) return -1;
else if(p.size() == 0) return 0;
vector<int> next = findNext(s);
for_each(next.begin(),next.end(),[](auto x){cout<<x<<" ";});
cout<<endl;
int i=0;
int j = 0;
for(i = 0;i<s.size();i++)
{
while (j > 0 && p[j] != s[i])
{
j = next[j-1];
}
if(s[i] == p[j])
{
j++;
}
if(j == p.size())
{
return i-p.size()+1;
}
}
return -1;
}
vector<int> findNext(string s)
{
vector<int> res(s.size(),0);
if(s.size() == 0) return res;
int i = 0;
int j = 0;
for(i = 1;i<s.size();i++)
{
while (j > 0 && s[i] != s[j])
{
j = res[j-1];
}
if(s[j] == s[i])
{
j++;
}
res[i] = j;
}
return res;
}
//优化过后的next 数组求法
//0721 New KMP https://blog.csdn.net/v_july_v/article/details/7041827
void GetNextval(char* p, int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || p[j] == p[k])
{
++j;
++k;
//较之前next数组求法，改动在下面4行
if (p[j] != p[k])
next[j] = k; //之前只有这一行
else
//因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
next[j] = next[k];
}
else
{
k = next[k];
}
}
}
int KmpSearch(char* s, char* p)
{
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
int nextVal[sLen];
GetNextval(s,nextVal);
while (i < sLen && j < pLen)
{
//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = nextVal[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
};
int main()
{
/*
Solution solution;
string s = "mississippi";
string p = "issip";
//string s = "aabccffdcddccdef";
//string p = "ccd";
const char* s1 = s.c_str();
const char* p1 = p.c_str();
char* s2 = new char[1000];
char* p2 = new char[100];
strcpy(s2,s1);
strcpy(p2,p1);
cout<<s2<<" "<<p2<<endl;
int kmpSearchRes = solution.KmpSearch(s2,p2);
cout<<"KMP search res is "<<kmpSearchRes<<endl;
*/
/*
vector<int> v = {0,1,2,2,3,0,4,2};
Solution solution;
cout<<solution.removeElement(v,2)<<endl;
for_each(v.begin(),v.end(),[](auto x){cout<<x<<" ";});
cout<<endl;
cout<<v.size()<<endl; //居然是会变化的，现在v.size() = 5
*/
/*
Solution solution;
//0,0,1,1,1,2,2,3,3,4
vector<int> nums = {0,0,1,2,3,3,4,5,5,6,6,7};
cout<<solution.removeDuplicates(nums)<<endl;
*/
/*
vector<int> v = {1,2,3,4,5};
v.erase(v.begin(),v.begin()+1);
cout<<v.size()<<endl;;
for_each(v.begin(),v.end(),[](auto x){cout<<x<<" ";});
*/
/*
ListNode* l7 = new ListNode(7);
ListNode* l6 = new ListNode(6,l7);
ListNode* l5 = new ListNode(5,l6);
ListNode* l4 = new ListNode(4,l5);
ListNode* l3 = new ListNode(3,l4);
ListNode* l2 = new ListNode(2,l3);
ListNode* l1 = new ListNode(1,l2);
Solution solution;
solution.travelListNode(solution.reverseKGroup(l1,4));
*/
/*
// 1->4->5, 1->3->4, 2->6
ListNode* l3 = new ListNode(5);
ListNode* l2 = new ListNode(4,l3);
ListNode* l1 = new ListNode(1,l2);
ListNode* l6 = new ListNode(4);
ListNode* l5 = new ListNode(3,l6);
ListNode* l4 = new ListNode(1,l5);
ListNode* l8 = new ListNode(6);
ListNode* l7 = new ListNode(2,l8);
Solution solution;
//solution.travelListNode(l1);
//solution.travelListNode(l4);
//solution.travelListNode(l7);
vector<ListNode*> allListNodes;
allListNodes.push_back(l1);
allListNodes.push_back(l4);
allListNodes.push_back(l7);
ListNode* res = solution.mergeKLists(allListNodes);
solution.travelListNode(res);
*/
/*
Solution solution;
vector<string> res = solution.generateParenthesis(3);
for_each(res.begin(),res.end(),[](auto x){cout<<x<<" ";});
cout<<endl;
*/
/*
Solution solution;
ListNode* insertTailListNode = solution.insertTail();
cout<<"first"<<endl;
solution.travelListNode(insertTailListNode);
ListNode* insertHeadListNode = solution.insertHead();
cout<<"second"<<endl;
solution.travelListNode(insertHeadListNode);
cout<<"first and second over"<<endl;
ListNode* l6 = new ListNode(6);
ListNode* l5 = new ListNode(2,l6);
ListNode* l4 = new ListNode(1,l5);
ListNode* testListNodeOne = l4;
solution.travelListNode(testListNodeOne);
ListNode* l3 = new ListNode(5);
ListNode* l2 = new ListNode(4,l3);
ListNode* l1 = new ListNode(3,l2);
ListNode* testListNodeTwo = l1;
solution.travelListNode(testListNodeTwo);
ListNode* res = solution.mergeTwoLists(testListNodeOne,testListNodeTwo);
cout<<"res is "<<endl;
solution.travelListNode(res);
*/
/*
TreeNode* p4 = new TreeNode(4);
TreeNode* p5 = new TreeNode(5);
TreeNode* p6 = new TreeNode(6);
TreeNode* p7 = new TreeNode(7);
TreeNode* p2 = new TreeNode(2,p4,p5);
TreeNode* p3 = new TreeNode(3,p6,p7);
TreeNode* p1 = new TreeNode(1,p2,p3);
TreeNode* root = p1;
Solution solution;
cout<<"This floor root is "<<endl;
solution.travelTreeNodeByFloor(root);
cout<<"This floor travel over"<<endl;
vector<vector<int>> res = solution.getAllPath(root);
for(int i=0;i<res.size();i++)
{
for_each(res[i].begin(),res[i].end(),[](auto x){cout<<x<<" ";});
cout<<endl;
}
*/
//cout<<sizeof("123456789")<<endl; 这个结果是10
/*
string str = "{}";
Solution solution;
cout<<solution.isValid(str)<<endl;
*/
/*
//ListNode* p5 = new ListNode(5);
ListNode* p4 = new ListNode(4);
ListNode* p3 = new ListNode(p4,3);
ListNode* p2 = new ListNode(p3,2);
ListNode* p1 = new ListNode(p2,1);
ListNode* head = p1;
Solution solution;
solution.travelListNode(head);
ListNode* res = solution.removeNthFromEnd(head,4);
cout<<"res is "<<endl;
solution.travelListNode(res);
*/
/*
Solution solution;
vector<int> v= {23,12,546,0,15,6,9,2,3,56,1};
vector<vector<int>> res = solution.fourSum(v,18);
for(int i=0;i<res.size();i++)
{
for(int j=0;j<res[i].size();j++)
{
cout<<res[i][j]<<" ";
}
cout<<endl;
}
*/
/*
string str = "23455693";
Solution solution;
vector<string> res = solution.letterCombinations(str);
for(auto u : res)
{
cout<<u<<" ";
}
cout<<endl;
cout<<"res.size is "<<res.size()<<endl;
*/
/*
vector<int> v = {0,2,1,-3};
Solution solution;
int res = solution.threeSumClosest(v,1);
cout<<res<<endl;
*/
time_t now_time = time(NULL);
tm* thisLocalTime = localtime(&now_time);
cout<<endl;
cout<<asctime(thisLocalTime)<<endl;
system("pause");
return 0;
} 
