leetcode4

4Sum

和3Sum差不多

#coding=utf-8 class Solution(object): def fourSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[List[int]] """ nums.sort() result=[] for i in range(len(nums)-3): if i==0 or nums[i]>nums[i-1]: for j in range(i+1,len(nums)-2): if j==i+1 or nums[j]>nums[j-1]: left=j+1;right=len(nums)-1 while left<right: now=nums[i]+nums[j]+nums[left]+nums[right] if now==target: result.append([nums[i],nums[j],nums[left],nums[right]]) left+=1;right-=1 while left<right and nums[left]==nums[left-1]: left+=1 while left<right and nums[right]==nums[right+1]: right-=1 elif now<target: left+=1 while left<right and nums[left]==nums[left-1]: left+=1 else: right-=1 while left<right and nums[right]==nums[right+1]: right-=1 return result

Remove Nth Node From End of List

C++:

class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { if(head==NULL) { return NULL; } ListNode *Pummy=NULL; ListNode *p=head; ListNode *q=head; for(int i=0;i<n-1;i++) { p=p->next; } while(p->next) { Pummy=q; q=q->next; p=p->next; } if(Pummy==NULL) { head=q->next; delete q; } else { Pummy->next=q->next; delete q; } return head; } };

python:

class Solution(object): def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ dummy=ListNode(0) dummy.next=head p1=p2=dummy for i in range(n): p1=p1.next while p1.next: p1=p1.next p2=p2.next p2.next=p2.next.next return dummy.next

Valid Parentheses

C++:如果当前字符为左半边括号时，则将其压入栈中，如果遇到右半边括号时，若此时栈为空，则直接返回false，如不为空，则取出栈顶元素，若为对应的左半边括号，则继续循环，反之返回false。

class Solution { public: bool isValid(string s) { stack<char> parentheses; //堆栈 for(int i=0;i<s.size();i++){ if(s[i]=='(' || s[i]=='[' || s[i]=='{'){ parentheses.push(s[i]); } else{ if(parentheses.empty()){ return false; } if(s[i]==')' && parentheses.top()!='(') return false; if(s[i]==']' && parentheses.top()!='[') return false; if(s[i]=='}' && parentheses.top()!='{') return false; parentheses.pop(); } } return parentheses.empty(); } };

python：

#coding=utf-8 class Solution(object): def isValid(self, s): """ :type s: str :rtype: bool """ matchDict={'(':')','[':']','{':'}'} stackList=[] for i in range(len(s)): if s[i] not in matchDict.keys() and len(stackList)==0: return False elif s[i] in matchDict.keys(): stackList.append(s[i]) elif s[i]==matchDict[stackList[-1]]:#是对应的才能从栈里弹出 stackList.pop() else: return False if len(stackList)==0: return True else: return False

栈(后进先出)

判断是否为空

STACK-EMPTY(S) if S.top==0 return True else return False

压入栈

PUSH(S,x) S.top=S.top+1 S[S.top]=x

从栈中弹出

POP(S,x) if STACK-EMPTY(S) error "underflow" else S.top=S.top-1 return S[S.top+1]

Generate Parentheses

列举出所有合法的括号匹配，使用dfs。如果左括号的数量大于右括号的数量的话，就不能产生合法的括号匹配。

#coding=utf-8 class Solution(object): def helpler(self,l,r,item,res): print l,r,item if r<l: return if l==0 and r==0: res.append(item) if l>0: self.helpler(l-1,r,item+'(',res) if r>0: self.helpler(l,r-1,item+')',res) def generateParenthesis(self, n): """ :type n: int :rtype: List[str] """ result=[] self.helpler(n,n,'',result) return result