leetcode1 with Vecotr and Map

In order to practise the c++ coding ability and have a prepare for the
work interview for the future.I start to do the leetcode in the
leisure time.Before that I introduce a code comparing tools: Beyond
Compare

Beyond Compare

Home Page
It is a tool for folder and file comparing, which useful for coding
compare as well. For now, it provides all the OS version including
WINDOWS, LINUX and MAC.

LeetCode1 Two Sum

Ques: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].

Solution1: Sort and Search

先排序，从开头和结尾向中间找，复杂度O(nlogn)

// 定义Node来重新装数据
typedef struct Node{
    int id,val;
}Node;
// 定义Node比较大小的原则，让sort从小到大排序
bool compare(const Node & a,const Node & b){
    return a.val < b.val;
}

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // 初始化Nodes列表
        Node nodes[numbers.size()];
        for(unsigned int i=0; i<numbers.size(); i++){
            nodes[i].id = i+1;
            nodes[i].val = numbers[i];
        }
        // 排序后，有序地检索
        sort(nodes, nodes+numbers.size(), compare);
        int start=0,end=numbers.size()-1;
        vector<int> ans;
        // 从两端往中间去搜索
        while(start < end){
            // 找到后，按序输出
            if(nodes[start].val + nodes[end].val == target){
                if(nodes[start].id > nodes[end].id)
                    swap(nodes[start].id , nodes[end].id);
                ans.push_back(nodes[start].id);
                ans.push_back(nodes[end].id);
                return ans;
            // 过小:start++; 过大:end--
            }else if( nodes[start].val + nodes[end].val < target ){
                start++;
            }else
                end--;
        }
    }
};

Solution2: 利用map.find

将数存入hash_map中，查找target-numbers[i],有即返回。

vector<int> twoSum(vector<int> &numbers, int target){
    vector<int> res;
    int length = numbers.size();
    map<int,int> mp;
    int find;
    for(int i=0; i < length; ++i){
        find = mp[target-numbers[i]];
        // 默认没的时候，初始化map,直到新加数据找到以往符合的值
        if(find){
            res.push_back(find);
            res.push_back(i+1);
            break;
        }
        mp[numbers[i]] = i+1;
    }
    return res;
}

总体而言，第二种方法假定了只有一种结果，先判断找到没，再初始化map。这样可以确保找到的索引值是在前的，在新插的数据索引是在后的。十分的巧妙在一边在检索结果一边初始化map的数据。

参考链接: acm之家

c++ Vector用法

1.头文件 #include
2.变量声明 vector a; 二维数组： vector a2;
3.具体用法

a.push_back(int)     pop_back()    begin()  end()  max_size() size()
a.at(5) a[5]  if(a.empty())   clear()  a.insert(pos,elem)

4.自定义排序

bool comp(const int &a,const int&b)
{
    return a<b;
}
调用sort(vec.begin(),vec.end(),comp);

5.Vector使用分析
一般不够大小会自动resize扩大两倍的容量，所以如果装入1000个元素，会自动重新分配10次，2^10.但如果用reserve(1000)的话，可以有效避免重新分配的消耗。
另外可以用swap来有效利用vector剩余的空间等。

参考链接： vecotr用法详解

c++ map的用法

STL中一对一的数据结构，第一个成为关键字，只能出现一次，第二个是其值。Key-Value
其内建组织是一颗红黑树（非严格定义的平衡二叉树），可以对数据自动排序。
1.头文件 #include

Map<int,string> mapStudent;
Pair<map<int,string>::iterator,bool> Insert_Pair;
Insert_Pair = mapStudent.insert(pair<int,string>(1,"stu_1"));
if(Insert_Pair.second==true)
    cout<<"Insert Suceess!";

所以我们知道map.insert返回的属性是pair(iterator,bool)
5.size()，数据遍历

// 演示一下反向迭代器
map<int,string>::reverse_iterator iter;
for(iter=mapStudent.rbegin();iter!=mapStudent.rend();iter++)
  cout<<iter->first<<" "<<iter->second<<end;

6.数据查找
6.1 count判断关键字是否出现，是1，否0.
6.2 find,返回一个迭代器，没有则返回end函数迭代器
6.3
7.判空empty()和清空clear()
以及其他swap,key_comp,value_comp,get_allocator等函数
8.数据删除
map.erase(iter) map.erase(key)
map.erase(begin(),end()) //成片删除，前开后闭
9.如果key上用自己的结构体，需要重载小于号<,不然无法遍历iterator

参考链接: STL中map的用法详解

官方给出解法

AP 1

Brute Force 暴力破解,复杂度为 TC=O(N^2),SC=O(1)

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            //分别遍历，找是否存在该值
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

AP 2

利用Hash Table，遍历两次,复杂度 TC=O(N),SC=O(1)
将元素插入hash_map中，直接使用map.containsKey寻找映射值匹配

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        //利用hash_map的找，这是STL的优化
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

AP 3

用Hash Table进一步优化，一边插入一边求解，达到一次遍历

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    //边插入hash_map,边找是否存在该key
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}