个人学习编程(3-18) leetcode刷题
爬楼梯：
假设你正在爬楼梯。需要
n阶你才能到达楼顶。每次你可以爬
1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？示例 1：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶示例 2：
输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
#include <stdio.h>
int climbStairs(int n) {
if (n == 1) {
return 1;
}
int dp[n + 1]; // 用来存储爬楼梯的方法数
dp[0] = 1; // 从地面到第0阶只有一种方式
dp[1] = 1; // 到第1阶也只有一种方式
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 每次可以选择从 i-1 阶或者 i-2 阶到达
}
return dp[n]; // 返回爬到第 n 阶的方法数
}
int main() {
int n;
printf("请输入楼梯的总阶数 n:");
scanf("%d", &n);
int result = climbStairs(n);
printf("爬到第 %d 阶楼顶的方法数是: %d\n", n, result);
return 0;
}
多数元素：
给定一个大小为
n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3] 输出：3示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2
双重循环（不能过全部）：
arr[nums[i]]来将 数组一的值当做本数组的下标，本数组的值，为上个数组出现的次数，然后只需要遍历值的大小，最后把本数组最大值对应的下标i 返回，即使上个数组最大出现次数的值。
问题：
负数索引问题：你需要处理负数值的情况。由于数组索引不能是负数，可以通过调整数组索引的方法来处理负数。
- 你可以将每个元素值
nums[i]加上一个常量值，使得所有索引变为正数。比如，arr[nums[i] + 500000]可以把负数映射到正数索引。- 这样，
nums[i]的值范围 [-1000000, 1000000] 会映射到arr数组的索引范围 [0, 1000000]。代码逻辑改进：在循环中，你只需要更新每个元素的出现次数，而不是每次都重置
count，并且你应该避免重复存储。
#include <stdio.h>
int majorityElement(int* nums, int numsSize) {
int count;
int times = numsSize / 2;
int arr[1000001] = {0}; // 调整数组大小
int index = 0;
int max = 0;
for (int i = 0; i < numsSize; i++) {
// 处理负数索引问题：将nums[i]映射到正数索引
int idx = nums[i] + 500000; // 偏移值，使索引始终为正
arr[idx]++; // 直接增加出现次数
// 记录最大出现次数
if (arr[idx] > max) {
max = arr[idx];
index = nums[i];
}
}
return index;
}
int main() {
int nums[] = {-1, 1, 1, 1, 2, 1};
int numsSize = 6;
printf("Majority Element: %d\n", majorityElement(nums, numsSize));
return 0;
}
摩尔投票法：
#include <stdio.h>
int majorityElement(int* nums, int numsSize) {
int count = 0;
int candidate = 0;
// 摩尔投票法
for (int i = 0; i < numsSize; i++) {
if (count == 0) {
candidate = nums[i]; // 找到新的候选元素
}
count += (nums[i] == candidate) ? 1 : -1; // 如果是候选元素，计数加 1，否则减 1
}
return candidate; // 最终候选元素即为多数元素
}
int main() {
int nums[] = {3, 2, 3};
int numsSize = 3;
printf("Majority Element: %d\n", majorityElement(nums, numsSize));
int nums2[] = {2, 2, 1, 1, 1, 2, 2};
int numsSize2 = 7;
printf("Majority Element: %d\n", majorityElement(nums2, numsSize2));
return 0;
}
买卖股票的最佳时机:
给定一个数组
prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回
0。示例 1：
输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。示例 2：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
#include <stdio.h>
#include <bits/stdc++.h>
int maxProfit(int* prices, int pricesSize) {
int i;
int min = prices[0]; // 初始化最小买入价格为第一个价格
int max_profit = 0; // 初始化最大利润为0
for (i = 1; i < pricesSize; i++) { // 从第二天开始
if (prices[i] < min) {
min = prices[i]; // 如果当前价格低于最小价格，更新最小价格
} else {
// 计算当前价格和最小价格的利润，并更新最大利润
int profit = prices[i] - min;
if (profit > max_profit) {
max_profit = profit;
}
}
}
return max_profit; // 返回最大利润
}
int main() {
int nums[6] = {7, 1, 5, 3, 6, 4};
int m = maxProfit(nums, 6);
printf("%d\n", m); // 输出最大利润
return 0;
}
SingleNumber：
找到数组当中的单一的数字
双重循环：
#include <stdio.h>
#include <bits/stdc++.h>
int singleNumber(int *nums,int numsSize){
int i,j;
for (int i = 0; i < numsSize; i++)
{
//printf("%d\n",nums[i]);
int count = 0;
for (j = 0; j < numsSize; j++){
if (nums[j] == nums[i]){
count++;
}
}
if (count == 1){
return nums[i];
}
}
return -1;
}
int main() {
int arr[]={2,2,3,3,5};
int singleNumber(int *nums,int numsSize);
int a = singleNumber(arr,5);
printf("%d\n",a);
}亦或：
#include <stdio.h>
#include <bits/stdc++.h>
int singleNumber(int *nums,int numsSize){
int n = nums[0];
int i;
for(i = 1;i < numsSize;i++){
n ^= nums[i];
}
return n;
//因为亦或，相同的元素亦或就是0,0亦或任何数还是任何数
}
int main() {
int arr[]={2,2,3,3,5};
int singleNumber(int *nums,int numsSize);
int a = singleNumber(arr,5);
printf("%d\n",a);
}找一个数列的子序列的最大值
双重循环：
#include <stdio.h>
#include <bits/stdc++.h>
int maxSubArray(int* nums,int numsSize){
int max = nums[0];
printf("i j : sum\n ---------");
int i,j,k;
for (i = 0;i < numsSize; i++){
for ( j = 0; j < numsSize; j++)
{
int sum = 0;
for (int k = i; k < j; k++)
{
sum += nums[k];
}
if (sum > max)
{
max = sum;
}
printf("%d %d : %2d (%d)\n",i,j,sum,max);
}
}
return max;
}
int main() {
int maxSubArray(int* num,int numsSize);
int arr[] = {-2,1,-3,4,-1,2,1,-5,4};
int max = arr[0];
max = maxSubArray(arr,9);
printf("%d",max);
}记录最大值：
for (int i = 0; i < numsSize; i++){
for (int j = i; j < numsSize; j++){
sum += nums[j];
if (sum > max){
max = sum;
}
}}
这段代码会记录从 i=0到numsSize-1的位置，再到 i=1到numsSize-1位置，慢慢记录他们的和赋值给max。
#include <stdio.h>
#include <bits/stdc++.h>
int maxSubArray(int* nums,int numsSize){
int max = nums[0];
for (int i = 0; i < numsSize; i++){
int sum = 0;
for (int j = i; j < numsSize; j++){
sum += nums[j];
if (sum > max){
max = sum;
}
}
}
return max;
}
int main() {
int maxSubArray(int* num,int numsSize);
int arr[] = {-2,1,-3,8,-1,2,1,-5,4};
int max = arr[0];
max = maxSubArray(arr,9);
printf("%d",max);
}