基础类型OJ题篇1

旧城等待， 2023-07-05 13:28 71阅读 0赞

### 基础类型OJ题篇 ###

*   *   *  1、反转字符串中的元音字母
         *  2、找不同
         *  3、字符串相加
         *  4、判断3的幂
         *  5、最短单词距离
         *  6、缺失数字
         *  7、长度最小的子数组
         *  8、2 的 幂

### 1、反转字符串中的元音字母 ###

编写一个函数，以字符串作为输入，反转该字符串中的元音字母

> 示例 1:  
> 输入: “hello”  
> 输出: “holle”

> 示例 2:  
> 输入: “leetcode”  
> 输出: “leotcede”

方法一：定义一个元音字典，然后去判断当前字符是否在字典中

def reverseVowels(self, s: str) -> str:
            start = 0
            end = len(s)-1
            dic = ['a','e','i','o','u','A','E','I','O','U']
            s = list(s)
            while start<end:
                if s[start] in dic and s[end] in dic:
                    s[start],s[end] = s[end],s[start]
                    start+=1
                    end-=1
                if s[start] not in dic:
                    start+=1
                if s[end] not in dic:
                    end-=1
            return ''.join(s)

方法二：C++ 版本，思路和代码写法几乎一样

把元音字符设置为一个字符串，然后利用 find 函数去查找，如果返回的是 -1 说明没有找到，意味着当前字符不是元音字符

string reverseVowels(string s) { 
            int start = 0;
            int end = s.size()-1;
            string tool = "aeiouAEIOU";
            while(start<end){ 
                while(tool.find(s[start]) ==-1 && start<end){ 
                    ++start;
                }
                while(tool.find(s[end])==-1 && start<end){ 
                    --end;
                }
                if(start<end){ 
                    swap(s[start++],s[end--]);
                }
            }
            return s;
        }

### 2、找不同 ###

给定两个字符串 s 和 t，它们只包含小写字母

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母

请找出在 t 中被添加的字母

> 示例  
> 输入：  
> s = “abcd”  
> t = “abcde”  
> 输出：  
> e  
> 解释：  
> ‘e’ 是那个被添加的字母

思路：使用异或运算符，但是需要注意字符和整数的转换

def findTheDifference(self, s: str, t: str) -> str:
            s = s+t
            res = 0
            for i in range(len(s)):
                # ord 函数将字符转换为 ASCII值
                res^= ord(s[i])
            # 将数字转换为字符
            return chr(res)

C++版本

char findTheDifference(string s, string t) { 
            string temp = s+t;
            int res = 0;
            for(int i =0;i<temp.size();++i){ 
                res ^=int(temp[i]);
            }
            return char(res);
        }

### 3、字符串相加 ###

给定两个字符串形式的非负整数 num1 和 num2 ，计算它们的和

注意：

num1 和num2 的长度都小于 5100.  
num1 和num2 都只包含数字 0-9.  
num1 和num2 都不包含任何前导零。  
你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式

思路：利用变量保存好每一次运算的余数和模，第二次运算要加进去.另外在计算之前先对输入列表进行逆置，因为我们平时运算都是右对齐，而模拟加法运算利用下标都是左对齐.

解题代码

def addStrings(self, num1: str, num2: str) -> str:
            n1,n2 = len(num1),len(num2)
            n = max(n1,n2)
            num1,num2 = num1[::-1],num2[::-1]
            carry,res = 0,''
            for i in range(n):
                a = int(num1[i])if i<n1 else 0
                b = int(num2[i])if i<n2 else 0
                sum = a+b+carry
                carry = sum//10
                res = str(sum%10)+res
            return str(carry) + res if carry else res

C++ 写法

string addStrings(string num1, string num2) { 
            int n1 = num1.size();
            int n2 = num2.size();
            int n = max(n1,n2);
            reverse(num1.begin(),num1.end());
            reverse(num2.begin(),num2.end());
            int carry = 0;
            string res;
            int sum,a,b;
            for(int i = 0;i<n;++i){ 
                if(i<n1){ 
                    a = num1[i]-'0'; 
                }else{ 
                    a = 0;
                }
                if(i<n2){ 
                    b = num2[i]-'0';
                }else{ 
                    b = 0;
                }
                sum = a+b+carry;
                carry = sum/10;
                res = to_string(sum%10) + res;
            }
            if(carry){ 
                res = "1"+res;
            }
            return res;
        }

