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

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

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;
}


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

 

相关文章
|
15天前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
30 1
|
22天前
|
存储
LeetCode整数反转
解决LeetCode上的整数反转问题的几种方法,包括错误的方法和优化后的解决方案,以及如何避免反转后的整数超出32位有符号整数范围的问题。
30 1
|
21天前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
29 0
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
102 2
|
24天前
【LeetCode】整数翻转
【LeetCode】整数翻转
13 1
|
22天前
|
存储 C++
Leetcode第十二题(整数转罗马数字)
LeetCode第12题“整数转罗马数字”的解题方法,包括罗马数字的基本规则和特殊规则,以及如何使用C++实现整数到罗马数字的转换。
14 0
|
22天前
|
C++
Leetcode第十三题(罗马数字转整数)
这篇文章介绍了LeetCode第13题“罗马数字转整数”的解题方法,通过一个C++的类`Solution`中的`romanToInt`函数来实现,该函数使用哈希表和遍历字符串的方法,根据罗马数字的规则将输入的罗马数字字符串转换为对应的整数值。
44 0
|
22天前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
14 0
|
22天前
Leetcode(最后一个单词长度)
这篇文章介绍了两种解决LeetCode第58题的方法,即计算给定字符串中最后一个单词的长度,方法包括翻转字符串和逆向遍历统计。
15 0
|
22天前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
15 0