leetCode力扣刷题记录

/ 0评 / 0

本人的编译器使用的是Visual Studio 2019,因此若有需要,当遇到scanf_s函数时,应该将其改成scanf。

简单级

1.两数之和(c

有人相爱,有人夜里看海,有人力扣第一道题做不出来

第九次提交终于过了

题目:

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:输入:nums = [3,2,4], target = 6
输出:[1,2]
示例 3:输入:nums = [3,3], target = 6
输出:[0,1] 

提示:

进阶:你可以想出一个时间复杂度小于 O(n^2) 的算法吗?

思路:

编辑器和PTA的差了许多,力扣编辑器直接给定了一个函数,把题目给的数组 数组长度 目标都以参数形式输入

直接用两个for循环遍历比对是否等于target,参考了官方答案,才知道需要直接申请数组内存然后填入,最后以数组形式返回结果(我还以为是直接printf)

#include <stdio.h>

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){

int cnt=0,cnt2=0;

for (cnt = 0; cnt < numsSize;cnt++){ //cnt遍历
    for (cnt2 = 0; cnt2 < numsSize;cnt2++){ //cnt2遍历
        if (nums[cnt] + nums[cnt2] == target && cnt != cnt2){
            printf("[%d,%d]", cnt, cnt2);
            int *ret = malloc(sizeof(int) * 2);
            ret[0] =cnt;
            ret[1] =cnt2;
            *returnSize =2;
            return ret;
        }
    }
}
*returnSize = 0;
return NULL;

}

写完又看了一眼官方答案发现我这边出现了重复判断,也就是cnt每次加1,cnt2都重复的从nums[0]开始判断,所以出现了某个数自己与自己相加的出结果而导致最终检测答案不正确的情况。

其实很简单 不需要判断cnt != cnt2 只需要每次都从cnt+1的位置开始判断即可。

