基础类型 OJ 题篇 2

快来打我* 2023-06-22 06:29 31阅读 0赞

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

*   *   *  1、存在重复元素
         *  2、最大数
         *  3、汇总区间
         *  4、旋转数组
         *  5、颠倒二进制位
         *  6、数字范围按位与

### 1、存在重复元素 ###

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

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

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

python 中 set 函数 可以去重  
`return len(set(nums)) != len(nums)`  
在C++ 中也可以利用 set 特性：容器不可以有两个相同的键值

bool containsDuplicate(vector<int>& nums) { 
    	set<int>value;
        for(int i =0;i<nums.size();++i){ 
        	// 如果存在相同的键值，则不会 insert
        	value.insert(nums[i]);
    	}
        return nums.size()!=value.size();
    }

### 2、最大数 ###

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

> 示例1  
> 输入: \[10,2\]  
> 输出: 210

> 示例2  
> 输入: \[3,30,34,5,9\]  
> 输出: 9534330

思路：字符串排序

python 写法一

from functools import cmp_to_key
        def largestNumber(self, nums: List[int]) -> str:
            def strCmp(s1,s2):
                if s1+s2>s2+s1:
                    return 1
                return -1
            
            nums = [str(x) for x in nums]
            nums = sorted(nums,key = cmp_to_key(strCmp),reverse=True)
            return ''.join(nums).lstrip('0') or '0'

这里特别要介绍 sorted 函数，sort 是应用于list列表的函数，而 sorted 是对于所有可迭代对象进行排序操作，list的 sort函数是在原来结构的基础上进行修改，而内建函数sorted 方法返回的是一个新的 list ，并不是在原来的基础上操作。

sorted 函数的参数有三个

> sorted(iterable, key=None, reverse=False)

**iterable** 可迭代对象

**key** 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序

**reverse = True 降序 ， reverse = False 升序**（默认)

python 写法二：

def largestNumber(self, nums):
            nums = [str(x) for x in nums]
            nums = sorted(nums, cmp= lambda x, y : cmp(x+y, y+x), reverse=True)
            return ''.join(nums).lstrip('0') or '0'

C++ 写法

string largestNumber(vector<int>& nums) { 
            sort(nums.begin(),nums.end(),\
                [](const int&a,const int&b){ 
                string aa = to_string(a);
                string bb = to_string(b);
                return aa+bb > bb+aa;
            });
    
            string res;
            for(auto n:nums){ 
            	// 这里是为了防止第一个字符串是0的情况
            	// 如果为0，则直接返回 “0” 
                if (res=="0"){ 
                    return "0"; 
                }else{ 
                    res= res+to_string(n);
                }
            }
            return res;
        }

### 3、汇总区间 ###

给定一个无重复元素的有序整数数组，返回数组区间范围的汇总

> 示例 1:  
> 输入: \[0,1,2,4,5,7\]  
> 输出: \[“0->2”,“4->5”,“7”\]  
> 解释: 0,1,2 可组成一个连续的区间; 4,5 可组成一个连续的区间。

> 示例 2:  
> 输入: \[0,2,3,4,6,8,9\]  
> 输出: \[“0”,“2->4”,“6”,“8->9”\]  
> 解释: 2,3,4 可组成一个连续的区间; 8,9 可组成一个连续的区间

思路：利用两个指针的方法将符合条件的数列转换为字符串添加到返回列表中

def summaryRanges(self, nums: List[int]) -> List[str]:
            if not nums:
                return []
            res = []
            n = len(nums)
            if n==1:
                return [str(nums[0])]
            start = 0
            end = 1
            while end < n:
                if nums[end]-nums[end-1]==1:
                    while end<n and nums[end]-nums[end-1]==1:
                        end+=1
                    res.append(str(nums[start])+'->'+str(nums[end-1]))
                else:
                    res.append(str(nums[start]))
                    
                start = end
                if start==n-1:
                    res.append(str(nums[start]))
                end+=1
            return res

C++ 写法，思路也是两个指针的操作

vector<string> summaryRanges(vector<int>& nums) { 
            vector<string>res;
            for(int i =0;i<nums.size();++i){ 
                string str = to_string(nums[i]);
                int j = i;
                while(i < nums.size()-1 && 
                    nums[i+1] - 1 == nums[i]){ 
                    ++i;
                }
                if(i-j>=1){ 
                    str = str+"->"+to_string(nums[i]);
                }
                res.push_back(str);
            }
            return res;
        }

### 4、旋转数组 ###

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数

> 示例1  
> 输入: \[1,2,3,4,5,6,7\] 和 k = 3  
> 输出: \[5,6,7,1,2,3,4\]  
> 解释:  
> 向右旋转 1 步: \[7,1,2,3,4,5,6\]  
> 向右旋转 2 步: \[6,7,1,2,3,4,5\]  
> 向右旋转 3 步: \[5,6,7,1,2,3,4\]

