爬楼梯：
假设你正在爬楼梯。需要
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; // 初始化最大利润为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);
}
