日常练习//算法类

1.Matrix

//二维线段树

 1 #include <iostream>
 2 #include <cstring>
 3 
 4 #define MAXN 1005
 5 #define xlson kx<<1, xl, mid
 6 #define xrson kx<<1|1, mid+1, xr
 7 #define ylson ky<<1, yl, mid
 8 #define yrson ky<<1|1, mid+1, yr
 9 
10 bool tree[MAXN<<2][MAXN<<2];
11 int X;
12 int N, T;
13 int num, X1, X2, Y1, Y2;
14 char ch;
15 
16 void editY(int kx, int ky, int yl, int yr)
17 {
18     if (Y1 <= yl && yr <= Y2)
19     {
20         tree[kx][ky] = !tree[kx][ky];
21         return ;
22     }    
23     int mid = (yl+yr)>>1;
24     if (Y1 <= mid) editY(kx, ylson);
25     if (Y2 > mid) editY(kx, yrson);
26 }
27 
28 void editX(int kx, int xl, int xr)
29 {
30     if (X1 <= xl && xr <= X2)
31     {
32         editY(kx, 1, 1, N);
33         return ;
34     }
35     int mid = (xl+xr) >> 1;
36     if (X1 <= mid) editX(xlson);
37     if (X2 > mid) editX(xrson);
38 }
39 
40 
41 
42 void queryY(int kx, int ky, int yl, int yr)
43 {
44     if (tree[kx][ky]) num++;
45     if (yl == yr) return ;
46     int mid = (yl+yr)>>1;
47     if (Y1 <= mid) queryY(kx, ylson);
48     else queryY(kx, yrson);
49 }
50 
51 void queryX(int kx, int xl, int xr)
52 {
53     queryY(kx, 1, 1, N);
54     if (xl == xr) return ;
55     int mid = (xl+xr) >> 1;
56     if (X1 <= mid) queryX(xlson);
57     else queryX(xrson);
58 }
59 
60 int main()
61 {
62     while (~scanf("%d", &X))
63     while (X--)
64     {
65         memset(tree, 0, sizeof(tree));                
66         scanf("%d %d%*c", &N, &T);
67         for (int i = 0; i < T; ++i)
68         {
69             scanf("%c %d %d%*c", &ch, &X1, &Y1);
70             if (ch == 'C')
71             {
72                 scanf("%d %d%*c", &X2, &Y2);
73                 editX(1, 1, N);
74             }
75             else
76             {
77                 num = 0;
78                 queryX(1, 1, N);
79                 if (num & 1)printf("1
");
80                 else printf("0
");
81             }
82         }
83         if (X) puts("");
84     }    
85     
86     return 0;
87 }
View Code

 2.happy-number

//水题

 1 class Solution {
 2 public:
 3     /**
 4      * @param n an integer
 5      * @return true if this is a happy number or false
 6      */
 7     bool isHappy(int n) {
 8         // Write your code here
 9         int a[1010];
10         memset(a, 0, sizeof(a));
11         int ans = 0;
12         while (ans != 1)
13         {
14             while (n)
15             {
16                 ans += (n%10)*(n%10);
17                 n /= 10;
18             }
19             if (ans == 1) return true;
20             if (a[ans]) return false;
21             a[n=ans] = 1;
22             ans = 0;
23         }
24     }
25 };
View Code

 3.generate-parentheses

//水题

 1 class Solution {
 2 public:
 3     /**
 4      * @param n n pairs
 5      * @return All combinations of well-formed parentheses
 6      */
 7     void dfs(vector<string>& ans, string str, int l, int r, int n)
 8     {
 9         if (l+r == 2*n)
10         {
11             ans.push_back(str);
12             return ;
13         }
14         if (l == r)
15             dfs(ans, str+"(", l+1, r, n);
16         else if (l == n)
17             dfs(ans, str+")", l, r+1, n);
18         else
19         {
20             dfs(ans, str+"(", l+1, r, n);
21             dfs(ans, str+")", l, r+1, n);
22         }
23     }
24     vector<string> generateParenthesis(int n) {
25         // Write your code here
26         vector<string> ret;
27         string str = "";
28         dfs(ret, str, 0, 0, n);
29         return ret;
30     }
31 };
View Code

 4.binary-tree-paths

//水题

 1 /**
 2  * Definition of TreeNode:
 3  * class TreeNode {
 4  * public:
 5  *     int val;
 6  *     TreeNode *left, *right;
 7  *     TreeNode(int val) {
 8  *         this->val = val;
 9  *         this->left = this->right = NULL;
10  *     }
11  * }
12  */
13 class Solution {
14 public:
15     /**
16      * @param root the root of the binary tree
17      * @return all root-to-leaf paths
18      */
19     string int2str(int val)
20     {
21         string ans = "";
22         int flag = 0;
23         if (val < 0) flag = 1, val = -val;
24         while (val)
25         {
26             ans += (val%10+'0');
27             val /= 10;
28         }
29         if (ans == "") ans = "0";
30         if (flag) ans += "-";
31         reverse(ans.begin(), ans.end());
32         return ans;
33     }
34     void dfs(string str, TreeNode *root, vector<string>& ans)
35     {
36         if (root == NULL) return ;
37         if (str != "") str += "->";
38         str += int2str(root->val);
39         if (root->left == NULL && root->right == NULL)
40         {
41             ans.push_back(str);
42             return;
43         }
44         dfs(str, root->left, ans);
45         dfs(str, root->right, ans);
46     }
47     vector<string> binaryTreePaths(TreeNode* root) {
48         // Write your code here
49         string str = "";
50         vector<string> ret;
51         dfs(str, root, ret);
52         return ret;
53     }
54 };
View Code

 5.surrounded-regions

//水题

 1 class Solution {
 2 public:
 3     /**
 4      * @param board a 2D board containing 'X' and 'O'
 5      * @return void
 6      */
 7     int dirx[4] = {0, 1, 0, -1};
 8     int diry[4] = {1, 0, -1, 0};
 9     void work(vector<vector<char>>& board, int x, int y, int m, int n)
10     {
11         queue<int> qx, qy;
12         while (!qx.empty()) qx.pop();
13         while (!qx.empty()) qy.pop();
14         qx.push(x), qy.push(y);
15         while (!qx.empty())
16         {
17             x = qx.front();
18             y = qy.front();
19             board[x][y] = '1';
20             qx.pop(), qy.pop();
21             for (int i = 0; i < 4; ++i)
22             {
23             
24                 int xx = x + dirx[i];
25                 int yy = y + diry[i];
26                 if (xx < 0 || xx >= m || yy < 0 || yy >= n) continue;
27                 if (board[xx][yy] == 'O')
28                     qx.push(xx), qy.push(yy);
29             }
30         }
31     }
32     void surroundedRegions(vector<vector<char>>& board) {
33         // Write your code here
34         int m = board.size();
35         if (m == 0) return ;
36         int n = board[0].size();
37         for (int i = 0; i < n; ++i)
38         {
39             if (board[0][i] == 'O') work(board, 0, i, m, n);
40             if (board[m-1][i] == 'O') work(board, m-1, i, m, n);
41         }
42         for (int i = 0; i < m; ++i)
43         {
44             if (board[i][0] == 'O') work(board, i, 0, m, n);
45             if (board[i][n-1] == 'O') work(board, i, n-1, m, n);
46         }
47         for (int i = 0; i < m; ++i)
48         {
49             for (int j = 0; j < n; ++j)
50             {
51                 if (board[i][j] == 'O') board[i][j] = 'X';
52                 if (board[i][j] == '1') board[i][j] = 'O';
53             }
54         }
55     }
56 };
View Code

 6.identical-binary-tree

//水题

 1 /**
 2  * Definition of TreeNode:
 3  * class TreeNode {
 4  * public:
 5  *     int val;
 6  *     TreeNode *left, *right;
 7  *     TreeNode(int val) {
 8  *         this->val = val;
 9  *         this->left = this->right = NULL;
10  *     }
11  * }
12  */
13 class Solution {
14 public:
15     /**
16      * @aaram a, b, the root of binary trees.
17      * @return true if they are identical, or false.
18      */
19     bool work(TreeNode *a, TreeNode *b)
20     {
21         bool flag = true;
22         if (a == NULL && b == NULL) return true;
23         if (a == NULL || b == NULL) return false;
24         if (a->val != b->val) return false;
25         if (!work(a->left, b->left)) flag = false;
26         if (!work(a->right, b->right)) flag = false;
27         return flag;
28     }
29     bool isIdentical(TreeNode* a, TreeNode* b) {
30         // Write your code here
31         return work(a, b);
32     }
33 };
View Code

 7.remove-linked-list-elements

//水题

 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     /**
12      * @param head a ListNode
13      * @param val an integer
14      * @return a ListNode
15      */
16     ListNode *removeElements(ListNode *head, int val) {
17         // Write your code here
18         if (head == NULL) return head;
19         ListNode* tgo = head;
20         while (tgo && tgo->val == val) tgo = tgo->next;
21         if (!tgo) return tgo;
22         ListNode *ret = tgo, *pre = tgo, *tmp = tgo->next;
23         while (tmp)
24         {
25             if (tmp->val == val) pre->next = tmp->next, tmp = tmp->next;
26             else pre = tmp, tmp = tmp->next;
27         }
28         return tgo;
29     }
30 };
View Code

 8.cosine-similarity

//水题

 1 class Solution {
 2 public:
 3     /**
 4      * @param A: An integer array.
 5      * @param B: An integer array.
 6      * @return: Cosine similarity.
 7      */
 8     double cosineSimilarity(vector<int> A, vector<int> B) {
 9         // write your code here
10         double a1 = 0, b1 = 0, c1 = 0;
11         for (int i = 0; i < A.size(); ++i)
12         {
13             a1 += A[i]*B[i];
14             b1 += A[i]*A[i];
15             c1 += B[i]*B[i];
16         }
17         b1 = sqrt(b1);
18         c1 = sqrt(c1);
19         if (b1 == 0 || c1 == 0) return 2.0000;
20         return a1/b1/c1;
21     }
22 };
View Code

 9.letter-combinations-of-a-phone-number

//水题

 1 class Solution {
 2 public:
 3     /**
 4      * @param digits A digital string
 5      * @return all posible letter combinations
 6      */
 7     string str[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
 8     void dfs(string& digits, string s, vector<string>& ans, int pos)
 9     {
10         if (pos == digits.length())
11         {
12             ans.push_back(s);
13             return ;
14         }
15         for (int i = 0; i < str[digits[pos]-'0'].length(); ++i)
16             dfs(digits, s+str[digits[pos]-'0'][i], ans, pos+1);
17     }
18     vector<string> letterCombinations(string& digits) {
19         // Write your code here
20         vector<string> ans;
21         if (digits != "")
22             dfs(digits, "", ans, 0);
23         return ans;
24     }
25 };
View Code

 10.restore-ip-addresses

//这个题写脑残了。

  1 class Solution {
  2 public:
  3     /**
  4      * @param s the IP string
  5      * @return All possible valid IP addresses
  6      */
  7     bool ok(string str)
  8     {
  9         long long int n = 0;
 10         for (int i = 0; i < str.length(); ++i)
 11             n = n*10 + str[i]-'0';
 12         if (n < 256) return true;
 13         return false;
 14     }
 15     int str2int(string str)
 16     {
 17         int ans = 0;
 18         for (int i = 0; i < str.length(); ++i)
 19             ans = ans*10 + str[i]-'0';
 20         return ans;
 21     }
 22     string int2str(int val)
 23     {
 24         string str = "";
 25         while (val)
 26         {
 27             str += (val%10+'0');
 28             val /= 10;
 29         }
 30         if(str == "") str = "0";
 31         reverse(str.begin(), str.end());
 32         return str;
 33     }
 34     bool judge(int pre, int last, string s)
 35     {
 36         string str = "";
 37         for (int i = pre; i < last; ++i)
 38             str += s[i];
 39         if (ok(str)) return true;
 40         return false;
 41     }
 42     int w(int pre, int last, string s)
 43     {
 44         string str = "";
 45         for (int i = pre; i < last; ++i)
 46             str += s[i];
 47         return str2int(str);
 48     }
 49     string sss(int pre, int last, string s)
 50     {
 51         string str = "";
 52         for (int i = pre; i < last; ++i)
 53             str += s[i];
 54         return str;
 55     }
 56     vector<vector<int>> cp;
 57     void work(vector<string>& ret, vector<int> add, string s, int pos, int cnt)
 58     {
 59         if (cnt == 3)
 60         {
 61             int fflag = 1;
 62             int pre = 0;
 63             vector<int> tmp;
 64             string sdd = "";
 65             for (int i = 0; i < add.size(); ++i)
 66             {
 67                 if (judge(pre, add[i], s) == false) return ;
 68                 tmp.push_back(w(pre, add[i], s));
 69                 if (i != 0) sdd += ".";
 70                 string ttt = sss(pre, add[i], s);
 71                 if (ttt.length() > 1 && ttt[0] == '0') fflag = 0;
 72                 sdd += ttt;
 73                 pre = add[i];
 74             }
 75             sdd += ".";
 76             tmp.push_back(w(pre, s.length(), s));
 77             string ttt = sss(pre, s.length(), s);
 78             if (ttt.length() > 1 && ttt[0] == '0') fflag = 0;
 79             sdd += ttt;
 80             if (!judge(pre, s.length(), s)) return ;
 81             int flag = 1;
 82             for (int i = 0; i < flag && cp.size(); ++i)
 83                 if (tmp == cp[i]) flag = 0;
 84             if (flag && fflag)
 85             {
 86                 cp.push_back(tmp);
 87                 ret.push_back(sdd);
 88             }
 89             return ;
 90         }
 91         
 92         for (int i = pos; i < s.length(); ++i)
 93         {
 94             add.push_back(i);
 95             work(ret, add, s, i+1, cnt+1);
 96             add.pop_back();
 97         }
 98     }
 99     vector<string> restoreIpAddresses(string& s) {
100         // Write your code here
101         vector<string> ret;
102         vector<int> add;
103         work(ret, add, s, 1, 0);
104         return ret;
105     }
106 };
View Code

11.add-and-search-word

//不太水的题

 1 class TrieNode
 2 {
 3 public:
 4     int flag;
 5     TrieNode* next[26];
 6     TrieNode(): flag(0)
 7     {
 8         memset(next, 0, sizeof(next));
 9     }
10 };
11 
12 TrieNode *root = NULL;
13 
14 class WordDictionary {
15 public:
16 
17     // Adds a word into the data structure.
18     void addWord(string word) {
19         // Write your code here
20         if(root == NULL)
21         {
22             TrieNode* tn = new TrieNode();
23             root = tn;
24         }
25         TrieNode *tmp = root;
26         for (int i = 0; i < word.length(); ++i)
27         {
28             if (tmp->next[word[i]-'a'] == NULL)
29             {
30                 TrieNode* tn = new TrieNode();
31                 tmp->next[word[i]-'a'] = tn;
32             }
33             tmp = tmp->next[word[i]-'a'];
34         }
35         tmp->flag = 1;
36     }
37 
38     // Returns if the word is in the data structure. A word could
39     // contain the dot character '.' to represent any one letter.
40     bool searchWork(TrieNode *rt, string word)
41     {
42         if (word == "" && rt->flag) return true;
43         else if (word == "") return false;
44         for (int i = 0; i < word.length(); ++i)
45         {
46             if (word[i] != '.')
47             {
48                 if (rt->next[word[i]-'a'] == NULL) return false;
49                 else rt = rt->next[word[i]-'a'];
50             }
51             else
52             {
53                 for (int j = 0; j < 26; ++j)
54                 {
55                     if (rt->next[j] != NULL)
56                     {
57                         if (searchWork(rt->next[j], word.substr(i+1, word.length()-i-1)))
58                             return true;
59                     }
60                 }
61                 return false;
62             }
63         }
64         if (rt->flag) return true;
65         return false;
66     }
67     
68     bool search(string word) {
69         // Write your code here
70         if (root == NULL) return false;
71         TrieNode *rt = root;
72         return searchWork(rt, word);
73     }
74 };
75 
76 // Your WordDictionary object will be instantiated and called as such:
77 // WordDictionary wordDictionary;
78 // wordDictionary.addWord("word");
79 // wordDictionary.search("pattern");
View Code

 12.swap-nodes-in-pairs

//水题

 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     /**
12      * @param head a ListNode
13      * @return a ListNode
14      */
15     void work(ListNode* head)
16     {
17         if (head->next == NULL || head->next->next == NULL) return ;
18         ListNode *tmp = head->next->next->next;
19         ListNode *t = head->next;
20         head->next = head->next->next;
21         head->next->next = t;
22         t->next = tmp;
23         work(t);
24     }
25     
26     ListNode* swapPairs(ListNode* head) {
27         // Write your code here
28         ListNode *root = (ListNode*)malloc(sizeof(ListNode));
29         ListNode *pre = root;
30         root->next = head;
31         work(root);
32         return root->next;
33     }
34 };
View Code

 13.palindrome-linked-list

//interesting problem

 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     /**
12      * @param head a ListNode
13      * @return a boolean
14      */
15     bool dfs(ListNode *head1, ListNode *stop1, ListNode *&head2)
16     {
17         if (head1 == stop1)
18         {
19             if (head1->val == head2->val){ head2 = head2->next; return true; }
20             else { head2 = head2->next;  return false; }
21         }
22         if (dfs(head1->next, stop1, head2) == false) return false;
23         else
24         {
25             if (head1->val == head2->val)
26             {
27                 head2 = head2->next;
28                 return true;
29             }
30             else
31             {
32                 head2 = head2->next;
33                 return false;
34             }
35         }
36     }
37     bool judge(ListNode *head, ListNode* stop1, ListNode* head2)
38     {
39         ListNode *head1 = head;
40         return dfs(head1, stop1, head2);
41     }
42     bool isPalindrome(ListNode* head) {
43         // Write your code here
44         if (head == NULL || head->next == NULL) return true;
45         ListNode *h1 = head, *h2 = head;
46         ListNode *pre;
47         while (h1->next != NULL && h2->next != NULL && h2->next->next != NULL)
48         {
49             pre = h1;
50             h1 = h1->next;
51             h2 = h2->next->next;
52         }
53         if (h2->next == NULL) return judge(head, pre, h1->next);
54         else return judge(head, h1,  h1->next);
55     }
56 };
View Code

 14.powx-n

