发表于   |   分类于

hadoop fs -ls /
列出hdfs文件系统根目录下的目录和文件
hadoop fs -ls -R /
列出hdfs文件系统所有的目录和文件

1

test if docker is alreay setup, $sudo docker info
配置一个hadoop环境，该环境中有一namenode（主机），两个datanode（子机）

2

$ mkdir bigdata-class2 # 创建一个目录
$ cd bigdata-class2 # 进入 文件夹
$ sudo docker pull joway/hadoop-cluster# 镜像文件 pull docker image ，接下来需要输入密码，需要管理员权限

这句话的意思是 docker pull
docker pull [-a “o”>] [user/ “o”>]name[:tag “o”>]
docker pull laozhu/telescope:latest
从 Docker Hub 中拉取或者更新指定镜像。
-a 拉取所有 tagged 镜像 。

There is no sudo command in Windows. The nearest equivalent is “run as # # administrator.” http://stackoverflow.com/questions/9652720/how-to-run-sudo-command-in-windows .

$ git clone https://github.com/joway/hadoop-cluster-docker # 把 github repository 复制到本地
$ ls # 检测 本地有一个hadoop cluster docker 的文件夹

$ sudo docker network create –driver=bridge hadoop # 创建 hadoop network
$ cd hadoop-cluster-docker # 进入到 hadoop-cluster-docker 文件夹
$ sudo ./start-container.sh # 运行， 如果你看到下面的类似的输出就恭喜你运行成功， 表示的意思是我们启动了1个name node叫做master, 2个data node 叫做 hadoop-slave，这段代码在每次使用Docker的时候必须运行

发表于   |   分类于

Index

1
2
3
4
Combinations // 可以sort也可以不sort
Combination Sum //sum类问题，因为有target == sum要求，dfs之前最好sort一遍，这样更大的元素就不用考虑，方便剪枝
Permutations
Permutations II

Combination

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

利用back tracking枚举可能情况，边界条件为path.size() == k，满足条件就把path vector放到result vector中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> path;
        
        if(n <= 0){
            return result;
        }
        trackback(result, path, n, k, 1);
        
        return result;
    }
    
    void trackback(vector<vector<int>>& result, vector<int> path, int n, int k, int level){
        
        if(path.size() == k){
            result.push_back(path);
            return;
        }
        
        if(path.size() > k){
            return;
        }
        
        for(int i = level; i <= n; i++){
            path.push_back(i);
            trackback(result, path, n, k, i + 1); //此处为i + 1，因为不涉及到返回处理，可以不用判定是否访问过，设置为i + 1即可
            path.pop_back();
        }
    }
};

Combination Sum

边界条件为 target == 0，每次路径更新target -= nums[i]，
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ret;
        
        if(candidates.size() == 0 || target < 0){
            return ret;
        }
        vector<int> curr;
        
        backtracking(ret, curr, candidates, target, 0);
        return ret;
    }
    
    void backtracking(vector<vector<int>>& ret, vector<int> curr, vector<int> candidates, int target, int level)
    {
        if(target == 0){
            ret.push_back(curr);
            return;
        }
        else if(target < 0){
            return;
        }
        
        for(int i = level; i < candidates.size(); ++i){
            target -= candidates[i];
            curr.push_back(candidates[i]);
            backtracking(ret, curr, candidates, target, i); //此处为i，只枚举i后面的数，防止有重复元素；
            curr.pop_back();
            target += candidates[i]; //释放targe值
        }
    }
};

Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

