【LeetCode】每日一题最后一个单词的长度投票法求解多数元素异或操作符巧解只出现一次的数字整数反转

=========================================================================

个人主页直达：小白不是程序媛

LeetCode系列专栏：LeetCode刷题掉发记

=========================================================================

目录

LeetCode 58.最后一个单词的长度

LeetCode169.多数元素

LeetCode 136.出现一次的数字

LeetCode 7.整数反转

---

LeetCode 58.最后一个单词的长度

难度：简单

OJ链接

题目描述：

给你一个字符串 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;
}

---

LeetCode169.多数元素

难度：简单

OJ链接

题目描述：

给定一个大小为 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;
}

---

LeetCode 136.出现一次的数字

难度：简单

OJ链接

题目描述：

给你一个 非空 整数数组 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

---

LeetCode 7.整数反转

难度：中等

OJ链接

题目描述：

给你一个 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;
}

 这周的题目分享就到这里了，希望大家可以理解上面的投票法和异或巧解那两道题目，有更好的解决方法可以在评论区多多交流！！！感谢大家的捧场！！！