> 示例2  
> 输入: \[-1,-100,3,99\] 和 k = 2  
> 输出: \[3,99,-1,-100\]  
> 解释:  
> 向右旋转 1 步: \[99,-1,-100,3\]  
> 向右旋转 2 步: \[3,99,-1,-100\]

def rotate(nums, k):
    	nums[:] = nums[-k%len(nums): ] + nums[: -k%len(nums)]

nums\[:\] 和 nums 里面的元素值一样，但是当元素值发生改变的时候，用nums\[:\]这种格式， id 会保持不变。也就是在原来的基础上改变。

k = len(nums)-k%len(nums)
     if k:
     	nums[:] = nums[k:]+nums[:k]

分别对三块区域进行翻转，先翻转左边，再翻转右边，最后整体翻转

def rotate(self, nums: List[int], k: int) -> None:
            def reverse_(nums,left,right):
                while left<right:
                    nums[left],nums[right]=nums[right],nums[left]
                    left+=1
                    right-=1
            k = len(nums)-k%len(nums)
            reverse_(nums,0,k-1)
            reverse_(nums,k,len(nums)-1)
            reverse_(nums,0,len(nums)-1)

C++版本

class Solution { 
    public:
        void reverse_(vector<int>& nums,int left,int right){ 
            while (left<right){ 
                swap(nums[left++],nums[right--]);
            }
        }
        void rotate(vector<int>& nums, int k) { 
            int n = nums.size()-k%(nums.size());
            reverse_(nums,0,n-1);
            reverse_(nums,n,nums.size()-1);
            reverse_(nums,0,nums.size()-1);
        }
        // C ++ 中也有这个库函数
        // k = k % nums.size();
    	// reverse(nums.begin(), nums.begin() + nums.size() - k);
    	// reverse(nums.begin() + nums.size() - k, nums.end());
        // reverse(nums.begin(), nums.end());
    };

### 5、颠倒二进制位 ###

颠倒给定的 32 位无符号整数的二进制位

> 示例1  
> 输入: 00000010100101000001111010011100  
> 输出: 00111001011110000010100101000000  
> 解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000

> 示例2  
> 输入：11111111111111111111111111111101  
> 输出：10111111111111111111111111111111  
> 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，  
> 因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001

def reverseBits(n):
    	n = '{0:032b}'.format(n)[::-1]
        return int(n,2)

--------------------

C++ 版本

> uint8\_t\\uint\_16\_t\\uint32\_t\\uint64\_t  
> 这些类型的来源：这些数据类型中都带有\_t, \_t 表示这些数据类型是通过 typedef 定义的，而不是新的数据类型。也就是说，它们其实是我们已知的类型的别名,使用这些变量的原因是方便维护。

> uint8\_t 相当于 char 类型占1个字节  
> uint16\_t 相当于 short 类型占2个字节  
> uint32\_t 相当于 int 类型占4个字节  
> uint64\_t 相当于 long 类型占8个字节

方法一

uint32_t reverseBits(uint32_t n) { 
            uint32_t ans = 0;
            int i = 32;
            while(i--){ 
                ans = ans<<1;
                ans +=n&1;// 把 n 的尾数加在 ans 的后面
                n = n>>1;
            }
            return ans;
        }

方法二：这种方法是先交换 32 中的16位数字，然后再交换16中的 8 位数字，再交换 8位数字中的 4 位数字，… 直到交换 2 位数字，就完成了翻转.

uint32_t reverseBits(uint32_t n) { 
            n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16); 
            n = ((n & 0xff00ff00) >>  8) | ((n & 0x00ff00ff) <<  8);  
            n = ((n & 0xf0f0f0f0) >>  4) | ((n & 0x0f0f0f0f) <<  4);  
            n = ((n & 0xcccccccc) >>  2) | ((n & 0x33333333) <<  2);  
            n = ((n & 0xaaaaaaaa) >>  1) | ((n & 0x55555555) <<  1);  
            return n;
        }

### 6、数字范围按位与 ###

给定范围 \[m, n\]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）

> 示例1  
> 输入: \[5,7\]  
> 输出: 4

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

def rangeBitwiseAnd(self, m: int, n: int) -> int:
            temp = m
            for i in range(m+1,n+1):
                temp &=i
            return temp

优化代码

**思路**：一旦 n 的二进制小于 m，就一定返回 0，而此时 n 的值就是 0

在循环里面，n 只会越来越小，一旦 n 和 n-1 的值是进位的话，就会返回 0，进位关系就是

3 和 4 之间
    011
    100
    
    7 和 8 之间
    0111
    1000

所以两个数字如果足够大，里面很多的案例返回都是0，只有不发生进位的时候，才进行一个一个的 & 操作

def rangeBitwiseAnd(self, m: int, n: int) -> int:
    	while m<n:
        	n = n&(n-1)
    	return n