//Easy Problem

 1 class Solution {
 2 public:
 3     /**
 4      * @param x the base number
 5      * @param n the power number
 6      * @return the result
 7      */
 8     double myPow(double x, int n) {
 9         // Write your code here
10         if (n == 0) return 1;
11         if (n < 0) x = 1.0/x, n = -n;
12         if (n%2)
13         {
14             double ans = myPow(x, n/2);
15             return ans*ans*x;
16         }
17         else
18         {
19             double ans = myPow(x, n/2);
20             return ans*ans;
21         }
22     }
23 };
View Code

 15.spiral-matrix

//zzz

 1 class Solution 
 2 {
 3 public:
 4     vector<int> spiralOrder(vector<vector<int> > &matrix) 
 5     {
 6         int m, n, i, j, count = 0;
 7         vector<int> ans;
 8         ans.clear();
 9         m = matrix.size();
10         if (m == 0) return ans;
11         n = matrix[0].size();
12         for (i = 0; i < (m+1)/2; i++)
13         {
14             for (j = i; j < n-i; j++) ans.push_back(matrix[i][j]), count++;
15             for (j = i+1; j < m-i; j++) ans.push_back(matrix[j][n-i-1]), count++;
16             if (m-i-1 != i) for (j = n-i-2; j >= i; j--) ans.push_back(matrix[m-i-1][j]), count++;
17             if (i != n-i-1) for (j = m-i-2; j > i; j--) ans.push_back(matrix[j][i]), count++;
18             if (count == m*n) break;
19         }
20         return ans;
21     }
22 };
View Code

 16.flatten-binary-tree-to-linked-list

