主要考点涵盖了基本数据结构，基础逻辑和算法应用以及智力题。

数据结构

主要考察数据结构在现实算法中的实际应用和变形转换。

链表（linked list）

从尾到头打印链表

题目：输入一个链表，从尾到头打印链表每个节点的值。
Input：

{67,0,24,58}

Output：

[58,24,0,67]

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题属于基本题，最直接的思路就是使用一个栈（stack）结构来依次存取数组中所有的元素，然后将stack的值按顺序pop即为答案。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        if listNode is None:
            return []
        stack = []
        while listNode is not None:
            stack.append(listNode.val)
            listNode = listNode.next
        return stack[::-1]

链表中倒数第k个结点

题目：输入一个链表，输出该链表中倒数第k个结点。
Input：

1, {1,2,3,4,5}

Output：

{5}

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题可以使用双指针解决，定义一前一后两个指针。让前指针先走k次，然后指针同时前进，当前指针到达链表尾部时，后指针所指的就是所要求的倒数第k个值。

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if head is None:
            return None
        count = k
        first = head
        second = None
        while count:
            if first is not None:
            	first = first.next
            	count -= 1
            else:
                return None
        second = head
        while first is not None:
            first = first.next
            second = second.next
        return second

合并两个排序的链表

题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
Input：

{1,3,5}, {2,4,6}

Output：

{1,2,3,4,5,6}

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本体主要的条件是已排序，所以我们只要依次比较两个链表的最左端元素大小，依次插入新的链表即可。具体流程可使用递归的方式。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if pHead1 == None:
            return pHead2
        elif pHead2 == None:
            return pHead1
        newHead = ListNode(0)
        if pHead1.val < pHead2.val:
            newHead.val = pHead1.val
            newHead.next = self.Merge(pHead1.next, pHead2)
        else:
            newHead.val = pHead2.val
            newHead.next = self.Merge(pHead1, pHead2.next)
        return newHead

两个链表的第一个交点

题目：输入两个链表，找出它们的第一个公共结点。
Input：

{1,2,3,6,7}, {4,5,6,7}

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 两个链表有公共节点，其必定共用结尾，因此可以计算两个链表的长度差，然后让长的先走相差的步数。最后两个链表同时移动，判断相同的点为公共点。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def findlength(self, pHead):
        count = 0
        while pHead:
            count += 1
            pHead = pHead.next
        return count
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if not pHead1 or not pHead2:
            return None
        len_one = self.findlength(pHead1)
        len_two = self.findlength(pHead2)
        dis = abs(len_one - len_two)
        if len_one > len_two:
            while dis:
                pHead1 = pHead1.next
                dis -= 1
        elif len_one < len_two:
            while dis:
                pHead2 = pHead2.next
                dis -= 1
        while pHead1:
            if pHead1.val == pHead2.val:
                return pHead1
            else:
                pHead1 = pHead1.next
                pHead2 = pHead2.next
        return None

链表中环的入口

题目：一个链表中包含环，请找出该链表的环的入口结点。
Input：

{1,2}, {3,4,5}

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题可以使用快慢指针，1个速度2倍于满指针的快指针。两指针一起移动，相遇的时候快指针在环中的距离为慢指针的2倍。此时慢指针距离入口的距离恰好等于起点距离入口的一半。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if not pHead or not pHead.next:
            return None
        slow = pHead.next
        fast = pHead.next.next
        while slow != fast:
            slow = slow.next
            fast = fast.next.next
        fast = pHead
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return fast

树（tree）

二叉树的镜像

题目：操作给定的二叉树，将其变换为源二叉树的镜像。
Input：

{8,6,10,5,7,9,11}

Output：

{8,10,6,11,9,7,5}

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题的主要观念还是在树结构的问题上，由于题目给定的是二叉树，因此只会有左子节点和右子节点。值得注意的是在交换父节点的同时，父节点对应的子节点也跟着交换，这点符合镜像的要求，因此可以考虑使用递归的方式来实现这个过程。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回镜像树的根节点
    def transform(self, node):
        temp = node.left
        node.left = node.right
        node.right = temp
        
    def Mirror(self, root):
        # write code here
        if root is not None:
            self.transform(root)
            self.Mirror(root.left)
            self.Mirror(root.right)

重构二叉树

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
Input：

{1,2,3,4,5,6,7}, {3,2,4,1,6,5,7}

Output：

{1,2,5,3,4,6,7}， root = 1

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本体需要了解的关键点包括：树的遍历性质，递归的思维步骤等。先序遍历总是优先打印当前最大子树的root节点，而root节点的所有左子树的元素在中序遍历中必定出现在root前，相反右子树的所有元素都在后。根据这些性质就能够根据递归的思路对数的结构进行拆解，最后回归整棵树的结构。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int cand = pre[0];
        if (vin.size() == 0){
            return NULL;
        }
        TreeNode* head = new TreeNode(cand);
        vector<int> left_pre, right_pre, left_in, right_in;
        int count = 0;
        for (int i = 0; i < vin.size(); i++){
            if (vin[i] == cand){
                count = i;
                break;
            }
        }
        for (int i = 0; i < count; i++){
            left_pre.push_back(pre[i+1]);
            left_in.push_back(vin[i]);
        }
        for (int i = count+1; i < vin.size(); i++){
            right_pre.push_back(pre[i]);
            right_in.push_back(vin[i]);
        }
        head -> left = reConstructBinaryTree(left_pre, left_in);
        head -> right = reConstructBinaryTree(right_pre, right_in);
        return head;
    }
};

树的子结构

题目：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
Input：

