Leetcode题解（28）

90. Subsets II

题目

分析:代码如下

 1 class Solution {
 2 public:
 3     vector<vector<int> > subsetsWithDup(vector<int> &S) {
 4         vector<vector<int> > result;
 5         map<vector<int>, bool> m;
 6         int size = S.size();
 7         for(int i = 0; i < pow(2.0, size); i ++)
 8         {
 9             int tag = i;
10             vector<int> cur;
11             for(int j = size-1; j >= 0; j --)
12             {
13                 if(!tag)
14                     break;
15                 if(tag%2 == 1)
16                 {
17                     cur.push_back(S[j]);
18                 }
19                 tag >>= 1;
20             }
21             sort(cur.begin(), cur.end());
22             if(m.find(cur) == m.end()) 
23             {
24                 m[cur] = true;
25                 result.push_back(cur);
26             }
27         }
28         return result;
29     }
30 };

-----------------------------------------------------------------------------分割线--------------------------------------------------------------------

91. Decode Ways

题目

分析：这道题只需要求解码的种类数，因此一看到这道题目，就条件反射似的想到找递推公式

假设f[i]表示s[0..i]的解码数。在字符串s中，如果s[i]!='0'并且s[i-1]s[i]构成的数大于等于10，小于等于26，则f[i]=f[i-1]+f[i-2]

代码如下：

 1 class Solution {
 2 public:
 3     int numDecodings(string s) {
 4         int len = s.length();
 5         
 6         if(len<=1)
 7         {
 8             if(s[0]=='0')
 9             return 0;
10             else
11             return len;
12         }
13         //如果第一位为0，不可能解码
14         if(s[0]=='0')
15             return 0;
16         
17         int first=1,second=1;
18         int temp,t;
19         
20         for(int i=1;i<len;i++)
21         {
22             t=0;
23             if(s[i] != '0')
24                 t +=second;
25             temp = (s[i-1]-'0')*10+s[i]-'0';
26             //一开始我写成temp>=1，不能通过，再仔细看题目，如果是“01”-->temp = 1这种情况是不能解码的，
27             //因此temp>=10才可以
28             if(temp>=10 &&temp <=26)
29                 t +=first;
30             first = second;
31             second = t;
32         }
33         return second;
34     }
35 };

--------------------------------------------------------------------------------分割线------------------------------------------------------------------

92. Reverse Linked List II

分析：指针操作，熟练掌握。算法不难，代码如下：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* reverseBetween(ListNode* head, int m, int n) {
12         if(NULL == head)
13             return NULL;
14         if(m==n)
15             return head;
16         ListNode *pre,*current,*pHead,*after;
17         pHead = new ListNode(-1);
18         pHead->next = head;    
19         
20         pre = pHead;
21         int i;
22         for(i=0;i<m-1;i++)//定位到第m个节点的前一个节点
23             pre = pre->next;
24         
25         current = pre->next;
26         i++;
27         
28         for(;i<n;i++)
29         {
30             after = current->next;
31             current->next=after->next;
32             after->next = pre->next;
33             pre->next = after;
34             
35         }
36         
37         return pHead->next;
38         
39     }
40 };