基礎類型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
![LeetCode231——2的幂[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)