[数据结构与算法]剑指offer 01

编程习惯

• 思考清楚再开始编码
• 良好的代码命名和缩进对齐习惯
• 能够进行单元测试

介绍项目

• 简短的项目背景（项目的规模，开打的软件的功能，目标用户等）
• 自己完成的任务（分清参与与负责）
• 为完成任务自己做了哪些工作（介绍系统架构，基于什么工具什么平台进行开发）
• 自己的贡献

题目

JZ50 数组中重复的数字

 * @param numbers int整型vector 
 * @return int整型
 
 * @param numbers int数组
 * @param length int
 * @param duplication int*  重复的值

• 对数组进行判空，检查长度是否大于0
• 对数据的范围进行判断（0~n-1）

int duplicate(vector<int>& numbers) {
    if(numbers.empty() || numbers.size() <= 0){
        return -1;
    }
    for(int i=0;i<numbers.size();i++){
        if(numbers[i] < 0 || numbers[i] > numbers.size() - 1)
            return -1;
    }
    for(int i = 0; i < numbers.size(); i++){
        while(numbers[i] != i){
            if(numbers[i] == numbers[numbers[i]]){
                return numbers[i];
            }
            int temp = numbers[i];
            numbers[i] = numbers[temp];
            numbers[temp] = temp;
        }
    }
    return -1;
}

题目2

长度为n+1的数组中所有数字在1~n范围内，找出任意一个重复的数字，不修改原数组。

总体思路：把1-n的数字分为两部分，1_m和m+1n,，如果前部分的数字的数目超过m，说明前面一定有重复的数字，也就是二分查找+统计区间内数字数目。

#include<iostream>

int countRange(const int* numbers, int length, int start, int end);
int getDuplication(const int* numbers, int length) {
	if (numbers == nullptr || length <= 0)
		return -1;

	int start = 1;
	int end = length - 1;
	while (end >= start) {
		int middle = ((end - start) >> 1) + start;
		int count = countRange(numbers, length, start, middle);
		if (end == start) {
			if (count > 1)
				return start;
			else
				break;
		}
		if (count > (middle - start + 1))
			end = middle;
		else
			start = middle + 1;
	}
	return -1;
}

int countRange(const int* numbers, int length, int start, int end) {
	if (numbers == nullptr)
		return -1;
	int count = 0;
	for (int i = 0; i < length; i++) {
		if (numbers[i] >= start && numbers[i] <= end)
			count++;
	}
	return count;
}

int main() {
	int arr[] = { 2,3,5,4,3,2,6,7 };
	int arrlen = 8;

	int brr[] = { 2,1,3,6,8,5,7,4 };
	int brrlen = 8;

	int* crr = NULL;
	int crrlen = 0;

	int a = getDuplication(arr, arrlen);
	int b = getDuplication(brr, brrlen);
	int c = getDuplication(crr, crrlen);

	printf("%d\n%d\n%d\n", a, b, c);
	return 0;
}

JZ1 二维数组中的查找

思路就是找顶点，通过顶点来筛除掉一行或一列，减少工作量。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int row = 0;
        int column = array[0].size()-1;
        while(row<array.size()&&column>=0){
            if(array[row][column]==target) return true;
            if(array[row][column]>target) column--;
            else row++;
        }
        return false;
    }
};

JZ2 替换空格

时间复杂度为O(n)的解法，需要两个指针，一个位于替换前数组的末尾，一个位于替换后数组的末尾。

举一反三：考虑从后往前复制，能够减少移动的次数。

string replaceSpace(string s) {
        if(s.length()<= 0) return "";
        int originalLength = 0;
        int numberOfBlank = 0;
        
        //查找空格个数
        int i=0;
        while(s[i]!='\0'){
            originalLength++; //str的实际长度
            
            if(s[i] == ' ')
                numberOfBlank++;
            i++;
        }
        
        int newLength = originalLength + numberOfBlank*2;

        int indexOfOriginal = s.length();
        int indexOfNew = newLength;
        s.append(numberOfBlank * 2, '0');
        while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal){
            if(s[indexOfOriginal] == ' '){
                s[indexOfNew--] = '0';
                s[indexOfNew--] = '2';
                s[indexOfNew--] = '%';
            }
            else{
                s[indexOfNew --] = s[indexOfOriginal];
            }
            indexOfOriginal--;
        }
        return s;
    }
};