//zzz

 1 /**
 2  * Definition of TreeNode:
 3  * class TreeNode {
 4  * public:
 5  *     int val;
 6  *     TreeNode *left, *right;
 7  *     TreeNode(int val) {
 8  *         this->val = val;
 9  *         this->left = this->right = NULL;
10  *     }
11  * }
12  */
13 class Solution {
14 public:
15     /**
16      * @param root: a TreeNode, the root of the binary tree
17      * @return: nothing
18      */
19     void flatten(TreeNode *root) {
20         // write your code here
21         if (root == NULL) return ;
22         if (root->left != NULL) 
23         {
24             TreeNode *left = root->left;
25             root->left = NULL;
26             TreeNode *right = root->right;
27             root->right = left;
28             TreeNode *tmp = left;
29             while (tmp->right != NULL)
30                 tmp = tmp->right;
31             tmp->right = right;
32         }
33         flatten(root->right);
34     }
35 };
View Code

 17.spiral-matrix-ii

//简单题

 1 class Solution {
 2 public:
 3     /**
 4      * @param n an integer
 5      * @return a square matrix
 6      */
 7     vector<vector<int>> generateMatrix(int n) {
 8         // Write your code here
 9         vector<vector<int>> ans(n, vector<int>(n));
10         int val = 1;
11         for (int i = 0; i < (n+1)/2; ++i)
12         {
13             for (int j = i; j < n-i; ++j) ans[i][j] = val++;
14             for (int j = i+1; j < n-i; ++j) ans[j][n-i-1] = val++;
15             for (int j = n-i-2; j >= i; --j) ans[n-i-1][j] = val++;
16             for (int j = n-i-2; j > i; --j) ans[j][i] = val++;
17             if (val > n*n) break;
18         }
19         return ans;
20     }
21 };
View Code

 18.intersection-of-two-linked-lists