### 4、判断3的幂 ###

给定一个整数，写一个函数来判断它是否是 3 的幂次方。

> 示例1  
> 输入: 27  
> 输出: true

> 示例2  
> 输入: 0  
> 输出: false

> 示例3  
> 输入: 9  
> 输出: true

> 示例4  
> 输入: 45  
> 输出: false

思路：一直除以 3，直到 n 不等于 1 则返回 False,如果最后等于 1 则返回 True

def isPowerOfThree(self, n: int) -> bool:
            if n==0:
                return False
            while n%3==0:
                n/=3
            return n==1

方法二：3 的幂次的质因子只有 3，而所给出的 n 如果也是 3 的幂次，故而题目中所给整数范围内最大的 3 的幂次的因子只能是 3 的幂次，1162261467 是 3 的19次幂，是整数范围内最大的 3 的幂次

def isPowerOfThree(self, n: int) -> bool:
            return n > 0 and 1162261467 % n == 0

### 5、最短单词距离 ###

给定一个单词列表和两个单词 word1 和 word2，返回列表中这两个单词之间的最短距离。

> 示例:  
> 假设 words = \[“practice”, “makes”, “perfect”, “coding”, “makes”\]

> 示例1  
> 输入: word1 = “coding”, word2 = “practice”  
> 输出: 3

> 示例2  
> 输入: word1 = “makes”, word2 = “coding”  
> 输出: 1

**注意**:你可以假设 word1 不等于 word2, 并且 word1 和 word2 都在列表里

思路：这里我们用到一个库函数 enumerate ，它的用法如下

nums = ['one', 'two', 'three', 'four']
    for index, num in enumerate(nums):
        print(index, num)

index 代表下标，num 代表值  
输出如下值  
![在这里插入图片描述][20191219215825945.png]  
所以我们利用这个库函数记录下两个单词的下标，然后再进行相减，选出最小的那个值，就是两个单词最近的距离

def shortestDistance(words, word1, word2):
        res = len(words)
        pos1, pos2 = None, None
        for idx, word in enumerate(words):
            if word == word1:
                pos1 = idx
            elif word == word2:
                pos2 = idx
            # 下标必须要都存在才可以执行下一步
            if pos1 is not None and pos2 is not None:
                res = min(res, abs(pos1 - pos2))
        return res

当然也可以不用查询下标的函数

C++ 写法

int shortestDistance(vector<string>& words, string word1, string word2) { 
            int p1 = -1, p2 = -1, res = INT_MAX;
            for (int i = 0; i < words.size(); ++i) { 
                if (words[i] == word1) p1 = i;
                else if (words[i] == word2) p2 = i;
                if (p1 != -1 && p2 != -1) res = min(res, abs(p1 - p2));
            }
            return res;
        }

### 6、缺失数字 ###

给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数

> 示例1  
> 输入: \[3,0,1\]  
> 输出: 2

> 示例2  
> 输入: \[9,6,4,2,3,5,7,0,1\]  
> 输出: 8

方法一：计算出整个数组的总和，然后利用 n 个数字之和减去数组之和就是缺失的那个数字

def missingNumber(self, nums: List[int]) -> int:
            nums_sum = len(nums)*(len(nums)+1)//2
            return nums_sum -sum(nums)

C++ 写法，缺陷，可能会出现数组越界

int missingNumber(vector<int>& nums) { 
            int n = nums.size();
            int sum = n*(n+1)/2;
            int sum_nums = 0;
            for(auto&e:nums){ 
                sum_nums+=e;
            }
            return sum - sum_nums;
        }

方法二：抵消

int missingNumber(vector<int>& nums) { 
            int sum = 0;
            for(int i = 0;i<nums.size();++i){ 
                sum+=(nums[i]-i);
            }
            sum-=nums.size();
            // 到这里，sum 就相当于是短缺的那个数的负数了
            // 因为加的数和减的数抵消了
            return -sum;
        }

方法三：数组中所有的数字与 1 ~ n+1 进行异或操作，出现两次的数都会消失，只剩下出现一次的数，即为缺失的数

