Leetcode 题目整理-1

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.

注：给出一个整数向量，和一个目标值，找出向量中加和等于目标值的那两个数所在的位置。（假如只有一组解）（位置索引是从0开始）

直接的想法：做两层循环，提交后失败，说明两层循环的耗时太长

参考代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    map<int, int> Hash;
        for (int i = 0; i < nums.size(); i++) {
            Hash[nums[i]] = i;
        }
        // 依次枚举第一个加数
        vector<int> ans(2);
        for (int i = 0; i < nums.size(); i++) {
            // 当存在对应的加数，而且这个加数不是自己时——找到了一组解
            if (Hash.find(target - nums[i]) != Hash.end() && Hash[target - nums[i]] != i) {
                ans[0] = i;//ans[0] = i + 1;
                ans[1] = Hash[target - nums[i]] ;//ans[1] = Hash[target - nums[i]] + 1;
                // 第一组解一定是满足ans[0] < ans[1]的
                break;
            }
        }
        // 返回答案
        return ans;
        
    }
};

参考代码中使用了map 构造所谓的hash表（一种根据key查找value 的表格，通常用来做数据压缩，可以提供快速查找），在c++ reference 中查了一下，map.find ()的复杂度是log(n)，再乘上外层的循环是 n*log(n)，（两层循环应该是n^2），所以参考代码可以通过leetcode的时间检验。

6. 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)

P A H N

A P L S I I G

Y I R

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".

注：把一串字母按照"z"形排列，现在要按行读出来。（不懂）

查了一下是这个样子：text="PAYPALISHIRING" , nRows=4 时

P I N

A L S I G

Y A H R

P I

结果是 "PINALSIGYAHRPI".

要弄清楚规律，按列存储一个字符串，然后按行读出来

发现自己不会使用动态数组，所以改为分组向量的方法存储数据，然后分情况进行读取，代码过程中由于粗心大意有很多特殊情况没有考虑到，比如，输入数据小于size_group时；numRows==1时，这些都是提交过程中发现的问题，现在看来这个平台还是不错的，可以帮忙检测码代码过程中的一些不好的习惯和一些容易漏掉的极端情况。

class Solution {
public:
    string convert(string s, int numRows) {
    string new_s;
    if (numRows == 1)
    {
        new_s = s;
        return new_s;
    }
    int size_group = 2 * numRows - 2;
    vector<vector<char>> array_group;
    vector<char> array_group_i;
    for (string::iterator idx_string = s.begin(); idx_string != s.end(); idx_string++)
    {
        array_group_i.push_back(*idx_string);
        if (array_group_i.size() == size_group)
        {
            array_group.push_back(array_group_i);
            array_group_i.clear();
        }    
    }
    if (array_group_i.size() != 0)
    {
        array_group.push_back(array_group_i);//如果这里没有判断则会多出一组空数据导致后面读取未赋值的向量元素
    }
    //the fist line
        for (vector<vector<char>>::iterator idx_group = array_group.begin(); idx_group != array_group.end(); idx_group++)
        {
            new_s.push_back((*idx_group).at(0));
        }
        //except the last line
        for (int i = 1; i < numRows - 1; i++)
        {
            for (vector<vector<char>>::iterator idx_group = array_group.begin(); idx_group != array_group.end(); idx_group++)
            {
                if ((*idx_group).size()>i)
                {
                    new_s.push_back((*idx_group).at(i));
                    if ((*idx_group).size() > (size_group - i ))
                    {        
                        new_s.push_back((*idx_group).at(size_group - i));
                    }
            
                }

            }
        }
        //the last line
        for (vector<vector<char>>::iterator idx_group = array_group.begin(); idx_group != array_group.end(); idx_group++)
        {
            if ((*idx_group).size()>(numRows - 1))
            {
                new_s.push_back((*idx_group).at(numRows - 1));

            }

        }
 
        return new_s;
    
    }
};