剑指offer

Link: [https://www.nowcoder.com/ta/coding-interviews]

1 - 10

第一题

看到题的直觉是用binary search。
先用暴力搜索–>15ms + 1484k–>O(nm)
对每一行预先判断首尾–>15ms + 1376k–>O(nm)
binary search–>12 + 1504k–>O(n*logm)
最后，发现矩阵整体是有序的，因此可以由左下开始直接判断,复杂度O(n+m)

PS: 设置的测试方案太过简单，直接暴力搜索也不是很慢。

附binary search代码：

bool Find(int target, vector<int> array) {
    int left = 0;
    int right = array.size() - 1;
    while (left <= right) {
        mid = left + (right - left) / 2;
        if (array[i][mid] == target){
            return true;
        }
        else if (array[i][mid] > target) {
            right = mid - 1;
        }
        else if (array[i][mid] < target) {
            left = mid + 1;
        }
    }
    return false;
}

第二题

本题较为简单，直接从后往前扫描插入即可。（如果用js/python直接用replace就好了）

第三题

本题较为简单，通过stack使得顺序改变即可。需要注意的是，这题head里面是存数据的。

第四题

由前中/中后序重构树。使用递归完成较为简单。
前中：1. 前序第一个一定是本节的根。2. 找到本节根在中序的位置。3. 计算左树点的数量。
中后：1. 后序最后一个一定是本节的根。2. 找到本节根在中序的位置。3. 计算左数点的数量。
附前中序代码：

TreeNode* R(vector<int> pre, vector<int> vin, int preStart, int preEnd, int vinStart, int vinEnd) {
    if (preStart >= preEnd || vinStart >= vinEnd) return NULL;
    // search the position in vin
    int vinPosition = -1;
    for (int i = vinStart; i < vinEnd; i++) {
    if (vin[i] == pre[preStart]) {
        vinPosition = i;
            break;
        }
    }
    int prePosition = preStart + vinPosition - vinStart;

    struct TreeNode* node = new struct TreeNode(pre[preStart]);
    node->left = R(pre, vin, preStart+1, prePosition+1, vinStart, vinPosition);
    node->right = R(pre, vin, prePosition+1, preEnd, vinPosition+1, vinEnd);
    return node;
}

第五题

此题较为简单。stack1储存，stack2给予，如果stack2为空时将stack1的点全部输入stack2即可。

第六题

旋转数组找最小成分。直观做法是线性扫描–>37ms.
稍加观察，发现出现先第一个小于首位的数即为最小–>32ms.

第七题

斐波那契数列。

第八题

斐波那契数列变种。$F(n) = F(n-1) + F(n-2)$

第九题

斐波那契数列变种。$F(n) = \sum_{k=1}^{n-1} F(k)+1$

第九题

斐波那契数列变种。$F(n) = F(n-1) + F(n-2)$

第十题

求二进制中1的个数。比较麻烦的是负数。有关负数补码，可以参考另一篇博客“原码，反码和补码”。
其实这道题还可以直接对bit操作，会简单很多。但是我觉得出题人的初衷是要考察对原反补码的理解。whatever。以下是相关代码。

int  NumberOf1(int n) {
    int tag = 1;
    int res = 0;
    for (int i = 0; i < 32; i++) {
        if (tag&n) {
            res ++;
        }
        tag = tag << 1;
    }

    return res;
}

11 - 20

第十一题

快速幂，增大base来减少相乘的次数。详细算法可以参考“大数相乘以及快速幂”。
其实直接用写好的pow即可快速通过。

第十二题

方法一：bubble sort。左偶数右奇数->交换。O(n^2).
方法二：新建vector。扫描奇数，扫描偶数。O(n)。

第十三题

方法一：遍历，得到list的大小，再次遍历，找到size-k。
方法二：使用stack，全部存下，然后pop k次。
方法三：使用queue，如果queue大于k，pop。
比较：我个人最喜欢方法三，只需要一次遍历并且存下k个node。属于折中的方法。

第十四题

最简单的方法是使用stack存下全部node，然后再根据stack的顺序新建node。然而需要遍历两遍，且需要新建一个list。
也可以直接操作list，需要记录前，中，后三点。

ListNode* ReverseList(ListNode* pHead) {
    ListNode* pre = NULL;
    ListNode* current = NULL;
    ListNode* post = NULL;
    
    current = pHead;
    while (current != NULL) {
        post = current->next;
        current->next = pre;
        pre = current;
        current = post;
    }
    
    return pre;
}

第十五题

较为简单，不做赘述。

第十六题

主要是对递归的理解。分为两个function。sub判断tree2是否为当前tree1的顶端。HasSubtree判断tree1是否包含tree2. 代码下。

bool sub(TreeNode* root1, TreeNode* root2) {
    if (root2 == NULL) {
        return true;
    }
    if (root1 == NULL) {
        return false;
    }
    if (root1->val == root2->val) {
        if (sub(root1->left, root2->left) && sub(root1->right, root2->right)) {
            return true;
        }
    }
    return false;
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
    if (pRoot1 == NULL || pRoot2 == NULL) return false;
    
    // case 1: same root
    if (sub(pRoot1, pRoot2)) return true;
    
    // case 2: left has sub tree
    if (pRoot1->left != NULL && HasSubtree(pRoot1->left, pRoot2)) return true;
    // case 3: right has sub tree
    if (pRoot1->right != NULL && HasSubtree(pRoot1->right, pRoot2)) return true;
    
    
    return false;
}

第十七题

较为简单，使用DFS遍历，然后交换左右子树。

void Mirror(TreeNode *pRoot) {
    // terminate condition
    if (pRoot == NULL) return;
    
    // DFS
    if (pRoot->left != NULL) Mirror(pRoot->left);
    if (pRoot->right != NULL) Mirror(pRoot->right);
    
    // swqp left and right
    TreeNode* tmp = pRoot->left;
    pRoot->left = pRoot->right;
    pRoot->right = tmp;
}

第十八题

比较麻烦的简单题。有四种不同状态，判断好边界就不是很难处理。

第十九题

题目要求要stack查找最小值时间复杂度为O(1)。很明显要储存一些数据来支持这个结构。那么我们需要储存什么呢？来看一下需求。要求最小值时间复杂度为1，且每次pop之后，重新寻找最小值也是O(1).设置一个一模一样的结构记录每一次pop后的最小值即可完成目标。
简单来说就是用两个stack，一个用来存放数据，一个用来存放最小值。当新的数值小于stack2.top时，我们将新的数值push到stack2中。

第二十题

本题比较有趣。如果判断某序列是否可以由stack pop出，可以根据“一旦pop，stack中剩余的元素相对order不可能改变”。
然而，本题如果用这种方式来判断，时间复杂度为O(n^2)。
我们可以模拟整个stack push pop的过程，如果最终stack为空，则该序列是合法的。

bool IsPopOrder(vector<int> pushV,vector<int> popV) {
    // simulate the situation
    stack<int> s;
    int popPos = 0;
    for (int i = 0; i < pushV.size(); i++) {
        s.push(pushV[i]);
        while (popPos < popV.size() && s.top() == popV[popPos]) {
            s.pop();
            popPos++;
        }
    }
    return s.empty();
}

21 - 30

第二十一题

BFS。使用queue来储存即可。同理，使用stack可以实现DFS。

vector<int> PrintFromTopToBottom(TreeNode* root) {
    // BFS
    vector<int> res;
    if (root == NULL) {
        return res;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        res.push_back(node->val);
        if (node->left != NULL) {
            q.push(node->left);
        }
        if (node->right != NULL) {
            q.push(node->right);
        }
    }
    return res;
}

第二十二题

递归问题。判断一个序列是否为合法的二叉搜索树后序排列，针对每一个root点，判断其前面序列是否可以分为左树和右树。

bool check(vector<int> sequence, int left, int right) {
    if (left >= right) return true;
    // sequence should be able to be splitted into 2 parts
    int pivot = sequence[right];
    bool isLeftPart = true;
    int mid = left;
    for (int i = left; i < right; i++) {
        if (isLeftPart) {
            if (sequence[i] > pivot) {
                isLeftPart = false; 
            }
            else {
                mid = i;
            }
        }
        else {
            if (sequence[i] < pivot) return false;
        }
    }
    return check(sequence, left, mid) && check(sequence, mid+1, right);
}
bool VerifySquenceOfBST(vector<int> sequence) {
    int size = sequence.size();
    if (size == 0) return false;
    return check(sequence, 0, size-1);
}

第二十三题

简单的DFS。但是如果用非递归方法，需要维持一些数据结构且要判断边界，很麻烦。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        if (root == NULL) return res;
        path.push_back(root->val);
        if (root->val == expectNumber && root->left == NULL && root->right == NULL) {
            res.push_back(path);
        }
        FindPath(root->left, expectNumber-root->val);
        FindPath(root->right, expectNumber-root->val);
        path.pop_back();
        return res;
    }
};

