No.1
题目链接：ZigZag Conversion
- 题目描述：
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:string convert(string text, int nRows);
convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.
(1)思路：思路比较简单，就是根据行数申请相应个字符串数组，然后由行数头尾循环把输入的字符串字母添加给相应的字符串数组中，最后按顺序输出字符串数组中的元素即可。
(2)代码：
class Solution {
public:
string convert(string s, int numRows) {
int size = s.length();
if(size==0 || numRows<=1) return s;
string *str=new string[numRows];
int flag=1;
int row=0;
for(int i=0; i<size; i++){
str[row]+=s[i];
row = row+flag;
if(row >= numRows){
row = numRows-2;
flag = -1;
}
if (row < 0){
row = 1;
flag = 1;
}
}
string result;
for(int i=0; i<numRows; i++){
result += str[i];
}
return result;
}
};
No.2
题目链接：Substring with Concatenation of All Words
- 题目描述：
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
For example, given: s: “barfoothefoobarman”
words: [“foo”, “bar”]
You should return the indices: [0,9].
(order does not matter).
(1)思路：使用两个map来记录每个单词的预期次数和已经检测的次数。然后检查每一个可能的位置，一旦遇到一个不符合要求的情况的话，或者某个词的次数大于预期的次数，就停止检查。如果完成检查就将i送入 vector中。空间复杂度 为O(words.size()) 。时间复杂度取决于两个循环，为O(n * num)。
(2)代码：
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
map<string, int> count;
int num = words.size();
for (int i = 0; i < num; i++)
count[words[i]]++;
int n = s.length(), len = words[0].length();
vector<int> indexes;
for (int i = 0; i < n - num * len + 1; i++) {
map<string, int> seen;
int j = 0;
while (j < num) {
string word = s.substr(i + j * len, len);
if (count.find(word) != count.end()) {
seen[word]++;
if (seen[word] > count[word])
break;
}
else break;
j++;
}
if (j == num) indexes.push_back(i);
}
return indexes;
}
};
No.3
题目链接：Maximum Binary Tree
- 题目描述：
Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:
The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
Construct the maximum tree by the given array and output the root node of this tree.
Example 1:
Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:
Note:
The size of the given array will be in the range [1,1000].
<1>思路：循环数组每一个元素，首先申请当前数组元素的节点，然后和已进入树中的最后一个节点（后面称为记录节点）比较大小，如果小于树中记录的最后一个节点，就直接跟在当前树记录节点的右子树（保证每个子树小的在最下面）；否则，把记录节点设置为当前数字节点的左子节点，然后抛掉它并将父节点设置为记录节点，再和它的父节点比较大小，直到把当前这个数节点插入到正确位置。保证最大数二元树每个子树都符合要求，即最大的在最上面。这是一个时间复杂度为O(n)的做法。
<2>代码：
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
vector<TreeNode*> con;
for (int i = 0; i < nums.size(); i++) {
TreeNode* curr = new TreeNode(nums[i]);
while (!con.empty() && con.back()->val < nums[i]) {
curr->left = con.back();
con.pop_back();
}
if (!con.empty())
con.back()->right = curr;
con.push_back(curr);
}
return con.front();
}
};
