【每日刷题】Day178
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 260. 只出现一次的数字 III - 力扣（LeetCode）
2. 167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）
3. 392. 判断子序列 - 力扣（LeetCode）
1. 260. 只出现一次的数字 III - 力扣（LeetCode）
//思路：位运算
class Solution {
public:
vector<int> singleNumber(vector<int>& nums)
{
int tmp = 0;
for(auto i:nums) tmp^=i;//tmp = val1^val2
int diff = 0;//diff定位到 val1 val2 第一个不相同的位，此时 val1 val2 有且仅有一个该位置为1，另一个则为0
while(diff<31)
{
if(((tmp>>diff)&1)==1) break;
else diff++;
}
int ans1 = 0,ans2 = 0;
for(auto i:nums)
if(((i>>diff)&1)==1) ans2^=i;//分离操作，这里记录进 ans1 ans2 无所谓，分离开就行
else ans1^=i;
return {ans1,ans2};
}
};
2. 167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）
//思路：二分。
//利用数组有序的特性，每次固定数组左端的元素，去右边区间进行二分查找。
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target)
{
int n = numbers.size();
vector<int> ans(2);
for(int i = 0;i<n-1;i++)// i是固定的左端元素，每轮右移
{
int left = i+1,right = n-1;//去右边区间二分
while(left<=right)
{
int mid = (left+right)/2;
if(numbers[i]+numbers[mid]>target) right = mid-1;
else if(numbers[i]+numbers[mid]<target) left = mid+1;
else
{
ans[0] = i+1;
ans[1] = mid+1;
return ans;
}
if(left<n&&numbers[i]+numbers[left]==target)//处理边界情况
{
ans[0] = i+1;
ans[1] = left+1;
return ans;
}
else if(right>=0&&numbers[i]+numbers[right]==target)
{
ans[0] = i+1;
ans[1] = right+1;
return ans;
}
}
}
return ans;
}
};
3. 392. 判断子序列 - 力扣（LeetCode）
//思路：双指针一次查询。
//定义 left 指针遍历 字符串s，right指针遍历 字符串t。当 s[left] == t[right] 时，left++，right一直保持++。
class Solution {
public:
bool isSubsequence(string s, string t)
{
int n = s.size(),m = t.size();
int left = 0,right = 0;
while(left<n&&right<m)
{
if(s[left]==t[right]) left++;
right++;
}
if(left==n) return true;//left==n说明 s 存在于 t 中
return false;
}
};