第二十四题

想破头的题。无论如何都找不到简单的方法，查看了人家的讲解，发现是在原本linked list上进行改动。感觉巧妙的同时也感慨自己的愚鲁。
此处附上偷来的讲解和自己的代码。

RandomListNode* Clone(RandomListNode* pHead)
{
    if (pHead == NULL) return NULL;
    RandomListNode* node = pHead;
    while (node != NULL) {
        // copy all the node alone path of next
        RandomListNode* newnode = new RandomListNode(node->label);
        RandomListNode* tmp = node->next;
        node->next = newnode;
        newnode->next = tmp;
        node = tmp;
    }
    node = pHead;
    while (node != NULL) {
        // copy all the node alone path of random
        RandomListNode* targetNode = node->random;
        if (targetNode != NULL) node->next->random = targetNode->next;
        node = node->next->next;
    }
    
    RandomListNode* newhead = pHead->next;
    RandomListNode* newnode = newhead;
    node = pHead;
    while (node != NULL) {
        // split the list
        node->next = newnode->next;
        if (newnode->next != NULL) newnode->next = newnode->next->next;
        node = node->next;
        newnode = newnode->next;
    }
    
    return newhead;
}

第二十五题

中序遍历即可。

class Solution {
public:
    TreeNode* pre = NULL;
    TreeNode* head = NULL;
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if (pRootOfTree == NULL) return NULL;
        Convert(pRootOfTree->left);
        if (pre == NULL) {
            pre = pRootOfTree;
            head = pRootOfTree;
        }
        else {
            pre->right = pRootOfTree;
            pRootOfTree->left = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree->right);
        return head;
    }
};

