20. Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
思路：
这很明显就是一个栈的题目。如果是左括号，就入栈。如果是右括号，就进行出栈检测。如果没办法正确出栈，就有问题。
class Solution {
public:
bool isValid(string s) {
stack<char> ss;
for(char c : s){
if(c=='(' || c=='{' || c=='[') ss.push(c);
else{
if(ss.empty()) return false;
char temp=ss.top();
if((temp=='{' && c=='}') || (temp=='('&& c==')') || (temp=='['&& c==']')){
ss.pop();
}
else return false;
}
}
if(ss.empty()) return true;
else return false;
}
};
24. Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
Note:
Your algorithm should use only constant extra space.
You may not modify the values in the list's nodes, only nodes itself may be changed.
思路：
难点在于不能够改变链表内部的变量，而是要通过指针来改变链表结构。主要注意点感觉在于这一对指针是否有NULL。一对一对检查，而不是一个一个检查。还要记录一个先前状态量。
在精简讨论中有一种更加吊的方法。我的方法有点冗余了。
冗余方法：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head==NULL || head->next==NULL) return head;
ListNode* first=head;
ListNode* second=head->next;
ListNode* pre=first;
while(first!=NULL && second!=NULL){
if(first==head){
first->next=second->next;
second->next=first;
head=second;
}
else{
first->next=second->next;
second->next=first;
pre->next=second;
}
if(first->next!=NULL && first->next->next!=NULL){
pre=first;
second=first->next->next;
first=first->next;
}
else break;
}
return head;
}
};
精简方法：
ListNode* swapPairs(ListNode* head) {
ListNode **pp = &head, *a, *b;
while ((a = *pp) && (b = a->next)) {
a->next = b->next;
b->next = a;
*pp = b;
pp = &(a->next);
}
return head;
}
34. Find First and Last Position of Element in Sorted Array
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
解析：
最初的想法：感觉用二分法找，找到后，找到后以剩下的数组再找。
我上面的想法是找到一个数，然后扩散两边找。但是这样就会超时。
新方法：
用二分法找最左边，和最右边。
1，最左边，固定start点，让end点慢慢向右移动。mid=(start+end)/2
2，最右边，固定end点，让start点慢慢向左移动，mid=(start+end)/2+1,这样才有向右移动的趋势。
算两次,还是nlog(n)。写起来很简单，主要是想法。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int start=0,end=nums.size()-1;
vector<int> res(2,-1);
if(end<0) return res;
int temp=-1;
//find the left target index
while(start<end){
temp=(end+start)/2;
if(nums[temp]>=target) end=temp;
else start=temp+1;
}
if(nums[start]!=target) return res;
res[0]=start;
start=0;
end=nums.size()-1;
while(start<end){
temp=(end+start)/2+1;
if(nums[temp]<=target) start=temp;
else end=temp-1;
}
res[1]=end;
return res;
}
};
47. Permutations II
iven a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
思路：
很明显，一开始要检测是否是重复。开始想到排序，但是应该用map来做比较好。接下来就是如何写重复的方法。
如何重排序呢，这是一个问题。难道是利用插入嘛？
做到遍历，很明显，就应该是一个递归调用的思路。接下来就是，如果发现重复元素，我们就不去打乱这个数组。如果不是重复元素，我们就打乱这个数组。就利用这种方法，不停递归。
如何发现这个重复的元素呢，我们必须要对这个vector先排序，然后再考虑递归的方法。
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> res;
help(nums,0,nums.size(),res);
return res;
}
void help(vector<int> num,int start,int end,vector<vector<int>> &res){
if(start==end-1){
res.push_back(num);
return;
}
for(int i=start;i<end;i++){
if(i!=start && num[i]==num[start]) continue;
swap(num[i],num[start]);
help(num,start+1,end,res);
}
}
};
56. Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
思路：
我的想法是先排序，然后按照数据来计算开始值和结束值。不需要DP的方法。
这里的注意点就在于这个排序函数怎么写。
我看到评论里面还有一种比较有意思的写法。
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals) {
//sort(intervals.begin(),intervals.end(),comp);
sort(intervals.begin(),intervals.end(),[](Interval a,Interval b){return a.start<b.start;});//更加快而短的方法
vector<Interval> res;
if(intervals.size()==0) return res;
Interval pre=intervals[0];
for(Interval interval : intervals){
if(interval.start<=pre.end) pre.end=max(interval.end,pre.end);
else{
res.push_back(pre);
pre=interval;
}
}
res.push_back(pre);
return res;
}
bool static comp(Interval a, Interval b){
return a.start<b.start;
}
};
105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
3
/
9 20
/
15 7
思路：
这是一到正统的二叉树遍历题目。给了我中序遍历和先序遍历，现在要我把这个二叉树构造出来。
需要用到vector的find功能。这里用map，节省时间。但是！用map有一个很致命的问题，没有办法判断重复数字的位置。完！但是这道题告诉我不需要考虑重复的情况。但是还是建议不要随便使用map。
这里是一个递归的方法，分为左子树，右子树。
事实证明，还是用find比较好。而且要分区写，一开始不要怕麻烦。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
TreeNode *head=update(preorder,inorder,0,preorder.size(),0,inorder.size());
return head;
}
TreeNode* update(vector<int> preorder,vector<int> inorder,int i,int j,int ii,int jj){
if(i>=j || ii>=jj) return NULL;
auto f=find(inorder.begin()+ii,inorder.begin()+jj,preorder[i]);
int dis=f-inorder.begin()-ii;
TreeNode* root=new TreeNode(preorder[i]);
root->left=update(preorder,inorder,i+1,i+1+dis,ii,ii+dis);
root->right=update(preorder,inorder,i+1+dis,j,ii+dis+1,jj);
return root;
}
};
//preorder = [3,9,20,15,7]
//inorder = [9,3,15,20,7]
//step 1 : 3 [9] [20,15,7]
// [9] 3 [15,20,7]
//step 2 : 20 [15] [7]
// [15] 20 [7]
242. Valid Anagram
Given two strings s and t , write a function to determine if t is an anagram of s.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
思路：
很明显，这里又是一个找相似的问题，问题说这个新字符串是否是打乱顺序的字符串。很明显就是map映射的问题。只要注意要看一下map映射的遍历问题。还有python怎么写。
当然直接排序是最简单的了
class Solution {
public:
bool isAnagram(string s, string t) {
unordered_map<char,int> m;
for(auto c : s){
m[c]++;
}
for(auto c : t){
m[c]--;
}
for(unordered_map<char,int>::iterator it=m.begin();it!=m.end();it++){
if(it->second!=0) return false;
}
return true;
}
};
350. Intersection of Two Arrays II
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
思路：
这道题比DP简单主要是他的无序性。他不是一个字符串，而是一个数组。
但是我想法确实没有什么好的，难道要查找吗，nlogn的复杂度，好像不是很好。
如果先排序会不会好一点？那应该也是nlogn的复杂度。
最好的方法应该是利用map来计算（无序性）
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> m;
vector<int> res;
for(int i=0;i<nums1.size();i++) m[nums1[i]]++;
for(int i=0;i<nums2.size();i++){
if(--m[nums2[i]]>=0) res.push_back(nums2[i]);
}
return res;
}
};
454. 4Sum II
iven four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.
Example:
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
Output:
2
Explanation:
The two tuples are:
- (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
思路：
我只能想到这是一个n的四次方的遍历问题。但是应该还有更加高效的方法。这样绝对会超时！
可以考虑两个两个一组。em.....第一个遍历，第二个两个查找。查找的时间为n。这样就下降为NNN*log(N).
最后确定为最后一个用map作查找。查到几个就加几个。但是这样内存占用又超了！真是烦人！
其实就差一点点了。我们用map记录前两个数据的值，然后再用map查询后面两个数据的值。这样就完全不会用空间超过以及时间超过的问题了。
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
int res=0;
unordered_map<int,int> m;
for(auto a:A){
for(auto b:B){
m[a+b]+=1;
}
}
for(auto c:C){
for(auto d:D){
res+=m[-c-d];
}
}
return res;
}
};
583. Delete Operation for Two Strings
Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.
思路：
DP问题？没有想到一个模型，可能要列一个数学公式吧，但是那个公式怎么写呢。。
解：这是一个典型的dp问题。主要是我们解出DP的最大值，然后，总长度减去DP的最大值2就可以了。
这个题目和求两个字符串相似长度最长的是多少是一类问题，就是利用动态规划。
我们这里一定要想到建立那个相似矩阵来一行一行求解。当然也可以自顶向下递归求解。
这里应该还有一个trik,我们把矩阵扩展为m+1n+1大小，全部制0.这样从1,1开始检测就不会出现边界碰撞的检测问题。
class Solution {
public:
int minDistance(string word1, string word2) {
int m=word1.size(),n=word2.size();
if(m==0) return n;
if(n==0) return m;
int aps[m][n];
int row,col,tra;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
row=(i-1>=0)? aps[i-1][j]:0;
col=(j-1>=0)? aps[i][j-1]:0;
if(word1[i]==word2[j]){
tra=1;
if(j-1>=0 && i-1>=0)
tra+=aps[i-1][j-1];
}
else tra=0;
aps[i][j]=std::max(row,col);
aps[i][j]=std::max(aps[i][j],tra);
}
}
return m+n-aps[m-1][n-1]*2;
}
};
704. Binary Search
Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
思路：
这个数组是排序过后的，我就不用干什么了，之间二分查找就行。有就返回索引，没有就返回-1
class Solution {
public:
int search(vector<int>& nums, int target) {
int start=0,end=nums.size();
int mid=(start+end)/2;
if(end==0) return -1;
while(start<end){
if(nums[mid]<target){
start=mid+1;
mid=(start+end)/2;
}
else if(nums[mid]>target){
end=mid;
mid=(start+end)/2;
}
else{
return mid;
}
}
return -1;
}
};
709. To Lower Case
mplement function ToLowerCase() that has a string parameter str, and returns the same string in lowercase.
Example 1:
Input: "Hello"
Output: "hello"
思路：
没什么花头，一个函数也可以解决了。但是注意我在写for循环里面的引用写法，否则没有办法改变变量。
class Solution {
public:
string toLowerCase(string str) {
for(char &c : str){
c=(c>='A' && c<='Z') ? c-'A'+'a':c;
}
return str;
}
};
713. Subarray Product Less Than K
Your are given an array of positive integers nums.
Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.
Example 1:
Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
思路：
有通过规律找到了一个新的方法。逐一增加法。先测一个，然后想右添加一个。从添加的那个开始从右往左找，找到的最大位数就是增加的总数。由于必须包含最后一位，所以从右往左移动几位就算是增加几个。
但是这样做会超时。。。见鬼了
超时的原因就是在于我没有储存之前的状态。实际上之前的状态很有用。如果我保存之前的开始状态，然后向右移动，就能够慢慢节约时间增加总长度。
超时版本：
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int size=nums.size();
if(k<1) return 0;
int res=0;
for(int i=0;i<size;i++){
if(nums[i]<k) res+=1;
int temp=nums[i];
for(int j=i-1;j>=0;j--){
if(nums[j]*temp>=k) break;
res+=1;
temp*=nums[j];
}
}
return res;
}
};
不超时版本：
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int size=nums.size();
if(k<1) return 0;
int res=0;
int left=0;
int temp=1;
for(int i=0;i<size;i++){
temp*=nums[i];
while(temp>=k && left<=i) temp/=nums[left++];
res+=i-left+1;
}
return res;
}
};
718. Maximum Length of Repeated Subarray
Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.
Example 1:
Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation:
The repeated subarray with maximum length is [3, 2, 1].
Note:
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100
解析：
最长公共串问题
我可以写一个死算的版本，但是问题就在于，首先时间复杂度可能太高了。其次，vector中可能出现重复的元素，这对我我的查找非常不利。
这种还是DP的方法。
我这样写的DP不是连续子串，而是分离最大子串。
matrix[i][j]=max(matrix[i-1][j],matrix[i][j-1]);
if(A[i-1]==B[j-1]) matrix[i][j]=max(matrix[i][j],matrix[i-1][j-1]+1);
我这里要多一个向上检测，是否满足左对角元素是否对应相等。但是还是出错了。
真正对的写法是如果相等，只要在对角位置加一就行，这样相当于对于一个串的遍历对比，利用了之前保存的结果，时间复杂度还是n*n。
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int m=A.size(),n=B.size();
if(m==0 || n==0) return 0;
int matrix[m+1][n+1];
int res=0;
for(int i=0;i<m+1;i++){
for(int j=0;j<n+1;j++){
if(i==0 || j==0){
matrix[i][j]=0;
}
else{
if(A[i-1]==B[j-1]){
matrix[i][j]=matrix[i-1][j-1]+1;
res=max(res,matrix[i][j]);
}
else matrix[i][j]=0;
}
}
}
return res;
}
};
860. Lemonade Change
At a lemonade stand, each lemonade costs 5.
Customers are standing in a queue to buy from you, and order one at a time (in the order specified by bills).
Each customer will only buy one lemonade and pay with either a 5, 10, or 20 bill. You must provide the correct change to each customer, so that the net transaction is that the customer pays 5.
Note that you don't have any change in hand at first.
Return true if and only if you can provide every customer with correct change.
解析：
主要思路就是，如果收到的钱是5，那么好，没有任何问题。如果收到的钱是10，那么好，如果五块零钱就没有问题，如果没有，那么抱歉找不开。如果收到20，先看有没有10块和5块，如果有，就成功，如果没有，检查有没有3张5块，如果有，那么成功，没有，就失败。这里还没有看到更加好的方法。
这里甚至还不需要用map，反而占用空间。
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
if(bills.size()==0) return true;
if(bills[0]!=5) return false;
map<int,int> b;
for(auto bill : bills){
if(bill==5) b[5]+=1;
if(bill==10){
if(b[5]==0) return false;
else{
b[5]--;
b[10]+=1;
}
}
if(bill==20){
if(b[5]==0) return false;
if(b[10]>0){
b[10]--;
b[5]--;
}
else{
if(b[5]<3) return false;
else b[5]-=3;
}
}
}
return true;
}
};
网友评论