{8,8,7,9,3,#,#,#,#,4,7}, {8,9,2}

Output：

False

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题用到的数据结构是二叉树，看到题目不难想到利用DFS的思路顺势搜索下去，如果能够找到答案就返回True，不行就返回False。DFS的行为主要依赖于递归的算法，对每一个节点进行深度检索，判断是否能够找到另一棵树。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def search(self, root1, root2):
        if root2 is None:
            return True
        if root1 is None or root1.val != root2.val:
            return False
        return self.search(root1.left, root2.left) and self.search(root1.right, root2.right)
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if pRoot1 is None or pRoot2 is None:
            return False
        return self.search(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2)

二叉树的广度优先检索

题目：从上往下打印出二叉树的每个节点，同层节点从左至右打印。
Input：

{10,6,14,4,8,12,16}

Output：

[10,6,14,4,8,12,16]

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题不需要考虑按层换行打印，因此难度稍微低了些。code中的last和nlast用来判断层的结束和遍历的位置。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        if root is None:
            return []
        queue = []
        ans = []
        last = root
        nlast = root
        queue.append(root)
        while queue:
            temp = queue.pop(0)
            ans.append(temp.val)
            if temp.left is not None:
                queue.append(temp.left)
                nlast = temp.left
            if temp.right is not None:
                queue.append(temp.right)
                nlast = temp.right
            if temp == last:
                last = nlast
        return ans

二叉树的后序遍历序列

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
Input：

[4,6,7,5]

Output：

True

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 值得注意的关键条件是对于一个后续遍历的二叉树序列而言，最后一个元素永远是root结点。因此可以使用递归的方式判断root结点的左右子树（小于的节点在左边，大于的节点在右边）。两者的值连续分布，如果存在交叉或者奇异值，则判断条件不成立。

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        if len(sequence) == 1:
            return True
        temp = sequence.pop()
        left = []
        right = []
        i = 0
        while i < len(sequence) and sequence[i] < temp:
            left.append(sequence[i])
            i += 1
        while i < len(sequence):
            if sequence[i] < temp:
                return False
            right.append(sequence[i])
            i += 1
        left_flag = True
        right_flag = True
        if len(left):
            left_flag = self.VerifySquenceOfBST(left)
        if len(right):
            right_flag = self.VerifySquenceOfBST(right)
        return left_flag and right_flag
``` 
### 平衡二叉树
题目：输入一棵二叉树，判断该二叉树是否是平衡二叉树。
**Input：**
{1,2,3,4,5,#,6,#,#,7}
**Output：**
True
**Requirement：**
Time limit = 1s, Space limit = 32768K
**思路：** 平衡二叉树的性质是最大的深度差不超过1，因此计算深度之后就能够容易得到结果。
```python=
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def check(self, root):
        if not root:
            return 0
        left = self.check(root.left)
        right = self.check(root.right)
        return max(left + 1, right + 1)
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if not pRoot:
            return True
        if abs(self.check(pRoot.left) - self.check(pRoot.right)) > 1:
            return False
        else:
            return True

二叉树的下一个节点

题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
Input：

{8,6,10,5,7,9,11}, 5

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题属于一个递归的思路，需要熟悉二叉树的中序遍历特点。首先如果一个node有右节点，那么我们就会去寻找这个右节点的左子树的最左节点。如果右节点不存在的时候我们就会去找父节点，如果父节点的左节点就是当前节点，那么父节点就是下一个输出的对象。这个需要考虑几个特殊情况，例如root节点，如果没有右节点，那么没有下一个节点；右子树的最右节点，没有next节点等。

# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def findleft(self, pNode):
        while pNode.left:
            pNode = pNode.left
        return pNode
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return None
        if pNode.right:
            return self.findleft(pNode.right)
        else:
            temp = pNode
            while temp.next:
                temp = pNode.next
                if temp.left == pNode:
                    return temp
                pNode = temp
            return None

二叉树的对称

题目：请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
Input：

{8,6,6,5,7,7,5}

Output：

True

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 该题的思路比较明确，就是判断二叉树的镜像是否相同，利用递归可以很好地解决。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def is_same(self, left, right):
        if not left and not right:
            return True
        if left and right and left.val == right.val:
            return self.is_same(left.left, right.right) and self.is_same(left.right, right.left)
        return False
    def isSymmetrical(self, pRoot):
        # write code here
        if not pRoot:
            return True
        if (pRoot.left and not pRoot.right) or (pRoot.right and not pRoot.left):
            return False
        return self.is_same(pRoot.left, pRoot.right)

字符串（string）

替换空格

题目：请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy。则经过替换之后的字符串为We%20Are%20Happy。
Input：

“hello world”

Output：

“hello%20world”

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本体使用python的replace function可以快速得到结果。如果使用C++或是Java需要考虑替换的长度变化问题。另外替换过程中如果从第一个元素开始替换，需要进行大量的元素位移，因此考虑时间复杂度应该考虑从最后一位进行替换。而在原有的数组中进行替换，就需要知道数组的元素新增多少个空间。

class Solution {
public:
    void replaceSpace(char *str,int length) {
        if (str == NULL || length <0)
            return;
        int countspace = 0;
        int oldlen = 0;
        int i = 0;
        while (str[i] != '\0'){
            oldlen++;
            if (str[i] == ' ')
                countspace++;
            i++;
        }
        int newlen = oldlen + 2*countspace;
        if (newlen > length)
            return;
        while (oldlen >= 0 && newlen > oldlen){
            if (str[oldlen] == ' '){
                str[newlen--] = '0';
                str[newlen--] = '2';
                str[newlen--] = '%';
            }
            else
                str[newlen--] = str[oldlen];
            oldlen--;
        }
    }
};

字符串的全排列

题目：输入一个字符串,按字典序打印出该字符串中字符的所有排列。
Input：

abc

Output：

abc,acb,bac,bca,cab,cba

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 全排列的问题可以看成是一个递归的过程，在固定第一个元素的基础上计算之后元素的排列数，以此类推。也可以理解成动态规划的问题，根据每一个元素在每一个位置出现的可能性，交换不同元素使之成为固定元素，然后计算其他元素的排列数，以此作为转换函数传递递归下去。

# -*- coding:utf-8 -*-
class Solution:
    def swap(self, ss, i, j):
        temp = ss[i]
        ss[i] = ss[j]
        ss[j] = temp
        
    def not_equal(self, ss, i, j):
        for k in range(i, j):
            if ss[k] == ss[j]:
                return False
        return True
        
    def permu(self, ss, temp, first, last):
        if not ss or last < 1:
            return
        if first == last:
            temp.append("".join(ss))
        else:
            for i in range(first, last):
                if self.not_equal(ss, first, i):
                    self.swap(ss, first, i)
                    self.permu(ss, temp, first + 1, last)
                    self.swap(ss, first, i)
            
    def Permutation(self, ss):
        # write code here
        if not ss:
            return []
        ans = []
        st = [i for i in ss]
        self.permu(st, ans, 0, len(st))
        return ["".join(i) for i in ans]

第一次只出现一次的字符

题目：在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置。
Input：

google

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题考察hash的用法以及字符类型字典的建构。

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        if (str.empty()){
            return -1;
        }
        map<char, int> hash;
        for (int i = 0; i < str.size(); i++){
            hash[str[i]]++;
        }
        for (int i = 0; i < str.size(); i++){
            if (hash[str[i]] == 1){
                return i;
            }
        }
        return 0;
    }
};