第二十六题

数组中大于一半的数。
方法一：储存一个数，如果不一样则相互抵消，如果一样则增加计数。最后验证该数次数是否超过一半。

int MoreThanHalfNum_Solution(vector<int> numbers) {
    int current = -1;
    int count = 0;
    for (int i = 0; i < numbers.size(); i++) {
        if (current == -1) {
            current = numbers[i];
            count ++;
        }
        else {
            if (current != numbers[i]) {
                count --;
            }
            else {
                count ++;
            }
            if (count == 0) {
                current = numbers[i];
                count ++;
            }
        }
    }
    count = 0;
    for (int i = 0; i < numbers.size(); i++) {
        if (numbers[i] == current) {
            count ++;
        }
    }
    if (count > numbers.size()/2) return current;
    else return 0;
}

方法二：排序，选取中间的数。但是此法为O(nlogn)。复杂度较高。附quicksort代码。

第二十七题
递归来做。

class Solution {
public:
    bool notFound(string& str) {
        for (int i = 0; i < rstr.size(); i++) {
            if (str == rstr[i]) return false;
        }
        return true;
    }
    void pen(string& str, int begin) {
        if (begin >= str.size()) {
            if (notFound(str)) rstr.push_back(str);
        }
        for (int i = begin; i < str.size(); i++) {
            swap(str, begin, i);
            pen(str, begin + 1);
            swap(str, begin, i);
        }
    }
    void swap(string& str, int i, int j) {
        char tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
    }
    vector<string> Permutation(string str) {
        if (str.size() == 0) return rstr;
        pen(str, 0);
        sort(rstr.begin(), rstr.end());
        return rstr;
    }
private:
    vector<string> rstr;
};

第二十八题

构建总数为K的最大heap。对每一个元素和heap比较，如果比堆顶小，则替换，重新排列heap。复杂度为O(nlogk)。
然而我用了暴力搜索，AC。大概是结果设置的太简单了。附k堆的代码。

第二十九题

很简单的动态规划题。

int FindGreatestSumOfSubArray(vector<int> array) {
    int greatestSumForPosition = array[0];
    int res = greatestSumForPosition;
    for (int i = 1; i < array.size(); i++) {
        greatestSumForPosition = max(greatestSumForPosition + array[i], array[i]);
        res = max(res, greatestSumForPosition);
    }
    return res;
}

第三十题

归纳法，按照每一位来计算。

int NumberOf1Between1AndN_Solution(int n)
{
    int tmp = 1;
    int count = 0;
    while (tmp <= n) {
        count += (n/(10*tmp)) * tmp;
        if (n%(10*tmp) < tmp) {
            count += 0;
        }
        else if (n%(10*tmp) < 2*tmp) {
            count += n%(10*tmp)-(tmp-1);
        }
        else {
            count += tmp;
        }
        tmp *= 10;
    }
    return count;
}

31 - 40

第三十一题

简单来说就是对数的排序。即从最高位到最低位的排序。我贴上两种做法。

struct gter {
     inline bool operator() (string a, string b) {
        int acount = 0;
        int bcount = 0;
        while (acount < a.size()-1 && bcount < b.size()-1) {
            if (a.at(acount) != b.at(bcount)) return a.at(acount) > b.at(bcount);
            else {
                if (acount < a.size()-1) acount ++;
                if (bcount < b.size()-1) bcount ++;
            }
        }
        return  a.at(acount) > b.at(bcount);
    }
};
class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        vector<string> strings;
        for (int i = 0; i < numbers.size(); i++) {
            string tmp = to_string(numbers[i]);
            strings.push_back(tmp);
        }
        // sort(strings.begin(), strings.end(), gter());
		sort(string.begin(), strings.end(), gt);
        string res;
        for (int i = strings.size() - 1; i >= 0; i--) {
            res.append(strings[i]);
        }
        return res;
    }
    static bool gt(string a, string b) {
        string c = a + b;
        string d = b + a;
        return c > d;
    }
};

第三十二题

丑数。很明显，后面的数要由前面数产生。那么如何产生呢？基本上这类题的做法都是维持一个数列，每一次push一个最小的候选人。难点在于确定候选人。
很明显，候选人=前人2或者前人3 或者前人5。前人可以是数组中任意的数，那么复杂度为O(n^2)。
然而，稍加思考，便可以得知，有很多都不必要验证。比如上一次选择的是23，那么对于前人*3这个选项，2就可以被剔除掉。因此，只需要维持三个pointer即可。

