个人学习编程(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 返回，即使上个数组最大出现次数的值。

问题：

1. 负数索引问题：你需要处理负数值的情况。由于数组索引不能是负数，可以通过调整数组索引的方法来处理负数。

   • 你可以将每个元素值 nums[i] 加上一个常量值，使得所有索引变为正数。比如，arr[nums[i] + 500000] 可以把负数映射到正数索引。
   • 这样，nums[i] 的值范围 [-1000000, 1000000] 会映射到 arr 数组的索引范围 [0, 1000000]。

2. 代码逻辑改进：在循环中，你只需要更新每个元素的出现次数，而不是每次都重置 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;    // 初始化最大利润为0for (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);
}