LeetCode 58.最后一个单词的长度
难度:简单
题目描述:
给你一个字符串 s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
示例 1:
输入:s = "Hello World"
输出:5
解释:最后一个单词是“World”,长度为5。
示例 2:
输入:s = " fly me to the moon "
输出:4
解释:最后一个单词是“moon”,长度为4。
示例 3:
输入:s = "luffy is still joyboy"
输出:6
解释:最后一个单词是长度为6的“joyboy”。
思路讲解:
使用库函数strlen求出字符串长度,定义一个计数器从后往前遍历,如果不是空格就加加,遇到空格就退出,最后返回这个计数器。
注意:有可能最后一个就是空格,也有可能最后几个字符都是空格。
我们要从后向前找到第一个不为空格的字符,从这里开始遍历,找下个空格,计数器加加。
实现代码
int lengthOfLastWord(char * s) { int len=strlen(s); int i=len-1; int ret=0; //从尾部开始遍历找到第一个不为空格的位置 while(i>=0&&s[i]==' ') { i--; } //从第一个不为空格的位置开始继续遍历,找到下个空格的位置 while(i>=0&&s[i]!=' ') { i--; ret++; } return ret; }
难度:简单
题目描述:
给定一个大小为 n
的数组 nums
,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2
⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入:nums = [3,2,3]
输出:3
示例 2:
输入:nums = [2,2,1,1,1,2,2]
输出:2
思路讲解:投票法
题目中说到出现次数大于n/2的元素,这表示相同的数一定多于不同的数,我们从第一个数开始默认有一票,遇到相同的数就加一票,不同的数减一票,当票数小于0时代表和这个数不同的数一定多于和这个数相同的数,不可能时此数,然后从此位置开始继续向后遍历。
实现代码
int majorityElement(int* nums, int numsSize){ int point =nums[0]; int count=1; //默认有一票 for(int i=1;i<numsSize;i++) { if(nums[i]==point) { //后一个和前一个相等加一票 count++; } else { //不相等加一票 count--; if(count<0) { //小于零时,代表反对票一定多于赞成票,重新开始投票 point=nums[i]; count=1; } } } return point; }
难度:简单
题目描述:
给你一个 非空 整数数组 nums
,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
示例 1 :
输入:nums = [2,2,1]
输出:1
示例 2 :
输入:nums = [4,1,2,1,2]
输出:4
示例 3 :
输入:nums = [1]
输出:1
思路讲解:异或操作符妙用
任何数和0异或不变,两个相同的数异或值为0。我们使用异或这一特点就可以巧解这个题。
只出现一次的数代表出这个数外的其他数都相同,那我们就使用异或操作符,让第一个数和0异或,其他的数和前面的数异或。
int singleNumber(int* nums, int numsSize){ int point=0; for(int i=0;i<numsSize;i++) { point^=nums[i]; } return point; } //nums[3]={ 2, 2, 1} //point =0^2=2; //point =2^2=0; //point =0^1=1; //所以出现一次的数为1
难度:中等
题目描述:
给你一个 32 位的有符号整数 x
,返回将 x
中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1]
,就返回 0。
假设环境不允许存储 64 位整数(有符号或无符号)。
示例 1:
输入:x = 123
输出:321
示例 2:
输入:x = -123
输出:-321
示例 3:
输入:x = 120
输出:21
示例 4:
输入:x = 0
输出:0
解题思路:
首先我们定义一个变量,然后让这个这个变量储存对数的取模,对其在乘以10,对数模10。当这个数大于0的时候一直循环下去是不是就可以得到这个数的反转?
注意:这里我们要考虑极端情况当给的数反转特别大的时候就要返回0;
实现代码
int reverse(int x){ long long point=0; while(x!=0) { point=point*10+x%10; x=x/10; } if(point>INT_MAX||point<-(INT_MAX)) { return 0; } return point; }
这周的题目分享就到这里了,希望大家可以理解上面的投票法和异或巧解那两道题目,有更好的解决方法可以在评论区多多交流!!!感谢大家的捧场!!!