个人学习编程(3-16) leetcode刷题
有多少小于当前数字的数字:
给你一个数组
nums
,对于其中每个元素nums[i]
,请你统计数组中比它小的所有数字的数目。换而言之,对于每个
nums[i]
你必须计算出有效的j
的数量,其中j
满足j != i
且nums[j] < nums[i]
。以数组形式返回答案。
示例 1:
输入:nums = [8,1,2,2,3] 输出:[4,0,1,1,3] 解释: 对于 nums[0]=8 存在四个比它小的数字:(1,2,2 和 3)。 对于 nums[1]=1 不存在比它小的数字。 对于 nums[2]=2 存在一个比它小的数字:(1)。 对于 nums[3]=2 存在一个比它小的数字:(1)。 对于 nums[4]=3 存在三个比它小的数字:(1,2 和 2)。示例 2:
输入:nums = [6,5,4,8] 输出:[2,1,0,3]示例 3:
输入:nums = [7,7,7,7] 输出:[0,0,0,0]
#include <stdio.h>
void countSmallerNumbers(int nums[],int n,int result[]){
//对每个元素nums[i],遍历整个数组来计数
for (int i = 0; i < n; i++)
{
int count = 0;
for (int j = 0; j < n; j++)
{
if (nums[i] > nums[j])
{
count++;
}
}
result[i] = count; //将结果存储在 result 数组中
}
}
int main() {
int nums[] = {8,1,2,2,3};
int n = sizeof(nums) / sizeof(nums[0]);
int result[n];
countSmallerNumbers(nums,n,result);
//打印结果数组
printf("[");
for (int i = 0; i < n; i++)
{
printf("%d",result[i]);
if (i != n - 1)
{
printf(", ");
}
}
printf("]\n");
return 0;
}
设计 Goal 解析器:
请你设计一个可以解释字符串
command
的 Goal 解析器 。command
由"G"
、"()"
和/或"(al)"
按某种顺序组成。Goal 解析器会将"G"
解释为字符串"G"
、"()"
解释为字符串"o"
,"(al)"
解释为字符串"al"
。然后,按原顺序将经解释得到的字符串连接成一个字符串。示例 1:
输入:command = "G()(al)" 输出:"Goal" 解释:Goal 解析器解释命令的步骤如下所示: G -> G () -> o (al) -> al 最后连接得到的结果是 "Goal"示例 2:
输入:command = "G()()()()(al)" 输出:"Gooooal"示例 3:
输入:command = "(al)G(al)()()G" 输出:"alGalooG"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char* interpret(char* command) {
//创建一个足够大的缓冲区来存储结果
int len = strlen(command);
char* result = (char*) malloc((len + 1) * sizeof(char)); //动态分配内存
int idx = 0; //结果数组的索引
for (int i = 0; i < len; i++){
if (command[i] == 'G')
{
result[idx++] = 'G';
}
else if (command[i] == '(' && command[i + 1] == ')')
{
result[idx++] = 'o';
i++; // 跳过 ')'
}
else if (command[i] == '(' && command[i + 1] == 'a' && command[i + 2] == 'l' && command[i + 3] == ')'){
result[idx++] = 'a';
result[idx++] = 'l';
i += 3; // 跳过"al)"
}
}
result[idx] = '\0';
return result;
}
int main() {
char command[] = "G()(al)(al)";
char* result = interpret(command);
printf("%s\n",result); //输出解析结果
free(result);
return 0;
}
仅替换一次字符串能否使得两个字符串相等:
给你长度相等的两个字符串
s1
和s2
。一次 字符串交换 操作的步骤如下:选出某个字符串中的两个下标(不必不同),并交换这两个下标所对应的字符。如果对 其中一个字符串 执行 最多一次字符串交换 就可以使两个字符串相等,返回
true
;否则,返回false
。
数组:
#include <stdio.h>
#include <stdlib.h>
#include<bits/stdc++.h>
bool areStringEqualAfterOneSwap(char* s1,char* s2){
int len = strlen(s1);
if(strcmp(s1, s2) == 0){
return true;
}
//找出不同的字符位置
int diffIndexs[2];
int diffCount = 0;
for (int i = 0; i < len; i++)
{
if(s1[i] != s2[i]){
if (diffCount == 2){
return false;
}
diffIndexs[diffCount++] = i;
}
}
//如果有两个不同的位置,检查交换后是否相等
if (diffCount == 2){
int i = diffIndexs[0];
int j = diffIndexs[1];
// 检查交换后的字符是否可以使两个字符串相等
if(s1[i] == s2[j] && s1[j] == s2[i]){
return true;
}
}
return false;
}
int main() {
char s1[101];
char s2[101];
scanf("%s",s1);
scanf("%s",s2);
//判断并输出结果
if(areStringEqualAfterOneSwap(s1,s2)){
printf("true\n");
}else{
printf("false\n");
}
return 0;
}
指针:
指针需要注意 首先是
char* p = s1;
char* q = s2;
其次是在while循环的判断条件,已经当前走到多长了 ==>> (p-s)
while (*p && *q) {
if (*p != *q) {
if (diffCount == 2) {
return false; // 超过两个不相等的字符,直接返回 false
}
diffIndices[diffCount++] = p - s1; // 记录位置
}
p++;
q++;
}
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool areAlmostEqual(char* s1, char* s2) {
// 如果两个字符串已经相等,直接返回 true
if (strcmp(s1, s2) == 0) {
return true;
}
// 指针初始化,遍历两个字符串
char* p = s1;
char* q = s2;
// 存储不相等的位置
int diffCount = 0;
int diffIndices[2]; // 最多只有两个不同的位置
// 遍历两个字符串
while (*p && *q) {
if (*p != *q) {
if (diffCount == 2) {
return false; // 超过两个不相等的字符,直接返回 false
}
diffIndices[diffCount++] = p - s1; // 记录位置
}
p++;
q++;
}
// 如果不相等的位置有两个,检查是否可以交换这两个字符
if (diffCount == 2) {
int i = diffIndices[0];
int j = diffIndices[1];
// 判断交换后的字符是否能使得字符串相等
if (*(s1 + i) == *(s2 + j) && *(s1 + j) == *(s2 + i)) {
return true;
}
}
return false;
}
int main() {
char s1[101], s2[101];
// 读取输入
scanf("%s", s1);
scanf("%s", s2);
// 判断并输出结果
if (areAlmostEqual(s1, s2)) {
printf("true\n");
} else {
printf("false\n");
}
return 0;
}
最大和谐子序列
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是
1
。给你一个整数数组
nums
,请你在所有可能的 子序列 中找到最长的和谐子序列的长度。数组的 子序列 是一个由数组派生出来的序列,它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
示例 1:
输入:nums = [1,3,2,2,5,2,3,7]
输出:5
解释:
最长和谐子序列是
[3,2,2,2,3]
。示例 2:
输入:nums = [1,2,3,4]
输出:2
解释:
最长和谐子序列是
[1,2]
,[2,3]
和[3,4]
,长度都为 2。示例 3:
输入:nums = [1,1,1,1]
输出:0
解释:
不存在和谐子序列。
超时:
if (numsSize <= 1) return 0;
// 使用一个哈希表来记录数字的频率
int min = INT_MAX, max = INT_MIN;
// 找到数组的最小值和最大值,用来确定哈希表的大小
for (int i = 0; i < numsSize; i++) {
if (nums[i] < min) min = nums[i];
if (nums[i] > max) max = nums[i];
}
// 数字的范围是 [min, max],所以我们可以创建一个哈希表来存储频率
int range = max - min + 1;
int* freq = (int*)calloc(range, sizeof(int)); // 初始化频率数组
// 统计每个数字的频率
for (int i = 0; i < numsSize; i++) {
freq[nums[i] - min]++;
}
int maxLength = 0;
// 遍历频率表,检查每个数字和它的邻居 (num + 1) 的和谐子序列长度
for (int i = 0; i < range - 1; i++) {
if (freq[i] > 0 && freq[i + 1] > 0) {
int length = freq[i] + freq[i + 1];
if (length > maxLength) {
maxLength = length;
}
}
}
return maxLength; // 返回最大和谐子序列的长度
删除最外层括号:
有效括号字符串为空
""
、"(" + A + ")"
或A + B
,其中A
和B
都是有效的括号字符串,+
代表字符串的连接。
- 例如,
""
,"()"
,"(())()"
和"(()(()))"
都是有效的括号字符串。如果有效字符串
s
非空,且不存在将其拆分为s = A + B
的方法,我们称其为原语(primitive),其中A
和B
都是非空有效括号字符串。给出一个非空有效字符串
s
,考虑将其进行原语化分解,使得:s = P_1 + P_2 + ... + P_k
,其中P_i
是有效括号字符串原语。对
s
进行原语化分解,删除分解中每个原语字符串的最外层括号,返回s
。示例 1:
输入:s = "(()())(())" 输出:"()()()" 解释: 输入字符串为 "(()())(())",原语化分解得到 "(()())" + "(())", 删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。示例 2:
输入:s = "(()())(())(()(()))" 输出:"()()()()(())" 解释: 输入字符串为 "(()())(())(()(()))",原语化分解得到 "(()())" + "(())" + "(()(()))", 删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。示例 3:
输入:s = "()()" 输出:"" 解释: 输入字符串为 "()()",原语化分解得到 "()" + "()", 删除每个部分中的最外层括号后得到 "" + "" = ""。
#include <stdio.h>
#include <string.h>
char* removeOuterParentheses(char* s) {
int n = strlen(s);
char* result = (char*)malloc(n + 1); // 为结果分配足够的空间
int index = 0; // 结果字符串的当前索引
int level = 0; // 括号的嵌套层级
for (int i = 0; i < n; i++) {
if (s[i] == '(') {
if (level > 0) { // 如果不是最外层括号
result[index++] = s[i]; // 添加到结果中
}
level++; // 增加嵌套层级
} else {
level--; // 减少嵌套层级
if (level > 0) { // 如果不是最外层括号
result[index++] = s[i]; // 添加到结果中
}
}
}
result[index] = '\0'; // 确保字符串以 '\0' 结尾
return result;
}
// 测试代码
int main() {
char s[] = "(()())(())";
char* result = removeOuterParentheses(s);
printf("Output: %s\n", result);
free(result); // 释放分配的内存
return 0;
}