interview_questions/算法面试题/数组和字符串.cpp

#include "数组和字符串.h"
#include <algorithm>

void 数组和字符串::merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

}

int 数组和字符串::removeElement(vector<int>& nums, int val) {
	int count = 0;
	for (int i = 0; i < nums.size(); i++) {
		if (nums[i] != val) {
			nums[count] = nums[i];
			count++;
		}
	}
	return count;
}

int 数组和字符串::removeDuplicates(vector<int>& nums) {
	set<int> mySet;
	int count = 0;
	for (int i = 0; i < nums.size(); i++) {
		// set的contains(value)需要20版本后才支持，判断是否存在
		if (mySet.find(nums[i]) == mySet.end()) {
			mySet.insert(nums[i]);
			nums[count] = nums[i];
			count++;
		}
	}
	return count;
}

// 因为nums是有序的，可以使用双指针，同一个值的起点和当前值，偏差2后不要
int 数组和字符串::removeDuplicates80(vector<int>& nums) {
	map<int, int> myMap;
	int count = 0;
	for (int i = 0; i < nums.size(); i++) {
		// map的contains(value)需要20版本后才支持，可以使用myMap.count(nums[i]),判断是否存在
		auto it = myMap.find(nums[i]);
		if (it == myMap.end()) {
			myMap[nums[i]] = 1;		// 更改值为1，有一个了
			nums[count] = nums[i];
			count++;
		} else if (it->second == 1) {
			it->second = 2;
			nums[count] = nums[i];
			count++;
		}
	}
	return count;
}

// nums = [1,2,3,4,5,6,7], k = 3。输出：[5,6,7,1,2,3,4]
void 数组和字符串::rotate(vector<int>& nums, int k) {
	k = k % nums.size();
	vector<int> vec(nums);
	for (int i = 0; i < k; i++) {
		nums[i] = vec[vec.size() - k + i];
	}
	for (int i = k; i < nums.size(); i++) {
		nums[i] = vec[i - k];
	}
}

int 数组和字符串::maxProfit(vector<int>& prices) {
#if debug
	int max = 0;
	for (int i = prices.size() - 2; i > 0; i--) {
		if (prices[i - 1] < prices[i] && prices[i] < prices[i + 1])
			prices.erase(prices.begin() + i);
	}
	for (int i = 0; i < prices.size() - 1; i++) {
		for (int j = i + 1; j < prices.size(); j++) {
			int offset = prices[j] - prices[i];
			if (offset > max)
				max = offset;
		}
	}
	return max;
#endif

	if (prices.empty()) {
		return 0;
	}

	int minPrice = prices[0]; // 初始化最低价格为第一天的价格
	int maxProfit = 0;        // 初始化最大利润为 0

	for (int i = 1; i < prices.size(); ++i) {
		if (prices[i] < minPrice) {
			// 如果当前价格比最低价格还低，更新最低价格
			minPrice = prices[i];
		}
		else {
			// 否则，计算当前利润并更新最大利润
			maxProfit = std::max(maxProfit, prices[i] - minPrice);
		}
	}

	return maxProfit;
}

int 数组和字符串::maxProfitAll(vector<int>& prices) {
	if (prices.empty() || prices.size() < 2)
		return 0;

	bool start = false;
	int min;
	int total = 0;
	int i = 0;
	for (; i < prices.size() - 1; i++) {
		if (prices[i] < prices[i + 1] && !start) {
			min = prices[i];
			start = true;
		} else if (start && prices[i] > prices[i + 1]) {
			total += (prices[i] - min);
			start = false;
		}
	}
	if (start && prices[i] > min)
		total += (prices[i] - min);
	return total;
}

bool 数组和字符串::canJump(vector<int>& nums) {
	int k = 0;
	for (int i = 0; i < nums.size(); i++) {
		if (i > k) return false;
		k = max(k, i + nums[i]);
	}
	return true;
}

