剑指offer学习笔记：3.3 代码的完整性

从功能测试，边界测试和负面测试三个方面设计测试用例，保证代码的完整性。

关于异常处理的三种方式

面试题11：数值的整数次方

题目：实现函数double Power(double base, int exponent)， 求base的exponent次方。不得使用库函数，同时，不考虑大数问题。
牛客网链接 https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00?tpId=13&&tqId=11165&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

class Solution {
public:
   bool Invalid_flag = false;   // 全局变量，标志输入是否合法
   double Power(double base, unsigned int exponent)
   {
       double result = 1;
       for(int i = 1; i <= exponent; i++)
       {
           result *= base;
       }
       return result;
   }
   bool equal(double a, double b)
   {
       if ((a-b) < 0.0000001 && (a-b) > 0.0000001)
       {
           return true;
       }
       return false;
   }
   double Power(double base, int exponent) {
       Invalid_flag = false;
       if(equal(base, 0.0) && exponent < 0)  // 注意小数相等判断不能直接用==
       {
           Invalid_flag = true;   // 输入数据无效
           return 0;
       }
       unsigned int tmp = (unsigned int)exponent;
       if (exponent < 0)
       {
           tmp = (unsigned int)(-exponent);
       }
       double result = Power(base, tmp);
       if (exponent < 0)
       {
           result = 1 / result;
       }
       return result;       
   }
};

考察点：
1.考虑到指数为负数的情况。尤其是指数为负数，底数为0的情况。注意在c++中判断小数相等不能直接用==，因为计算机在表示小数的时候是有误差的，要判断两个数绝对值的差在一个很小的范围内。
2.考察对于异常处理的方式。
3.乘方可以进行拆分
4.用右移代替除法，与代替余数运算，可以调高运算效率

面试题12：打印1到最大的n位数

题目：输入数字n，按顺序打印出从1到最大的n位10进制数。比如输入3，则打印1，2，3一直到999。 两种方法 1.字符串模拟加法 2.全排列，递归实现
leetcode链接
https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/ leetcode上这个链接其实有问题，他的返回定义成了vector<int>既然是int，其实没有考虑大数问题

//
// Created by Xue,Lin on 2020/6/25.
//
#ifndef UNTITLED_PRINT_N_NUMBER_H
#define UNTITLED_PRINT_N_NUMBER_H
#include "string"
#include "iostream"
using namespace std;
// 方法1：字符串模拟加法操作
// 因为数字可能存在越界情况，因此用长度为n+1的字符串模拟数字，+1的原因是字符串末尾需要'/0'结束符
// increase函数进行+1操作，当达到上限返回true。printNumber函数进行打印操作
void printNumber(char* number)
{
   // 打印非0开始数字
   // 因为有字符串结束标志符，可以在函数中进行长度判断
   bool start = true;
   for(int i = 0; i < strlen(number); i++)
   {
       if (number[i] == '0' && start)
       {
           continue;
       }
       start = false;
       cout << number[i];
   }
   cout << " ";
}
// 注意需要变量保留进位标志
// 注意结束标志是当前已是n位数，且产生了进位
bool increase(char* number)
{
   // 达到n位且产生进位时置true，外部循环可以结束
   bool overFlow = false;
   // 进位标志符
   int takeOver = 0;
   int len = strlen(number);
   for(int i = len - 1; i >= 0; i--)
   {
       // cout << "number: " << number << endl;
       // cout << "i: " << i << " takeover: " << takeOver << endl;
       int tmp;
       if (i == len - 1)
       {
           // 最后一位+1
           tmp = number[i] - '0' + 1;
       } else{
           // 其余位+进位
           tmp = number[i] - '0' + takeOver;
       }
       number[i] = tmp % 10 + '0';
       takeOver = tmp / 10;
       if (i == 0 && takeOver != 0)
       {
           overFlow = true;
       }
       // cout << "takeOver: " << takeOver << endl;
   }
   return overFlow;
}
void printMaxN(int n)
{
   if(n <= 0)
   {
       return;
   }
   char* number = new char[n+1];
   memset(number, '0', n);  
   number[n] = '\0';
   while(!increase(number))
   {
       printNumber(number);
   }
   delete [] number;
}
// 方法2：全排列，递归
// 每一位都有0-9 10种选择
// 递归结束条件是已经设置到数字的最后一位
void printMaxRec(char* number, int index)
{
   int len = strlen(number);
   // cout << "len: " << len << endl;
   if (index == len - 1)
   {
       printNumber(number);
       return;
   }
   for(int i = 0; i <= 9; i++)
   {
       number[index + 1] = '0' + i;
       printMaxRec(number, index + 1);
   }
}
void printMaxNRec(int n)
{
   if (n <= 0)
   {
       return;
   }
   // cout << "n:" << n << endl;
   char* number = new char[n+1];
   memset(number, '0', n);  // 注意一定要有这个赋值操作，不然strlen长度是0 ！！！
   number[n] = '\0';
   // cout << "len1: " << strlen(number) << endl;
   for(int i = 0; i <= 9; i++)
   {
       number[0] = '0' + i;
       printMaxRec(number, 0);
   }
}
#endif //UNTITLED_PRINT_N_NUMBER_H