可以用同样的模版，但是permutation一定要有判定是否访问过了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> path;
        vector<vector<int>> result;
        bool visit[nums.size()] = {false};
        
        dfs(result, path, nums, visit);
        return result;
    }
    
    void dfs(vector<vector<int>>& result, vector<int> path, vector<int> nums, bool visit[])
    {
        if(path.size() == nums.size()){
            result.push_back(path);
            return;
        }
        
        for(int i = 0; i < nums.size(); i++){
            if(visit[i] == false){
                visit[i] = true;
                path.push_back(nums[i]);
                dfs(result, path, nums, visit);  //循环，但是访问过的元素不放入数组中
                visit[i] = false; // 释放判定
                path.pop_back();
            }
        }
    }
};

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
于上一题一样，除了是否访问过的判定，还要加上是否重复的判定 visit[i - 1] == false && i != 0 && nums[i] == nums[i - 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    
    vector<vector<int>> permuteUnique(vector<int>& num) {
        vector<vector<int>> result;
        if(num.size() == 0){
            return result;
        }
        vector<int> path;
        vector<bool> visited(num.size(), false);
        
        sort(num.begin(), num.end());
        dfs(result, path, num, visited);
        return result;
    }
    
    void dfs(vector<vector<int>>& result, vector<int> path, vector<int> num, vector<bool> visited)
    {
        if(path.size() == num.size()){
            result.push_back(path);
            return;
        }
        
        for(int i = 0; i < num.size(); i++){
            if(visited[i] == false){
                if(i != 0 && visited[i - 1] == false && num[i] == num[i - 1]){ //判定一定要考虑[i - 1]项，i != 0 在前
                    continue;
                }
                visited[i] = true;
                path.push_back(num[i]);
                dfs(result, path, num, visited);
                visited[i] = false;
                path.pop_back();
            }
        }
            
    }
};

发表于   |   分类于

Index

1
2
3
Best Time to Buy and Sell Stock
Best Time to Buy and Sell Stock II
Longest Increasing Subsequence

http://www.cnblogs.com/wuyuegb2312/p/3281264.html

1. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

假设 f[i] 为到第 i 天为止可以拿到的最大利润。对于第 i 天，有两种选择，即在当天卖掉股票，或者在第 i 天之前已经卖掉了。那么 f[i] 就是这两种选择中的最大值。如果在第 i 天卖掉股票，那么问题就是在哪天买股票，只要维护一个到第 i 天为止股价的最小值 minPrice 就可以了，此时 f[i] = prices[i] - minPrice ；如果在第 i 天股票已经卖出，则 f[i] = f[i-1] (类似于背包问题，两种选择，卖还是不卖)。综上所述，令 f[i] 表示到第 i 天为止可以拿到的最大利润。状态转移方程为 f[i] = max(f[i-1], prices[i] - minPrice) ，其中 minPrice 表示到第 i 天为止的最低股价，并且有 minPrice = min(minPrice, prices[i]) 。边界条件为 f[0] = 0, minPrice = prices[0] 。最终结果为 f[n-1] 。时间复杂度与空间复杂度均为 O(n) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() <= 1){
            return 0;
        }
        
        int minP = prices[0];
        int profit = prices[1] - prices[0];
        
        for(int i = 2; i < prices.size(); i++){
            minP = min(prices[i - 1], minP);
            profit = max(profit, prices[i] - minP);
        }
        
        if(profit < 0){
            return 0;
        }
        
        return profit;
    }
};

2. Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

由于可以无限次买卖，上次的状态模型显然不能用了。考虑第 i 天的行为可以是买入、卖出，或什么都不做。如果要买入，显然至少在第 i-1 天的时候手中是没有持有股票的，而如果要卖出，则至少在第 i-1 天的时候手中必须持有股票，如果什么都不做，则没有限制。根据这样的分析，我们可以知道为了计算第 i 天的情况，我们（只）需要第 i-1 天时持有和未持有股票的情况。据此可以抽象出状态。令 hold[i] 表示第 i 天时持有股票可以获得的最大利润， free[i] 表示第 i 天时未持有股票能获得的最大利润。第 i 天持有股票有两种情况，即第 i-1 天就已经持有，或在第 i 天买入。即 hold[i] = max(hold[i-1], free[i-1] - prices[i]) 。同理第 i 天未持有股票也有对应两种情况，即第 i-1 天未持有，或第 i 天卖出。即 free[i] = max(free[i-1], hold[i-1] + prices[i]) 。初始条件为 hold[0] = -prices[0], free[0] = 0 。最终结果为 free[n-1] 。时间复杂度和空间复杂度均为 O(n) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //本题也可以做是最大m 子段和
        int sum = 0;
        for(int i = 1; i < prices.size(); i++){
            int diff = prices[i] - prices[i - 1];
            if(diff > 0){
                sum += diff;
            }
        }
        return sum;
    }
};

3. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?
最长单调递增自序列，有nlog(n)算法，思考过程类似于背包问题，此题中背包不必装满，但是比i(背包容量)小的数j(宝石)，判断max(dp[j]+1, dp[i])，dp[]为子序列个数，相当于背包问题中宝石价值。但是背包问题中，背包捡起一次宝石，背包容量会减小，所以在状态转移方程为max(dp[i - vj(重量)] + 价值，dp[i])，而这个问题不存在背包容量问题，只需要判断j比i小就行了。除此之外还要排出i左边的坑，比如nums[10, 9, 2, 5, 3, 7, 101, 18]中nums[4] = 7，比7小的有[2, 5, 3]，但是子序列要把3这个坑去掉，所以才用max(dp[j] + 1)，解释一下比如i取7的位置，j取3的位置，此时dp[i] = 2，因为有2和5，但是dp[j] ＝ 1，只有2比3小，这时候就跳过3这个数。因为dp[i]是i左边小于nums[i]，并且递增的总和，如果前面有个坑，这个总数会比坑左面的数值小。因此取max(dp[j] + 1)。这个方法经常用，要记住。一般复杂度为O(n^2)。

再说nlog(n)解法，考虑两个数a[x]和a[y]，x<y且a[x]<a[y],且dp[x]=dp[y]，当a[t]要选择时，到底取哪一个构成最优的呢？显然选取a[x]更有潜力，因为可能存在a[x]<a[z]<a[y]，这样a[t]可以获得更优的值。在这里给我们一个启示，当dp[t]一样时，尽量选择更小的a[x].按dp[t]=k来分类，只需保留dp[t]=k的所有a[t]中的最小值，设d[k]记录这个值，d[k]=min{a[t],dp[t]=k}。
这时注意到d的两个特点（重要）：

  1. d[k]在计算过程中单调不升；
  2. d数组是有序的，d[1]<d[2]<..d[n]。
    利用这两个性质，可以很方便的求解：
  3. 设当前已求出的最长上升子序列的长度为len（初始时为1），每次读入一个新元素x：
  4. 若x>d[len]，则直接加入到d的末尾，且len++；（利用性质2）
    否则，在d中二分查找，找到第一个比x小的数d[k]，并d[k+1]=x，在这里x<=d[k+1]一定成立（性质1,2）。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    O(n^2)
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int n=nums.size();
            if(!n) return 0;
            int result=1;
            vector<int> dp(n,1);
            
            for(int i=1;i<n;i++){
                int temp=0;
                for(int j=0;j<i;j++){
                    if(nums[j]<nums[i]) temp=max(temp,dp[j]);
                }
                dp[i]=temp+1;
                result=max(dp[i],result);
            }
            return result;
        }
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// C++ implementation to find longest increasing subsequence
// in O(n Log n) time.
#include <bits/stdc++.h>
using namespace std;
 
// Binary search
int GetCeilIndex(int arr[], vector<int> &T, int l, int r,
                 int key)
{
    while (r - l > 1)
    {
        int m = l + (r - l)/2;
        if (arr[T[m]] >= key)
            r = m;
        else
            l = m;
    }
 
    return r;
}
 
int LongestIncreasingSubsequence(int arr[], int n)
{
    // Add boundary case, when array n is zero
    // Depend on smart pointers
 
    vector<int> tailIndices(n, 0); // Initialized with 0 
    vector<int> prevIndices(n, -1); // initialized with -1
 
    int len = 1; // it will always point to empty location
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < arr[tailIndices[0]])
        {
            // new smallest value
            tailIndices[0] = i;
        }
        else if (arr[i] > arr[tailIndices[len-1]])
        {
            // arr[i] wants to extend largest subsequence
            prevIndices[i] = tailIndices[len-1];
            tailIndices[len++] = i;
        }
        else
        {
            // arr[i] wants to be a potential condidate of
            // future subsequence
            // It will replace ceil value in tailIndices
            int pos = GetCeilIndex(arr, tailIndices, -1,
                                   len-1, arr[i]);
 
            prevIndices[i] = tailIndices[pos-1];
            tailIndices[pos] = i;
        }
    }
 
    cout << "LIS of given input" << endl;
    for (int i = tailIndices[len-1]; i >= 0; i = prevIndices[i])
        cout << arr[i] << " ";
    cout << endl;
 
    return len;
}
 