int GetUglyNumber_Solution(int index) {
    if (index == 0) return 0;
    vector<int> uglyNumber;
    int base = 1;
    uglyNumber.push_back(base);
    int ptr2=0, ptr3=0, ptr5=0;
    while (uglyNumber.size() < index) {
        // select the minimum of ptr2, 3, 5
        uglyNumber.push_back(min(min(uglyNumber[ptr2]*2, uglyNumber[ptr3]*3), uglyNumber[ptr5]*5));
        if (uglyNumber[ptr2]*2 == uglyNumber.back()) ptr2++;
        if (uglyNumber[ptr3]*3 == uglyNumber.back()) ptr3++;
        if (uglyNumber[ptr5]*5 == uglyNumber.back()) ptr5++;
    }
    return uglyNumber.back();
}

第三十三题

找只出现一次的数。很明显是线性时间。使用bucket sort 来储存出现的个数（使用map也可以，不过map的开销更大）。

第三十四题

很恐怖的一道题。算法还是比较简单的，用merge sort 的思想，在合并的时候从最后一个单位开始比较。一次比较可以增加size/2个逆序数组。
值得注意的是，在递归的时候一定要用引用！

class Solution {
public:
	long long cnt;
    vector<int> cp;
	int InversePairs(vector<int> data) {
		cnt = 0;
		// reverse(data.begin(), data.end());
		cp = data;
		mergeSort(data, 0, data.size());
		return cnt % 1000000007;
	}
	void mergeSort(vector<int>& data, int start, int end) {
		if (end - start <= 1) return;
		int mid = start + (end - start) / 2;
		mergeSort(data, start, mid);
		mergeSort(data, mid, end);
		int ptr1 = mid - 1;
		int ptr2 = end - 1;
		int ptr = end - 1;
		while (ptr1 >= start && ptr2 >= mid) {
			if (cp[ptr1] > cp[ptr2]) {
				data[ptr--] = cp[ptr1--];
				cnt += ptr2 - mid + 1;
			}
			else {
				data[ptr--] = cp[ptr2--];
			}
        }
		for (;ptr1 >= start;ptr1--) {
			data[ptr--] = cp[ptr1];
		}
		for(;ptr2 >= mid; ptr2--) {
			data[ptr--] = cp[ptr2];
		}
        for (int i = start; i < end; i++) {
            cp[i] = data[i];
        }
	}
};

第三十五题

本题比较简单。扫描得到长度，然后再扫描一次即可。

第三十六题

binary search。

第三十七题

两种做法，第一种递归。比较简单。第二种bfs，需要控制几个变量来记录第几层。

第三十八题

方法一：直接递归，每一次求子树高度。但是balance要便利一遍，每个点都要求一次深度，所以复杂度为O(n^2).
方法二：直接求深度，如果左右子树不符合要求，直接返回false即可。

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return height(pRoot) != -1;
    }
    int height(TreeNode* pRoot) {
        if (pRoot == NULL) return 0;
        int left = height(pRoot->left);
        if (left == -1) return -1;
        int right = height(pRoot->right);
        if (right == -1) return -1;
        return (abs(left-right)<=1) ? max(left, right) + 1 : -1;
    }
};

第三十九题

方法一，直接用map。bucket sort的思想。扫描两次即可。

void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
    map<int, int> mp;
    for (int i = 0; i < data.size(); i++) {
        mp[data[i]]++;
    }
    bool firstNum = true;
    for (int i = 0; i < data.size(); i++) {
        if (mp[data[i]] == 1) {
            if (firstNum) {
                *num1 = data[i];
                firstNum = false;
            }
            else {
                *num2 = data[i];
            }
        }
    }
}

方法二，利用xor，一定是奇数个数字的结果。同样是扫描两次，由于不用构建map，速度会快很多。

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int bitResult = 0;
        for (int i = 0; i < data.size(); i++) {
            bitResult ^= data[i];
        }
        // find the one position that is 1 in bitResult
        *num1 = 0;
        *num2 = 0;
        int index = findPos(bitResult);
        for (int i = 0; i < data.size(); i++) {
            if (isFirst(data[i], index)) {
                (*num1) ^= data[i];
            }
            else {
                (*num2) ^= data[i];
            }
        }

    }
    int findPos(int bitResult) {
        int index = 0;
        while ((bitResult & 1) == 0 && index < 32) {
            index ++;
            bitResult >>= 1;
        }
        return index;

    }
    bool isFirst(int bitResult, int index) {
        int num = bitResult >> index;
        return num&1;
    }
};

第四十题

比较简单，求中间数字，要注意边界。

vector<vector<int> > FindContinuousSequence(int sum) {
    vector<vector<int>> res;
    for (int i = 2; (sum/i) >= (i/2); i++) {
        int mid = sum / i;
        if (i%2==0 && ((sum%i)*2==i) && (sum/i)-(i/2) + 1 > 0) {
            vector<int> v;
            for (int j = (sum/i)-(i/2) + 1; j < (sum/i)+(i/2)+1; j++) {
                v.push_back(j);
            }
            res.push_back(v);
        }
        if (i%2==1 && ((sum%i)==0) && (sum/i)-(i/2)> 0) {
            vector<int> v;
            for (int j = (sum/i)-(i/2); j < (sum/i)+(i/2)+1; j++) {
                v.push_back(j);
            }
            res.push_back(v);
        }
    }
    reverse(res.begin(), res.end());
    return res;
}

41 - 50

第四十一题

