Implement strStr()

description:

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

solve:

class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        unsigned int len_h = strlen(haystack);
        unsigned int len_n = strlen(needle);
        if(len_n == 0) {
            return haystack;
        }
        for(unsigned int i = 0; i < len_h; ++ i) {
            unsigned int t = i, j = 0;
            while(t < len_h && j < len_n) {
                if(i + len_n > len_h) break;
                //if(len_n)
                if(*(haystack + t) != *(needle + j) ||
                *(haystack + len_n + 2 * i - t - 1) != *(needle + len_n - j - 1)) {
                    break;
                }
                ++ t;
                ++ j;
            }
            if(j == len_n) {
                return haystack + i;
            }
        }
        return NULL;
    }

};

坑：
裸暴力不让过，加个小优化（头部和尾部同时对比）。为啥不用kmp？，因为忘光了。

Word Search

decription:

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

slove:
class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        bool got_it = false;
        vector<char> tp;
        int h = board.size();
        int w = board.at(0).size();
        bool* visit = new bool[h * w];
        for(int k = 0; k < w * h; ++ k) visit[k] = false;
        for(int i = 0; i < h; ++ i) {
            tp = board.at(i);
            for(int j = 0; j < tp.size(); ++ j) {
                if(tp.at(j) == word[0]) {
                    got_it = run(visit, board, i, j, word, 0);
                    if(got_it) {
                        return got_it;
                    } else {
                        for(int k = 0; k < w * h; ++ k) visit[k] = false;
                    }
                }
            }
        }
        return got_it;
    }
    bool run(bool visit[], const vector<vector<char> >& board, int i, int j, string word, int idx) {
        if(i >= board.size() || i < 0) {
            return false;
        }
        if(j >= board.at(i).size() || j < 0) {
            return false;
        }
        if(idx >= word.length()) {
            return false;
        }
        if(visit[i * board.at(0).size() + j] == true) {
            return false;
        }
        if(board.at(i).at(j) == word.at(idx)) {
            visit[i * board.at(0).size() + j] = true;
            if(idx == word.length() - 1) {
                return true;
            }
            return run(visit, board, i + 1, j, word, idx + 1) ||
                run(visit, board, i - 1, j, word, idx + 1) ||
                run(visit, board, i, j - 1, word, idx + 1) ||
                run(visit, board, i, j + 1, word, idx + 1);
        }
        return false;
    }

};

坑:
递归时保存访问信息的数组更新有问题

Subsets

description:

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

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

slove:

通过位标记来记录某个值是否参与到此次组合。

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int> > ret;
        std::sort(S.begin(), S.end());
        run(ret, S);
        return ret;
    }
    void run(vector<vector<int> >&ret, vector<int> str) {
        vector<int> res;
        ret.push_back(res);
        int len = str.size();
        for(int i = 1; i < (1<<len); ++ i) {
            for(int j = 0; j < len; ++ j) {
                if(i & (1 << j)) {
                    res.push_back(str.at(j));
                }
            }
            ret.push_back(res);
            res.clear();
        }
    }

};


坑：
输入向量不一定是有序的。

Path Sum II

description:

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

solve:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > res;
        vector<int> fk;
        //string tmp;
        //ostringstream ret;
        run(root, res, fk, 0, sum);

        return res;
    }
    void run(TreeNode* root, vector<vector<int> >& res, vector<int> ret, int total, int sum) {
        if(root == NULL) {
            return;
        }
        total += root->val;
        ret.push_back(root->val);
        if(root->right == NULL && root->left == NULL) {
            if(sum == total) {
                if(ret.size() > 0) {
                    res.push_back(ret);
                }
            }
            return;
        }
        //ret << root->val << ",";
        run(root->right, res, ret, total, sum);
        run(root->left, res, ret, total, sum);
    }
};

Sum Root to Leaf Numbers

[leetcode不能查看ac代码，开贴暂存]
description:

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

solve：

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int res = 0;
        run(root, 0, res);
        return res;
     
    }
    void run(TreeNode* root, int out, int& res) {
        if(root == NULL) {
            return;
        }
        out = out * 10 + root->val;
     
        if(root->right == NULL && root->left == NULL) {
            res += out;
        } else {
            run(root->right, out, res);
            run(root->left, out, res);
        }
    }   return v;
};