vector - milkandbread/summary-interview GitHub Wiki

1 有序数组中不同平方值的个数(头条面试题)---C++实现
题目：

求解一个有序数组不同平方值的个数，{-1,-1,0,1,1}这里平方值只有0，1两种情况，返回2；{-3,-1,0,0,2,3}这里拼房族有0，1，4，9共4中情况，返回4。
要求：时间复杂度O(n)空间复杂度O(1)

思路:

刚开始看到这题，哈希表应该是大多数人都能想到的，且复杂度要求都能满足。就是遍历数组，把每个数的平方放入哈希表中去重即可。
但是这种想法很难通过面试，因为有序的条件没有利用到。

正解：

有序数组普遍是利用双指针问题求解，这里也一样。每次检查头尾指针的和是等于0、大于0还是小于0.根据这3中情况分析。注意数字可能重复，需要去重。

int diffSquareNum(const vector<int>& nums) {
	if (!nums.size())
		return 0;
	int left = 0;
	int right = nums.size() - 1;
	int sum = 0;
	while (left <= right) {
		if (nums[left] + nums[right] == 0) {
			sum++;
			int t = nums[left];
			//这里是为了去重
			while (left <= right && nums[left] == t)
				left++;
			while (left <= right && nums[right] == -t)
				right--;
		}
		else if (nums[left] + nums[right] < 0) {
			sum++;
			int t = nums[left];
			while (left <= right && nums[left] == t)
				left++;
		}
		else{
			sum++;
			int t = nums[right];
			while (left <= right && nums[right] == t)
				right--;
		}
	}
	return sum;
}

2 买卖股票的最佳时机

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if ( prices.size()<1)
            return 0;
        int res=0;
        int min=prices[0];
        for(int i=1;i<prices.size();i++){
            if (prices[i]<min)
                min = prices[i];
            if (prices[i]-min>res)
                res = prices[i] - min;
        }
        return res;
    }
};

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

#include <iostream>

bool duplicate(int numbers[], int length, int * duplication){
    if(numbers == nullptr || length <= 0){
        return false;
    }
    for(int i = 0;i < length;i ++){
        if(numbers[i] < 0 || numbers[i] > length - 1)
            return false;
    }
    for(int i = 0;i < length;i ++){
        while(numbers[i] != i){
            if(numbers[i] == numbers[numbers[i]]){
                * duplication = numbers[i];
                return true;
            }
            int temp = numbers[i];
            numbers[i] = numbers[temp];
            numbers[temp] = temp;
        }
    }
    return false;
}

int main(int argc, const char * argv[]) {
    int numbers[] = {3, 1, 2, 0, 2, 5, 3};
    int dup;
    if(duplicate(numbers, 7, & dup)){
        std::cout << dup << std::endl;
    }
}

4 二分查找

/*折半查找*/
int Binary_Search(int a*,int n,int key)
{
    int low,high,mid;
    low=1;     /*定义最底下标为记录首位*/
    high=n;    /*定义最高下标为记录末位*/
    while(low<=high)
    {
        mid=(low+high)/2;    /*折半*/
        if(key<a[mid])
            high=mid-1;
        if(key>a[mid])
            low=mid+1;
        else
            return mid;
    }
    return 0;
}

vector - milkandbread/summary-interview GitHub Wiki

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️