//简单题

 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     /**
12      * @param headA: the first list
13      * @param headB: the second list
14      * @return: a ListNode
15      */
16     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
17         // write your code here
18         int lenA = 0, lenB = 0;
19         ListNode *t = headA;
20         while (t != NULL)
21         {
22             t = t->next;
23             lenA++;
24         }
25         t = headB;
26         while (t != NULL)
27         {
28             t = t->next;
29             lenB++;
30         }
31         while (lenA > lenB)
32         {
33             headA = headA->next;
34             lenA--;
35         }
36         while (lenA < lenB)
37         {
38             headB = headB->next;
39             lenB--;
40         }
41         while (headA != headB)
42         {
43             headA = headA->next;
44             headB = headB->next;
45         }
46         return headA;
47     }
48 };
View Code

 19.reverse-nodes-in-k-group

//中等偏下

 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     /**
12      * @param head a ListNode
13      * @param k an integer
14      * @return a ListNode
15      */
16     ListNode* work(ListNode* pre, int k)
17     {
18         ListNode *t1 = pre->next;
19         ListNode *t2 = t1->next;
20         int len = 1;
21         while (len < k)
22         {
23             ListNode *tmp = t2->next;
24             t2->next = t1;
25             t1 = t2;
26             t2 = tmp;
27             len++;
28         }
29         ListNode *tmp = pre->next;
30         pre->next->next = t2;
31         pre->next = t1;
32         return tmp;
33     }
34     ListNode *reverseKGroup(ListNode *head, int k) {
35         // Write your code here
36         ListNode *ret = (ListNode*)malloc(sizeof(ListNode));
37         ret->next = head;
38         int len = 0;
39         ListNode *tmp = head;
40         while (tmp) len++, tmp = tmp->next;
41         tmp = ret;
42         for (int i = 0; i < len/k; ++i)
43         {
44             tmp = work(tmp, k);
45         }
46         return ret->next;
47     }
48 };
View Code

 20.implement-trie