维持两个指针，保证右端一定大于左端。从左到右扫描数组，对每一个数A，从右到左扫描数B。
线性时间。

vector<int> FindNumbersWithSum(vector<int> array,int sum) {
    vector<int> res;
    if (array.size() == 0) return res;
    int left = 0;
    int right = array.size() - 1;
    int tmp;
    for (left = 0; left < (right - left) / 2 + 1; left++) {
        tmp = sum - array[left];
        if (sum % array[left] == 0) {
            while (array[right] > tmp && right > left) {
                right --;
            }
            if (array[right] == tmp) break;
        }
    }

    if (left < array.size() && right >= 0) {
        if (array[left] + array[right] == sum) {
            res.push_back(array[left]);
            res.push_back(array[right]);
        }
    }
    return res;
}

第四十二题

简单的做法就是用辅助数组，然后线性扫描即可。
但是上述做法需要额外的空间，还有一种不需要空间的做法。YX = (XT YT)T
即对前后分别做反转，然后对全部做反转。需要扫描三次，但是不需要空间。

string LeftRotateString(string str, int n) {
    // YX = (XT YT)T
    int size = str.size();
    if (size == 0) return "";
    n = n % size;
    for (int i = 0, j = n - 1; i < j; i++, j--) swap(str[i], str[j]);
    for (int i = n, j = size - 1; i < j; i++, j--) swap(str[i], str[j]);
    for (int i = 0, j = size - 1; i < j; i++, j--) swap(str[i], str[j]);
    return str;
}

第四十三题

注意系数即可完成。比较简单。

string ReverseSentence(string str) {
	int size = str.size();
	if (size == 0) return "";
	string res(str);
	int count = 0;
	for (int i = size - 1; i >= 0; i--) {
		// scan from last to front
		if (str[i] == ' ') {
			cout << i << endl;
			// copy to last pos
			for (int j = i + 1; str[j] != ' ' && j < size; j++) res[count++] = str[j];
			res[count++] = ' ';
		}
	}
	for (int i = 0; i < size; i++) {
		if (str[i] == ' ') break;
		res[count++] = str[i];
	}
	return res;
}

第四十四题

比较简单。

bool IsContinuous( vector<int> numbers ) {
    int size = numbers.size();
    if (size <= 0) return false;
    sort(numbers.begin(), numbers.end());
    int godnum = 0;
    int i = 0;
    for (i = 0; i < size; i++) {
        if (numbers[i] == 0) godnum++;
        else break;
    }
    int count = 0;
    for (int j = max(1, i+1); j < size; j++) {
        if (numbers[j] == numbers[j-1]) {
            return false;
        }
        count += (numbers[j] - numbers[j-1] - 1);
    }
    return count <= godnum;
}

第四十五题

简单做法当然是模拟。构建数组然后循环。但是这种题明显是可以从公式中推出来的。
约瑟夫环${f(n,m)=(f(n-1,m)+m)%n}$
由此可以写出递归代码。

int LastRemaining_Solution(int n, int m)
{
    if (n == 0) return -1;
    if (n == 1) return 0;
    return (m%n+LastRemaining_Solution(n-1, m))%n;
}

第四十六题

卡了半个小时，看了各位大佬的做法，心态有点小崩。任重而道远啊。
方法一：使用sizeof模拟乘法，使用位数移动模拟除法。

int Sum_Solution(int n) {
    bool a[n][n+1];
    int sum = sizeof(a) >> 1;
    return sum;
}

方法二：使用&&短路的特性模拟if

int Sum_Solution(int n) {
    int sum = n;
    int ans = (n > 0) && (sum += Sum_Solution(n-1));
    return sum;
}

第四十七题

很明显是要从bit位来作。
二进制加法，如果xor结果为1，则不进位。结果相应位应为1.
如果and结果为1，则需要进位，结果高一位应为1.
那么如何把这两个结合到一起呢？用一个循环直到xor等于0就好了。

int Add(int num1, int num2)
{
    while (num2) {
        int xort = num1 ^ num2;
        num2 = (num1 & num2) << 1;
        num1 = xort;
    }
    return num1;
}

第四十八题

每一位来转换。

int StrToInt(string str) {
	// check if the input is valid
	int ch = 1;
	int res = 0;
	int startPos = 0;
	if (str[0] == '+') {
		ch = 1;
		startPos = 1;
	}
	else if (str[0] == '-') {
		ch = -1;
		startPos = 1;
	}
	for (int i = startPos; i < str.size(); i++) {
		if (!(str[i] >= '0' && str[i] <= '9')) return 0;
	}
	for (int i = startPos; i < str.size(); i++) {
		res *= 10;
		res += (str[i] - '0');
	}
	return res * ch;

}

第四十九题

bucket sort的思想。如果已经有数，返回。

bool duplicate(int numbers[], int length, int* duplication) {
    for (int i = 0; i < length; i++) {
        if (numbers[numbers[i]] == numbers[i] && numbers[i] != i) {
            *duplication = numbers[i];
            return true;
        }
        else {
            int tmp = numbers[numbers[i]];
            numbers[numbers[i]] = numbers[i];
            numbers[i] = tmp;
        }
    }
    return false;
}