左旋转字符

题目：汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。
Input：

abcdefg, 2

Output：

“cdefgab”

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 旋转字符属于基本的算法之一，其思路也有许多，包括最基本的取值平移（K位数直接平移）；以及3次反向（先对前k个取反，然后对后n-k个取反，最后对整个字符串取反）等。

# -*- coding:utf-8 -*-
class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        if len(s) == 0:
            return ""
        if len(s) <= n:
            return s
        left = s[:n]
        right = s[n:]
        ans = left[::-1] + right[::-1]
        return ans[::-1]

翻转单词顺序列

题目：牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。后来才意识到，这家伙原来把句子单词的顺序翻转了。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
Input：

I am a student.

Output：

student. a am I

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题属于旋转字符串的运用。

# -*- coding:utf-8 -*-
class Solution:
    def ReverseSentence(self, s):
        # write code here
        temp = s.split(" ")
        if len(temp) == 0:
            return []
        return " ".join(temp[::-1])

把字符串转换成整数

题目：将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0。
Input：

+2147483647
1a33

Output：

2147483647
0

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 实作stoi函数，需要考虑的有4点：是否有无关字符，正负符号问题，空指针以及是否越界（超过integer临界值）。

class Solution {
public:
    int StrToInt(string str) {
        const char* temp = str.c_str();
        const static int MAX_INT = (int)((unsigned)~0 >> 1);
        const static int MIN_INT = -(int)((unsigned)~0 >> 1) - 1;
        unsigned int ans = 0;
        
        if (*temp == '\0'){
            return 0;
        }
        
        while (isspace(*temp)){
            temp++;
        }
        
        int sign = 1;
        if (*temp == '+' || *temp == '-'){
            if (*temp == '-'){
                sign = -1;
            }
            temp++;
        }
        
        while (*temp != '\0'){
            if (isdigit(*temp)){
                int c = *temp - '0';
                if (sign > 0 && (ans > MAX_INT / 10 || (ans == MAX_INT / 10 && c > MAX_INT % 10))){
                    ans = MAX_INT;
                    break;
                }
                else if (sign < 0 && (ans > (unsigned)MIN_INT / 10 || (ans == (unsigned)MIN_INT / 10 && c > (unsigned)MIN_INT % 10))){
                    ans = MIN_INT;
                    break;
                }
                ans = ans * 10 + c;
                temp++;
            }
            else{
                return 0;
            }
        }
        
        return sign > 0 ? ans : -ans;
    }
};

表示数值的字符串

题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值而”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。
Input：

“+100”

Output：

True

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题是要设计一个正则表达式能够判断字符的格式。

# -*- coding:utf-8 -*-
import re
class Solution:
    # s字符串
    def isNumeric(self, s):
        # write code here
        return re.match("^[+-]?\\d*(\\.\\d+)?([Ee][+-]?\\d+)?$", s)

字符流中第一次只出现一次的字符

题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。
Input：

google

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题使用hash的方式统计次数，需要注意的是需要得到的是第一次出现的单一字符，因此需要从头到尾判断。

# -*- coding:utf-8 -*-
class Solution:
    # 返回对应char
    def __init__(self):
        self.dic = {}
        self.s = ""
    def FirstAppearingOnce(self):
        # write code here
        for i in self.s:
            if self.dic[i] == 1:
                return i
        return '#'
    def Insert(self, char):
        # write code here
        self.s += char
        if char in self.dic:
            self.dic[char] += 1
        else:
            self.dic[char] = 1

数组（array）

二维数组中的查找

题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
Input：