int main()
{
    int arr[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };
    int n = sizeof(arr)/sizeof(arr[0]);
 
    printf("LIS size %d\n", LongestIncreasingSubsequence(arr, n));
 
    return 0;
}

发表于   |   分类于

Index

1
2
3
4
5
计算器
旋转字符串(rotate string) // 来自[July](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/01.01.md)
字符串转换成整数
palindrome
最长回文

Notes

  1. string类里面可以用append(), push_back(), += 来追加字符，push_back()参数为char, length增加1; append和 +=可以增加string和char.
  2. 可以用to_string()转换numerical类型到string类型, return是一个representation而不是copy，反过来可以用atoi，但是只return一个value.
  3. string转换相应数字可以用”number” - “0”，利用ASCII码转化.

1. 实现一个计算器

Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.

Some examples:
“3+2*2” = 7
“ 3/2 “ = 1
“ 3+5 / 2 “ = 5
Note: Do not use the eval built-in library function.

思路：这题有乘除，那么就牵扯到了运算优先级的问题，但是这题没有括号，估计再出一道的话就该加上括号了(记得再写一道带括号的)。不管那么多，这道题先按木有有括号来处理，由于存在运算优先级，我们采取的措施是使用一个栈保存数字，如果该数字之前的符号是加或减，那么把当前数字压入栈中，注意如果是减号，则加入当前数字的相反数，因为减法相当于加上一个相反数。如果之前的符号是乘或除，那么从栈顶取出一个数字和当前数字进行乘或除的运算，再把结果压入栈中，那么完成一遍遍历后，所有的乘或除都运算完了，再把栈中所有的数字都加起来就是最终结果了。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int calculate(string s) {
        int res = 0, d = 0;
        char sign = '+';
        stack<int> nums;
        for(int i = 0; i < s.size(); ++i){
            if(s[i] >= '0'){               // 注意这个条件
                d = d * 10 + s[i] - '0';   //从左边读入数据, d为读入数据，如果数据为INT_MAX，则会溢出，要不要用long?
            }
            if((s[i] < '0' && s[i] != ' ') || i == s.size() - 1){
                if(sign == '+') nums.push(d);
                if(sign == '-') nums.push(-d);
                if(sign == '*' || sign == '/'){
                    int tmp = sign == '*' ? nums.top() * d : nums.top() / d;
                    nums.pop();
                    nums.push(tmp);
                } 
                sign = s[i];               //使得数据读取进行下去
                d = 0;
            }
        }
        while(!nums.empty()){
            res += nums.top();
            nums.pop();
        }
        return res;
    }
};

1. 旋转字符串

给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符’a’和’b’移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。

1. brute force

初看此题，可能最先想到的方法是按照题目所要求的，把需要移动的字符一个一个地移动到字符串的尾部，如此我们可以实现一个函数LeftShiftOne(char* s, int n) ，以完成移动一个字符到字符串尾部的功能，代码如下所示：
(思考，如果是反着旋转呢？)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void LeftShiftOne(char* s, int n)
{
    char temp = s[0];          //save the first element
    for(int i = 0; i < n; i++){
        s[i + 1] = s[i];
    }
    s[n - 1] = temp;
}
void LeftRotateString(char* s, int m)
{
    while(m--){
        LeftShiftOne(s, n);
   }
}

针对长度为n的字符串来说，假设需要移动m个字符到字符串的尾部，那么总共需要 mn 次操作，同时设立一个变量保存第一个字符，如此，时间复杂度为O(m n)，空间复杂度为O(1)，空间复杂度符合题目要求，但时间复杂度不符合，所以，我们得需要寻找其他更好的办法来降低时间复杂度。

2. 三步反转法

