火车出战
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long cat[40];
int n,t;
void init(){
memset(cat,0,sizeof(cat));
cat[0]=cat[1]=1;
for(int i=2;i<36;i++)
{
for(int j=0;j<i;j++)
cat[i]+=cat[j]*cat[i-1-j];
}}int main(){
init();
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%lld\n",cat[n]);
}
return 0;}
4.协助工作
//4.协助工作
#include <stdio.h>
int main()
{
int h,w,a,b,c;
while((scanf("%d%d%d%d",&h,&w,&a,&b))!=EOF)
{
c=h*h+w*w;
if(c>=a*a || c>=b*b)
printf("Just do it.\n");
else
printf("We have a problem.\n");
}
return 0;
}
#include<iostream>
using namespace std;
int main() {
int h, w, a, b;
//h：门的高度，w：门的宽度
//a、b：黑板的两个边长
do
{
cin >> h >> w >> a >> b;
int door = sqrt(h * h + w * w);
int shortEdge = a < b ? a : b;
if (shortEdge <= door) {
cout << "Just do it.";
}
else
{
cout << "We have a problem.";
}
cout << endl;
} while (cin.get() != EOF);
}
import ast
class Solution:
def problem(self, nums):
c = nums[0] ** 2 + nums[1] ** 2
if c >= nums[2] ** 2 or c >= nums[3] ** 2:
print("Just do it.\n")
else:
print("We have a problem.\n")
def main():
list1 = ast.literal_eval(input())
obj = Solution()
print(obj.problem(list1))
if __name__ == '__main__':
main()
15.炒股
// 15.炒股
#include <iostream>
#include<vector>
using namespace std;
int CountUp(vector<int>& days) {
int sum = 0;
int max = 0;
for (int i = 0; i + 1 < days.size(); i++) {
int begin = i;
if (days[begin] < days[begin + 1]) {
sum++;
max = max > sum ? max : sum;
}
else
{
sum = 1;
}
}
return max;
}
int main()
{
vector<int> nums;
while (true)22:42 2021/12/27
{
int temp;
cin >> temp;
nums.push_back(temp);
if (cin.get() == '\n') break;
}
cout << CountUp(nums) << endl;
system("PAUSE");
return 0;
}
1.最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），
返回其最大和。
//1.最大子序和
#include <iostream>
#include <vector>
using namespace std;
int maxSubArray(vector<int>& nums) {
//此时不确定数组的长度
int MaxSum = 0;
int PreSum = 0;
for (int i = 0; i < nums.size(); i++) {
PreSum += nums[i];
if (PreSum > MaxSum) {
MaxSum = PreSum;
}
if (PreSum <= 0) PreSum = 0;
}
return MaxSum;
}
int main() {
int n;
//cout << "请输入元素总个数：";
cin >> n;
vector<int> nums;
//cout << "清输入各元素：";
for (int i = 0; i < n; i++) {
int num;
cin >> num;
nums.push_back(num);
}
cout << maxSubArray(nums);
return 0;
}
2.买卖股票的最佳时机
给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。
//2.股票
#include <iostream>
#include <vector>
using namespace std;
int maxProfit(vector<int>& prices)
{
int MaxProfit = 0;
for (int i = 0; i < prices.size(); i++)
{
for (int j = i + 1; j < prices.size(); j++)
{
int temp = prices[j] - prices[i];
if (temp > MaxProfit)
{
MaxProfit = temp;
}
}
}
return MaxProfit;
}
int main() {
int n;
cout << "请输入总天数：";
cin >> n;
vector<int> prices;
cout << "清输入每天的股票价格：";
for (int i = 0; i < n; i++) {
int price;
cin >> price;
prices.push_back(price);
}
cout << maxProfit(prices);
return 0;
}
3.The missing integer
现在有 9个整数，这 9个整数都在 1到 10 之间（含 1 和 10），而且每个整数只出现了一次。
因此，肯定会有一个整数缺失。现在把这个艰难的任务交给你，让你找到缺失的整数。
//3.The missing integer
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int findInteger(vector<int>& nums) {
sort(nums.begin(), nums.end());//升序
int i;
for (i = 1; i <= nums.size(); i++) {
if (nums[i - 1] != i)
break;
}
return i;
}
int main()
{
int n = 9;
vector<int> nums;
//cout << "输入这些整数：";
for (int i = 0; i < n; i++) {
int temp;
cin >> temp;
nums.push_back(temp);
}
cout << "The missing integer is:" << findInteger(nums);
}
5.假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
//5.分发饼干
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int KidSum = 0;
int i = 0;
int j = 0;
while (i < s.size() && j < g.size()) {
if ( g[j] <= s[i] ) {
j++;
i++;
KidSum++;
}
else {
i++;
}
}
return KidSum;
}
int main() {
vector<int> vec1{ 1,2 }, vec2{ 1,2,3 };
cout << findContentChildren(vec1, vec2);
system("PAUSE");
return 0;
}
6.排列的数目
给定一个由不同正整数组成的数组 nums，和一个目标整数target。
请从 nums 中找出并返回总和为 target 的元素组合的个数。
//6.排列的数目
#include<iostream>
#include<vector>
using namespace std;
int combinationSum4(vector<int>& nums, int target) {
//动态规划方法
vector<int> dp(target + 1);
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int& num : nums) {
if (num <= i && dp[i - num] < INT_MAX - dp[i]) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
int main() {
int n;
int target;
vector<int> nums;
cout << "请输入数组元素个数：";
cin >> n;
cout << "请输入元素：";
for (int i = 0; i < n; i++) {
int temp;
cin >> temp;
nums.push_back(temp);
}
cout << "请输入目标整数：";
cin >> target;
cout <<"组合个数："<< combinationSum4(nums, target)<<endl;
system("PAUSE");
return 0;
}
7.不同路径
一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start”）。
//7.不同路径
#include<iostream>
using namespace std;
int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) return 0;
if (m == 1 && n == 1) return 1;
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}
int main() {
int m, n;
cout << "m = ";
cin >> m;
cout << "n = ";
cin >> n;
cout << uniquePaths(m, n)<<endl;
system("PAUSE");
return 0;
}
8.Torry从小喜爱数学。一天，老师告诉他，像2、3、5、7……这样的数叫做质数。
Torry突然想到一个问题，前10、100、1000、10000……个质数的乘积是多少呢？
//8.Torry的困惑
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
int n, i, j, count = 0;
long long sum = 1;
cin >> n;
for (i = 2; i <= sqrt(10000); i++)
{
for (j = 2; j < i; j++)
{
if (i % j == 0)
break;
}
if (j >= i)
{
count++;
sum = (sum * i) % 50000;
if (count == n)
break;
}
}
cout << sum << endl;
return 0;
}
9.第 k 个数
有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。// 9.第k个数
#include <iostream>
#include <stdio.h>
using namespace std;
int min(int a, int b, int c){
int minNum = a < b ? a : b;
minNum = minNum < c ? minNum : c;
return minNum;
}
int findUglyNumber(int k){
int* pArray = new int[k + 1];
pArray[0] = 1;
int* p3, * p5, * p7;
p3 = p5 = p7 = pArray;
int count = 0;
int minNum;
while (count < k){
count++;
minNum = min(*p3 * 3, *p5 * 5, *p7 * 7);
pArray[count] = minNum;
while (*p3 * 3 <= minNum){
p3++;
}
while (*p5 * 5 <= minNum){
p5++;
}
while (*p7 * 7 <= minNum){
p7++;
}
}
int result = pArray[k];
delete[] pArray;
return result;
}
int main(){
int k;
cin >> k;
cout << findUglyNumber(k);
return 0;
}
10.删除有序数组中的重复项
给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。
// 10.删除有序数组中的重复项
#include<iostream>
#include<vector>
using namespace std;
int DeleteDuplicate(vector<int>& nums) {
if (nums.empty())
return 0;
int low = 0;
for (int fast = 1; fast < nums.size(); fast++) {
if (nums[fast] != nums[low]) {
low++;
nums[low] = nums[fast];
}
}
return low+1;
}
int main() {
int n;
cout << "输入数组元素个数：";
cin >> n;
vector<int> nums;
cout << "输入元素：";
for (int i = 0; i < n; i++) {
int temp;
cin >> temp;
nums.push_back(temp);
}
int size = DeleteDuplicate(nums);
cout << "去除重复项后的数组长度：" << size << endl;
cout << "nums = ";
for (int i = 0; i < size; i++) {
cout << nums[i] << " ";
}
return 0;
}
11.无重叠区间
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
// 11.无重叠区间
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return 0;
}
sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
return u[1] < v[1];
});
int n = intervals.size();
int right = intervals[0][1];
int ans = 1;
for (int i = 1; i < n; ++i) {
if (intervals[i][0] >= right) {
++ans;
right = intervals[i][1];
}
}
return n - ans;
}
int main() {
int n;
cout << "输入区间个数：";
cin >> n;
vector<vector<int>> out(n, vector<int>(2));
for (int i = 0; i < n; i++) {
cout << "输入第" << i + 1 << "个区间的起始点：";
cin >> out[i][0] >> out[i][1];
}
cout<<"移除数量："<<eraseOverlapIntervals(out);
return 0;
}
12.周期串
// 12.周期串
#include<iostream>
#include<string>
using namespace std;
int main()
{
int t;
char str[80];
cin >> t;
while (t--) {
cin >> str;
int len = strlen(str);
for (int i = 1; i <= len; i++) {//假设 i 是周期
int flag = 1;//i 是周期的话，flag = 1，不是的话 flag 为 0
if (len % i == 0) {//假设 i 是周期，肯定可以被长度整除
for (int j = i; j < len; j++) {
if (str[j] != str[j % i]) {
flag = 0;
break;
}
}
if (flag == 1) {
cout << i << endl;
break;
}
}
}
}
return 0;
}
13.拼车
// 13.拼车
#include <iostream>
#include<vector>
#include<map>
using namespace std;
bool carPooling(vector<vector<int>>& trips, int capacity)
{
map<int, int> tmp;
for (auto it : trips)
{
for (int i = it[1]; i < it[2]; i++)
{
tmp[i] += it[0];
}
}
for (auto it : tmp)
{
if (it.second > capacity)
{
return false;
}
}
return true;
}
int main()
{
int n;
int cap;
cout << "行程数：";
cin >> n;
cout << "空位数：";
cin >> cap;
vector<vector<int>> trips(n, vector<int>(3));
for (int i = 0; i < n; i++) {
cout << "输入第" << i + 1 << "个行程的信息：";
cin >> trips[i][0] >> trips[i][1] >> trips[i][2];
}
if (carPooling(trips, cap)) {
cout << "true" << endl;
}
else
{
cout << "false" << endl;
}
return 0;
}
14.最小操作次数使数组元素相等
给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。
返回让数组所有元素相等的最小操作次数。
// 14.最小操作次数使数组元素相等
#include <iostream>
#include<vector>
using namespace std;
int minMoves(vector<int>& nums) {
int n = nums.size();
if (n == 0 || n == 1)return 0;
int s = 0;
int min = nums[0];
for (int i = 0; i < n; i++) {
if (nums[i] < min)min = nums[i]; //不用sort函数，o(n)找到最小值
}
for (int i = 0; i < n; i++) {
s = s + nums[i] - min;
}
return s;
}
int main()
{
vector<int> nums;
while (true)
{
int temp;
cin >> temp;
nums.push_back(temp);
if (cin.get() == '\n') break;
}
cout << minMoves(nums)<<endl;
system("PAUSE");
return 0;
}
16.替换空格
// 16.替换空格
#include <iostream>
#include<string>
using namespace std;
string replaceSpace(string s) {
int og_len = s.size();
int count_blank = 0;
for (int i = 0; i < og_len; i++) {
if (s[i] == ' ') count_blank++;
}
s.resize(og_len + count_blank * 2);
int new_len = s.size();
for (int i = og_len - 1, j = new_len - 1; i < j; i--, j--) {
if (s[i] != ' ') s[j] = s[i];
else {
s[j - 2] = '%';
s[j - 1] = '2';
s[j] = ' 0';
j -= 2;
}
}
return s;
}
int main() {
string s;
getline(cin, s);
cout << replaceSpace(s) << endl;
}
17.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值target的那两个整数，
并返回它们的数组下标。
// 17.两数之和
#include <iostream>
#include<vector>
using namespace std;
void twoSum(vector<int>& nums, int target) {
int n = nums.size();
int a, b;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
a = i;
b = j;
}
}
}
cout << "[" << a << "," << b << "]" << endl;
}
int main()
{
int tar;
vector<int> nums;
cout << "目标：";
cin >> tar;
cout << "数组：";
do
{
int temp;
cin >> temp;
nums.push_back(temp);
} while (cin.get() != '\n');
twoSum(nums,tar);
system("PAUSE");
return 0;
}
18.种花问题
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。
// 18.种花问题
#include <iostream>
#include<vector>
using namespace std;
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int sum = flowerbed.size();
/*if(flowerbed.empty() || n > (sum+1)/2){ return false; }*/
if (n == 0) return true;
if (sum == 1) {
if (flowerbed[0] == 0) {
return true;
}
else {
if (n == 0) {
return true;
}
return false;
}
}
if (flowerbed[0] == 0 && sum >= 2) {
if (flowerbed[1] == 0) {
n--;
flowerbed[0] = 1;
}
}
int i = 1;
while (i < (sum - 1) && n != 0) {
if (flowerbed[i] == 0 && flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
flowerbed[i] = 1;
n--;
}
i++;
}
if (flowerbed[sum - 1] == 0 && sum >= 2 && n != 0) {
if (flowerbed[sum - 2] == 0) {
n--;
}
}
if (n == 0) {
return true;
}
return false;
}
int main()
{
int n;
vector<int> flowers;
cout << "n=";
cin >> n;
do
{
int t;
cin >> t;
flowers.push_back(t);
} while (cin.get()!='\n');
if (canPlaceFlowers(flowers, n)) {
cout << "true";
}
else
{
cout << "false";
}
}
19.三角形中最小路径之和
给定一个三角形 triangle ，找出自顶向下的最小路径和。
// 19.三角形中最小路径之和
#include <iostream>
#include<vector>
using namespace std;
int minimumTotal(vector<vector<int>>& triangle) {
for (int i = triangle.size() - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
triangle[i - 1][j] += min(triangle[i][j], triangle[i][j + 1]);
}
}
return triangle[0][0];
}
int main()
{
vector<vector<int>> triangle;
vector<int> t;
bool flag = true;
int temp;
while (flag){
do
{
cin >> temp;
if (!cin) {
flag = false;
break;
}
t.push_back(temp);
} while (cin.get()!='\n');
if (flag) {
triangle.push_back(t);
t.clear();
}
}
cout << minimumTotal(triangle) << endl;
return 0;
}
20.在排序数组中查找元素的第一个和最后一个位置
#include<iostream>
#include<vector>
using namespace std;
class Solution
{
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.empty() || target < nums.front() || target > nums.back()) //特殊情况
return { -1, -1 };
int l = 0, r = nums.size() - 1, mid;
int res1, res2;
//二分查找,分别找左右边缘
//注意不能找到左边缘再循环遍历到右边缘，因为可能整个数组都是这个数，这样复杂度就是变成n+logn了
while (l <= r) {
mid = (l + r) / 2;
if (nums[mid] >= target)
r = mid - 1;
else
l = mid + 1;
}
if (nums[l] != target)//没有瞒足条件的数组值
return{ -1, -1 };
res1 = l;
//从左边缘到最后开始继续二分找到右边缘
r = nums.size() - 1;
while (l <= r) {
mid = (l + r) / 2;
if (nums[mid] <= target)
l = mid + 1;
else
r = mid - 1;
}
res2 = r;
return { res1, res2 };
}
};
int main() {
Solution s;
vector<int> nums;
int tar;
}
21.分解正整数
将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。
编程求出正整数N的所有整数分解式子。
#include<iostream>
using namespace std;
int s[100];//拆分结果保存在这个数组里
int top;//记录个数
int total, n;//累加数和所求数
int k;
void dfs(int index)
{
int i;
if (total == n)//满足打印出来
{
printf("%d=", n);
for (i = 0; i < top - 1; i++)
printf("%d+", s[i]);
k++;
if (k == 4 || top == 1)//四个或最后一个了一换行，换行时的特殊讨论
{
k = 0;
printf("%d\n", s[top - 1]);
}
else
printf("%d;", s[top - 1]);
return;
}
if (total > n) //累加大于所需跳出
return;
for (i = index; i <= n; i++)
{
total += i;
s[top++] = i; //将每次加的数保存在数组里
dfs(i);
total -= i;
s[--top]; //回退
}
}
int main()
{
while (cin >> n)
{
k = 0;
top = 0;
total = 0;
dfs(1);
}
return 0;
system("pause");
}
22.物品装箱问题
//22.物品装箱问题
#include<iostream>
using namespace std;
int main() {
int n;
cin >> n;
int a[50], b[50], c[50];
for (int i = 0; i < n; i++) {
cin >> a[i];
b[i] = 100;
}
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i] <= b[j]) {
b[j] = b[j] - a[i];
c[i] = j + 1;
sum = sum > c[i] ? sum : c[i];
break;
}
}
cout << a[i] << " " << c[i] << endl;
}
cout << sum;
}
23.恢复二叉搜索树
给你二叉搜索树的根节点root，该树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
//23.恢复二叉搜索树
#include<iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* firstmis;
TreeNode* secondmis;
TreeNode* pre;
void result(TreeNode* root)
{
if (root == NULL)
{
return;
}
result(root->left);
if (pre && pre->val > root->val)
{
if (firstmis == nullptr)
{
firstmis = pre;
secondmis = root;
}
else
{
secondmis = root;
}
}
pre = root;
result(root->right);
}
void recoverTree(TreeNode* root) {
firstmis = secondmis = pre = nullptr;
result(root);
int first = firstmis->val;
firstmis->val = secondmis->val;
secondmis->val = first;
}
};
24.通过删除字母匹配到字典里最长单词
给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，
该字符串可以通过删除 s 中的某些字符得到。
//24.通过删除字母匹配到字典里最长单词
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
static bool compared(string s1, string s2)
{
if (s1.length() == s2.length())
{
return s1 < s2;
}
else
{
return s1.length() > s2.length();
}
}
bool func(string a, string b)
{
int m = a.length();
int n = b.length();
int index = 0;
int i = 0;
while (index < m && i < n)
{
if (a[index] == b[i])
{
index++;
}
i++;
}
if (index == m)
{
return true;
}
else
{
return false;
}
}
string findLongestWord(string s, vector<string>& d)
{
int m = s.length();
int n = d.size();
vector<string> tmp;
for (int i = 0; i < n; i++)
{
if (func(d[i], s))
{
tmp.push_back(d[i]);
}
}
if (0 == tmp.size())
{
return "";
}
sort(tmp.begin(), tmp.end(), compared);
return tmp[0];
}
};
# dictionary:List[str]
class Solution:
def findLongestWord(self, s: str, dictionary) -> str:
res = ""
for t in dictionary:
i = j = 0
while i < len(t) and j < len(s):
if t[i] == s[j]:
i += 1
j += 1
if i == len(t):
if len(t) > len(res) or (len(t) == len(res) and t < res):
res = t
return res
def main():
s = input()
dic = list(input().split())
obj = Solution()
print(obj.findLongestWord(s,dic))
if __name__ == '__main__':
main()
25.三数之和
问题描述：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
请你找出所有和为 0 且不重复的三元组。
//25.三数之和
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
int num = nums.size();
sort(nums.begin(), nums.end());
if (nums.empty() || nums.front() > 0 || nums.back() < 0)
return {};
for (int i = 0; i < num - 2; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int head = i + 1;
int tail = num - 1;
while (head < tail) {
if (nums[head] + nums[tail] == -nums[i]) {
if (head == i + 1 || tail == num - 1) {
result.push_back(vector<int>{nums[i], nums[head], nums[tail]});
head++; tail--;
}
else if (nums[head] == nums[head - 1]) {
head++;
}
else if (nums[tail] == nums[tail + 1]) {
tail--;
}
else {
result.push_back(vector<int>{nums[i], nums[head], nums[tail]});
head++; tail--;
}
}
else if (nums[head] + nums[tail] < -nums[i]) {
head++;
}
else {
tail--;
}
}
}
return result;
}
};
from typing import List
def threeSum(nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
ans = list()
# 枚举 a
for first in range(n):
# 需要和上一次枚举的数不相同
if first > 0 and nums[first] == nums[first - 1]:
continue
# c 对应的指针初始指向数组的最右端
third = n - 1
target = -nums[first]
# 枚举 b
for second in range(first + 1, n):
# 需要和上一次枚举的数不相同
if second > first + 1 and nums[second] == nums[second - 1]:
continue
# 需要保证 b 的指针在 c 的指针的左侧
while second < third and nums[second] + nums[third] > target:
third -= 1
# 如果指针重合，随着 b 后续的增加
# 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if second == third:
break
if nums[second] + nums[third] == target:
ans.append([nums[first], nums[second], nums[third]])
return ans
def main():
list1 = list(map(int, input().split()))
print(threeSum(list1))
if __name__ == '__main__':
main()
26.用最少数量的箭引爆气球
//26.用最少数量的箭引爆气球
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points)
{
if (points.empty()) return 0;
//按末尾的值从小到大进行排序
sort(begin(points), end(points),
[](const vector<int>& a, const vector<int>& b) {
return (a[1] < b[1]);
});
//初始化的第一个参考值：第一个区间的右端点
int right = points[0][1];
int ans = 1;
for (auto n : points)
{
//当前区间的起点小于参考右端点时继续遍历
//当前区间的起点大于参考右端点时，说明需要另一支箭
//则结果进行累加，参考右端点重新赋值
if (n[0] > right)
{
right = n[1];
ans++;
}
}
return ans;
}
};
from typing import List
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
points.sort(key=lambda balloon: balloon[1])
pos = points[0][1]
ans = 1
for balloon in points:
if balloon[0] > pos:
pos = balloon[1]
ans += 1
return ans
def main():
print('请输入共几个气球')
n = int(input())
list1 = [[int(item) for item in input().split()] for row in range(n)]
obj = Solution()
print(obj.findMinArrowShots(list1))
if __name__ == '__main__':
main()
27.LLP
//27.LLP
#include<stdio.h>
#include<string.h>
int main() {
double molecularWeight(char ch);//函数声明
int n, tempn;//暂存数字
int flag;
double temp, ans;//temp-暂存分子量
char str[90];
scanf("%d", &n);
while (n--) {
tempn = 0;
temp = 0;
ans = 0;
flag = 1;
scanf("%s", str);
int i;
for (i = 0; i < strlen(str); i++) {
if (str[i] >= 'A' && str[i] <= 'Z') {
if (flag == 1) {//当前是字母并且前一位是字母
ans = ans + temp;
}
else {//当前是字母并且前面是数字
temp = temp * tempn;
ans = ans + temp;
tempn = 0;
}
temp = molecularWeight(str[i]);//求分子量
flag = 1;//当前位是字母，flag = 1
}
else {
tempn = tempn * 10 + str[i] - '0';//求数字
flag = 0;//当前位是数字，flag = 0
}
}
if (flag == 1) {//最后一位是字母的话，加上当前位的分子量
temp = molecularWeight(str[i - 1]);
ans = ans + temp;
}
else {//最后面是数字
ans = ans + temp * tempn;
}
printf("%.3lf\n", ans);
}
}
double molecularWeight(char ch) {
double temp;
if (ch == 'C') {
temp = 12.01;
}
else if (ch == 'H') {
temp = 1.008;
}
else if (ch == 'O') {
temp = 16;
}
else if (ch == 'N') {
temp = 14.01;
}
return temp;
}
28.二叉树中和为某一值的路径
输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。
//28.二叉树中和为某一值的路径
#include<iostream>
#include<vector>
using namespace std;
struct TreeNode
{
int val;
struct TreeNode* left;
struct TreeNode* right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
class Solution
{
public:
int sum = 0;
vector<int> temp;
int dfs(vector<vector<int>>& result, TreeNode* root, int number) {
if (root == NULL)
return 0;
sum += root->val;
temp.push_back(root->val);
if (sum == number && root->left == NULL && root->right == NULL) {
result.push_back(temp);
return 0;
}
else
{
if (root->left) {
dfs(result, root->left, number);
sum -= root->left->val;
temp.pop_back();
}
if (root->right) {
dfs(result, root->right, number);
sum -= root->right->val;
temp.pop_back();
}
}
return 0;
}
vector<vector<int>> FindPath(TreeNode* root, int expectNumber) {
vector<vector<int>> result;
dfs(result, root, expectNumber);
return result;
}
};
29.合并两个有序链表
//29.合并两个有序链表
#include<iostream>
using namespace std;
//Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
//如果head1 和 head2有一个为空 则直接返回另一个
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
ListNode* head = new ListNode(0);
//递归可以理解为之后的情况都处理好了 只需要解决好当前这步就行了
if (l1->val < l2->val) {
head = l1;
l1->next = mergeTwoLists(l1->next, l2);
}
else {
head = l2;
l2->next = mergeTwoLists(l1, l2->next);
}
return head;
}
};