第五十题

很有趣的一道题。要用reuse的思想。如何reuse之前的结果呢？以下图说明了做法。

vector<int> multiply(const vector<int>& A) {
    vector<int> B;
    B.push_back(1);
    for (int i = 1; i < A.size(); i++) {
        B.push_back(B.back()*A[i-1]);
    }
    vector<int> C;
    C.push_back(1);
    for (int i = A.size() - 2; i >= 0; i--) {
        C.push_back(C.back()*A[i+1]);
    }
    for (int i = 0; i < A.size(); i++) {
        B[i] *= C[A.size() - i - 1];
    }
    return B;
}

51 - 60

第五十一题

正则表达式，递归来做。

bool match(char* str, char* pattern)
{
	cout << str << " " << pattern;
	if (str[0] == 0 && pattern[0] == 0) return true;
	if (pattern[0] && pattern[1] == '*') {
		if (match(str, pattern + 2)) return true;
	}
	if (str[0] && (str[0] == pattern[0] || pattern[0] == '.')) {
		if (match(str + 1, pattern + 1)) return true;
		if (pattern[1] == '*') {
			if (match(str + 1, pattern)) return true;
		}
	}
	return false;
}

第五十二题

注意细节。分几个case
case1. integer（+/- [1-9][0-9]* or 0)
case2. float (+/- [0-9].[0-9])
case3. e (float E integer)

bool isInteger(char* string, int start, int end) {
	int startPos = start;
	if (string[startPos] == '+' || string[startPos] == '-') startPos += 1;
	if (string[startPos] >= '1' && string[startPos] <= '9') {
		bool pureNumber = true;
		for (int i = startPos + 1; i < end; i++) {
			if (!(string[i] >= '0' && string[i] <= '9')) {
				pureNumber = false;
				break;
			}
		}
		if (pureNumber) return true;
	}
	else if (string[startPos] == '0') {
		if (startPos + 1 == end) return true;
		else return false;
	}
	return false;
}
bool isNumber(char* string, int start, int end) {
	for (int i = start; i < end; i++) {
		if (!(string[i] >= '0' && string[i] <= '9')) return false;
	}
	return true;
}
bool isFloat(char* string, int start, int end) {
	int startPos = start;
	if (string[startPos] == '+' || string[startPos] == '-') startPos = startPos + 1;
	// scan for point
	int pos = -1;
	for (int i = startPos; i < end; i++) {
		if (string[i] == '.') {
			pos = i;
			break;
		}
	}
	if (pos != -1 && (isInteger(string, start, pos) || pos == startPos) && isNumber(string, pos + 1, end)) return true;
	return false;
}
bool isNumeric(char* string)
{
	int size = strlen(string);
	if (size <= 0) return false;

	if (isInteger(string, 0, size)) return true;
	if (isFloat(string, 0, size)) return true;

	// scan for 'e' 'E'
	int pos = -1;
	for (int i = 0; i < size; i++) {
		if (string[i] == 'e' || string[i] == 'E') {
			pos = i;
			break;
		}
	}
	if (pos != -1 && (isFloat(string, 0, pos) || isInteger(string, 0, pos)) && isInteger(string, pos + 1, size)) return true;
	return false;
}

第五十三题

比较简单。因为给定的是char，所以用bucket sort计数即可。

class Solution
{
public:
    string s;
  //Insert one char from stringstream
    void Insert(char ch)
    {
		if (cnt[ch] == 0)
			str.push_back(ch);
        cnt[ch] ++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        while (ptr < str.size() && cnt[str[ptr]] != 1) {
            ptr++;
        }
        if (str.size() == ptr) return '#';
        return str[ptr];
    }
private:
    vector<char> str;
    char cnt[256];
    int ptr=0;
};

第五十四题

三个方法。
方法一，直接keep住过往的node，然后对每一node检查是否访问过。O(n^2).

bool isVisited(vector<ListNode*>& v, ListNode* node) {
    for (int i = 0; i < v.size(); i++) {
        if (v[i] == node) return true;
    }
    return false;
}
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
    vector<ListNode*> visited;
    ListNode* node = pHead;
    while (node != NULL && !isVisited(visited, node)) {
        visited.push_back(node);
        node = node->next;
    }
    return node;
}

方法二，每次访问之后，把前面的链接断掉。这样如果出现loop，则下一次访问时，next为null(ps: 不过这样会破坏原有的list). O(n)
方法三，先求出ring的长度a，然后让指针一先走a，指针b再走。则ab相遇时，一定在入口点。O(n)