int 数组和字符串::jump(vector<int>& nums) {
	int n = nums.size();
	int maxPos = 0;      // 当前跳跃能到达的最远下标
	int nextMaxPos = 0;  // 下次跳跃能到达的最远下标
	int res = 0;
	for (int i = 0; i < n; ++i) {
		if (i > maxPos) {  // 超过了当前跳跃的最远距离，需要再跳一次
			maxPos = nextMaxPos;
			++res;
		}
		nextMaxPos = max(nextMaxPos, i + nums[i]);  // 更新最远距离
	}
	return res;
}

int 数组和字符串::findKthLargest(vector<int>& nums, int k) {
	sort(nums.begin(), nums.end());
	reverse(nums.begin(), nums.end());
	return nums[k - 1];
}

int 数组和字符串::hIndex(vector<int>& citations) {
	sort(citations.begin(), citations.end());
	reverse(citations.begin(), citations.end());
	for (int i = 0; i < citations.size(); i++) {
		int citNums = i + 1;
		if (citations[i] < citNums)
			return i;
	}
	return citations.size();
}

// 获取set中随机值
int 数组和字符串::getRandom(set<int> mySet) {
	random_device rd;
	mt19937 gen(rd()); // Mersenne Twister 引擎
	uniform_int_distribution<> dis(0, mySet.size() - 1); // 生成 [0, 99] 的整数
	// 生成随机数
	int randomVal = dis(gen);
	auto it = next(mySet.begin(), randomVal);
	return *it;
}

int 数组和字符串::candy(vector<int>& ratings) {
	if (ratings.size() <= 1)
		return ratings.size();

	int count = 0;
	vector<int> vec{ 1 };
	int start = 0;		// 设置起始点
	for (int i = 1; i < ratings.size(); i++) {
		if (ratings[i - 1] < ratings[i])
			vec.push_back(vec[i - 1] + 1);
		else
			vec.push_back(1);
	}
	count += vec[vec.size() - 1];
	for (int i = ratings.size() - 2; i >= 0; i--) {
		int value;
		if (ratings[i] > ratings[i + 1])
			value = vec[i + 1] + 1;
		else
			value = 1;

		vec[i] = max(value, vec[i]);
		count += vec[i];
	}
	return count;
}

int 数组和字符串::trap(vector<int>& height) {
	// 在第一个和最后一个添加0
	height.insert(height.begin(), 0);
	height.push_back(0);

	vector<int> vec;
	int count = 0;
	for (int i = 1; i < height.size() - 1; i++) {
		// 上升或下降，获取每个地方的高峰位置
		if ((height[i] > height[i - 1] && height[i] >= height[i + 1]) ||
			(height[i] >= height[i - 1] && height[i] > height[i + 1])) {
			vec.push_back(i);
		}
	}
	// 去除掉高点小于小边高点的
	bool dataOk = false;
	while (!dataOk) {
		dataOk = true;
		for (int i = vec.size() - 2; i > 0; i--) {
			if (height[vec[i - 1]] >= height[vec[i]] && height[vec[i]] <= height[vec[i + 1]])
			{
				vec.erase(vec.begin() + i);
				dataOk = false;
			}
		}
	}
	// 计算最终结果
	for (int i = 0; !vec.empty() && i < (int)(vec.size() - 1); i++) {
		// 先找出最高点
		int max = min(height[vec[i]], height[vec[i + 1]]);
		for (int j = vec[i] + 1; j < vec[i + 1]; j++) {
			int offset = max - height[j];
			count += offset > 0 ? offset : 0;
		}
	}
	return count;
}


string 数组和字符串::intToRoman(int num) {
	string str = "";
	string rome[] = { "I", "V", "X", "L", "C", "D", "M" };
	int values[] = { 1, 5, 10, 50, 100, 500, 1000 };

	for (int i = sizeof(values) / sizeof(values[0]) - 1; i >= 0; i--) {
		int val = num / values[i];
		if (i % 2 == 1 && num / values[i - 1] == 9)
		{
			str += rome[i - 1] + rome[i + 1];
			num %= values[i--];
			num %= values[i];
		}
		else {
			num %= values[i];
			if (val == 4)
				str += rome[i] + rome[i + 1];
			else
			{
				for (int j = 1; j <= val; j++) {
					str += rome[i];
				}
			}
		}
	}
	return str;
}