//基础题

 1 /**
 2  * Your Trie object will be instantiated and called as such:
 3  * Trie trie;
 4  * trie.insert("lintcode");
 5  * trie.search("lint"); will return false
 6  * trie.startsWith("lint"); will return true
 7  */
 8 class TrieNode {
 9 public:
10     int flag;
11     TrieNode* a[26];
12     // Initialize your data structure here.
13     TrieNode() {
14         flag = 0;
15         memset(a, 0, sizeof(a));
16     }
17 };
18 
19 class Trie {
20 public:
21     Trie() {
22         root = new TrieNode();
23     }
24     // Inserts a word into the trie.
25     void insert(string word) {
26         TrieNode *tmp = root;
27         for (int i = 0; i < word.length(); ++i)
28         {
29             if (tmp->a[word[i]-'a'] == NULL)
30             {
31                 TrieNode *nd = new TrieNode();
32                 tmp->a[word[i]-'a'] = nd;
33             }
34             tmp = tmp->a[word[i]-'a'];
35         }
36         tmp->flag = 1;
37     }
38 
39     // Returns if the word is in the trie.
40     bool search(string word) {
41         TrieNode *tmp = root;
42         for (int i = 0; i < word.length(); ++i)
43         {
44             if (tmp->a[word[i]-'a'] == NULL) return false;
45             tmp = tmp->a[word[i]-'a'];
46         }
47         if (tmp->flag) return true;
48         return false;
49     }
50 
51     // Returns if there is any word in the trie
52     // that starts with the given prefix.
53     bool startsWith(string prefix) {
54         TrieNode *tmp = root;
55         for (int i = 0; i < prefix.length(); ++i)
56         {
57             if (tmp->a[prefix[i]-'a'] == NULL) return false;
58             tmp = tmp->a[prefix[i]-'a'];
59         }
60         return true;
61     }
62 
63 private:
64     TrieNode* root;
65 };
View Code

 21.Scramble String