ListNode* EntryNodeOfLoop(ListNode* pHead)
{
    // get the length of loop
    // Vptr1 = 2, Vptr2 = 1
    if (pHead == NULL) return NULL;
    if (pHead->next == NULL) return NULL;
    if (pHead->next->next == NULL) return NULL;
    ListNode* ptr1 = pHead->next->next;
    ListNode* ptr2 = pHead->next;
    int time = 1;
    while (ptr1 != ptr2 && ptr1 != NULL && ptr2 != NULL) {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
        if (ptr1 != NULL) ptr1 = ptr1->next;
        time += 1;
    }
    if (ptr1 == NULL) return NULL;
    int lengthOfLoop = time;
    ptr1 = pHead;
    ptr2 = pHead;
    // move ptr1 to length of loop
    for (int i = 0; i < lengthOfLoop; i++) {
        ptr1 = ptr1->next;
    }
    while (ptr1 != ptr2) {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return ptr1;
}

第五十五题

暖心题。比较简单。

ListNode* deleteDuplication(ListNode* pHead)
    {
        if (pHead == NULL) return NULL;
        if (pHead->next == NULL) return pHead;
        int tmp = NULL;
        while (pHead != NULL && pHead->val == pHead->next->val || (pHead->val == tmp)) {
            tmp = pHead->val;
            pHead = pHead->next;
            if (pHead->next == NULL) break;
        }
        if (pHead == NULL || pHead->val == tmp) return NULL;
        if (pHead->next == NULL) return pHead;
        ListNode* node = pHead->next->next;
        ListNode* pre = pHead;
        while (node != NULL) {
            if (node != NULL && node->val == pre->next->val) {
                while (node != NULL && node->val == pre->next->val) {
                    node = node->next;
                }
                pre->next = node;
            }
            else pre = pre->next;
            if (node != NULL) node = node->next;
        }
        return pHead;
    }

第五十六题

分类讨论，共有三种case，node是左子，右子，家长。

TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
    if (pNode == NULL) return NULL;
    // case1 if node is leftchild
    TreeLinkNode* parent = pNode->next;
    if (parent != NULL && parent->left == pNode) {
        if (pNode->right == NULL) return pNode->next;
        TreeLinkNode* node = pNode->right;
        while (node->left != NULL) {
            node = node->left;
        }
        return node;
    }
    // case2 if node is rightchild
    if(parent != NULL && parent->right == pNode) {
        if (pNode->right != NULL) {
            TreeLinkNode* node = pNode->right;
            while (node->left != NULL) {
                node = node->left;
            }
            return node;
        }
        TreeLinkNode* grandpa = parent->next;
        if (grandpa == NULL) return NULL;
        if (grandpa->left == parent) return grandpa;
        else return NULL;
    }
    // case3 if node has no parent
    if (parent == NULL) {
        if (pNode->right == NULL) return NULL;
        TreeLinkNode* node = pNode->right;
        while (node->left != NULL) {
            node = node->left;
        }
        return node;
    }
    return NULL;
}

第五十七题

使用递归可以轻松解决。方法一，构建镜像，再比较是否相等。方法二，直接比较两个节点的左右是否对称。

class Solution {
public:
    TreeNode* mirror(TreeNode* node) {
        if (node == NULL) return node;
		TreeNode* n = new TreeNode(node->val);
		TreeNode* left = NULL;
		TreeNode* right = NULL;
		if (node->left != NULL) n->right = mirror(node->left);
		if (node->right != NULL) n->left = mirror(node->right);
		return n;
    }
    bool isSame(TreeNode* root, TreeNode* node) {
        if (root == NULL && node == NULL) return true;
        else if (root != NULL && node != NULL) {
            if (root->val != node->val) return false;
            if (isSame(root->left, node->left) && isSame(root->right, node->right)) return true;
            else return false;
        }
        else return false;
    }
    bool isSymmetrical(TreeNode* pRoot)
    {
        // build mirror
        TreeNode* m = mirror(pRoot);
        // check if mirror is same with pRoot
        return isSame(pRoot, m);
    }

};

第五十八题

BFS即可。值得注意的是，如果要在bfs得到层数，需要改变queue的pop时机，每一次都pop一层。

vector<vector<int> > Print(TreeNode* pRoot) {
    vector<vector<int>> res;
    if (pRoot == NULL) return res;
    // bfs
    queue<TreeNode*> q;
    q.push(pRoot);
    bool odd = true;
    while (!q.empty()) {
        vector<int> tmp;
        // pop all node out of queue
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            tmp.push_back(node->val);
            if (node->left != NULL) q.push(node->left);
            if (node->right != NULL) q.push(node->right);
        }
        if (!odd) {
            reverse(tmp.begin(), tmp.end());
        }
        res.push_back(tmp);
        odd = !odd;
    }
    return res;
}

第五十九题

同上一题一样。

第六十题

用dfs可以完成。值得注意的是，妥善使用c++中的引用可以很elegant的完成任务。

class Solution {
public:
	void Serialize(TreeNode* root, string& str) {
		if (root == NULL) {
			str += "#";
			str += ",";
			return;
		}
		str += to_string(root->val);
		str += ",";
		Serialize(root->left, str);
		Serialize(root->right, str);
	}
	char* Serialize(TreeNode *root) {
		string str;
		Serialize(root, str);
		char* res = new char[str.length()];
		for (int i = 0; i < str.length(); i++) {
			res[i] = str[i];
		}
		res[str.length()-1] = '\0';
		return res;
	}
    TreeNode* dfs(char* ptr) {
        ++index;
		if (ptr[index] == '#') {
			++index;
			return NULL;
		}
        int num = ptr[index++] - '0';
        for (; ptr[index] != ',' && ptr[index] != '#'; index++) {
            num = 10 * num + ptr[index] - '0';
        }
        TreeNode* node = new TreeNode(num);
        node->left = dfs(ptr);
        node->right = dfs(ptr);
        return node;
    }
    TreeNode* Deserialize(char *str) {
        TreeNode* node = dfs(str);
        return node;
    }
private:
    int index = -1;
};

