之前看过一点《C++数据结构与算法》所以就用的这本书复习准备找工作的，上周看了一下这本书出到第四版了，于是京东买了一本花了一周的时候复习了一下。基本上第四版和第三版差别还是有一点，数据结构讲的更细致也有了取舍，这一点我很喜欢。但是每一章后面莫名其妙的加入了一个针对一个问题的具体算法实现就比较蛋疼了，全是代码莫名奇妙，而且后面把算法里面的很多东西删掉了，回溯、贪心、动态规划和分治都没有好好讲，这一点还不如第3版。

完了之后，稍微有一点level up的感觉，以前遇到的很多算法都有了思路，于是刷了一下leetcode，基本上真正的要accept一道题比了解一道题的思路要划分n倍的时间，所以我基本上只看题然后看思路题解。遇到不会的或者手痒想试一试的才会去码。今天动手码的有2道题，还是放出来留个参考：

Leetcode问题1：Two Sum
这道题看似简单，leetcode上的accept率却不是很高，这道题最简单直观的就是遍历变量一个个的尝试O(N^2)的复杂度，我这么写了就导致超时了；于是想办法改进，思路就是对nums进行排序O(NlogN)，然后在排好序的基础上查找一个数就是logN的复杂度，遍历一遍就是NlogN的复杂度，也就是说总体上把复杂度降到了NlogN了。用stl的二分查找的时候发现binary_search居然只返回bool不返回iterator，这个接口的设计我真是看不懂……
[code]
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> nums2 = nums;
sort(nums2.begin(), nums2.end());
vector<int>res;

for (auto i = nums2.begin(); i<nums2.end(); i++)
{
//在i+1到nums.size()之间，二分查找出target-nums2[i]即可
bool found = binary_search(i + 1, nums2.end(), target – *i);
if (found)
{
int tmp1 = *i;
int tmp2 = target – *i;
int res1 = 0, res2 = 0;
bool f1 = false, f2 = false;
for (int k = 0; k<nums.size(); k++)
{
if (nums[k] == tmp1 && f1 == false)
{

res1 = k + 1;
f1 = true;
if (f1&&f2)
break;
}
else if (nums[k] == tmp2 &&f2 == false)
{
res2 = k + 1;
f2 = true;
if (f1&&f2)
break;
}
}

if (res1>res2)swap(res1, res2);
res.push_back(res1);
res.push_back(res2);

break;
}
}

return res;
}
[/code]

另外就是leetcode问题37：Sudoku Solver
很普遍的用回溯解数独的问题，本身算法思想很容易理解，但是我很想实现一下这个问题，因为觉得很有趣。我用的VS2013的ide，debug起来超方便的，知乎上一堆人表示刷leetcode不要用ide，还列出一堆我看不懂的理由，真是厉害……
不说了上代码（debug的时候需要测试用例，所以一并附上）：
[code]
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
vector<char> sentaku(vector<vector<char>>& board, int x, int y)
{
char c[9] = { ‘?’, ‘?’, ‘?’, ‘?’, ‘?’, ‘?’, ‘?’, ‘?’, ‘?’};
for (int i = 0; i < 9; i++)//横
if (board[y][i] != ‘.’)
c[board[y][i] – ‘1’] = ‘!’;;
for (int j = 0; j < 9; j++)//竖
if (board[j][x] != ‘.’)
c[board[j][x] – ‘1’] = ‘!’;;
//小块
int xx = x – x % 3, yy = y – y % 3;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
{
if (board[yy+j][xx+i] != ‘.’)
c[board[yy + j][xx + i]-‘1’] = ‘!’;
}

vector<char> res;
char k = ‘1’;
for (int i = 0; i < 9; i++, k++)
{
if (c[i] == ‘?’)
res.push_back(k);
}
return res;
}

bool tsugi(vector<vector<char>>& board, int &x, int& y)
{
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
{
if (board[j][i]== ‘.’)
{
x = i;
y = j;
return true;
}
}
return false;
}

bool track_back(vector<vector<char>>& board, int x, int y) {
vector<char> sen = sentaku(board, x, y);

for (int i = 0; i < sen.size(); i++)
{
board[y][x] = sen[i];

int x2, y2;
bool tsu = tsugi(board, x2, y2);
if (tsu == false)//全部填完，sen的size为1
return true;

if (track_back(board, x2, y2) == true)
return true;
}
board[y][x] = ‘.’;
return false;
}

void solveSudoku(vector<vector<char>>& board) {
int x, y;
tsugi(board, x, y);
bool res = track_back(board, x, y);
//cout << res;
}
};

int main()
{
Solution so;
vector<vector<char>>board;

char ii[9][10] = { "..9748…", "7……..", ".2.1.9…", "..7…24.", ".64.1.59.", ".98…3..", "…8.3.2.", "……..6", "…2759.." };
for (int i = 0; i < 9; i++)
{
vector<char> tmp;
for (int j = 0; j < 9; j++)

tmp.push_back(ii[i][j]);

board.push_back(tmp);
}

so.solveSudoku(board);
// cout << (const char*)str1;

return 0;
}
[/code]

嘛……今天就到这里，这停工1个多月就有点吃不起饭了，明天开始继续码活儿吧。