vector<string> 数组和字符串::fullJustify(vector<string>& words, int maxWidth) {
	vector<string> vec;
	int start = 0;
	int len = 0;
	int spaceNum = maxWidth;
	for (int i = 0; i < words.size(); i++) {
		len += words[i].size();
		spaceNum -= words[i].size();
		// 至少一个空格
		if (start != i)
			len += 1;

		if (len > maxWidth) {
			string str;
			// 处理start到i-1
			spaceNum += words[i].size();
			// 间隔的空格个数需要减一
			int wordNum = i - start - 1;
			if (wordNum == 1)
			{
				str += words[start];
				str.append(spaceNum, ' ');
			}
			else if (wordNum > 1) {
				int eachSpaceLen = spaceNum / wordNum;	// 空格数
				int rem = spaceNum % wordNum;			// 前面多一个字节的数量
				str += words[start];
				for (int j = 1; j <= wordNum; j++) {
					str.append(eachSpaceLen, ' ');
					if (j < rem) {
						str += " ";
					}
					str += words[start + j];
				}
			} else {
				str += words[start];
				str.append(spaceNum, ' ');
			}
			// 更新起始点
			start = i;
			spaceNum = maxWidth;
			vec.push_back(str);
			len = words[i].size();
		}
	}
	// 最后start开始的单独处理
	string lastStr;
	for (int i = start; i < words.size(); i++) {
		lastStr += words[i] + " ";
	}
	lastStr.append(maxWidth - lastStr.length(), ' ');
	if (lastStr.length() > maxWidth)
		lastStr = lastStr.substr(0, maxWidth);
	vec.push_back(lastStr);
	return vec;
}

int 数组和字符串::strStr(string haystack, string needle) {
	for (int i = 0; i < haystack.length(); i++) {
		bool ok = true;
		for (int j = 0; j < needle.length(); j++) {
			if (i + j >= haystack.size() || haystack[i + j] != needle[j])
			{
				ok = false;
				break;
			}
		}
		if (ok)
			return i;
	}
	return -1;
}

string 数组和字符串::reverseWords(string s) {
	// 去头去尾
	for (int i = 0; i < s.length(); i++) {
		if (s[i] != ' ') {
			s.erase(0, i);
			break;
		}
	}
	for (int i = 1; i <= s.length(); i++) {
		int n = s.length() - i;
		if (s[n] != ' ') {
			if (n < s.length() - 1)
				s.erase(n + 1, i);
			break;
		}
	}
	// 得到字符数组
	vector<string> vec;
	string str;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] != ' ')
			str += s[i];
		else {
			if (str != "")
				vec.push_back(str);
			str = "";
		}
	}
	vec.push_back(str);
	string ans;
	for (int i = vec.size() - 1; i > 0; i--)
		ans += vec[i] + " ";
	ans += vec[0];
	return ans;
}

string 数组和字符串::convert(string s, int numRows) {
	vector<string> temp(numRows);
	string res;
	if (s.empty() || numRows < 1) return res;
	if (numRows == 1) return s;
	for (int i = 0; i < s.size(); i++) {
		int ans = i / (numRows - 1);
		int cur = i % (numRows - 1);
		if (ans % 2 == 0) {  //结果为偶数或0
			temp[cur].push_back(s[i]); //按余数正序保存
		}
		if (ans % 2 != 0) {  //结果为奇数
			temp[numRows - cur - 1].push_back(s[i]); //按余数倒序保存
		}
	}
	for (int i = 0; i < temp.size(); i++) {
		res += temp[i];
	}
	return res;
}