7.整数反转(c

我直接选做第二道简单难度题

题目:

给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ,就返回 0。

假设环境不允许存储 64 位整数(有符号或无符号)。

示例 1:

输入:x = 123
输出:321

示例 2:

输入:x = -123
输出:-321

示例 3:

输入:x = 120
输出:21

示例 4:

输入:x = 0<br>输出:0

提示:

-2^31 <= x <= 2^31 - 1

思路:

由例3可知,要求反转之后数前的0不保留,遂正数部分可直接用循环处理得出每位数后运算相加来反转。而负数部分或许可以先拿掉负号,然后同上处理?

以下进行代码写入

1523. 在区间范围内统计奇数数目(c#

难度简单

给你两个非负整数 low 和 high 。请你返回 low  high 之间(包括二者)奇数的数目。

示例 1:

输入:low = 3, high = 7
输出:3
解释:3 到 7 之间奇数数字为 [3,5,7] 。

示例 2:

输入:low = 8, high = 10
输出:1
解释:8 到 10 之间奇数数字为 [9] 。

提示:

思路:

public class Solution
{
    public int CountOdds(int low, int high)
    {
        int i = 0;
        for(int num = low; num <= high; num++)
        {
            if(num % 2 == 1)
            {
                i++;
            }
        }
        return i;
    }
}

2367. 算术三元组的数目(c#

难度简单

给你一个下标从 0 开始、严格递增 的整数数组 nums 和一个正整数 diff 。如果满足下述全部条件,则三元组 (i, j, k) 就是一个 算术三元组 :

返回不同 算术三元组 的数目

示例 1:

输入:nums = [0,1,4,6,7,10], diff = 3
输出:2
解释:
(1, 2, 4) 是算术三元组:7 - 4 == 3 且 4 - 1 == 3 。
(2, 4, 5) 是算术三元组:10 - 7 == 3 且 7 - 4 == 3 。

示例 2:

输入:nums = [4,5,6,7,8,9], diff = 2
输出:2
解释:
(0, 2, 4) 是算术三元组:8 - 6 == 2 且 6 - 4 == 2 。
(1, 3, 5) 是算术三元组:9 - 7 == 2 且 7 - 5 == 2 。

提示:

思路:暴力求解!

public class Solution
{
    public int ArithmeticTriplets(int[] nums, int diff)
    {
        int num = 0;
        for (int i = 0;i <= nums.Length - 1 - 2; i++) //nums.Length - 1是最后一个元素,再减2留出j和k的位置,减2是第倒数第3个
        {
            for(int j = i+1; j <= nums.Length - 1 - 1; j++)//j从i的下一位开始,一直到倒数第2个
            {
                for(int k = j+1; k <= nums.Length - 1; k++)//k从j的下一个开始,一直到最后一个
                {
                    if (nums[j] - nums[i] == diff && nums[k] - nums[j] == diff)
                    {
                        num++;
                    }
                }
            }
        }
        return num;
    }
}

1758. 生成交替二进制字符串的最少操作数

难度简单

给你一个仅由字符 '0' 和 '1' 组成的字符串 s 。一步操作中,你可以将任一 '0' 变成 '1' ,或者将 '1' 变成 '0' 。

交替字符串 定义为:如果字符串中不存在相邻两个字符相等的情况,那么该字符串就是交替字符串。例如,字符串 "010" 是交替字符串,而字符串 "0100" 不是。

返回使 s 变成 交替字符串 所需的 最少 操作数。

示例 1:

输入:s = "0100"
输出:1
解释:如果将最后一个字符变为 '1' ,s 就变成 "0101" ,即符合交替字符串定义。

示例 2:

输入:s = "10"
输出:0
解释:s 已经是交替字符串。

示例 3:

输入:s = "1111"
输出:2
解释:需要 2 步操作得到 "0101" 或 "1010" 。

提示:

思路:抄的

public class Solution {
    public int MinOperations(string s) {
        int a=0,b=0;//计数,a代表01开头字符串,b代表10开头字符串
        for(int i=0;i<s.Length;i++){//循环遍历字符串
            if((i&1)!=s[i]-'0'){//两边都是同类型运算,避免隐式类型转换降低效率,i&1判断奇偶数,比%高效
                a++;//01开头字符串变更次数+1
            }else{
                b++;//10开头字符串变更次数+1
            }
        }
        return a<b?a:b;//三目运算取最小值,避免min函数在内存栈区的调用。
    }
}

这句if((i&1)!=s[i]-'0')的解析如下:

例如输入的字符串是"0100"。

以!=为中心,将这条表达式拆分为两部分:

前半部分:当上一层的for开始运行时,i首先=0,i&1判断了这个i代表的位数是第奇数个位还是第偶数个位,因为0101或是1010的每个奇数位或每个偶数位的内容都是一样的。

实际上就是使用i&1制作出0101开头的字符串,然后进行比对,在if中使用!=可能是为了强调对比的是两个字符串的"差异",输入的字符串中某一位与0101字符串相应那一位对比后,判断为相等是1010字符串与输入字符串的差异性,判断为不相等则是输入字符串与0101字符串的差异。

后半部分:s[i]减去字符0,如果s[i]是1,结果就是1(ASCII码相减),反之结果是0,这一步的意义可能是转str为int。

i&1,i经历了0123,运算结果是"0101"。对比输入的字符串"0100",第一次判断0!=0进else,第二三次同理。第四次1!=0为1,因此a++。

2418. 按身高排序(C#

难度简单

给你一个字符串数组 names ,和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。

对于每个下标 inames[i] 和 heights[i] 表示第 i 个人的名字和身高。

请按身高 降序 顺序返回对应的名字数组 names 。

示例 1:

输入:names = ["Mary","John","Emma"], heights = [180,165,170]
输出:["Mary","Emma","John"]
解释:Mary 最高,接着是 Emma 和 John 。

示例 2:

输入:names = ["Alice","Bob","Bob"], heights = [155,185,150]
输出:["Bob","Alice","Bob"]
解释:第一个 Bob 最高,然后是 Alice 和第二个 Bob 。

提示:

思路:冒泡排序

public class Solution
{
    public string[] SortPeople(string[] names, int[] heights)
    {
        int temp = 0;
        string temp2;
        bool swapped;
        for (int i = 0; i < heights.Length; i++)
        {
            swapped = false;
            for (int j = 0; j < heights.Length - 1 - i; j++)
                if (heights[j] < heights[j + 1])
                {
                    temp = heights[j];
                    heights[j] = heights[j + 1];
                    heights[j + 1] = temp;
                    temp2 = names[j];
                    names[j] = names[j + 1];
                    names[j + 1] = temp2;
                    if (!swapped)
                        swapped = true;
                }
            if (!swapped)
                return names;
        }
        return null;
    }
}

“借鉴”菜鸟教程的冒泡排序例段,加了一段使names与heights同时进行排序

一开始没有加倒数第三行的return null,所以因为编译器认为不一定会进入if所以提示

错误 CS0161 “Solution.SortPeople(string[], int[])”: 并非所有的代码路径都返回值

所以在第一个for外面加上return null,反正也运行不到这里。

506. 相对名次

难度简单

给你一个长度为 n 的整数数组 score ,其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都 互不相同 。

运动员将根据得分 决定名次 ,其中名次第 1 的运动员得分最高,名次第 2 的运动员得分第 2 高,依此类推。运动员的名次决定了他们的获奖情况:

使用长度为 n 的数组 answer 返回获奖,其中 answer[i] 是第 i 位运动员的获奖情况。

示例 1:

输入:score = [5,4,3,2,1]
输出:["Gold Medal","Silver Medal","Bronze Medal","4","5"]
解释:名次为 [1st, 2nd, 3rd, 4th, 5th] 。

示例 2:

输入:score = [10,3,8,9,4]
输出:["Gold Medal","5","Bronze Medal","Silver Medal","4"]
解释:名次为 [1st, 5th, 3rd, 2nd, 4th] 。

提示:

思路:

因为得分互不相同,所以好像可以维护一个数组,将score排序后放入,此时这个数组有序且互不相等。然后用score中的每一位对此数组再次进行遍历,即可得到score从第一个到最后一个的排名都是什么,最后得出answer

using System;
public class Solution
{
    static int Main()
    {
        int[] score = new int[5] {10, 3, 8, 9, 4};
        FindRelativeRanks(score);
        return 0;
    }
    static string[] FindRelativeRanks(int[] score)
    {
        //数组复制
        int[] ranking = new int[score.Length];
        for (int i = 0; i != ranking.Length; i++)
        {
            ranking[i] = score[i];
        }

        string[] answer = new string[score.Length];

        //对ranking冒泡排序
        int temp = 0;
        bool swapped;
        for (int i = 0; i < ranking.Length; i++)
        {
            swapped = false;
            for (int j = 0; j < ranking.Length - 1 - i; j++)
                if (ranking[j] < ranking[j + 1])
                {
                    temp = ranking[j];
                    ranking[j] = ranking[j + 1];
                    ranking[j + 1] = temp;
                    if (!swapped)
                        swapped = true;
                }
            if (!swapped)
                break;
        }

        /*foreach (int i in score)
        {
            Console.Write(i + " ");
        }
        
        foreach (int i in ranking)
        {
            Console.Write(i + " ");
        }*/

        //直接将排序与未排序的版本比较,将score数组中的每个元素的排名根据ranking输出到answer
        for (int i = 0; i < score.Length; i++)
        {
            for(int j = 0; j < ranking.Length; j++)
            {
                if(score[i] == ranking[j])
                {
                    switch (j+1)
                    {
                        case 1: answer[i] = "Gold Medal"; break;
                        case 2: answer[i] = "Silver Medal"; break;
                        case 3: answer[i] = "Bronze Medal"; break;
                        default: answer[i] = (j + 1).ToString(); break;
                    }
                }
            }
        }
        /*
        foreach (string i in answer)
        {
            Console.Write(i + " ");
        }*/
        return answer;
    }
}

用了七十分钟,其实四十分钟在没必要的Debug上,因为我TMD把Ranking排反了,排成升序了,找了半天才找到

66. 加一

难度简单

给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。

最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外,这个整数不会以零开头。

翻译:

给定一个非空数组,此数组由整数组成,数组的各个整数组合在一起可以表达一个非负整数,例如[1,2]表示12,现在 在该数的基础加一

最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外,这个整数不会以零开头。

示例 1:

输入:digits = [1,2,3]
输出:[1,2,4]
解释:输入数组表示数字 123。

示例 2:

输入:digits = [4,3,2,1]
输出:[4,3,2,2]
解释:输入数组表示数字 4321。

示例 3:

输入:digits = [0]
输出:[1]

提示:

思路:看注释

public class Solution
{
    public int[] PlusOne(int[] digits)
    {
        for (int i = digits.Length - 1; i >= 0; i--)
        {
            digits[i]++;
            if (digits[i] > 9)
            {
                digits[i] = 0;
            }//因为digits[i]++后成功的进入了if线,所以不会导致for结束,继续给下一位++
            else//除非这位数加1之后不大于9,那就可以直接输出了
            {
                return digits;
            }
        }
        //如果成功运行到这里,证明每一次+1后>9的检查都成立,那么会导致原数组所有的元素都变成0,因此在0号位插入一个1即可
        int[] ans = new int[digits.Length+1];
        ans[0] = 1;
        return ans;
    }
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注