//Hard

 1 class Solution {
 2 public:
 3     bool isScramble(string s1, string s2) {
 4         int l1 = s1.length();
 5         int l2 = s2.length();
 6         if (l1 != l2) return false;
 7         if (l1 == 1) return s1 == s2;
 8         string st1 = s1, st2 = s2;
 9         sort(st1.begin(), st1.end());
10         sort(st2.begin(), st2.end());
11         for (int i = 0; i < l1; ++i) 
12         {
13             if (st1[i] != st2[i]) 
14             {
15                 return false;
16             }
17         }
18         string s11, s12, s21, s22;
19         bool res = false;
20         for (int i = 1; i < l1 && !res; ++i) 
21         {
22             s11 = s1.substr(0, i);
23             s12 = s1.substr(i, l1 - i);
24             s21 = s2.substr(0, i);
25             s22 = s2.substr(i, l1 - i);
26             res = isScramble(s11, s21) && isScramble(s12, s22);
27             if (!res) 
28             {
29                 s21 = s2.substr(0, l1 - i);
30                 s22 = s2.substr(l1 - i, i);
31                 res = isScramble(s11, s22) && isScramble(s12, s21);
32             }
33         }
34         return res;
35     }
36 };
View Code

 22.Trapping Rain Water

// Medium

 1 class Solution {
 2 public:
 3     /**
 4      * @param heights: a vector of integers
 5      * @return: a integer
 6      */
 7     int trapRainWater(vector<int> &heights) {
 8         // write your code here
 9         int cnt = 0;
10         int size = heights.size();
11         int i = size-1, j, maxidx, maxheight = 0;
12         while (i > 0)
13         {
14             while (i > 0 && heights[i] <= heights[i-1]) i--;
15             maxheight = -1;
16             maxidx = -1;
17             for (j = i-1; j >= 0; --j)
18             {
19                 if (heights[j] > heights[i]) break;
20                 if (heights[j] >= maxheight) maxheight = heights[j], maxidx = j;
21             }
22             if (j >= 0)
23             {
24                 for (int k = i-1; k > j; --k)
25                     cnt += heights[i]-heights[k];
26                 i = j;
27             }
28             else
29             {
30                 if (maxidx == -1) break;
31                 for (int k = i-1; k > maxidx; --k)
32                     cnt += maxheight-heights[k];
33                 i = maxidx;
34             }
35         }
36         return cnt;
37     }
38 };
View Code

 23.kth-largest-element