对于这个问题，换一个角度思考一下。
将一个字符串分成X和Y两个部分，在每部分字符串上定义反转操作，如X^T，即把X的所有字符反转（如，X=”abc”，那么X^T=”cba”），那么就得到下面的结论：(X^TY^T)^T=YX，显然就解决了字符串的反转问题。
例如，字符串 abcdef ，若要让def翻转到abc的前头，只要按照下述3个步骤操作即可：
首先将原字符串分为两个部分，即X:abc，Y:def；
将X反转，X->X^T，即得：abc->cba；将Y反转，Y->Y^T，即得：def->fed。
反转上述步骤得到的结果字符串X^TY^T，即反转字符串cbafed的两部分（cba和fed）给予反转，cbafed得到defabc，形式化表示为(X^TY^T)^T=YX，这就实现了整个反转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void ReverseString(char* s, int from, int to)
{
    while(from < to){
        char temp = s[from];
        s[from++] = s[to];
        s[to--] = t; 
        /*或者
        swap(s[from++], s[to--]); */
    }
}
void LeftRotateString(char* s, int n, int m)
{
    m %= n;  //左移大于n位，和%n是等价的
    ReverseString(s, 0, m - 1); //反转［0, m - 1］
    ReverseString(s, m, n - 1); //反转 [m, n - 1]
    ReverseString(s, 0, n - 1); //反转 [0, n - 1]
}

举一反三

1、链表翻转。给出一个链表和一个数k，比如，链表为1→2→3→4→5→6，k=2，则翻转后2→1→6→5→4→3，若k=3，翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→6→5，用程序实现。

2、编写程序，在原字符串中把字符串尾部的m个字符移动到字符串的头部，要求：长度为n的字符串操作时间复杂度为O(n)，空间复杂度为O(1)。 例如，原字符串为”Ilovebaofeng”，m=7，输出结果为：”baofengIlove”。

3、单词翻转。输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如，输入“I am a student.”，则输出“student. a am I”。

2. 字符串包含

给定两个分别由字母组成的字符串A和字符串B，字符串B的长度比字符串A短。请问，如何最快地判断字符串B中所有字母是否都在字符串A里？
为了简单起见，我们规定输入的字符串只包含大写英文字母，请实现函数bool StringContains(string &A, string &B)
比如，如果是下面两个字符串：
String 1：ABCD
String 2：BAD
答案是true，即String2里的字母在String1里也都有，或者说String2是String1的真子集。
如果是下面两个字符串：
String 1：ABCD
String 2：BCE
答案是false，因为字符串String2里的E字母不在字符串String1里。
同时，如果string1：ABCD，string 2：AA，同样返回true。

字符串转换整数 ‘string’ - ‘0’，因为’0’对应的ASCII为48，整数字符串减去48得到相应的整数。另外

大小写字母的转换：先看ASCII码：a~z是97~122的二进制，而A~Z是65~90的二进制编码，于是我们就得出：大写字母=小写字母-32 ；这个公式了。当然这里的32我也可以这么写‘Z’=‘z’-‘空格’。因为空格的ASCII码是32对应的二进制编码。

比如

字符串转换成整数

输入一个由数字组成的字符串，把它转换成整数并输出。例如：输入字符串”123”，输出整数123。给定函数原型int StrToInt(const char *str) ，实现字符串转换成整数的功能，不能使用库函数atoi。

1
2
3
4
5
6
7
8
9
10
11
int StrToInt(const char *str)
{
    int n = 0;
    while (*str != 0)
    {
        int c = *str - '0';
        n = n * 10 + c;
        ++str;
    }
    return n;
}

显然，上述代码忽略了以下细节：

空指针输入：输入的是指针，在访问空指针时程序会崩溃，因此在使用指针之前需要先判断指针是否为空。
正负符号：整数不仅包含数字，还有可能是以’+’或’-‘开头表示正负整数，因此如果第一个字符是’-‘号，则要把得到的整数转换成负整数。
非法字符：输入的字符串中可能含有不是数字的字符。因此，每当碰到这些非法的字符，程序应停止转换。
整型溢出：输入的数字是以字符串的形式输入，因此输入一个很长的字符串将可能导致溢出。