考察点：大数问题
当存在大数越界风险，需要用字符串模拟数字
注意用字符串模拟数字相加时进位和判断长度是否超限方法。
注意打印函数需要去前面无效0

本题扩展：在前面代码中，我们都是用一个char型字符表示十进制数字中的一位，但是char占8个bit，可以表示256个字符，用来表示10进制有些浪费，有没有其余更高效的方法来表示大数。
答：想到的方法是用bit来表示，用4个bit来表示一个数。但是感觉写起来比较麻烦，不研究了。

相关题目：定义一个函数，在该函数中可以实现任意两个整数的加法。

//
// Created by Xue,Lin on 2020/6/25.
//

#ifndef UNTITLED_SUM_H
#define UNTITLED_SUM_H
#include <iostream>
#include "math.h"
using namespace std;
// 任意两个整数的和，是个大数问题，两个整数的和可能会超出int
// 相比+1这个大数问题，这个函数需要增加考虑负数情况
// 一个加法函数，一个打印函数
void printNumber(char* number)
{
   // 符号在函数外处理，打印的时候不考虑
   bool start = true;
   for(int i = 0; i < strlen(number); i++)
   {
       if (number[i] == '0' && start)
       {
           continue;
       }
       start = false;
       cout << number[i];
   }
   cout << " ";
}
void sum(const int a, const int b)
{
   // 如果是一个正数，一个负数，肯定不会超限
   if ((a >= 0 && b <= 0) || (a <= 0 && b >= 0))
   {
       cout << a + b << endl;
       return;
   }
   // 这里需要判断下a和b的符号，若是负数，可以先输出-号
   // 这里有个坑，负数最小 -2^31，正数最大2^31-1 转换会有问题
// 这里转换下的原因是我更习惯操作正数，没有其余原因
   int tmpA = a;
   int tmpB = b;
   if(a < 0)
   {
       cout << '-';
       tmpA = -1 - a;
       tmpB = -1 - b;
   }
   // 我有个不一样的想法
   // 不用转换字符串
   // c++带符号int最多2147483647,为10位数
   // 把进位和最高位记录下来，再加一下就可以了
   int max = int(pow(10, 9)); // 注意pow返回是double
   int a1 = tmpA / max;
   int b1 = tmpB / max;
   int a2 = tmpA % max;
   int b2 = tmpB % max;
   int low;
   if (a < 0)
   {
       low = a2 + b2 + 2;
   } else{
       low = a2 + b2;
   }
   /*
   cout << "a1: " << a1 << " b1: " << b1;
   cout << " a2: " << a2 << " b2: " << b2;
   cout << " low: " << low << endl;
    */
   int high = low / max + a1 + b1;
   if (high != 0)
   {
       cout << high << low << endl;
   } else{
       cout << low << endl;
   }

   // printNumber(number);
   return;
}
#endif //UNTITLED_SUM_H

考察点：由于没有限定两个数大小范围，需要当做大数来处理。同时，需要考虑，如果输入数字中有负数，应该如何处理。

面试题13：在o(1)时间内删除链表节点