//Medium 快排思想

 1 class Solution {
 2 public:
 3     /*
 4      * param k : description of k
 5      * param nums : description of array and index 0 ~ n-1
 6      * return: description of return
 7      */
 8     int kthLargestElement(int k, vector<int> nums) {
 9         // write your code here
10         int left = 0, right = nums.size()-1;
11         while (left < right)
12         {
13             int l = left, r = right;
14             int key = nums[l];
15             while (l < r)
16             {
17                 while (l < r && nums[r] < key) r--;
18                 nums[l] = nums[r];
19                 while (l < r && nums[l] >= key) l++;
20                 nums[r] = nums[l];
21             }
22             nums[l] = key;
23             if (l == k-1) return nums[l];
24             else if (l > k-1) right = r-1;
25             else left = l+1;
26         }
27         return nums[k-1];
28     }
29 };
View Code

 24.Tennis Tournament

//简单模拟

 1 #include <iostream>
 2 #include <string>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdio>
 6 #include <cstdlib>
 7 
 8 using namespace std;
 9 
10 int n, b, p;
11 
12 int main()
13 {
14     scanf("%d%d%d", &n, &b, &p);
15     int ans1 = 0, ans2 = 0;
16     ans2 = n*p;
17     while (n != 1)
18     {
19         int k = 1;
20         while (k <= n) k *= 2;
21         k /= 2;
22         ans1 += k*b + k/2;
23         n = k/2 + n-k;
24     }
25     printf("%d %d
", ans1, ans2);
26 
27     return 0;
28 }
View Code

25.New Skateboard

//数学类，考虑是否为4的倍数，只需考虑个位、十位。

 1 #include <iostream>
 2 #include <string>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdio>
 6 #include <cstdlib>
 7 
 8 using namespace std;
 9 
10 const int maxn = 300010;
11 char ch[maxn];
12 int a[maxn];
13 
14 int main()
15 {
16     long long int ans = 0;
17     scanf("%s", ch);
18     int len = strlen(ch);
19     for (int i = 0; i < len; ++i)
20         a[i] = ch[i] - '0';
21     for (int i = 0; i < len; ++i)
22     {
23         if (a[i]%4 == 0) ans += 1;
24         if (i != 0)
25         {
26             if ((a[i-1]*10+a[i])%4 == 0)
27                 ans += i;
28         }
29     }
30     printf("%I64d
", ans);
31 
32     return 0;
33 }
View Code

 26.Bear and String Distance

//简单的题目

 1 #include <iostream>
 2 #include <string>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdio>
 6 #include <cstdlib>
 7 
 8 using namespace std;
 9 
10 char ch[100010];
11 
12 int main()
13 {
14     int n, k;
15     scanf("%d%d", &n, &k);
16     scanf("%s", ch);
17     int mx = 0;
18     int len = strlen(ch);
19     for (int i = 0; i < len; ++i)
20         mx += max(ch[i]-'a', 'z'-ch[i]);
21     if (mx < k) printf("-1
");
22     else
23     {
24         for (int i = 0; i < len; ++i)
25         {
26             if (k >= max(ch[i]-'a', 'z'-ch[i]))
27             {
28                 k -= max(ch[i]-'a', 'z'-ch[i]);
29                 if (ch[i]-'a' > 'z'-ch[i]) ch[i] = 'a';
30                 else ch[i] = 'z';
31             }
32             else
33             {
34                 if (ch[i]-k >= 'a') ch[i] -= k;
35                 else ch[i] += k;
36                 break;
37             }
38         }
39         printf("%s", ch);
40     }
41 
42     return 0;
43 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/JustForCS/p/5000916.html