7, [[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

Output：

True

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 既然二维数组满足严格的递增关系，那么我们可以考虑从数组的一个极端值开始考虑。以左下角为例，row = len(array)-1，col = 0的点比同一个col的其他值都大，因此如果此时这个数比我们的目标要大，我们只需要向上寻找即可。寻找过程中如果出现当前数字小于目标的时候，尝试往右寻找。如此往复，直到无路可走为止。想法类似DFS。

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if not array[0]:
            return False
        row = len(array)-1
        col = 0
        while (row >=0) and (col < len(array[0])):
            if array[row][col] == target:
                return True
            elif array[row][col] > target:
                row-=1
            else:
                col+=1
        return False

调整数组顺序让基数位于偶数前面

题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
Input：

[1,2,3,4,5,6,7]

Output：

[1,3,5,7,2,4,6]

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 利用两个指针来表示新数组中奇数和偶数的位置，然后依次插入即可。

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        if len(array) == 0:
            return []
        new_list = []
        temp = 0
        for i in array:
            if i % 2 == 0:
                new_list.append(i)
            else:
                new_list.insert(temp, i)
                temp += 1
        return new_list

数组中最小的k个数

题目：输入n个整数，找出其中最小的K个数。
Input：

{4,5,1,6,2,7,3,8}， 4

Output：

[1,2,3,4]

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题是经典的算法题之一，其思路多种多样。其中包括最基本的排序取前k个数；维护一个长度为k的最小堆以及BFPRT算法（利用中位数进行更精准的二分）等。

# -*- coding:utf-8 -*-
class Solution:
    def is_min(self, s, k):
        temp = s[-1]
        if k < temp:
            s[-1] = k
        s = sorted(s)
        return s
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if k == len(tinput):
            return sorted(tinput)
        if k == 0 or not tinput or k > len(tinput):
            return []
        min_heap = []
        for i in range(k):
            min_heap.append(tinput[i])
        min_heap = sorted(min_heap)
        for i in range(k, len(tinput)):
            min_heap = self.is_min(min_heap, tinput[i])
        return min_heap

连续子数组的最大和

题目：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？
Input：

{6,-3,-2,7,-15,1,2,2}

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本体求的是连续数组，可以使用循环或者动态规划的思维来解决。其核心就是在遍历数组的过程中维护两个值，其中一个记录当前的和，另一个记录最大和。当当前和大于0且大于最大和的时候，更新最大和；如果当前和小于零，则令当前和等于下一个元素。

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        if len(array) == 0:
            return 0
        ans = array[0]
        cur = 0
        for i in range(len(array)):
            if cur < 0:
                cur = array[i]
            else:
                cur += array[i]
            if cur > ans:
                ans = cur
        return ans

把数组排成最小的数

题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
Input：

{3，32，321}

Output：

321323

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题使用贪心（Greedy）算法和DFS结合的思路按照从长到短的顺序判断左右拼接字符的大小，然后选择大的继续。注意从长到短是因为长的数对全局影响比较大，用大的拼接小的可变化范围会增加。

# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if len(numbers) == 0:
            return ""
        ans = ""
        numbers = sorted(numbers)
        for i in range(len(numbers)):
            ans1 = int(ans + str(numbers[i]))
            ans2 = int(str(numbers[i]) + ans)
            if ans1 > ans2:
                ans = str(ans2)
            else:
                ans = str(ans1)
        return ans

丑数

题目：把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
Input：

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题如果使用遍历实数域的方式很难实现，所以可以考虑对因数进行组合。因为丑数是只包含2、3和5的因数，因此其值可以表示为 2i+3j+5k 的形式，因此我们去匹配相应的i、j、k系数，取组合数的最小值作为下一个出现的丑数，从而找到结果。注意：一次只加i、j、k中的一个值。

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index == 0:
            return 0
        if index == 1:
            return 1
        l = [1]
        idx_two = 0
        idx_three = 0
        idx_five = 0
        for _ in range(index-1):
            temp = min(l[idx_two]*2, l[idx_three]*3, l[idx_five]*5)
            l.append(temp)
            if temp % 2 == 0:
                idx_two += 1
            if temp % 3 == 0:
                idx_three += 1
            if temp % 5 == 0:
                idx_five += 1
        return l[-1]

数组中只出现一次的数字

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
Input：

[2,4,3,6,3,2,5,5]

Output：

“4,6”

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 利用hash和字典可以轻松解决。

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        if len(array) == 0:
            return
        ans = []
        dic = {i : 0 for i in array}
        for i in array:
            dic[i] += 1
        for i, j in dic.items():
            if j == 1:
                ans.append(i)
        return ans

数组中重复的数字

题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
Input：

[2,1,3,1,4]

Output：

“true, 1”

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 利用一个bool数组来动态规划。原本所有的数字table都为false，如果某一个数字对应数值位置的值为true，表示该数字已经出现过了。

public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        boolean temp[] = new boolean[length];
        for (int i = 0; i < length; i++){
            if (temp[numbers[i]] == true) {
                duplication[0] = numbers[i];
                return true;
            }
            temp[numbers[i]] = true;
        }
        return false;
    }
}

栈和堆叠（stack & heap）

用两个栈实现队列

题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。
Input：

[1, 2, 3, “POP”, “POP”, 4, “POP”, 5, “POP”, “POP”]

Output：

1,2,3,4,5

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 栈的特点是先进后出，如果要让栈内元素先进先出，就必须使用另一个栈来接它pop出去的元素，利用第二个栈的顺序依次pop即为队列（queue）的顺序。此外要注意的是，在pop结束之后，如果第二个栈内有剩余的元素，需要将这些元素pop回第一个栈再继续push的动作，这样才能保证元素的顺序正确。

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
    int pop() {
        while (!stack1.empty()){
            stack2.push(stack1.top());
            stack1.pop();
        }
        int ans = stack2.top();
        stack2.pop();
        while (!stack2.empty()){
            stack1.push(stack2.top());
            stack2.pop();
        }
        return ans;
    }
private:
    stack<int> stack1;
    stack<int> stack2;
};

包含min函数的栈

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
Input：

[3, “MIN”, 4, “MIN”, 2, “MIN”, 3, “MIN”, “POP”, “MIN”, “POP”, “MIN”, “POP”, “MIN”, 0, “MIN”]

Output：

3,3,2,2,2,3,3,0

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题考察数据结构的实作，在stack的基础上实现判断最小值的功能。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
    def push(self, node):
        # write code here
        self.stack.append(node)
    def pop(self):
        # write code here
        if self.stack:
            del self.stack[-1]
    def top(self):
        # write code here
        if self.stack:
            return self.stack[-1]
    def min(self):
        # write code here
        self.min_stack = []
        if self.stack:
            min = self.stack[-1]
        else:
            min = 0
        while self.stack:
            temp = self.top()
            self.min_stack.append(temp)
            self.pop()
            if temp < min:
                min = temp
        self.stack = self.min_stack[::-1]
        return min

栈的压入与弹出序列

题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
Input：

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

Output：

False

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 利用DFS的思路可以对pushV和popV里面所有时刻的值进行对比，判断是否能够组成一条完整的输出路线即可。

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        if not pushV or len(pushV) != len(popV):
            return False
        stack = []
        for i in range(len(pushV)):
            stack.append(pushV[i])
            while stack and popV[0] == stack[-1]:
                stack.pop()
                popV.pop(0)
        if len(stack) != 0:
            return False
        return True

智力题和知识迁移

矩阵覆盖

题目：我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，总共有多少种方法？
*Input：

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： t时刻的状态可以由t-1时刻的状态加上一个21的小矩阵构成，因此不难想到利用状态转移的方式进行解答。由于是21的矩阵，因此在扩展2n大矩阵的时候可能出现 ‘||’ 和 *’=’ 两种摆放形式，而这要求下矩阵需要以偶数形式出现。因此不难想到状态在偶数时会比奇数时多，一个典型的斐波那契数列应用。

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number < 1:
            return 0
        if number == 1:
            return 1
        ans = 1
        a = 1
        for i in range(2, number + 1):
            temp = ans
            ans += a
            a = temp
        return ans

顺时针打印矩阵

题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
Input：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Output：

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Requirement： 本体考察空间想象能力，通过每次将二维阵列的第一行从左到右顺序打印，然后删除打印的元素。之后对阵列进行倒序转置，一次往复就能够实现螺旋打印了。

Time limit = 1s, Space limit = 32768K

思路： 本体需要考虑的问题是打印的顺序属于动态变化的情况，因此我们采用动态阵列的定义

# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def transform(self, matrix):
        n = len(matrix)
        m = len(matrix[0])
        B = []
        for i in range(m):
            A = []
            for j in range(n):
                A.append(matrix[j][i])
            B.append(A)
        return B[::-1]
    def printMatrix(self, matrix):
        # write code here
        result = []
        while matrix:
            result += matrix.pop(0)
            if not matrix:
                break
            matrix = self.transform(matrix)
        return result

复杂链表的复制

题目：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空。
Input：

{1,2,3,4,5,3,5,’#’,2,’#’}

Output：

{1,2,3,4,5,3,5,’#’,2,’#’}

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 该题可以利用几种不同的思路进行解答，其中包括先利用临时阵列存取所有node的random值，然后复制原先的阵列，再将random值顺序赋值给对应的node。另一种是将遍历的每一个node复制到它的next结点，然后通过跳过一次的方式提取偶数node作为复制后的链表。

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Build(self, pHead):
        temp = []
        while pHead:
            ans = pHead.random
            temp.append(ans)
            pHead = pHead.next
        return temp
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return
        temp = self.Build(pHead)
        root = pHead
        res = RandomListNode(root.label)
        result = res
        result2 = res
        while root.next:
            root = root.next
            newNode = RandomListNode(root.label)
            result.next = newNode
            result = result.next
        for i in temp:
            result2.random = i
            result2 = result2.next
        return res

二叉检索树转换成双向链表

题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
Input：

{10,6,14,4,8,12,16}

Output：

From left to right are: 4,6,8,10,12,14,16; From right to left are: 16,14,12,10,8,6,4;

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题主要考察的是对数据结构的熟悉程度以及利用深度优先检索的中续遍历来构建双向链表的思路。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return None
        stack = []
        flag = True
        root = pRootOfTree
        while root or len(stack) != 0:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if flag:
                pRootOfTree = root
                pre = root
                flag = False
            else:
                pre.right = root
                root.left = pre
                pre = root
            root = root.right
        return pRootOfTree

整数中1出现的次数

题目：求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。
Input：

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 设N = abcde ,其中abcde分别为十进制中各位上的数字。
如果要计算百位上1出现的次数，它要受到3方面的影响：百位上的数字，百位以下（低位）的数字，百位以上（高位）的数字。
① 如果百位上数字为0，百位上可能出现1的次数由更高位决定。比如：12013，则可以知道百位出现1的情况可能是：100-199，1100-1199,2100-2199，，…，11100-11199，一共1200个。可以看出是由更高位数字（12）决定，并且等于更高位数字（12）乘以当前位数（100）。
② 如果百位上数字为1，百位上可能出现1的次数不仅受更高位影响还受低位影响。比如：12113，则可以知道百位受高位影响出现的情况是：100-199，1100-1199,2100-2199，，….，11100-11199，一共1200个。和上面情况一样，并且等于更高位数字（12）乘以当前位数（100）。但同时它还受低位影响，百位出现1的情况是：12100-12113,一共114个，等于低位数字（113）+1。
③ 如果百位上数字大于1（2~9），则百位上出现1的情况仅由更高位决定，比如12213，则百位出现1的情况是：100-199,1100-1199，2100-2199，…，11100-11199,12100-12199,一共有1300个，并且等于更高位数字+1（12+1）乘以当前位数（100）。

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        ans = 0
        temp = 1
        cand = n
        while cand:
            last = cand % 10
            cand = cand // 10
            ans += cand * temp
            if last == 1:
                ans += n % temp + 1
            elif last > 1:
                ans += temp
            temp *= 10
        return ans

扑克牌顺子

题目：LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。为了方便起见,你可以认为大小王是0。
Input：

[1,3,2,5,4]

Output：

true

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题比起正向思考，反向考虑其矛盾点更为明智。首先需要组成顺子必须保证有5张牌，其次如果5张牌有王，就必须保证除了王之外的数相差不超过5。同时不能有重复的出现。

# -*- coding:utf-8 -*-
class Solution:
    def is_same(self, s, i, k):
        for i in range(i, k-1):
            temp = s[i]
            for j in range(i+1, k):
                if s[j] == temp:
                    return True
        return False
    def IsContinuous(self, numbers):
        # write code here
        if len(numbers) != 5:
            return False
        num = sorted(numbers)
        point = 0
        if num[-1] == 0:
            return False
        while num[point] == 0:
            point += 1
        if point != len(num) - 1:
            if self.is_same(num, point, len(num)):
                return False
            if num[-1] - num[point] >= 5:
                return False
        return True

孩子们的游戏（环中剩下的数）

题目：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)。
Input：

5, 3

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题可以使用递归的思路解答，最后的胜利者永远不变，可以不断添加失败者进行递归的动作。另一种解法就是把环当成一个数组，然后根据规则每次删除数组中的相应的元素，最后的元素就是胜利者。

# -*- coding:utf-8 -*-
class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if n == 0 or m < 0:
            return -1
        temp = 0
        ans = range(n)
        while len(ans) > 1:
            temp = (temp + m - 1) % len(ans)
            ans.pop(temp)
        return ans[0]

1+2+3+4+…+n

题目：求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
Input：

1+2+3

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题的难点在于无法使用判断退出循环。因此可以使用位操作符的特性来进行判断，大于小于作为bool值返回的时候可以作为判断条件。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.sum = 0
    def Sum_Solution(self, n):
        # write code here
        def func(n):
            self.sum += n
            n -= 1
            return n > 0 and self.Sum_Solution(n)
        func(n)
        return self.sum

构建乘积数组

题目：给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…A[i-1]A[i+1]…A[n-1]。不能使用除法。
Input：

[1,2,3,4,5]

Output：

[120,60,40,30,24]

Requirement：

Time limit = 1s, Space limit = 32768K

思路： B数组中的值就是A数组的值去掉i对应的哪一项后的乘积。不能使用除法的情况下，我们就可以使用动态规划，维护一个A*B的二维阵列，其中对应Ai = Bi的值全为1，然后计算整个阵列每行的乘积和即可。

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        B = [1 for _ in range(len(A))]
        for i in range(1, len(A)):
            B[i] = B[i - 1] * A[i - 1]
        temp = 1
        for j in range(len(A) - 2, -1, -1):
            temp *= A[j + 1]
            B[j] *= temp
        return B

正则表达式

题目：请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”aba”均不匹配。
*Input：

“aa”, “aa”

Output：

true

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题的思路是递归加DFS。需要考虑的情况包括。如果下一个字符是’‘，则当前的值如果是’.’或者与匹配字符相等，则继续判断三种情况：1、匹配字符跳过与当前正则表达式的字符继续匹配；2、跳过正则表达式的当前字符和’‘，继续和匹配字符的当前字符比较；3、跳过正则表达式的当前字符和’‘同时跳过匹配字符的当前字符，匹配双方的下一个字符。这三种情况有一种成立即可继续。另外，如果’‘前面的字符不匹配，则跳过’‘继续匹配。如果下一个字符不是’‘，则匹配当前字符是否为’.’或者匹配字符，如果是跳过双方继续。

# -*- coding:utf-8 -*-
class Solution:
    # s, pattern都是字符串
    def match(self, s, pattern):
        # write code here
        if len(s) == 0 and len(pattern) == 0:
            return True
        if len(s) > 0 and len(pattern) == 0:
            return False
        if len(pattern) > 1 and pattern[1] == '*':
            if len(s) > 0 and (pattern[0] == '.' or pattern[0] == s[0]):
                return self.match(s, pattern[2:]) or self.match(s[1:], pattern) or self.match(s[1:], pattern[2:])
            else:
                return self.match(s, pattern[2:])
        else:
            if len(s) > 0 and (pattern[0] == '.' or pattern[0] == s[0]):
                return self.match(s[1:], pattern[1:])
        return False

之字形打印二叉树

题目：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
Input：

{8,6,10,5,7,9,11}

Output：

[[8], [10,6], [5,7,9,11]]

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题的思路就是在二叉树的广度优先检索（BFS）算法的基础上加上了一些变形，维护一个flag来判断当前是顺序打印还是逆序打印。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        res, temp = [], []
        last = pRoot
        queue = [pRoot]
        flag = True
        while queue:
            cand = queue.pop(0)
            temp.append(cand.val)
            if cand.left:
                queue.append(cand.left)
            if cand.right:
                queue.append(cand.right)
            if cand == last:
                res.append(temp if flag else temp[::-1])
                flag = not flag
                temp = []
                if queue:
                    last = queue[-1]
        return res

序列化和反序列化二叉树

题目：请实现两个函数，分别用来序列化和反序列化二叉树。
Input：

{8,6,10,5,#,9,11}

Output：

{8,6,10,5,#,9,11}

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 序列化二叉树就是用一个数据结构来表示二叉树，最简单的就是利用字符串以’,’区隔树的每一个node，然后用’#’表示空，按照从左到右的顺序编码。解码的时候就是编码的逆序。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.idx = -1
    def Serialize(self, root):
        # write code here
        if not root:
            return '#'
        return str(root.val) + ',' + self.Serialize(root.left) + ',' + self.Serialize(root.right)
    def Deserialize(self, s):
        # write code here
        temp = s.split(',')
        self.idx += 1
        if temp[self.idx] == '#':
            return None
        root = TreeNode(int(temp[self.idx]))
        root.left = self.Deserialize(s)
        root.right = self.Deserialize(s)
        return root

滚动窗口的最大值

题目：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
Input：

[2,3,4,2,6,2,5,1], 3

Output：

[4,4,6,6,6,5]

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题的关键信息在于window的size，我们可以维护一个window大小的数组，然后从左往右判断第一个数是否是最大的，如果此时长度已经达到了size的要求，那么pop第一个数，数组右移加入新的成员；或者如果数组中有数比第一个元素大则pop左边元素（目的是保证数组最左边的数永远最大）。

# -*- coding:utf-8 -*-
class Solution:
    def is_max(self, deque):
        temp = deque[0]
        for j in range(1, len(deque)):
            if temp <= deque[j]:
                return True
        return False
    def process(self, num, deque, size):
        while len(deque) > size or self.is_max(deque):
            deque.pop(0)
            if len(deque) == 1:
                break
        return deque
    def maxInWindows(self, num, size):
        # write code here
        ans = []
        if len(num) == 0 or len(num) < size or size == 0:
            return []
        deque = num[:size-1]
        for i in range(size-1, len(num)):
            deque.append(num[i])
            temp = self.process(num, deque, size)
            ans.append(temp[0])
        return ans

机器人的运动范围

题目：地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
Input：

5, 10, 10

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题是一个深度检索和动态规划的结合应用，利用维护一个阵列来动态判断每一个格子的可能性，然后利用深度检索的方式便利空间图形中的所有格子。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.count = 0
    def move(self, matrix, threshold, rows, cols, i, j):
        if not (0<=i<rows and 0<=j<cols):
            return
        temp = sum(map(int, str(i) + str(j)))
        if matrix[i][j] == -1 or temp > threshold:
            matrix[i][j] = -1
            return
        if matrix[i][j] == 1:
            return
        matrix[i][j] = 1
        self.count += 1
        self.move(matrix, threshold, rows, cols, i+1, j)
        self.move(matrix, threshold, rows, cols, i-1, j)
        self.move(matrix, threshold, rows, cols, i, j+1)
        self.move(matrix, threshold, rows, cols, i, j-1)
    def movingCount(self, threshold, rows, cols):
        # write code here
        matrix = [[0 for _ in range(cols)] for _ in range(rows)]
        self.move(matrix, threshold, rows, cols, 0, 0)
        return self.count

基本算法和逻辑

递归和循环（recursive & recurrent）

斐波那契数列

题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。（n<=39）
Input：

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 斐波那契数列的性质来看，通过循环或者动态规划可以轻松实现。

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n <= 0:
            return 0
        ans = 1
        pre = 1
        while n > 2:
            temp = ans
            ans = ans + pre
            pre = temp
            n-=1
        return ans

普通跳台阶问题

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
Input：

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 斐波那契数列的简单应用。

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number == 1:
            return 1
       	if number == 2:
            return 2
        a1 = 1
        a2 = 2
        ans = 0
        for i in range(3, number+1):
            ans = a1 + a2
            a1 = a2
            a2 = ans
        return ans

跳台阶进阶问题

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
Input：

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 不同与普通跳台阶问题，状态的转移关系到之前所有的状态累加。因此考虑t+1的状态可以表示成t状态的转移量，即1~t-1所有状态到t状态的可能性加上t到t+1状态的可能性。我们用ans表示X状态下对应的说有可能性，则t+1时刻的ans = t时刻的ans + （1~t-1）时刻的ans，而1~t-1时刻的ans又 = t时刻的ans。因此t+1时刻的ans = 2*t时刻的ans。

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        ans = 1
        for i in range(2, number + 1):
            ans += ans
        return ans

数值的整数次方

题目：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
Input：

2, 3

Output：

8.00000

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题如果用python的pow function可以轻易实现，如果使用循环的方式则属于考察临界条件的连乘问题。

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        ans = 1
        if base == 0:
            return 0
        temp = exponent
        if exponent < 0:
            temp = -exponent
        while temp != 0:
            ans *= base
            temp -= 1
        return ans if exponent >= 0 else 1/ans

二叉树的深度

题目：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
Input：

{1,2,3,4,5,#,6,#,#,7}

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 典型的递归问题。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if not pRoot:
            return 0
        left = self.TreeDepth(pRoot.left)
        right = self.TreeDepth(pRoot.right)
        return max(left+1, right+1)

删除链表中重复的结点

题目：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
Input：

{1,2,3,3,4,4,5}

Output：

{1,2,5}

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题可以使用递归的思路解决，可以使用两个指针分别遍历链表，如果下一个指针和当前指针相同的话则跳过后者。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if not pHead or not pHead.next:
            return pHead
        temp = pHead.next
        if temp.val != pHead.val:
            pHead.next = self.deleteDuplication(temp)
        else:
            while pHead.val == temp.val and temp.next:
                temp = temp.next
            if temp.val != pHead.val:
                pHead = self.deleteDuplication(temp)
            else:
                return None
        return pHead

矩阵中的路径

题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
Input：

“ABCESFCSADEE”, 3, 4, “ABCCED”

Output：

true

Requirement：

Time limit = 3s, Space limit = 32768K

思路： 本题是典型的DFS应用在Graph上的例子，在空间二维字符表中进行深度检索，利用动态规划的方式确定答案是否存在。

# -*- coding:utf-8 -*-
class Solution:
    def search(self, matrix, rows, cols, path, i, j):
        if not path:
            return True
        matrix[i*cols + j] = -1
        if j+1<cols and matrix[i*cols+j+1] == path[0]:
            return self.search(matrix, rows, cols, path[1:], i, j+1)
        elif j-1>=0 and matrix[i*cols+j-1] == path[0]:
            return self.search(matrix, rows, cols, path[1:], i, j-1)
        elif i+1<rows and matrix[(i+1)*cols+j] == path[0]:
            return self.search(matrix, rows, cols, path[1:], i+1, j)
        elif i-1>=0 and matrix[(i-1)*cols+j] == path[0]:
            return self.search(matrix, rows, cols, path[1:], i-1, j)
        else:
            return False
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        if not path or not matrix:
            return False
        for i in range(rows):
            for j in range(cols):
                if matrix[i*cols + j] == path[0]:
                    if self.search(list(matrix), rows, cols, path[1:], i, j):
                        return True
        return False

查找和排序（search & sort）

旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
Input：

[6501,6828,6963,7036,7422,7674,8146,8468,8704,8717,9170,9359,9719,9895,9896,9913,9962,154,293,334,492,1323,1479,1539,1727,1870,1943,2383,2392,2996,3282,3812,3903,4465,4605,4665,4772,4828,5142,5437,5448,5668,5706,5725,6300,6335]

Output：

154

Requirement：

Time limit = 3s, Space limit = 32768K

思路： 本体的关键条件是已排序数组，因此旋转之后的数组仍存在具有有序性。利用这个规律二分查找转折点就是最小值所在。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if (rotateArray.size() == 0){
            return 0;
        }
        int first = 0;
        int last = rotateArray.size()-1;
        int mid = -1;
        while (true){
            if (last - first == 1){
                mid = last;
                break;
            }
            mid = first + (last - first) / 2;
            if (rotateArray[mid] <= rotateArray[last]){
                last = mid;
            }
            if (rotateArray[mid] >= rotateArray[first]){
                first = mid;
            }
        }
        return rotateArray[first];
    }
};

数组中出现次数超过一半的数

题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字，如果不存在则输出0。
Input：

{1,2,3,2,2,2,5,4,2}

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题属于经典题目之一，其解法和思路多种多样，包括最基本的排序取中间值；每次删除2个不同的元素，以及利用两个变数candidate和nTime来动态规划。遍历数组，利用candidate参数记录一个元素，并用nTime参数记录当前该元素出现次数，如果下一个相同则nTime加1，否则减1。直到nTime等于0，candidate替换成下一个出现的元素。

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if not numbers:
            return 0
        if len(numbers) == 1:
            return numbers[0]
        numbers = sorted(numbers)
        n = len(numbers)
        if n % 2 == 0:
            if numbers[int(n / 2)] == numbers[int(n / 2) - 1]:
                return numbers[int(n / 2)]
        else:
            if numbers[int(n / 2)] == numbers[int(n / 2) + 1]:
                return numbers[int(n / 2)]
        return 0

二叉树中和为某一值的路径

题目：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
Input：

{10,5,12,4,7}, 22

Output：

[[10,5,7],[10,12]]

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 求和为定值的问题最先想到的应该是利用递归的方式考虑所有可能路径数字组合的DFS问题。只是这次的数据结构换成了二叉树，因此搜索的方向变成了树的深度方向。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if not root:
            return []
        if root and not root.left and not root.right and root.val == expectNumber:
            return [[root.val]]
        res = []
        left = self.FindPath(root.left, expectNumber - root.val)
        right = self.FindPath(root.right, expectNumber - root.val)
        for i in left+right:
            res.append([root.val] + i)
        return res

数字在排序数组中出现的次数

题目：统计一个数字在排序数组中出现的次数。
Input：

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

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 一个典型的利用二分查找的思路。

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if len(data) == 0:
        	return 0
        left = 0
        right = len(data)-1
        while left <= right:
            mid = int(left + (right - left) / 2)
            if data[mid] == k:
                first, last = mid, mid
                if data[first] == data[0]:
                    first = 0
                else:
                    while data[first - 1] == k:
                        first -= 1
                if data[last] == data[-1]:
                    last = len(data) - 1
                else:
                    while data[last + 1] == k:
                        last += 1
                return last - first + 1
            elif data[mid] > k:
                right = mid - 1
            else:
                left = mid + 1
        return 0

和为定值的连续正数序列

题目：小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
Input：

Output：

[[1,2]]

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题可以使用双指针的思路解决。一大一小两个指针分别位移，终止条件为小指针大于总数的一半（两个数都大于一半和一定超过总数）。因为是连续的，因此如果大小指针和小于总数，只要把大指针加1继续扩大和就行，同时当前总数加上新的值。如果等于总数，则输出小指针到大指针之间的所有数。如果当前总数大于总数，则小指针加1，同时当前总数减去新的值。

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        if tsum < 3:
            return []
        small = 1
        big = 2
        ans = []
        cur = small + big
        stop = int((1 + tsum) / 2)
        while small < stop:
            if tsum == cur:
                ans.append(list(range(small, big+1)))
                big += 1
                cur += big
            elif tsum > cur:
                big += 1
                cur += big
            else:
                cur -= small
                small += 1
        return ans

和为定制的两个数

题目：输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
Input：

[1,2,4,7,11,15], 15

Output：

[4,11]

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 因为数组为递增排序的数组，因此考虑使用大小指针进行解答。另外需要判断输出的多样性，需要对所有结果进行乘积的比较。

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        if len(array) == 0:
            return []
        if len(array) == 1:
            return array[0]
        left = 0
        right = len(array) - 1
        ans = []
        flag = True
        while left < right:
            cur = array[left] + array[right]
            if tsum == cur:
                if flag:
                    temp = array[left] * array[right]
                    flag = False
                    ans = [array[left], array[right]]
                else:
                    if array[left] * array[right] < temp:
                        temp = array[left] * array[right]
                        ans = [array[left], array[right]]
                left += 1
                right -= 1
            elif tsum > cur:
                left += 1
            else:
                right -= 1
        return ans

二叉树的分层列印

题目：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
Input：

{8,6,10,5,7,9,11}

Output：

[[8],[6,10],[5,7,9,11]]

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 二叉树的分层打印是经典算法之一，其主要思想是在传统的BFS算法基础上维护两个变量来判断换行的条件。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        queue = [pRoot]
        last = pRoot
        nlast = pRoot
        res, cand = [], []
        while len(queue) != 0:
            temp = queue.pop(0)
            cand.append(temp.val)
            if temp.left:
                queue.append(temp.left)
                nlast = temp.left
            if temp.right:
                queue.append(temp.right)
                nlast = temp.right
            if last == temp:
                last = nlast
                res.append(cand)
                cand = []
        return res

二叉检索树的第k大节点

题目：给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
Input：

{5,3,7,2,4,6,8}

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 本题利用了二叉检索树的性质，就是左子树的节点小于根节点小于右子树的节点。根据这个规律利用中序遍历的方式可以得到排序后的节点数组。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def middle_traversal(self, root, ans):
        if not root:
            return
        self.middle_traversal(root.left, ans)
        ans.append(root)
        self.middle_traversal(root.right, ans)
    def KthNode(self, pRoot, k):
        # write code here
        ans = []
        self.middle_traversal(pRoot, ans)
        if k <= 0 or len(ans) < k:
            return None
        return ans[k-1]

位运算

二进制中1的个数

题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
Input：

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 看到二进制问题首先想到的应该是位运算，将数字n右移一位的结果和1作and位运算，就可以知道当前位是否为1。

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        return sum([(n >> a & 1) for a in range(32)])

不用加减乘除做加法

题目：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、、/四则运算符号。
*Input：

4, 5

Output：

Requirement：

Time limit = 1s, Space limit = 32768K

思路： 经典的位运算运用，两个数的加法等于两数的xor加上2*两书的and。

# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        return (num1 ^ num2) + ((num1 & num2) << 1)

剑指offer算法编程题（Python、C++、Java）

数据结构

链表（linked list）

从尾到头打印链表

链表中倒数第k个结点

合并两个排序的链表

两个链表的第一个交点

链表中环的入口

树（tree）

二叉树的镜像

重构二叉树

树的子结构

二叉树的广度优先检索

二叉树的后序遍历序列

二叉树的下一个节点

二叉树的对称

字符串（string）

替换空格

字符串的全排列

第一次只出现一次的字符

左旋转字符

翻转单词顺序列

把字符串转换成整数

表示数值的字符串

字符流中第一次只出现一次的字符

数组（array）

二维数组中的查找

调整数组顺序让基数位于偶数前面

数组中最小的k个数

连续子数组的最大和

把数组排成最小的数

丑数

数组中只出现一次的数字

数组中重复的数字

栈和堆叠（stack & heap）

用两个栈实现队列

包含min函数的栈

栈的压入与弹出序列

智力题和知识迁移

矩阵覆盖

顺时针打印矩阵

复杂链表的复制

二叉检索树转换成双向链表

整数中1出现的次数

扑克牌顺子

孩子们的游戏（环中剩下的数）

1+2+3+4+…+n

构建乘积数组

正则表达式

之字形打印二叉树

序列化和反序列化二叉树

滚动窗口的最大值

机器人的运动范围

基本算法和逻辑

递归和循环（recursive & recurrent）

斐波那契数列

普通跳台阶问题

跳台阶进阶问题

数值的整数次方

二叉树的深度

删除链表中重复的结点

矩阵中的路径

查找和排序（search & sort）

旋转数组的最小数字

数组中出现次数超过一半的数

二叉树中和为某一值的路径

数字在排序数组中出现的次数

和为定值的连续正数序列

和为定制的两个数

二叉树的分层列印

二叉检索树的第k大节点

位运算

二进制中1的个数

不用加减乘除做加法

谢谢您~~