int missingNumber(vector<int>& nums) { 
            int res = nums.size();
            for(int i = 0;i<nums.size();++i){ 
                res^=nums[i];
                res^=i;
            }
            return res;
        }

### 7、长度最小的子数组 ###

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0

> 示例1:  
> 输入: s = 7, nums = \[2,3,1,2,4,3\]  
> 输出: 2  
> 解释: 子数组 \[4,3\] 是该条件下的长度最小的连续子数组。

方法一：时间度为 O(N2)的暴力解法

def minSubArrayLen(self, s,nums):
            if not nums:
                return 0
            if s>sum(nums):
                return 0
            min_num  = len(nums)
            for left in range(0,len(nums)):
                for i in range(1,len(nums)+1):
                    if sum(nums[left:i])>=s:
                        min_num = min(min_num,len(nums[left:i]))
            return min_num

方法二：利用双指针的方法，如果当前列表大于目标值则计算出长度并且更新左边的指针，如果小于目标值则更新右边的指针。

def minSubArrayLen(self, s: int, nums: List[int]) -> int:
            if not sum or s>sum(nums):
                return 0
            left ,right,end = 0,1,len(nums)+1
            min_num  = len(nums)
            while right<end:
                if sum(nums[left:right])>=s:
                    min_num = min(min_num,len(nums[left:right]))
                    left+=1
                else:
                    right+=1
            return min_num

进行优化 sum 函数，直接对和进行运算

def minSubArrayLen(self, s: int, nums: List[int]) -> int:
            if not sum or s>sum(nums):
                return 0
            n = len(nums)
            start = 0
            min_len = n+1
            cur_sum = 0
            for i in range(n):
                cur_sum += nums[i]
                while cur_sum >= s:
                    min_len = min(min_len, i-start+1)
                    cur_sum -= nums[start]
                    start += 1
            return min_len

下面是三种C++写法，大致思路都是一样的  
C++：写法1

int Sum(vector<int>&nums){ 
            int sum = 0;
            for(auto&e:nums){ 
                sum+=e;
            }
            return sum;
        }
        int minSubArrayLen(int s, vector<int>& nums) { 
            int sum = 0,res = nums.size(),start = 0;
            if(Sum(nums)<s){ 
                return 0;
            }
            for(int i = 0;i<nums.size();++i){ 
                sum+=nums[i];
                while(sum>=s){ 
                    res = min(res,i-start+1);
                    sum-=nums[start];
                    ++start;
                }
            }
            return res;
        }

C++：写法2

int minSubArrayLen(int s, vector<int>& nums) { 
            int sum = 0,res = 0,start = 0;
            for(int i = 0;i<nums.size();++i){ 
                sum+=nums[i];
                while(sum>=s){ 
                    if(res == 0){ 
                        res = i-start+1;
                    }else{ 
                        res = min(res,i-start+1);
                    }
                    sum-=nums[start];
                    ++start;
                }
            }
            return res;
        }

C++：写法三

int minSubArrayLen(int s, vector<int>& nums) { 
            int sum = 0,res = nums.size()+1,start = 0;
            for(int i = 0;i<nums.size();++i){ 
                sum+=nums[i];
                while(sum>=s){ 
                    res = min(res,i-start+1);
                    sum-=nums[start];
                    ++start;
                }
            }
            return res == nums.size()+1?0:res;
        }

### 8、2 的 幂 ###

给定一个整数，编写一个函数来判断它是否是 2 的幂次方

> 示例  
> 输入: 1  
> 输出: true  
> 解释: 20 = 1

> 示例2  
> 输入: 16  
> 输出: true  
> 解释: 24 = 16

> 示例3  
> 输入: 218  
> 输出: false

思路：二进制位移的思想。因为如果一个数是二的幂次方，那么除了最高的那位是1，其余位都是0.

def isPowerOfTwo(self, n: int) -> bool:
            if n==0:
                return False
            while n!=1:
                if n&1 != 0:
                    return False
                n = n>>1
            return True

当然也有更简单的方法,也是利用二进制的思想，如果 n 是2的次方，n-1 和 n 的二进制位恰相反。

if n<=0:
      	return False
    return not n&(n-1)

[20191219215825945.png]: https://img-blog.csdnimg.cn/20191219215825945.png