剑指Offer题解

剑指Offer刷题 链接

共66题 历时 2018.02.28-2018.03.01 共2天

=============================== 2.28

  1. 二维数组中的查找 较为简单
    类似于二分的思路,先找到中间的数(广义中位数),然后每次缩小一大块空间

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    bool Find(int target, vector<vector<int> > array) {
    const int line = array.size();
    if(line == 0)
    return false;
    const int row = array[0].size();
    int i = 0, j = line - 1;
    while(i < row && j >= 0)
    {
    if(target > array[i][j])
    i++;
    else if(target < array[i][j])
    j--;
    else
    return true;
    }
    return false;
    }
  2. 替换空格
    从尾部进行处理以防止头部数据被覆盖 简单字符串处理

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    void replaceSpace(char *str,int length)
    {
    if(str == nullptr)
    return ;
    int nonspace = 0;
    char *tmp = str;
    while(*tmp != '\0')
    {
    if(*tmp == ' ')
    nonspace++;
    tmp++;
    }
    for(int i = length-1; i >= 0; --i)
    {
    if(*(str+i) == ' ')
    {
    *(str+i+nonspace*2-2) = '%';
    *(str+i+nonspace*2-1) = '2';
    *(str+i+nonspace*2) = '0';
    nonspace--;
    }
    else
    {
    *(str+nonspace*2+i) = *(str+i);
    }
    }
    return ;
    }
  3. 从尾到头打印链表
    简单递归处理链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    vector<int> printListFromTailToHead(ListNode* head)
    {
    vector<int > re;
    printList(head,re);
    return re;

    }
    void printList(ListNode *node,vector<int > &re)
    {
    if(node == nullptr)
    return;
    printList(node->next,re);
    re.push_back(node->val);
    }
  4. 重建二叉树
    中等难度的 递归问题,记得划分子问题的时候,子问题的解决方法应该与原问题一致

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    #include <iostream>
    #include <vector>
    //// 记住 递归类的问题的子问题一定是与原问题给出的信息等价 也就是 子问题与原问题完全一致
    using namespace std;

    struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

    TreeNode* reCon(vector<int> pre,vector<int> vin, int pLeft, int pRight, int vStart, int vEnd)
    {

    if(pLeft > pRight || vStart > vEnd)
    return NULL;
    //cout<<pLeft<<" "<<pRight<<" "<<vStart<<" "<<vEnd<<endl;
    int count = 0;
    TreeNode* root = new TreeNode(pre[pLeft]);
    if(pLeft == pRight || vStart == vEnd)//到达叶子节点,不需要寻找左右节点
    return root;

    for(int i = vStart; i <= vEnd; ++i)
    {
    if(pre[pLeft] == vin[i])// 找到在中序遍历中的下标进行划分
    {
    break;
    }
    count++;
    }
    root->left = reCon(pre,vin,pLeft+1,pLeft+count,vStart,vStart+count-1);
    root->right = reCon(pre,vin,pLeft+count+1,pRight,vStart+count+1,vEnd);
    return root;

    }

    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
    TreeNode* root = reCon(pre,vin,0,pre.size()-1,0,vin.size()-1);
    return root;
    }
    int main(int argc, char *argv[])
    {
    vector<int > pre = {1,2,4,7,3,5,6,8};
    vector<int > vin = {4,7,2,1,5,3,8,6};
    reConstructBinaryTree(pre,vin);

    return 0;
    }
  5. 用两个栈实现队列
    简单的栈处理 一个用于push 一个用于pop

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution
    {
    public:
    void push(int node) {
    stack1.push(node);
    }

    int pop() {
    if(stack2.size() < 1)
    {
    while(stack1.size() > 0)
    {
    stack2.push(stack1.top());
    stack1.pop();
    }

    }
    int tmp = stack2.top();
    stack2.pop();
    return tmp;

    }

    private:
    stack<int> stack1;
    stack<int> stack2;
    };
  6. 旋转数组的最小数字
    简单的二分思想的运用,当一个序列可以用函数的单调性来描述的时候就会使用二分
    但是要注意单调不减 所以注意等号的处理

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    int findMinNum(vector<int> &rArr, int start, int end)
    {
    if(end - start < 2)
    {
    return min(rArr[start],rArr[end]);
    }
    int middle = (start+end)/2;
    if(rArr[middle] >= rArr[start] && rArr[middle] >= rArr[end])
    {
    return findMinNum(rArr,middle,end);
    }
    else if(rArr[middle] <= rArr[start] && rArr[middle] <= rArr[end])
    {
    return findMinNum(rArr,start,middle);
    }
    else if(rArr[middle] <= rArr[start] && rArr[middle] >= rArr[end])
    {
    return rArr[middle];
    }

    return 0;
    }
    int minNumberInRotateArray(vector<int> rotateArray)
    {
    if(rotateArray.size() < 1)
    return 0;
    return findMinNum(rotateArray,0,rotateArray.size()-1);
    }
  7. 斐波那契数列
    非常简单的递归转动态规划(或迭代)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    int Fibonacci(int n) {
    int i = 3;
    int f1 = 1, f2 = 1;
    if(n == 0)
    return 0;
    else if(n < 3)
    return 1;
    int tmp;
    while(i++ <= n)
    {
    tmp = f2;
    f2 = f1 + f2;
    f1 = tmp;
    }
    return f2;

    }
  8. 跳台阶
    上题的变种

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int jumpFloor(int number) {
    if(number <= 0)
    return 0;
    else if(number == 1)
    return 1;
    else if(number == 2)
    return 2;
    int f1 = 1, f2 = 2;
    int tmp, index = 3;
    while(index++ <= number)
    {
    tmp = f2;
    f2 = f1+f2;
    f1 = tmp;
    }
    return f2;

    }
  9. 变态跳台阶
    数学归纳法找规律的题

    1
    2
    3
    4
    5
    6
    int jumpFloorII(int number) {
    if(number <= 0)
    return 0;
    else
    return pow(2,number-1);
    }
  10. 矩形覆盖
    斐波那契数列变种

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    int rectCover(int number) {
    if(number <= 0)
    return 0;
    else if(number == 1)
    return 1;
    else if(number == 2)
    return 2;
    else
    {
    int index = 3;
    int tmp,f1 = 1, f2 = 2;
    while(index++ <= number)
    {
    tmp = f2;
    f2 = f1+f2;
    f1 = tmp;
    }
    return f2;
    }
    }
  11. 二进制中1的个数
    简单的数值处理 记得有负数不能用移位然后与1与的方法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int  NumberOf1(int n) {
    int count = 0;
    while(n)
    {
    count++;
    n&=(n-1);
    }
    return count;
    }
  12. 数值的整数次方
    简单数值处理(也是二分) 注意细节 指数为0 指数为负 指数为奇数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    double Power(double base, int exponent) {
    bool neg = exponent > 0 ? 0 : 1;
    bool ood = exponent % 2;
    exponent = abs(exponent);
    double re = base;
    if(exponent == 0)
    re = 1;
    else if(exponent != 1)
    {
    while(exponent>1)
    {
    re = re*re;
    exponent/=2;
    }
    if(ood)
    re = re*base;
    }
    return neg ? 1/re : re;
    }
  13. 调整数组顺序使奇数位于偶数前面
    数组 处理 在空间不允许的情况下(不要求位置不变) 可以 用两个指针 指向头和尾,然后交换

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void reOrderArray(vector<int> &array) {
    vector<int> re;
    for(int i = 0; i < array.size();++i)
    {
    if(array[i] % 2)
    re.push_back(array[i]);
    }
    for(int i = 0; i < array.size();++i)
    {
    if(array[i] % 2 == 0)
    re.push_back(array[i]);
    }
    array = re;
    }
  14. 链表中倒数第k个结点
    简单的链表处理,头尾两个指针进行处理

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    ListNode* tmp = pListHead;
    for(int i = 0; i < k; ++i)
    {
    if(tmp == NULL)
    return NULL;
    tmp = tmp->next;
    }
    while(tmp!= NULL)
    {
    tmp = tmp->next;
    pListHead = pListHead->next;
    }
    return pListHead;

    }
  15. 反转链表
    中等难度的链表处理,千万要注意细节,就是指针为空的时候
    然后有递归(难理解 简洁)和迭代两种方式来实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    //// 反转链表

    #include <iostream>

    using namespace std;


    struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
    val(x), next(NULL) {
    }
    };

    // 非递归实现,注意空指针的判断,否则直接段错误
    ListNode* ReverseList(ListNode* pHead) {
    if(pHead == nullptr)
    return nullptr;
    ListNode *pre = NULL,*tmp2;
    while(pHead->next != NULL)
    {
    tmp2 = pHead->next;
    pHead->next = pre;
    pre = pHead;
    pHead = tmp2;
    }
    pHead->next = pre;
    return pHead;
    }
    // 递归版
    ListNode* RecReverseList(ListNode* pHead) {
    if(pHead->next == nullptr || pHead == nullptr)
    {
    return pHead;
    }
    ListNode *pre = RecReverseList(pHead->next);
    // 注意每次 pHead 这个局部变量的存在,都是指向之前的指针,相当于每次pHead 的值是栈顶的值
    pHead->next->next = pHead;
    pHead->next = nullptr;
    return pre;
    }

    int main(int argc, char *argv[])
    {
    ListNode *pHead = new ListNode(0);
    ListNode *ptmp = pHead;
    for(int i = 1; i < 6; ++i)
    {
    ptmp->next = new ListNode(i);
    ptmp = ptmp->next;
    }
    RecReverseList(pHead);

    return 0;
    }
  16. 合并两个排序的链表
    简单的链表处理

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47

    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
    if(pHead1 == nullptr && pHead2 == nullptr)
    return nullptr;
    else if(pHead1 != nullptr && pHead2 == nullptr)
    return pHead1;
    else if(pHead1 == nullptr && pHead2 != nullptr)
    return pHead2;

    ListNode *head, *tmp;
    if(pHead1->val < pHead2->val)
    {
    head = pHead1;
    pHead1 = pHead1->next;
    }
    else
    {
    head = pHead2;
    pHead2 = pHead2->next;
    }

    tmp = head;
    while(pHead1 != nullptr && pHead2 != nullptr)
    {
    if(pHead1->val < pHead2->val)
    {
    tmp->next = pHead1;
    tmp = pHead1;
    pHead1 = pHead1->next;
    }
    else
    {
    tmp->next = pHead2;
    tmp = pHead2;
    pHead2 = pHead2->next;
    }
    }
    if(pHead1 != nullptr)
    {
    tmp->next = pHead1;
    }
    else
    {
    tmp->next = pHead2;
    }
    return head;
  17. 树的子结构
    aaa

    1
    2


  18. 二叉树的镜像
    aaa

    1
    2


=================== 3.1

T B
站点访问量: / , 本页阅读量:
T B