字符串转换成整数，完整的参考代码为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int StrToInt(const char* str)
{
    static const int MAX_INT = (int)((unsigned)~0 >> 1);
    static const int MIN_INT = -(int)((unsigned)~0 >> 1) - 1;
    unsigned int n = 0;
    //判断是否输入为空
    if (str == 0)
    {
        return 0;
    }
    //处理空格
    while (isspace(*str))
        ++str;
    //处理正负
    int sign = 1;
    if (*str == '+' || *str == '-')
    {
        if (*str == '-')
            sign = -1;
        ++str;
    }
    //确定是数字后才执行循环
    while (isdigit(*str))
    {
        //处理溢出
        int c = *str - '0';
        if (sign > 0 && (n > MAX_INT / 10 || (n == MAX_INT / 10 && c > MAX_INT % 10)))
        {
            n = MAX_INT;
            break;
        }
        else if (sign < 0 && (n >(unsigned)MIN_INT / 10 || (n == (unsigned)MIN_INT / 10 && c > (unsigned)MIN_INT % 10)))
        {
            n = MIN_INT;
            break;
        }
        //把之前得到的数字乘以10，再加上当前字符表示的数字。
        n = n * 10 + c;
        ++str;
    }
    return sign > 0 ? n : -n;

举一反三

实现string到double的转换
分析：此题虽然类似于atoi函数，但毕竟double为64位，而且支持小数，因而边界条件更加严格，写代码时需要更加注意。

回文判断

题目描述
回文，英文palindrome，指一个顺着读和反过来读都一样的字符串，比如madam、我爱我，这样的短句在智力性、趣味性和艺术性上都颇有特色，中国历史上还有很多有趣的回文诗。
那么，我们的第一个问题就是：判断一个字串是否是回文？
解法一
同时从字符串头尾开始向中间扫描字串，如果所有字符都一样，那么这个字串就是一个回文。采用这种方法的话，我们只需要维护头部和尾部两个扫描指针即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
bool IsPalindrome(const char *s, int n)
{
    // 非法输入
    if (s == NULL || n < 1)
    {
        return false;
    }
    const char* front,*back;
    // 初始化头指针和尾指针
    front = s;
    back = s+ n - 1;
    while (front < back)
    {
        if (*front != *back)
        {
            return false;
        }
        ++front;
        --back;
    }
    return true;
}
解法二
上述解法一从两头向中间扫描，那么是否还有其它办法呢？我们可以先从中间开始、然后向两边扩展查看字符是否相等。参考代码如下：
```bash
bool IsPalindrome2(const char *s, int n)
{
    if (s == NULL || n < 1)
    {
        return false;
    }
    const char* first, *second;
    // m定位到字符串的中间位置      
    int m = ((n >> 1) - 1) >= 0 ? (n >> 1) - 1 : 0; 
    first = s + m;
    second = s + n - 1 - m;
    while (first >= s)
    {
        if (*first!= *second)
        {
            return false;
        }
        --first;
        ++second;
    }
    return true;
}

最长回文

最容易想到的办法是枚举所有的子串，分别判断其是否为回文。这个思路初看起来是正确的，但却做了很多无用功，如果一个长的子串包含另一个短一些的子串，那么对子串的回文判断其实是不需要的。
解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int LongestPalindrome(const char *s, int n)
{
    int i, j, max,c;
    if (s == 0 || n < 1)
        return 0;
    max = 0;
    for (i = 0; i < n; ++i) { // i is the middle point of the palindrome  
        for (j = 0; (i - j >= 0) && (i + j < n); ++j){ // if the length of the palindrome is odd  
            if (s[i - j] != s[i + j])
                break;
            c = j * 2 + 1;
        }
        if (c > max)
            max = c;
        for (j = 0; (i - j >= 0) && (i + j + 1 < n); ++j){ // for the even case  
            if (s[i - j] != s[i + j + 1])
                break;
            c = j * 2 + 2;
        }
        if (c > max)
            max = c;
    }
    return max;
}

解法二 Manacher算法
首先通过在每个字符的两边都插入一个特殊的符号，将所有可能的奇数或偶数长度的回文子串都转换成了奇数长度。比如 abba 变成 #a#b#b#a#， aba变成 #a#b#a#。

此外，为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符，这样就不用特殊处理越界问题，比如$#a#b#a#。此外，为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符，这样就不用特殊处理越界问题，比如$#a#b#a#。
以字符串12212321为例，插入#和$这两个特殊符号，变成了 S[] = “$#1#2#2#1#2#3#2#1#”，然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左或向右扩张的长度（包括S[i]）。

比如S和P的对应关系：

S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
可以看出，P[i]-1正好是原字符串中最长回文串的总长度，为5。

接下来怎么计算P[i]呢？Manacher算法增加两个辅助变量id和mx，其中id表示最大回文子串中心的位置，mx则为id+P[id]，也就是最大回文子串的边界。得到一个很重要的结论：

如果mx > i，那么P[i] >= Min(P[2 * id - i], mx - i)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$".
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
string preProcess(string s) {
  int n = s.length();
  if (n == 0) return "^$";
  string ret = "^";
  for (int i = 0; i < n; i++)
    ret += "#" + s.substr(i, 1);
 
  ret += "#$";
  return ret;
}
 
string longestPalindrome(string s) {
  string T = preProcess(s);
  int n = T.length();
  int *P = new int[n];
  int C = 0, R = 0;
  for (int i = 1; i < n-1; i++) {
    int i_mirror = 2*C-i; // equals to i' = C - (i-C)
    
    P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
    
    // Attempt to expand palindrome centered at i
    while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
      P[i]++;
 
    // If palindrome centered at i expand past R,
    // adjust center based on expanded palindrome.
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }
 
  // Find the maximum element in P.
  int maxLen = 0;
  int centerIndex = 0;
  for (int i = 1; i < n-1; i++) {
    if (P[i] > maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }
  delete[] P;
  
  return s.substr((centerIndex - 1 - maxLen)/2, maxLen);
}

另外附上九章算法的binary search模版
// Comment
public class Solution {
/**

 * @param array source array
 * @param target target to search
 * @return the first occurrence position of target 
 */
public int binarySearch(int[] A, int target) {
    if (A.length == 0) {
        return -1;
    }

    int start = 0;
    int end = A.length - 1;
    int mid;

    while (start + 1 < end) {
        mid = start + (end - start) / 2;
        if (A[mid] == target) {
            end = mid;
        } else if (A[mid] < target) {
            start = mid;
        } else if (A[mid] > target) {
            end = mid;
        }
    }

    if (A[start] == target) {
        return start;
    }
    if (A[end] == target) {
        return end;
    }

    return -1;
}

}

Attention:
1) Why start + 1 < end?
There might be deadlock if use start < end, for example, if start = 1, end = 2, => mid = 1. Then, it will be a deadlock.(To solve this problem, mid + 1, for some problems)

  1. Related Problems

2.1 Search for Insertion Position
2.2 Search for a Range
2.3 Search in Rotated Sorted Array
写好不容易，有细节，算法性强，类似分糖果题。
用二分法的变种做，循环左移。

发表于   |   分类于

参考WalkingInTheWind的博客

Let’s Start //从最简单的开始

链表声明

1
2
3
4
5
struct ListNode
{
    int val;
    ListNode* next;
}

Index

1
2
3
4
5
6
7
8
9
10
11
求单链表中结点的个数
将单链表反转
查找单链表中的倒数第K个结点（k > 0）
查找单链表的中间结点
从尾到头打印单链表
已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序
判断一个单链表中是否有环
判断两个单链表是否相交
求两个单链表相交的第一个节点
已知一个单链表中存在环，求进入环中的第一个节点
给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted

1. 求单链表中结点的个数

遍历整个链表就好, O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int GetListLen(ListNode* head)
{
	int n = 0;
	if(head == NULL){
	    return 0;
    }
    ListNode* p = head;
    while(p != NULL){
    	p = p->next;
    	n++;
    }
    return n;
}

2. 将单链表反转

方法1
用3个指针实现反转，in-place，时间复杂度为O(n), 空间O(1)。
定义p, q, r指针，p = head, q = head->next, r = q->next;

  1. p指向null，旧链表的头为新链表的尾；
  2. q指向p(新链表的尾)
  3. p = q, q = r; 然后下一轮循环(r=q->next)，参考代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ListNode* ReverseList(ListNode* head)
{
	// remember always test if node is NULL;
	if(head == NULL || head->next == NULL){
	    return head;
    }
    ListNode* p = head;
    ListNode* q = head->next;
    head->next = NULL;
    while(q){
    	ListNode* r = q->next; //当前节点的下一届点；
    	q->next = p; //当前节点指向头(新链表的尾)
    	p = q; // p向前移动一位，到当前节点
    	q = r; // q想前移动一位，在一下循环处理下一个节点；
    }
    head = p; //循环结束，p == NULL, p指向head，实现反转
    return head;
}

方法2
从图上观察，方法是：对于一条链表，从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，(N-1)次这样的操作结束之后将第1个节点挪到新表的表尾即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ListNode* ReverseList(ListNode* head)
{
	// remember always test if node is NULL;
	if(head == NULL || head->next == NULL){
	    return head;
    }
    ListNode* p;
    ListNode* q;
    p = head->next
    while(p->next != NULL){
    	q = p->next;
    	p->next = q->next;
    	q->next = head->next;
    	head->next = p;
    }
    
    p->next = head; //like a loop
    head = p->next->next; // new head is old head->next
    p->next->next = NULL; // break the loop
    return head
}

3. 查找单链表中的倒数第K个结点（k > 0）

最普遍的方法是，先统计单链表中结点的个数，然后再找到第（n-k）个结点。注意链表为空，k为0，k为1，k大于链表中节点个数时的情况。时间复杂度为O（n）。也可以用双指针法，一个runner，一个chaser

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ListNode* getkthNode(ListNode* head)
{
	// remember always test if node is NULL;
	if(head == NULL || k == 0){
	    return NULL;
    }
    ListNode* runner = head;
    ListNode* chaser = head;
    
    while(k > 1 && runner != NULL){
    	runner = runner->next;
    	k--;
    }
    
    if(k > 1 || head == NULL){ //判断节点树是否小于k，我觉着有点多余啊；
    	return NULL;
    }
    while(head->next != NULL){
    	chaser = chaser->next;
    	runner = runner->next;
    }
    return chaser;
}

4. 查找单链表的中间结点

依然用双指针法，代码略。

5. 从尾到头打印单链表

用栈来实现，先进后出。要么自己维护栈，要么用递归，注意链表为空的情况，还有base case. 复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> printList(ListNode* head)
{
	vector<int> result;
	stack<ListNode*> s;
	ListNode* node = head;
	while(node != NULL){
	    s.push(node);
	    node = node->next;
    }
    
    while(!s.empty()){
        node = s.top();
        result.push_back(node->val);
        s.pop();
    }
    return result;
}

6. 已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序

类似于merge sort，用Divide conque，注意两个链表为空，或一个为空的情况。O(max(len1, len2))

7. 判断一个单链表中是否有环

用双指针法，如果相遇则有环，否则无环。如果要找出环的开始点，则相遇后把chaser放回head，两个指针每次走一步，相遇节点为loop起始点。
代码略。

8. 如果要遍历链表，可以考虑在head前加一个dummy node，并且检查边界条件防治数组越界(切记，出现好多次了;( )

比如swap nodes这一题，可以swap(p->val, p->next->val)，注意数组不要越界，也可以考虑在head前面加dummy node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == NULL){
            return head;
        }
        
        ListNode dummy(0);
        ListNode* p = &dummy; //指针指向dummy节点；
        dummy.next = head; //链接dummy和head节点
        
        while(p && p->next && p->next->next){
            ListNode* swap1 = p->next;
            ListNode* swap2 = p->next->next;
            p->next = swap2;
            swap1->next = swap2->next;
            swap2->next = swap1;
            p = p->next->next;
        }
        return dummy.next;
    }
};

注意：一个重复周期内涉及的链表先保存下一个变量，不然->next会timeout limit。并且设定初始条件链表元素数目是(head == NULL)还是(head == NULL || head->next == NULL)。

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

发表于

Wei’s first blog on github

To record the summary on Leetcode

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment