LeetCode开心刷题第十天——19Remove Nth Node from the end of List(**********)20. Valid Parent

19. Remove Nth Node From End of List Medium 1878 136 Favorite Share

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

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.

The problem has two:
1(accomplished)how to write main funtion ,Fortunately,I got a main example.But this main function‘s
input order has problem.So the answer always wrong,It‘s really confused me.The main problem is cnt this 
count variable.++cnt&&cnt++ can cause a lot of problem.
2.One loop method cannot understand **=& this kinds of function‘s meaning so keep and finish in
the future.It‘s clean and clear.
**********************************************************************************************

ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode **slow = &head, *fast = head; 
while (--n) fast = fast->next;
while(fast->next) {
slow = &((*slow)->next);
fast = fast->next;
} 
*slow = (*slow)->next; 
return head;
}

********************************************************************************************************************************************************************************************

True Answer：

#include<iostream>
#include<string>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<vector>
#include<list>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        int cnt=0;
        //not harm head node
        ListNode* node=head;
        while(node)
        {
            ++cnt;
            node=node->next;
        }
        int index=cnt-n-1;
        if(0==index)
        {
            head=head->next;
        }
        else
        {
            node=head;
            while(--index)
            {
                node=node->next;
            }
            node->next=node->next->next;
        }
        return head;
    }

};
int main()
{
    ListNode *p,*head,*l,*head2;
    int n;
    p=(ListNode*)malloc(sizeof(ListNode*));
    head=p;
    p->val=0;
    p->next=NULL;
    char ch1;
    while((ch1=cin.get())!=‘\n‘ )
    {
        cin.putback(ch1);
        scanf("%d",&p->val);
        l=(ListNode*)malloc(sizeof(ListNode*));
        l->val=0;
        l->next=NULL;
        p->next=l;
        p=p->next;
    }


    Solution s;
    cin>>n;
    head2=s.removeNthFromEnd(head,n);
    while(head2->next!=NULL)
    {
        cout<<head2->val;
        head2=head2->next;
    }
    return 0;
}

20. Valid Parentheses Easy 3007 148 Favorite Share

Given a string containing just the characters ‘(‘, ‘)‘, ‘{‘, ‘}‘, ‘[‘ and ‘]‘, determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

#include<iostream>
#include<string>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<vector>
#include<list>
#include<queue>
#include<algorithm>
#include<stack>
#include<map>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        stack<int> temp;
        int size1=s.length();
        for(int i=0;i<size1;i++)
        {
            switch(s[i])
            {
                case ‘{‘:
                {
                    temp.push(1);
                    break;
                }
                case ‘}‘:
                {
                    if(temp.empty()) return false;
                    if(temp.top()==1)
                        temp.pop();
                    else
                        temp.push(1);
                    break;
                }
                case ‘[‘:
                {
                    temp.push(2);
                    break;
                }
                case ‘]‘:
                {
                    if(temp.empty()) return false;
                    if(temp.top()==2)
                        temp.pop();
                    else
                        temp.push(2);
                    break;
                }
                case ‘(‘:
                {
                    temp.push(3);
                    break;
                }
                case ‘)‘:
                {
                    if(temp.empty()) return false;
                    if(temp.top()==3)
                        temp.pop();
                    else
                        temp.push(3);
                    break;
                }
            }
        }
        if(temp.empty()) return true;
        else return false;
    }
};
int main()
{
    string s;
    bool res;
    cin>>s;
    Solution s1;
    res=s1.isValid(s);
    cout<<res<<endl;
    return 0;
}

if(s.empty()) return true;

if  we add this to top of code,it will fast the speed and less storage.So judge whether input empty is very important!!!!!!!!!!!!!!!!!!!!

This is a good solution but it‘s more complex.But this is more like a coding  theory.Because code‘s meaning is to push special problem into similar.The way  I solve is a trick.But the time cost and space cost nearly same.

class Solution {
public:
    bool isValid(string s) {
        if(s.length() == 0)
        {
            return true;
        }
 
        stack<char> st;
        st.push(s[0]);
 
        for(int i = 1; i < s.length(); ++i)
        {
            if(!st.empty() && isMatch(st.top(), s[i]))
            {
                st.pop();
            }
            else
            {
                st.push(s[i]);
            }
        }
 
        if(st.empty())
        {
            return true;
        }
        else
        {
            return false;
        }
    }
 
    bool isMatch(char s, char p)
    {
        if((s == ‘(‘ && p == ‘)‘)
        || (s == ‘{‘ && p == ‘}‘)
        || (s == ‘[‘ && p == ‘]‘))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};