61 - 66

第六十一题

使用dfs遍历即可。O(klogn)

class Solution {
public:
    void DFS(TreeNode* node) {
        if (node == NULL) return;
        if (node->left != NULL && res == NULL) DFS(node->left);
        count++;
        if (count == target) res = node;
        if (node->right != NULL && res == NULL) DFS(node->right);
    }
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        target = k;
        DFS(pRoot);
        return res;
    }

private:
    int count = 0;
    int target = 0;
    TreeNode* res = NULL;
};

第六十二题

DFS

class Solution {
public:
    void DFS(TreeNode* node) {
        if (node == NULL) return;
        if (node->left != NULL && res == NULL) DFS(node->left);
        count++;
        if (count == target) res = node;
        if (node->right != NULL && res == NULL) DFS(node->right);
    }
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        target = k;
        DFS(pRoot);
        return res;
    }
 
private:
    int count = 0;
    int target = 0;
    TreeNode* res = NULL;
};

第六十三题

直接暴力排序即可

class Solution {
public:
    void Insert(int num)
    {
        numstream.push_back(num);
        sort(numstream.begin(), numstream.end());
    }
 
    double GetMedian()
    {
        int size = numstream.size();
        if (size%2 == 0) {
            double res = numstream[size/2] + numstream[size/2-1];
            res /= 2;
            return res;
        }
        else {
            return numstream[size/2];
        }
    }
private:
    vector<int> numstream;
};

第六十四题

递归来做。简单随意。

class Solution {
public:
    int findMax(const vector<int>& num, int startPos, int size) {
        int maxPos = startPos;
        for (int i = startPos; i < startPos + size && i < num.size(); i++) {
            if (num[maxPos] < num[i]) maxPos = i;
        }
        return maxPos;
    }
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> res;
        if(num.empty()||size>num.size()||size<1)
            return res;
        int numptr = -1;
        for (int i = 0; i <= num.size() - size; i++) {
            if (numptr < i) {
                numptr = findMax(num, i, size);
            }
            else {
                if (num[i + size - 1] > num[numptr]) numptr = i + size - 1;
            }
            res.push_back(num[numptr]);
        }
        return res;
    }
};

第六十五题

递归。

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                visitedRow.clear();
                visitedCol.clear();
                if (hasPathPos(matrix, rows, cols, i, j, str)) return true;
            }
        }
        return false;
    }
    bool hasPathPos(char* matrix, int rows, int cols, int row, int col, char* str) {
        if (str[0] == 0) {
            return true;
        }
        if (visited(row, col)) return false;
        if (row < 0 || row >= rows) return false;
        if (col < 0 || col >= cols) return false;
 
        cout << matrix[row*cols + col] << endl;
        if (matrix[row*cols + col] == str[0]) {
            visitedRow.push_back(row);
            visitedCol.push_back(col);
            if (hasPathPos(matrix, rows, cols, row+1, col, str+1)
                || hasPathPos(matrix, rows, cols, row-1, col, str+1)
                || hasPathPos(matrix, rows, cols, row, col+1, str+1)
                || hasPathPos(matrix, rows, cols, row, col-1, str+1)) {
                return true;
            }
            visitedRow.pop_back();
            visitedCol.pop_back();
        }
        return false;
    }
    bool visited(int row, int col) {
        for (int i = 0; i < visitedRow.size(); i++) {
            if (visitedRow[i] == row && visitedCol[i] == col) {
                return true;
            }
        }
        return false;
    }
private:
    vector<int> visitedRow;
    vector<int> visitedCol;
};

第六十六题
递归。

class Solution {
public:
int movingCount(int threshold, int rows, int cols)
    {
        this->rows = rows;
        this->cols = cols;
        matrix = new bool[rows*cols];
        u = new bool[rows*cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                u[i*cols + j] = calc(i, j, threshold);
                matrix[i*cols+j] = true;
            }
        }
        return m(0, 0, threshold);
    }
    int m(int row, int col, int threshold) {
        if (row < 0) return 0;
        if (row >= rows) return 0;
        if (col < 0) return 0;
        if (col >= cols) return 0;
        if (!matrix[row*cols + col]) return 0;
        if (u[row*cols + col]) {
            matrix[row*cols + col] = false;
            int up = m(row-1, col, threshold);
            int down = m(row+1, col, threshold);
            int left = m(row, col-1, threshold);
            int right = m(row, col+1, threshold);
            return 1 + up + down + left + right;
        }
        else return 0;
    }
    bool calc(int row, int col, int th) {
        int sum = 0;
        while (row > 0) {
            sum += row % 10;
            row /= 10;
        }
        while (col > 0) {
            sum += col % 10;
            col /= 10;
        }
        cout << sum << " " << th << endl;
        return (sum <= th);
    }
private:
    bool* matrix;
    bool* u;
    int rows;
    int cols;
};