给定单向链表的头指针和一个节点指针，定义一个函数，在o(1)时间内删除该节点链表节点和函数的定义如下：保证要删除节点一定在链表中
leetcode链接 https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/ 不太一样，还是自己写吧，正好再练下建立链表

struct ListNode   {  int m_pValue;  ListNode* m_pNext; };
void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)

//
// Created by Xue,Lin on 2020/6/25.
//
#ifndef UNTITLED_DELETE_VECTOR_NODE_H
#define UNTITLED_DELETE_VECTOR_NODE_H
#include<iostream>
#include<vector>
using namespace std;
struct ListNode{
   int val;
   ListNode* next;
};
ListNode* createList(vector<int> arr)
{
   if (arr.size() == 0)
   {
       return NULL;
   }
   ListNode* head = new ListNode;
   head->val = arr[0];
   ListNode* pre = head;
   for(int i = 1; i < arr.size(); i++)
   {
       ListNode* tmp = new ListNode;
       tmp->val = arr[i];
       pre->next = tmp;
       pre = pre->next;
   }
   pre->next = NULL;
   return head;
}
void printList(ListNode* head)
{
   if (head == NULL)
   {
       return;
   }
   ListNode* tmp = head;
   while(tmp != NULL)
   {
       cout << tmp->val << " ";
       tmp = tmp->next;
   }
   cout << endl;
}
void deleteNode(ListNode** pListHead, ListNode* pToBeDelete)
{
   // 因为要求时间复杂度是1，不能直接遍历
   if (pListHead == NULL || *pListHead == NULL)
   {
       return;
   }
   // 要删除节点不是尾节点
   if(pToBeDelete->next != NULL)
   {
       ListNode* next = pToBeDelete->next;
       pToBeDelete->val = next->val;
       pToBeDelete->next = next->next;
       delete next;
       next = NULL;
   } else if(*pListHead == pToBeDelete)
   {
       // 链表只有一个节点
       delete pToBeDelete;
       pToBeDelete = NULL;
       *pListHead = NULL;
   } else
   {
       // 多个节点，但是是尾节点
       /* 本来以为这么直接写会成功的，但是并没有，为什么这样不行呢。。
       delete pToBeDelete;
       pToBeDelete = NULL;
        */
       ListNode* tmp = *pListHead;
       while(tmp->next != pToBeDelete)
       {
           tmp = tmp->next;
       }
       tmp->next = NULL;
       delete  pToBeDelete;
       pToBeDelete = NULL;
   }
}
#endif //UNTITLED_DELETE_VECTOR_NODE_H
// main中
   vector<int> arr = {2,3,1};
   ListNode* head = createList(arr);
   deleteNode(&head, head->next->next);
   printList(head);

解题思路：
要删除节点，首先想到是找到该节点前一个节点，然后将其next指向要删除节点next，但是找到前一个节点需要从头指针开始遍历，不符合时间复杂度o(1)要求。
变换思路，要删除当前节点，其实可以用当前节点next覆盖掉当前节点，然后删除当前节点的next节点，不需要从前往后遍历，时间复杂度o(1)。
注意要删除节点是尾节点和链表只有一个节点的情况。
leetcode 上那个题因为给的是value，只能找前一个节点，注意判断删除节点是不是头节点：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if (head->val == val)
        {
            head = head->next;
            return head;
        }
        ListNode* index = head;
        while(index->next != NULL)
        {
            if (index->next->val == val)
            {
                index->next = index->next->next;
                break;
            }
            index = index->next;
        }
        return head;
    }
};

面试题14：调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数，调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
leetcode链接 https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/

class Solution {
public:
   vector<int> exchange(vector<int>& nums) {
       // 双指针
       vector<int> result = nums;
       int begin = 0, end = result.size() - 1;
       while(begin <= end)
       {
           if (result[begin] % 2 != 0)
           {
               begin++;
               continue;
           }
           if (result[end] % 2 == 0)
           {
               end--;
               continue;
           }
           int tmp = result[end];
           result[end] = result[begin];
           result[begin] = tmp;
       }
       return result;
   }
};

解题思路：首尾双指针。尾指针指向遇到的第一个奇数，首指针指向遇到的第一个偶数，交换。
升级：把判断条件拎出来设计成独立函数，可以提高代码兼容性。