力扣题解
力扣 no.88\ 给你两个按非递减顺序排列的整数数组 nums1 和 nums2, 另有两个整数 m 和 n , 分别表示 nums1 和 nums2 中的元素数目\ 请你合并 nums2 到 nums1 中, 使合并后的数组同样按非递减顺序排列
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int m1(0),n1(0);
int num[m+n];
for(int i=0;i<m+n;){
if(m1==m){
while(i<m+n) num[i++]=nums2[n1++];
break;
}
if(n1==n){
while(i<m+n) num[i++]=nums1[m1++];
break;
}
if(nums1[m1]<=nums2[n1]) num[i++]=nums1[m1++];
else num[i++]=nums2[n1++];
}
for(int i=0;i<m+n;i++) nums1[i]=num[i];
}
};
非常简单, 两个有序数组归并 但是我没有从后归浪费了空间
力扣 no.27\ 给你一个数组 nums 和一个值 val, 你需要原地移除所有数值等于 val 的元素 元素的顺序可能发生改变 然后返回 nums 中与 val 不同的元素的数量
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int r=nums.size(),l(0);
for(l;l<r;l++){
if(nums[l]==val){
while(r--){
if(r==l) return l;
if(nums[r]!=val) break;
}
nums[l]=nums[r];
}
}
return l;
}
};
双指针去除数 调了好久, 思路是对的
力扣 no.26\ 给你一个 非严格递增排列 的数组 nums , 请你原地删除重复出现的元素, 使每个元素只出现一次, 返回删除后数组的新长度元素的相对顺序, 应该保持一致, 然后返回 nums 中唯一元素的个数
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int s(1),mn=nums.size();
for(int q=1;q<mn;q++){
if(nums[q]==nums[q-1]) continue;
else nums[s++]=nums[q];
}
return s;
}
};
去除重复数, 双指针一样简单
力扣 no.80\ 给你一个有序数组 nums, 请你原地删除重复出现的元素, 使得出现次数超过两次的元素只出现两次, 返回删除后数组的新长度\ 不要使用额外的数组空间, 你必须在原地修改输入数组 并在使用 \(O(1)\) 额外空间的条件下完成
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int i(1),j(1),cnt(0);
for(j;j<nums.size();j++){
if(nums[j]==nums[j-1]) cnt++;
else cnt=0;
if(cnt<2) nums[i++]=nums[j];
}
return i;
}
};
一样的简单双指针
力扣 no.169\ 给定一个大小为 n 的数组 nums , 返回其中的多数元素 多数元素是指在数组中出现次数 大于 \(⌊n/2⌋\) 的元素\ 你可以假设数组是非空的, 并且给定的数组总是存在多数元素\ 只想到一个哈希表 太差了, 附一个官方正解
class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate = -1;
int count = 0;
for (int num : nums) {
if (num == candidate)
++count;
else if (--count < 0) {
candidate = num;
count = 1;
}
}
return candidate;
}
};
排序法 (n\2), 分治 (求众数) 随机化 摩尔投票 (超半数可用, 去除不同数对)
力扣 no.189\ 给定一个整数数组 nums, 将数组中的元素向右轮转 k 个位置, 其中 k 是非负数\ 只想到了额外空间
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k=k%nums.size();
if(!k) return;
int a[k];
for(int i=nums.size()-k,j=0;i<nums.size();i++) a[j++]=nums[i];
for(int i=nums.size()-1;i>=k;i--) nums[i]=nums[i-k];
for(int i=0;i<k;i++) nums[i]=a[i];
}
};
看了题解, 之前以为多玄妙\ 翻转就是简单的三次翻转 还有一个环状替换, 都是 \(O(1)\) 空间
力扣 no.121\
给定一个数组 prices , 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格\
你只能选择 某一天 买入这只股票, 并选择在 未来的某一个不同的日子 卖出该股票 设计一个算法来计算你所能获取的最大利润\
返回你可以从这笔交易中获取的最大利润 如果你不能获取任何利润, 返回 0\
维护此前最小值
class Solution {
public:
int maxProfit(vector<int>& prices) {
int min(0),max(0);
for(int i=1;i<prices.size();i++){
if(prices[i]-prices[min]>max) max=prices[i]-prices[min];
if(prices[i]<prices[min]) min=i;
}
return max;
}
};
正解
力扣 no.122\
给你一个整数数组 prices , 其中 prices[i] 表示某支股票第 i 天的价格\
在每一天, 你可以决定是否购买和出售股票 你在任何时候 最多 只能持有 一股 股票 你也可以先购买, 然后在 同一天 出售\
返回 你能获得的 最大 利润\
递增累加, 递减不计
秒杀
class Solution {
public:
int maxProfit(vector<int>& prices) {
int sum(0);
for(int i=1;i<prices.size();i++)
if(prices[i]>prices[i-1]) sum+=prices[i]-prices[i-1];
return sum;
}
};
正解 动态规划也可以, 空间稍微多点
力扣 no.55\
给你一个非负整数数组 nums , 你最初位于数组的 第一个下标 数组中的每个元素代表你在该位置可以跳跃的最大长度
判断你是否能够到达最后一个下标, 如果可以, 返回 true ; 否则, 返回 false
class Solution {
public:
bool canJump(vector<int>& nums) {
int m(0);
for(int i=0;i<nums.size();i++){
if(i>m) return 0;
if(nums[i]+i>m) m=nums[i]+i;
}
return 1;
}
};
维护可到达区域
力扣 no.45\
给定一个长度为 n 的 0 索引整数数组 nums 初始位置为 nums[0]\
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度\
返回到达 nums[n-1] 的最小跳跃次数 生成的测试用例可以到达 nums[n-1]
class Solution {
public:
int jump(vector<int>& nums) {
int m=nums[0]+1,cnt(1);
if(nums.size()==1) return 0;
while(m<nums.size()){
int j=m;
for(int i=0;i<j;i++){
m=max(m,nums[i]+i+1);
}
cnt++;
}
return cnt;
}
};
思路没错, 嘎嘎调试, 忘记保存 m 的值
力扣 no.274\
给你一个整数数组 citations , 其中 citations[i] 表示研究者的第 i 篇论文被引用的次数 计算并返回该研究者的 h 指数\
根据维基百科上 h 指数的定义:h 代表 "高引用次数", 一名科研人员的 h 指数是指他至少发表了 h 篇论文, 并且至少有 h 篇论文被引用次数大于等于 h 如果 h 有多种可能的值,h 指数是其中最大的那个
class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.rbegin(),citations.rend());
for(int i=0;i<citations.size();i++){
if(i+1>citations[i]) return i;
}
return citations.size();
}
};
排序秒杀\
研究了一下题解, 由于 h 在 [0,n] 中分布的特性
引出二分, 计数排序 \(O(n)\), 差分, 等方法
力扣 no.380
实现 RandomizedSet 类:
RandomizedSet() 初始化 RandomizedSet 对象
bool insert (int val) 当元素 val 不存在时, 向集合中插入该项, 并返回 true ; 否则, 返回 false\
bool remove (int val) 当元素 val 存在时, 从集合中移除该项, 并返回 true ; 否则, 返回 false\
int getRandom () 随机返回现有集合中的一项 (测试用例保证调用此方法时集合中至少存在一个元素) 每个元素应该有 相同的概率 被返回
你必须实现类的所有函数, 并满足每个函数的 平均 时间复杂度为 \(O(1)\)
class RandomizedSet {
public:
RandomizedSet() {
srand((unsigned)time(NULL));
}
bool insert(int val) {
if (indices.count(val)) {
return false;
}
int index = nums.size();
nums.emplace_back(val);
indices[val] = index;
return true;
}
bool remove(int val) {
if (!indices.count(val)) {
return false;
}
int index = indices[val];
int last = nums.back();
nums[index] = last;
indices[last] = index;
nums.pop_back();
indices.erase(val);
return true;
}
int getRandom() {
int randomIndex = rand()%nums.size();
return nums[randomIndex];
}
private:
vector<int> nums;
unordered_map<int, int> indices;
};
没做出来, 附一个官方解 我用 bitset 存元素状态, 数组来存数以随机 但是样本有针对检验的, 使退化到 \(O(n)\)
力扣 no.9
给你一个整数 x , 如果 x 是一个回文整数, 返回 true ; 否则, 返回 false
class Solution {
public:
bool isPalindrome(int x) {
std::string s=to_string(x);
for(int i=0;i<s.size()/2;i++){
if(s[i]==s[s.size()-1-i]);
else return 0;
}
return 1;
}
};
被题解羞辱了 反转一半数字, 直到剩下的小于等于反转的
力扣 no.13\ 罗马数字转整数
class Solution {
public:
int romanToInt(string s) {
int sum(0);
int cnt[s.size()];
for(int i=s.size()-1;i>-1;i--){
switch(s[i]){
case 'I':cnt[i]=1;break;
case 'V':cnt[i]=5;break;
case 'X':cnt[i]=10;break;
case 'L':cnt[i]=50;break;
case 'C':cnt[i]=100;break;
case 'D':cnt[i]=500;break;
case 'M':cnt[i]=1000;
}
if((i==s.size()-1)||cnt[i]>=cnt[i+1]) sum+=cnt[i];
else sum-=cnt[i];
}
return sum;
}
};
简单
力扣 no.14\
编写一个函数来查找字符串数组中的最长公共前缀\
如果不存在公共前缀, 返回空字符串 ""
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string s;
for(int i(0);strs[0][i];i++){
for(int j(1);j<strs.size();j++){
if(strs[j][i]==strs[0][i]) continue;
else return s;
}
s+=strs[0][i];
}
return s;
}
};
用的横向查找 可以分治, 二分搜索, 纵向
力扣 no.28 给你两个字符串 haystack 和 needle, 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标 (下标从 0 开始) 如果 needle 不是 haystack 的一部分, 则返回 -1
class Solution {
public:
int strStr(string haystack, string needle) {
for(int i(0);i<haystack.size();i++){
if(haystack[i]==needle[0]){
int a(i),j(0);
for(j;j<needle.size();j++) if(haystack[a++]!=needle[j]) goto a;
return i;
}
a:
}
return -1;
}
};
顺手写一个暴力 \(O(mn)\) 正解 KMP
力扣 no.58\ 给你一个字符串 s, 由若干单词组成, 单词前后用一些空格字符隔开, 返回字符串中最后一个单词的长度\ 单词是指仅由字母组成且不包含任何空格字符的最大子字符串
class Solution {
public:
int lengthOfLastWord(string s) {
int ans(0),i(s.size()-1);
for(i;s[i]==' ';i--);
for(i;i>=0&&s[i]!=' ';i--) ans++;
return ans;
}
};
今天打牛客, 水一道简单
力扣 no.125\
如果在将所有大写字符转换为小写字符 并移除所有非字母数字字符之后, 短语正着读和反着读都一样, 则可以认为该短语是一个回文串\
字母和数字都属于字母数字字符\
给你一个字符串 s, 如果它是回文串 , 返回 true 否则, 返回 false
class Solution {
public:
bool isPalindrome(string s) {
int r(s.size()-1),l(0);
while(r>l){
if(s[r]<'0'||(s[r]>'9'&&s[r]<'A')||(s[r]>'Z'&&s[r]<'a')||s[r]>'z'){
r--;continue;
}
if(s[l]<'0'||(s[l]>'9'&&s[l]<'A')||(s[l]>'Z'&&s[l]<'a')||s[l]>'z'){
l++;continue;
}
if(s[l]==s[r]||(s[r]>='a'&&s[l]+32==s[r])||(s[l]>='a'&&s[l]==s[r]+32)){
r--;l++;continue;
}
else return 0;
}
return 1;
}
};
双指针秒杀
力扣 no.392\ 给定字符串 s 和 t , 判断 s 是否为 t 的子序列\ 字符串的一个子序列是原始字符串删除一些 (也可以不删除) 字符而不改变剩余字符相对位置形成的新字符串 (例如,"ace" 是 "abcde" 的一个子序列, 而 "aec" 不是)\ 如果有大量输入的 S, 称作 S1, S2, ... , Sk 其中 k >= 10 亿, 你需要依次检查它们是否为 T 的子序列
class Solution {
public:
bool isSubsequence(string s, string t) {
int m(0);
for(int i(0);i<s.size();i++){
while(m<=t.size()) if(t[m++]==s[i]) break;
if(m==t.size()+1) return 0;
}
return 1;
}
};
双指针\ 动态规划
class Solution {
public:
bool isSubsequence(string s, string t) {
int n = s.size(), m = t.size();
vector<vector<int> > f(m + 1, vector<int>(26, 0));
for (int i = 0; i < 26; i++) {
f[m][i] = m;
}
for (int i = m - 1; i >= 0; i--) {
for (int j = 0; j < 26; j++) {
if (t[i] == j + 'a')
f[i][j] = i;
else
f[i][j] = f[i + 1][j];
}
}
int add = 0;
for (int i = 0; i < n; i++) {
if (f[add][s[i] - 'a'] == m) {
return false;
}
add = f[add][s[i] - 'a'] + 1;
}
return true;
}
};
对于每一字符, 我们可以预处理出对于每一个位置, 下一个出现某字符的位置
力扣 no.383\
给你两个字符串: ransomNote 和 magazine , 判断 ransomNote 能不能由 magazine 里面的字符构成\
如果可以, 返回 true ; 否则返回 false\
magazine 中的每个字符只能在 ransomNote 中使用一次
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int a[256]={0};
for(int i(0);i<magazine.size();i++) a[magazine[i]]++;
for(int i(0);i<ransomNote.size();i++) if(--a[ransomNote[i]]==-1) return 0;
return 1;
}
};
力扣 no.205\ 给定两个字符串 s 和 t , 判断它们是否是同构的\ 如果 s 中的字符可以按某种映射关系替换得到 t , 那么这两个字符串是同构的\ 每个出现的字符都应当映射到另一个字符, 同时不改变字符的顺序, 不同字符不能映射到同一个字符上, 相同字符只能映射到同一个字符上, 字符可以映射到自己本身
class Solution {
public:
bool isIsomorphic(string s, string t) {
int c1[256]={0},c2[256]={0};
for(int i(0);i<s.size();i++){
if(!c1[s[i]]&&!c2[t[i]]){
c1[s[i]]=t[i];
c2[t[i]]=s[i];
}
else if(c1[s[i]]!=t[i]||c2[t[i]]!=s[i]) return 0;
}
return 1;
}
};
哈希双射
力扣 no.1\ 给定一个整数数组 nums 和一个整数目标值 target, 请你在该数组中找出 和为目标值 target 的那两个整数, 并返回它们的数组下标
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
return {it->second, i};
}
hashtable[nums[i]] = i;
}
return {};
}
};
力扣 no.202\
编写一个算法来判断一个数 n 是不是快乐数\
对于一个正整数, 每一次将该数替换为它每个位置上的数字的平方和\
然后重复这个过程直到这个数变为 1, 也可能是 无限循环 但始终变不到 1\
如果这个过程结果为 1, 那么这个数就是快乐数\
如果 n 是快乐数 就返回 true ; 不是, 则返回 false
class Solution {
int happy(int n){
int sum;
for(sum=0;n>0;n/=10) sum+=(n%10)*(n%10);
return sum;
}
public:
bool isHappy(int n) {
map<int,bool> m;
while(n!=1){
n=happy(n);
if(m[n]) return 0;
m[n]=1;
}
return 1;
}
};
快慢指针判断环更好!!!\ 数学角度, 这道题其实只能存在一个环, 找到那个环, 然后只要到达某一个数字就返回 0
力扣 no.238\
给你一个整数数组 nums, 返回数组 answer , 其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积\
题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内\
请不要使用除法, 且在 \(O(n)\) 时间复杂度内完成此题
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len=nums.size();
vector<int> l(len),r(len),v(len);
l[0]=r[len-1]=1;
for(int i(1);i<len;i++) l[i]=l[i-1]*nums[i-1];
for(int i(len-2);i>=0;i--) r[i]=r[i+1]*nums[i+1];
for(int i(0);i<len;i++) v[i]=l[i]*r[i];
return v;
}
};
前缀积与后缀积\ 可以省去两个数组, 初始化一个前缀数组在动态计算后缀积的同时将前数组改变
力扣 no.167\ 给你一个下标从 1 开始的整数数组 numbers , 该数组已按 非递减顺序排列, 请你从数组中找出满足相加之和等于目标数 target 的两个数\ 你可以假设每个输入只对应唯一的答案 , 而且你不可以重复使用相同的元素\ 你所设计的解决方案必须只使用常量级的额外空间
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int len(numbers.size());
vector<int> ans(2);
ans[0]=0;ans[1]=len-1;
while(numbers[ans[0]]+numbers[ans[1]]!=target){
if(numbers[ans[0]]+numbers[ans[1]]>target) ans[1]--;
if(numbers[ans[0]]+numbers[ans[1]]<target) ans[0]++;
}
ans[0]++;
ans[1]++;
return ans;
}
};
第一次中等题一遍出正解
力扣 no.151 给你一个字符串 s , 请你反转字符串中 单词 的顺序
class Solution {
public:
string reverseWords(string s) {
string ans;
int i(s.size()-1);
for(;i>=0;i--) if(s[i]!=' ') break;
for(;i>=0;i--){
if(s[i]==' '&&s[i+1]!=' '){
for(int k=i+1;k<s.size()&&s[k]!=' ';k++) ans+=s[k];
ans+=' ';
}
}
if(s[0]!=' ')
for(int k=0;k<s.size()&&s[k]!=' ';k++) ans+=s[k];
else ans.erase(ans.size()-1);
return ans;
}
};
双端队列也可以
力扣 no.141 环形链表
class Solution {
public:
bool hasCycle(ListNode *head) {
if(!head||!head->next) return 0;
ListNode *q(head->next->next),*s(head->next);
for(;;q=q->next->next,s=s->next){
if(!q||!q->next||!s) return 0;
if(q==s) return 1;
}
return 0;
}
};
快慢指针!
力扣 no.21 将两个升序链表合并为一个新的升序链表并返回 新链表是通过拼接给定的两个链表的所有节点组成的
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode a(0);
ListNode *ans=&a;
while(list1&&list2){
if(list1->val<=list2->val){
ans->next=list1;
list1=list1->next;
}
else{
ans->next=list2;
list2=list2->next;
}
ans=ans->next;
}
if(list1) ans->next=list1;
else ans->next=list2;
return a.next;
}
};
美丽的递归, 何时我能与她心有灵犀
力扣 no.12\ 整数转罗马数字
class Solution {
public:
string intToRoman(int num) {
string s;
for(num;num>=1000;num-=1000) s+='M';
if(num>=900){
num-=900;
s+="CM";
}
if(num>=500){
num-=500;
s+='D';
}
if(num>=400){
num-=400;
s+="CD";
}
for(num;num>=100;num-=100) s+='C';
if(num>=90){
num-=90;
s+="XC";
}
if(num>=50){
num-=50;
s+='L';
}
if(num>=40){
num-=40;
s+="XL";
}
for(num;num>=10;num-=10) s+='X';
if(num>=9){
num-=9;
s+="IX";
}
if(num>=5){
num-=5;
s+='V';
}
if(num>=4){
num-=4;
s+="IV";
}
for(num;num;num--) s+='I';
return s;
}
};
模拟或者硬解码
明显硬解码好看
力扣 no.2 链表模拟加法
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int tmp(0);
ListNode* ans=l1;
while(l1->next&&l2->next){
if((l1->val=l1->val+l2->val+tmp)>9){
l1->val-=10;tmp=1;
}
else tmp=0;
l1=l1->next;
l2=l2->next;
}
if((l1->val=l1->val+l2->val+tmp)>9){
l1->val-=10;tmp=1;
}
else tmp=0;
if(!l1->next&&!l2->next);
else if(l1->next){
while(l1->next){
l1=l1->next;
if((l1->val+=tmp)>9){
l1->val-=10;tmp=1;
}
else tmp=0;
}
}
else
while(l2->next){
l1->next=new ListNode;
l1=l1->next;
l2=l2->next;
if((l1->val=l2->val+tmp)>9){
l1->val-=10;tmp=1;
}
else tmp=0;
}
if(tmp){
l1->next=new ListNode;
l1=l1->next;
l1->val=1;
l1->next=0;
}
return ans;
}
};
力扣 no.11
给定一个长度为 n 的整数数组 height 有 n 条垂线, 第 i 条线的两个端点是 (i, 0) 和 (i, height[i])\
找出其中的两条线, 使得它们与 x 轴共同构成的容器可以容纳最多的水\
返回容器可以储存的最大水量
class Solution {
public:
int maxArea(vector<int>& h) {
int l(0),r(h.size()-1);
int ans(0);
while(l<r){
ans=ans>min(h[l],h[r])*(r-l)?ans:min(h[l],h[r])*(r-l);
if(h[l]<=h[r]) l++;
else r--;
}
return ans;
}
};
谁小换谁\ 非常简单, 重点在算法可行性
力扣 no.70 假设你正在爬楼梯 需要 n 阶你才能到达楼顶\ 每次你可以爬 1 或 2 个台阶 你有多少种不同的方法可以爬到楼顶呢
class Solution {
public:
int climbStairs(int n) {
vector<int> ans(n+1);
ans[0]=1;ans[1]=1;
for(int i=2;i<n+1;i++) ans[i]=ans[i-2]+ans[i-1];
return ans[n];
}
};
动态规划秒了, 不知道可以算通项我还美呢\ 正解矩阵快速幂........
力扣 no.35\ 给定一个排序数组和一个目标值, 在数组中找到目标值, 并返回其索引如果目标值不存在于数组中, 返回它将会被按顺序插入的位置
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left=0,right=nums.size()-1;
while(left<=right){
mid=(left+right)/2;
if(nums[mid]<target){
left=mid+1;
}
else{
right=mid-1;
}
}
return left;
}
};
二分查找
力扣 no.191\ 编写一个函数, 输入是一个无符号整数 (以二进制串的形式), 返回其二进制表达式中数字位数为 '1' 的个数 (也被称为汉明重量)
基于n&(n-1)恰为把n的二进制位中的最低位的 1 变为 0
class Solution {
public:
int hammingWeight(uint32_t n) {
int ret = 0;
while (n) {
n &= n - 1;
ret++;
}
return ret;
}
};
SWAP算法, $O(1)$,分治思想
public class Solution {
public int hammingWeight(int n) {
n = n - ((n >>> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
n = (n + (n >>> 4)) & 0x0f0f0f0f;
n = n + (n >>> 8);
n = n + (n >>> 16);
return n & 0x3f;
}
}
力扣 no.136 给定一个非空整数数组, 除了某个元素只出现一次以外, 其余每个元素均出现两次 找出那个只出现了一次的元素
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans(0);
for(int i(0);i<nums.size();i++) ans^=nums[i];
return ans;
}
};
异或秒杀
力扣 no.134\
给定一个整数数组 gas , 其中 gas[i] 表示在第 i 个加油站有多少汽油\
给定一个整数数组 cost , 其中 cost[i] 表示从第 i 个加油站开往第 i+1 个加油站需要消耗的汽油\
如果你可以按顺序绕环路行驶一周, 则返回出发时加油站的编号, 否则返回 -1
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int l(gas.size()),a[gas.size()];
for(int i(0);i<l;i++) a[i]=gas[i]-cost[i];
int e(-1),f(l),sum(0);
while(1){
if(sum>=0){
if(e+1<l) e++;
else return 0;
sum+=a[e];
if(e==f) break;
}
else{
sum+=a[--f];
if(f==e) return -1;
}
}
return f;
}
};
顺序遍历即可, 我双指针复杂了
力扣 no.42\ 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图, 计算按此排列的柱子, 下雨之后能接多少雨水
class Solution {
public:
int trap(vector<int>& height) {
int l(0),r(height.size()-1),m(0),ans(0);
while(l<r){
m=max(m,min(height[l],height[r]));
if(height[l]<m) ans+=m-height[l];
if(height[r]<m) ans+=m-height[r];
if(height[l]<=height[r]) l++;
else r--;
}
return ans;
}
};
hard 出正解, 好!
力扣 no.754\ 在一根无限长的数轴上, 你站在 0 的位置 终点在 target 的位置\ 每次你可以选择向左或向右移动第 n 次移动 (从 1 开始), 可以走 n 步\ 返回到达终点需要的最小移动次数
class Solution {
public:
int reachNumber(int target) {
target = abs(target);
int n = (-1 + sqrt(1 + 8.0 * target)) / 2;
int d = target - n * (n + 1) / 2;
if (!d) return n;
d -= ++n;
return (d & 1 ? n + 1 + n % 2 : n);
}
};
数学 + 贪心 \(O(1)\) 秒杀,sqrt 现代 CPU 有指令
力扣 no.20\
给定一个只包括 '(' ')' '{' '}' '[' ']' 的字符串 s , 判断字符串是否有效
class Solution {
public:
bool isValid(string s) {
stack<int> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') st.push(i);
else {
if (st.empty()) return false;
if (s[i] == ')' && s[st.top()] != '(') return false;
if (s[i] == '}' && s[st.top()] != '{') return false;
if (s[i] == ']' && s[st.top()] != '[') return false;
st.pop();
}
}
return st.empty();
}
};
堆栈秒杀
力扣 no.190\ 颠倒给定的 32 位无符号整数的二进制位
uint32_t reverseBits(uint32_t n) {
uint32_t result = 0;
for (int i = 0; i < 32; ++i) {
result <<= 1;
result |= (n & 1);
n >>= 1;
}
return result;
}
正解是分治
力扣 no.66\ 给定一个由整数组成的非空数组所表示的非负整数, 在该数的基础上加一\ 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int l(digits.size());
while(l--){
if(digits[l]==9){
digits[l]=0;
continue;
}
else{
digits[l]++;
return digits;
}
}
vector<int> ans(digits.size()+1);
ans[0]=1;
return ans;
}
};
考虑最长 9 后缀
力扣 no.69\
实现 int sqrt(int x) 函数
class Solution {
public:
int mySqrt(int x) {
int l = 0, r = x, ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long long)mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
};
附一个二分法\ 还有袖珍计算器法和牛顿迭代法
力扣 no.50\
实现 pow(x, n) 函数
class Solution {
public:
double myPow(double x, int n) {
if (x == 0) return 0; // 如果底数x为0,则结果为0
if (x == 1 || n == 0) return 1; // 如果底数x为1或者指数n为0,则结果为1
if (x == -1) return n % 2 == 1 ? -1 : 1; // 如果底数x为-1,指数n为奇数时结果为-1,为偶数时结果为1
if (n < 0) { // 如果指数n为负数
if (n == INT_MIN) { // 如果n为INT_MIN,直接取相反数会有溢出风险
// 需要特殊处理,先计算x的INT_MAX次幂,再乘以x
return 1 / (myPow(x, static_cast<int>(INT_MAX)) * x);
}
// 对于其他负指数情况,计算其倒数的正指数次幂
return 1 / myPow(x, -n);
}
// 对于正指数情况,调用递归函数计算x的n次幂
return pow_(x, n);
}
private:
double pow_(double x, int n) {
double result = 1.0;
double current_product = x;
while (n > 0) {
if (n % 2 == 1) {
result *= current_product;
}
current_product *= current_product;
n /= 2;
}
return result;
}
};
附一个正解\ 还有递归
力扣 no.172\ 给定一个整数 n, 返回 \(n!\) 结果尾数中零的数量
class Solution {
public:
int trailingZeroes(int n) {
int ans(0);
int a[6]={1,5,25,125,625,3125};
for(int i(1);i<6;i++){
ans+=n/a[i];
}
return ans;
}
};
//正解
class Solution {
public:
int trailingZeroes(int n) {
int ans = 0;
while (n) {
n /= 5;
ans += n;
}
return ans;
}
};
我是小丑
力扣 no.198\ 你是一个专业的小偷, 计划偷窃沿街的房屋每间房内都藏有一定的现金, 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入, 系统会自动报警\ 给定一个代表每个房屋存放金额的非负整数数组, 计算你 不触动警报装置的情况下, 一夜之内能够偷窃到的最高金额
class Solution {
public:
int rob(vector<int>& nums) {
vector<int> m(nums.size()+1);
m[1]=nums[0]; //手动进行前两步,就不用预留m[0],也不用size+1
for(int i(2);i<nums.size()+1;i++) m[i]=max(m[i-1],m[i-2]+nums[i-1]);
return m[nums.size()];
}
};
使用滚动数组, 存前两位,\(O(1)\) 空间
力扣 no.162\ 给你一个整数数组 nums, 找到峰值元素并返回其索引, 数组可能包含多个峰值, 在这种情况下, 返回任何一个峰值所在位置即可
class Solution {
public:
int findPeakElement(vector<int>& nums) {
if(nums.size()==1) return 0;
if(nums.size()==2) return nums[0]<nums[1];
int i(nums.size()/2);
while(i>0&&i<nums.size()-1){
if(nums[i]>nums[i+1]){
if(nums[i]>nums[i-1]) return i;
else i--;
}
else i++;
}
if(!i) return 0;
return nums.size()-1;
}
};
//写成一坨
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int n = nums.size();
// 辅助函数,输入下标 i,返回一个二元组 (0/1, nums[i])
// 方便处理 nums[-1] 以及 nums[n] 的边界情况
auto get = [&](int i) -> pair<int, int> {
if (i == -1 || i == n) {
return {0, 0};
}
return {1, nums[i]};
};
int left = 0, right = n - 1, ans = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (get(mid - 1) < get(mid) && get(mid) > get(mid + 1)) {
ans = mid;
break;
}
if (get(mid) < get(mid + 1)) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return ans;
}
};
//正解
二分查找 \(O(logn)\)
力扣 no.64\ 给定一个包含非负整数的 \(m*n\) 网格 grid, 请找出一条从左上角到右下角的路径, 使得路径上的数字总和为最小
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m(grid.size()),n(grid[0].size());
for(int i(1);i<m;i++) grid[i][0]+=grid[i-1][0];
for(int i(1);i<n;i++) grid[0][i]+=grid[0][i-1];
for(int i(1);i<m;i++)
for(int j(1);j<n;j++) grid[i][j]+=min(grid[i-1][j],grid[i][j-1]);
return grid[m-1][n-1];
}
};
简简单单二维动态规划
力扣 no.82\ 给定一个已排序的链表的头 head , 删除所有重复的元素, 使每个元素只出现一次 返回已排序的链表
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head||!head->next) return head;
int tmp(0);
while(head->next->val==head->val){
tmp=head->val;
while(head->val==tmp)
if(head->next)head=head->next;
else return 0;
if(!head->next) return head;
}
ListNode *h(head),*l(head);
while(l->next){
l=l->next;
if(!l->next) break;
while(l->next->val==l->val){
tmp=l->val;
while(l->val==tmp)
if(l->next) l=l->next;
else{
h->next=0;
goto ans;
}
h->next=l;
if(!l->next) break;
}
h=l;
}
ans:
return head;
}
};
我写的太丑陋了\ 链表问题 head 会改变考虑创建哑节点
力扣 no.104\ 给定一个二叉树, 找出其最大深度
class Solution {
int d(TreeNode* root){
if(!root->left&&!root->right) return 1;
int l(1),r(1);
if(root->left) l+=d(root->left);
if(root->right) r+=d(root->right);
return max(l,r);
}
public:
int maxDepth(TreeNode* root) {
if(!root) return 0;
return d(root);
}
};
//撒子这么写
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
//正解
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
queue<TreeNode*> Q;
Q.push(root);
int ans = 0;
while (!Q.empty()) {
int sz = Q.size();
while (sz > 0) {
TreeNode* node = Q.front();Q.pop();
if (node->left) Q.push(node->left);
if (node->right) Q.push(node->right);
sz -= 1;
}
ans += 1;
}
return ans;
}
};
广度优先
力扣 no.34\
给定一个按照升序排列的整数数组 nums, 和一个目标值 target 找出给定目标值在数组中的开始位置和结束位置, 如果数组中不存在目标值 target, 返回 [1, -1]
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(!nums.size()) return (vector<int>){-1,-1};
int l(0),r(nums.size()),m(nums.size()/2);
vector<int> ans(2);
while(nums[m]!=target){
if(r-l<=1) return (vector<int>){-1,-1};
if(nums[m]>target) r=m;
else l=m;
m=l+(r-l)/2;
}
l=r=m;
while(l>-1&&nums[l]==target) l--;
while(r<nums.size()&&nums[r]==target) r++;
ans[0]=l+1;ans[1]=r-1;
return ans;
}
};
简单二分
力扣 no.19\ 给定一个链表, 删除链表的倒数第 n 个结点, 并且返回链表的头结点
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
head=new ListNode(0,head);
ListNode *s(head),*q(head);
for(;n>-1;n--) q=q->next;
while(q){
q=q->next;
s=s->next;
}
s->next=s->next->next;
return head->next;
}
};
双指针加哑节点
力扣 no.92\
给你单链表的头指针 head 和两个整数 left 和 right , 其中 left <= right, 请你反转从位置 left 到位置 right 的链表节点, 返回反转后的链表
class Solution {
public:
ListNode* reverseBetween(ListNode* h, int l, int r) {
if(l==r) return h;
r=r-l+1;
ListNode* y=new ListNode(0,h);
stack<ListNode*> s;
ListNode *p(y);
while(--l) p=p->next;
h=p;
while(r--){
p=p->next;
s.push(p);
}
p=p->next;
while(!s.empty()){
h->next=s.top();
s.pop();
h=h->next;
}
h->next=p;
return y->next;
}
};
//脑子抽了
//正常反转就行
力扣 no.83\ 给定一个已排序的链表的头 head , 删除所有重复的元素, 使每个元素只出现一次, 返回已排序的链表
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head) return head;
ListNode* d=new ListNode(0,head);
ListNode* y(head);
while(y){
if(y->val!=head->val){
head->next=y;
head=y;
}
y=y->next;
}
head->next=0;
return d->next;
}
};
超级简单, 懒一天
力扣 no.67\ 给定两个二进制字符串 a 和 b, 返回它们的和 (用二进制表示)
class Solution {
public:
string addBinary(string a, string b) {
int l1(a.size()),l2(b.size()),t(0);
if(l1>l2) b.insert(0,l1-l2,'0');
else a.insert(0,l2-l1,'0');
int l(a.size());
while(l--){
t=a[l]-'0'+b[l]-'0'+t;
if(t>1){
t-=2;
a[l]='0'+t;
t=1;
}
else{
a[l]='0'+t;
t=0;
}
}
if(t) return a.insert(0,1,'1');
return a;
}
};
//考虑用位运算优化
class Solution:
def addBinary(self, a, b) -> str:
x, y = int(a, 2), int(b, 2)
while y:
answer = x ^ y
carry = (x & y) << 1
x, y = answer, carry
return bin(x)[2:]
力扣 no.138\ 给你一个长度为 n 的链表, 每个节点包含一个额外增加的随机指针 random , 该指针可以指向链表中的任何节点或空节点\ 构造这个链表的深拷贝
class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head) return 0;
unordered_map<Node*,Node*> m;
Node* h(head);
Node* s=new Node(h->val);
m[h]=s;
h=h->next;
while(h){
Node* q=new Node(h->val);
m[h]=q;
s->next=q;
s=q;
h=h->next;
}
h=head;
while(h){
if(h->random)
m[h]->random=m[h->random];
else m[h]->random=0;
h=h->next;
}
return m[head];
}
};
本方法可以在第二个循环中链接链表, 更简洁\ 可以同时建立后继与随机, 哈希记录, 复杂度一样\ 正解建立新节点插在原链表节点后面 (哈希关系就是后继), 再拆分
力扣 no.290\ 给定一种规律 pattern 和一个字符串 s , 判断 s 是否遵循相同的规律\ 这里的遵循指完全匹配, 例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律
class Solution {
public:
bool wordPattern(string pattern, string s) {
unordered_map<char, string> p2s; // pattern中的字符到s中的字符子串的映射表
unordered_map<string, char> s2p; // s中的字符字串到pattern中的字符的映射表
int n = pattern.size();
int m = s.size();
int wordStart = 0; // 单词的起点索引
int wordEnd = 0; // 单词的终点索引(边界或指向空格),不包含
char ch;
string word;
for(int i = 0; i < n; i++){
if(wordStart >= m)return false; // 单词起点已经到达边界,说明s中的单词遍历完了;而pattern的字符还有,字符数量多余单词数,不匹配
while(wordEnd < m && s[wordEnd] != ' ')wordEnd++; // wordEnd右移直到到达s边界或者分割的空格
word = s.substr(wordStart, wordEnd - wordStart); // 截取单词
ch = pattern[i]; // 获取当前字符
if((p2s.count(ch) && p2s[ch] != word) || (s2p.count(word) && s2p[word] != ch)){
// 字符与单词没有一一映射:即字符记录的映射不是当前单词或单词记录的映射不是当前字符
return false;
}
// 更新映射,已存在的映射更新后仍然是不变的;不存在的映射将被加入
p2s[ch] = word;
s2p[word] = ch;
// 更新单词区间,起点为当前终点的下一个位置;终点初始与起点相同
wordStart = wordEnd + 1;
wordEnd = wordStart;
}
// 如果pattern遍历结束后,字符串s也遍历结束(即单词起点到达了边界),则二者匹配;
// 否则s还有单词没有匹配,字符数与单词数不匹配
return wordStart == m + 1;
}
};
就是双射\ 对 stl 不熟太难受了, 如 substr,count 这些方法
力扣 no.242\ 给定两个字符串 s 和 t , 编写一个函数来判断 t 是否是 s 的字母异位词
class Solution {
public:
bool isAnagram(string s, string t) {
int m[26]={0},l(0);
if(s.size()==t.size()) l=s.size();
else return 0;
for(int i(0);i<l;i++){
m[s[i]-'a']++;m[t[i]-'a']--;
}
for(int i(0);i<26;i++){
if(m[i]) return 0;
}
return 1;
}
};
unicode 考虑 hashmap
力扣 no.219\
给你一个整数数组 nums 和一个整数 k, 判断数组中是否存在两个 不同索引 i 和 j , 满足 nums[i] == nums[j] 且 abs (i - j) <= k
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int,int> m;
int l(nums.size());
int s(0),i(0);
for(;i<l&&i<k;i++){
if(m[nums[i]]) return 1;
else m[nums[i]]=1;
}
for(;i<l;i++){
if(m[nums[i]]) return 1;
else m[nums[i]]=1;
m[nums[s++]]=0;
}
return 0;
}
};
滑动窗口
力扣 no.228\
给定一个无重复元素的有序整数数组 nums\
返回恰好覆盖数组中所有数字最小有序区间范围列表\
nums 的每个元素都恰好被某个区间范围所覆盖, 并且不存在属于某个范围但不属于 nums 的数字 x\
列表中的每个区间范围 [a,b] 应该按如下格式输出:\
"a->b" , 如果 a != b\
"a" , 如果 a == b
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
string s;
vector<string> v;
int l(nums.size());
for(int i(0);i<l;i++){
int b(i);
for(int j(nums[i]);i<l&&nums[i]==j;j++){
i++;
if(nums[i-1]==INT_MAX) break;
}
if(i-1!=b){
s+=to_string(nums[b]);
s+="->";
s+=to_string(nums[i-1]);
v.push_back(s);
}
else v.push_back(to_string(nums[b]));
s.clear();
i--;
}
return v;
}
};
妈的, 看见题解才意识到 INT_MAX 一定是数组最后一个元素, 所以不用特判, 改一下逻辑就好
力扣 no.61\ 给定一个链表, 旋转链表, 将链表每个节点向右移动 k 个位置
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(!head) return 0;
int l(0);
ListNode *h(head),*e(head);
while(h){
l++;
h=h->next;
}
k%=l;
h=head;
while(k--) h=h->next;
while(h->next){
h=h->next;
e=e->next;
}
h->next=head;
head=e->next;
e->next=0;
return head;
}
};
力扣 no.15\
给你一个整数数组 nums, 判断是否存在三元组 [nums[i], nums[j],nums[k]] 满足 i != j i != k 且 j != k, 同时还满足 nums[i] + num[j] + nums[k] == 0 请你返回所有和为 0 且不重复的三元组
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合,随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
ans.push_back({nums[first], nums[second], nums[third]});
}
}
}
return ans;
}
};
排序加双指针
力扣 no.100 给你两棵二叉树的根节点 p 和 q, 编写一个函数来检验这两棵树是否相同
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p||!q) return p==q;
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right)&&p->val==q->val;
}
};
递归实现 DFS
力扣 no.226\ 给你一棵二叉树的根节点 root, 翻转这棵二叉树, 并返回其根节点
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return root;
invertTree(root->left);
invertTree(root->right);
TreeNode *t=root->left;
root->left=root->right;
root->right=t;
return root;
}
};
递归实现 DFS
力扣 no.112\ 给定一个二叉树和一个目标和, 判断该树中是否存在根节点到叶子节点的路径, 这条路径上所有节点值相加等于目标和
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(!root) return 0;
if(targetSum==root->val&&!root->left&&!root->right) return 1;
return hasPathSum(root->left,targetSum-root->val)||hasPathSum(root->right,targetSum-root->val);
}
};
递归实现 DFS
力扣 no.101\ 给定一个二叉树, 检查它是否是镜像对称的
class Solution {
public:
bool isSymmetric(TreeNode* l,TreeNode* r=(TreeNode*)6) {
if(r==(TreeNode*)6) return(isSymmetric(l->left,l->right));
if(!l&&!r) return 1;
else if(!l||!r) return 0;
else if(l->val!=r->val) return 0;
return isSymmetric(l->left,r->right)&&isSymmetric(l->right,r->left);
}
};
递归实现 DFS
力扣 no.102\ 给定一个二叉树, 返回其按层序遍历得到的节点值
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
queue<TreeNode*> q;
q.push(root);
short i[2000]={0},x(0);
i[0]++;
vector<int> t;
while(!q.empty()){
i[x]--;
TreeNode* r(q.front());q.pop();
if(!r) continue;
t.push_back(r->val);
if(r->left){
q.push(r->left);
i[x+1]++;
}
if(r->right){
q.push(r->right);
i[x+1]++;
}
if(!i[x]){
ans.push_back(t);
t.clear();
x++;
}
}
return ans;
}
};
这是我写的, 与正解的差距主要在我考虑确定每层节点数量的方法是动态调整不同位置的值, 但既然不同层不相干, 就可以差时用同一个变量
力扣 no.637\ 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> ans;
double a(0);
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int t=q.size();
for(int i(t);i>0;i--){
TreeNode* r(q.front());q.pop();
if(!r){
t--;
continue;
}
q.push(r->left);q.push(r->right);
a+=r->val;
}
ans.push_back(a/t);
a=0;
}
ans.pop_back();
return ans;
}
};
此即上题同思路正解
力扣 no.6\ 将一个给定字符串 s 根据给定的行数 numRows, 以从上往下从左到右进行 Z 字形排列
class Solution {
public:
string convert(string s, int numRows) {
int n = s.length(), r = numRows;
if (r == 1 || r >= n) {
return s;
}
string ans;
int t = r * 2 - 2;
for (int i = 0; i < r; ++i) { // 枚举矩阵的行
for (int j = 0; j + i < n; j += t) { // 枚举每个周期的起始下标
ans += s[j + i]; // 当前周期的第一个字符
if (0 < i && i < r - 1 && j + t - i < n) {
ans += s[j + t - i]; // 当前周期的第二个字符
}
}
}
return ans;
}
};
这么简单都没想出来\ 直接模拟都行\ 正解就是找周期规律 (对于每行跳周期, 加周期的第一个字符, 有周期的第二个字符再加)
力扣 no.135\ n 个孩子站成一排 给你一个整数数组 ratings 表示每个孩子的评分\ 你需要按照以下要求, 给这些孩子分发糖果:\ 每个孩子至少分配到 1 个糖果\ 相邻两个孩子评分更高的孩子会获得更多的糖果\ 请你给每个孩子分发糖果, 计算并返回需要准备的最少糖果数目
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> a(ratings.size(),1);
int l(ratings.size());
for(int i(1);i<l;i++){
if(ratings[i]>ratings[i-1]) a[i]=a[i-1]+1;
}
int ans=a[l-1];
for(int i(l-2);i>=0;i--){
if(ratings[i]>ratings[i+1]&&a[i]<=a[i+1]) a[i]=a[i+1]+1;
ans+=a[i];
}
return ans;
}
};
两次遍历解决\ 但本质无需建立数组再加和, 只要记录当前位置所在的最长单调序列, 即可在 \(O(1)\) 空间解决
力扣 no.68\
给定一个单词数组 words 和一个长度 maxWidth, 重新排版单词, 使其成为每行恰好有 maxWidth 个字符, 且左右两端对齐的文本\
你应该使用"贪心算法"来放置给定的单词, 也就是说, 尽可能多地往每行中放置单词 . 必要时可用空格 ' ' 填充, 使得每行恰好有 maxWidth 个字符\
要求尽可能均匀分配单词间的空格数量, 如果某一行单词间的空格不能均匀分配, 则左侧放置的空格数要多于右侧的空格数\
文本的最后一行应为左对齐, 且单词之间不插入额外的空格\
注意:\
单词是指由非空格字符组成的字符序列\
每个单词的长度大于 0, 小于等于 maxWidth\
输入单词数组 words 至少包含一个单词
class Solution {
// blank 返回长度为 n 的由空格组成的字符串
string blank(int n) {
return string(n, ' ');
}
// join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串
string join(vector<string> &words, int left, int right, string sep) {
string s = words[left];
for (int i = left + 1; i < right; ++i) {
s += sep + words[i];
}
return s;
}
public:
vector<string> fullJustify(vector<string> &words, int maxWidth) {
vector<string> ans;
int right = 0, n = words.size();
while (true) {
int left = right; // 当前行的第一个单词在 words 的位置
int sumLen = 0; // 统计这一行单词长度之和
// 循环确定当前行可以放多少单词,注意单词之间应至少有一个空格
while (right < n && sumLen + words[right].length() + right - left <= maxWidth) {
sumLen += words[right++].length();
}
// 当前行是最后一行:单词左对齐,且单词之间应只有一个空格,在行末填充剩余空格
if (right == n) {
string s = join(words, left, n, " ");
ans.emplace_back(s + blank(maxWidth - s.length()));
return ans;
}
int numWords = right - left;
int numSpaces = maxWidth - sumLen;
// 当前行只有一个单词:该单词左对齐,在行末填充剩余空格
if (numWords == 1) {
ans.emplace_back(words[left] + blank(numSpaces));
continue;
}
// 当前行不只一个单词
int avgSpaces = numSpaces / (numWords - 1);
int extraSpaces = numSpaces % (numWords - 1);
string s1 = join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1)); // 拼接额外加一个空格的单词
string s2 = join(words, left + extraSpaces + 1, right, blank(avgSpaces)); // 拼接其余单词
ans.emplace_back(s1 + blank(avgSpaces) + s2);
}
}
};
排版题, 纯模拟, 真的烦人
力扣 no.222 给定一个完全二叉树的根节点 root , 求出该树的节点个数
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int level = 0;
TreeNode* node = root;
while (node->left != nullptr) {
level++;
node = node->left;
}
int low = 1 << level, high = (1 << (level + 1)) - 1;
while (low < high) {
int mid = (high - low + 1) / 2 + low;
if (exists(root, level, mid)) {
low = mid;
} else {
high = mid - 1;
}
}
return low;
}
bool exists(TreeNode* root, int level, int k) {
int bits = 1 << (level - 1);
TreeNode* node = root;
while (node != nullptr && bits > 0) {
if (!(bits & k)) {
node = node->left;
} else {
node = node->right;
}
bits >>= 1;
}
return node != nullptr;
}
};
你看我够不够 2\ 先向左到底算层数, 然后二分查找就一个节点 / 满节点 (最后一层), 用二进制验证 (对于 12 (1100), 第一个 1 为 root, 然后 rll (右左左))
力扣 no.3\ 给定一个字符串 s, 请你找出其中不含有重复字符的最长子串的长度
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(!s.size()) return 0;
int len(s.size()),l(0),r(1),ans(1);
bool h[128]={0};
h[s[l]]=true;
while(r<len){
if(!h[s[r]]){
ans=max(ans,r-l+1);
}
else{
while(s[l]!=s[r]){
h[s[l]]=false;
l++;
}
l++;
}
h[s[r]]=true;r++;
}
return ans;
}
};
滑动窗口, 哈希表
力扣 no.209\ 给定一个含有 n 个正整数的数组和一个正整数 target\ 找出该数组中满足其总和大于等于 target 的长度最小的 子数组并返回其长度\ 如果不存在符合条件的子数组, 返回 0
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int ans = INT_MAX;
int start = 0, end = 0;
int sum = 0;
while (end < n) {
sum += nums[end];
while (sum >= s) {
ans = min(ans, end - start + 1);
sum -= nums[start];
start++;
}
end++;
}
return ans == INT_MAX ? 0 : ans;
}
};
滑动窗口
力扣 no.128\ 给定一个未排序的整数数组 nums, 找出数字连续的最长序列 (不要求序列元素在原数组中连续) 的长度
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int n(0),t(0),ans(0),l(nums.size());
map<int,bool> m;
for(int i(0);i<l;i++){
m[nums[i]]=1;
}
for(int i(0);i<l;i++){
if(m[nums[i]]&&!m[nums[i]-1]){
int at=nums[i];
while(m[t++]){
m[t-1]=0;
n++;
}
ans=max(ans,n);
n=0;
}
}
return ans;
}
};
检查 nums[i-1] 以确定是否为合法起点, 避免重复检查\
注意边检查边删除更快, 我用怪方法 map, 官方用的是 unordered_set 更好\
草, 才知道 map 的实现是红黑树, 比 unordered_set 慢很多
力扣 no.300\ 给你一个整数数组 nums , 找到其中最长严格递增子序列的长度
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int l(nums.size()),ans(1);
vector<int> dp(l);
dp[0]=1;
for(int i(1);i<l;i++){
int t(1);
for(int j(0);j<i;j++){
if(nums[i]>nums[j]) t=max(dp[j]+1,t);
}
dp[i]=t;
ans=max(ans,t);
t=1;
}
return ans;
}
};
简单 dp
力扣 no.36\ 请你判断一个 9 x 9 的数独是否有效\ 验证已经填入的数字是否有效即可
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int v1[9][10]={0},v2[9][10]={0},v3[9][10]={0};
for(int i(0);i<9;i++)
for(int j(0);j<9;j++){
if(board[i][j]=='.') continue;
int t=board[i][j]-'0';
if(v1[i][t]) return 0;
else v1[i][t]=1;
if(v2[j][t]) return 0;
else v2[j][t]=1;
if(v3[i/3*3+j/3][t]) return 0;
else v3[i/3*3+j/3][t]=1;
}
return 1;
}
};
哈希表
力扣 no.54\ 给你一个 m 行 n 列的矩阵 matrix , 请按照顺时针螺旋顺序, 返回矩阵中的所有元素
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) {
return {};
}
int rows = matrix.size(), columns = matrix[0].size();
vector<int> order;
int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
while (left <= right && top <= bottom) {
for (int column = left; column <= right; column++) {
order.push_back(matrix[top][column]);
}
for (int row = top + 1; row <= bottom; row++) {
order.push_back(matrix[row][right]);
}
if (left < right && top < bottom) {
for (int column = right - 1; column > left; column--) {
order.push_back(matrix[bottom][column]);
}
for (int row = bottom; row > top; row--) {
order.push_back(matrix[row][left]);
}
}
left++;
right--;
top++;
bottom--;
}
return order;
}
};
模拟可以, 但是用哈希表占空间\ 关于方向的改变, 用方向索引数组 (不同方向就是 ij 加的值不同) 即可, 我是傻子, 用状态机\ 最优是按层 (内外) 遍历, 有分治递归的意思
力扣 no.139\ 给你一个字符串 s 和一个字符串列表 wordDict 作为字典\ 请你判断是否可以利用字典中出现的单词拼接出 s
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
auto wordDictSet = unordered_set <string> ();
for (auto word: wordDict) {
wordDictSet.insert(word);
}
auto dp = vector <bool> (s.size() + 1);
dp[0] = true;
for (int i = 1; i <= s.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) {
dp[i] = true;
break;
}
}
}
return dp[s.size()];
}
};
动态规划, 用 dp[i] 表示 s 的前 i 个字符能否被 wordDict 中的单词表示\
转移方程:dp[i]=dp[j]&&check(s[j+1,i])\
check(s[j+1,i]) 表示 s[j+1,i] 是否出现在字典中
力扣 no.322\ 给你一个整数数组 coins, 表示不同面额的硬币, 以及一个整数 amount , 表示总金额\ 计算并返回可以凑成总金额所需的, 最少的硬币个数\ 如果没有任何一种硬币组合能组成总金额, 返回 -1
class Solution {
vector<int>count;
int dp(vector<int>& coins, int rem) {
if (rem < 0) return -1;
if (rem == 0) return 0;
if (count[rem - 1] != 0) return count[rem - 1];
int Min = INT_MAX;
for (int coin:coins) {
int res = dp(coins, rem - coin);
if (res >= 0 && res < Min) {
Min = res + 1;
}
}
count[rem - 1] = Min == INT_MAX ? -1 : Min;
return count[rem - 1];
}
public:
int coinChange(vector<int>& coins, int amount) {
if (amount < 1) return 0;
count.resize(amount);
return dp(coins, amount);
}
};
// 第一种方法,递归搜索所有可能,利用数组记忆最优解优化时间
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int Max = amount + 1;
vector<int> dp(amount + 1, Max);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int j = 0; j < (int)coins.size(); ++j) {
if (coins[j] <= i) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};
// 第二种方法,动态规划,转移方程for coins dp[i]=min(dp[i],dp[i-coin]+1)
力扣 no.49\ 给你一个字符串数组, 请你将字母异位词组合在一起, 可以按任意顺序返回结果列表\ 字母异位词是由重新排列源单词的所有字母得到的一个新单词
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (string& str: strs) {
string key = str;
sort(key.begin(), key.end());
mp[key].emplace_back(str);
}
vector<vector<string>> ans;
for (auto it = mp.begin(); it != mp.end(); ++it) {
ans.emplace_back(it->second);
}
return ans;
}
};
简单的哈希表, 关键在于键的形式\ 使用单词的排序作为键, 可以保证异位词的键相同\ 也可以用数组作为键, 因为只有 26 个字母 (小哈希表)
力扣 no.48\ 给你一个 n x n 的二维矩阵 matrix 表示一个图像, 请你将图像顺时针旋转 90 度
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int l(matrix.size());
for(int i(0);i<l;i++){
reverse(matrix[i].begin(),matrix[i].end());
}
for(int i(0);i<l;i++)
for(int j(0);j<l-i-1;j++){
int t=matrix[i][j];
int d=l-1-i-j;
matrix[i][j]=matrix[i+d][j+d];
matrix[i+d][j+d]=t;
}
return;
}
};
先反转, 再对角线交换, 正解\ 还可以模拟旋转保存 tmp (每四个一组, 枚举每组)
力扣 no.289\ 生命游戏
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int neighbors[3] = {0, 1, -1};
int rows = board.size();
int cols = board[0].size();
// 遍历面板每一个格子里的细胞
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// 对于每一个细胞统计其八个相邻位置里的活细胞数量
int liveNeighbors = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
// 相邻位置的坐标
int r = (row + neighbors[i]);
int c = (col + neighbors[j]);
// 查看相邻的细胞是否是活细胞
if ((r < rows && r >= 0) && (c < cols && c >= 0) && (abs(board[r][c]) == 1)) {
liveNeighbors += 1;
}
}
}
}
// 规则 1 或规则 3
if ((board[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {
// -1 代表这个细胞过去是活的现在死了
board[row][col] = -1;
}
// 规则 4
if (board[row][col] == 0 && liveNeighbors == 3) {
// 2 代表这个细胞过去是死的现在活了
board[row][col] = 2;
}
}
}
// 遍历 board 得到一次更新后的状态
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (board[row][col] > 0) {
board[row][col] = 1;
} else {
board[row][col] = 0;
}
}
}
}
};
模拟就不多说了\ 重点是对于 int 数组可以用其它值标记复合状态实现 \(O(1)\) 空间
力扣 no.73\ 给定一个 m x n 的矩阵, 如果一个元素为 0 , 则将其所在行和列的所有元素都设为 0, 请使用 原地 算法
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
int flag_col0 = false;
for (int i = 0; i < m; i++) {
if (!matrix[i][0]) {
flag_col0 = true;
}
for (int j = 1; j < n; j++) {
if (!matrix[i][j]) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (int i = m - 1; i >= 0; i--) {
for (int j = 1; j < n; j++) {
if (!matrix[i][0] || !matrix[0][j]) {
matrix[i][j] = 0;
}
}
if (flag_col0) {
matrix[i][0] = 0;
}
}
}
};
标记第一列是否有 0, 然后用第一列标记其他行列是否有 0 (注意倒置处理矩阵)
力扣 no.86\ 给你一个链表的头节点 head 和一个特定值 x , 请你对链表进行分隔, 使得所有 小于 x 的节点都出现在大于或等于 x 的节点之前\ 你应当保留两个分区中每个节点的初始相对位置
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* small = new ListNode(0);
ListNode* smallHead = small;
ListNode* large = new ListNode(0);
ListNode* largeHead = large;
while (head != nullptr) {
if (head->val < x) {
small->next = head;
small = small->next;
} else {
large->next = head;
large = large->next;
}
head = head->next;
}
large->next = nullptr;
small->next = largeHead->next;
return smallHead->next;
}
};
简单的链表题, 用两个链表分别存储小于 x 和大于等于 x 的节点, 最后合并
力扣 no.146\ 实现 LUR 缓存
struct DLinkedNode {
int key, value;
DLinkedNode* prev;
DLinkedNode* next;
DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
unordered_map<int, DLinkedNode*> cache;
DLinkedNode* head;
DLinkedNode* tail;
int size;
int capacity;
public:
LRUCache(int _capacity): capacity(_capacity), size(0) {
// 使用伪头部和伪尾部节点
head = new DLinkedNode();
tail = new DLinkedNode();
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (!cache.count(key)) {
return -1;
}
// 如果 key 存在,先通过哈希表定位,再移到头部
DLinkedNode* node = cache[key];
moveToHead(node);
return node->value;
}
void put(int key, int value) {
if (!cache.count(key)) {
// 如果 key 不存在,创建一个新的节点
DLinkedNode* node = new DLinkedNode(key, value);
// 添加进哈希表
cache[key] = node;
// 添加至双向链表的头部
addToHead(node);
++size;
if (size > capacity) {
// 如果超出容量,删除双向链表的尾部节点
DLinkedNode* removed = removeTail();
// 删除哈希表中对应的项
cache.erase(removed->key);
// 防止内存泄漏
delete removed;
--size;
}
}
else {
// 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部
DLinkedNode* node = cache[key];
node->value = value;
moveToHead(node);
}
}
void addToHead(DLinkedNode* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
void removeNode(DLinkedNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void moveToHead(DLinkedNode* node) {
removeNode(node);
addToHead(node);
}
DLinkedNode* removeTail() {
DLinkedNode* node = tail->prev;
removeNode(node);
return node;
}
};
利用哈希表 + 双向链表实现 \(O(1)\) 的查找和修改\ 建立 key 与节点的哈希表, 用双向链表维护节点的顺序实现缓存
力扣 no.56\
以数组 intervals 表示若干个区间的集合, 其中单个区间为 intervals[i] == [starti, endi] 请你合并所有重叠的区间, 并返回一个不重叠的区间数组, 该数组需恰好覆盖输入中的所有区间
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.size() == 0) {
return {};
}
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
for (int i = 0; i < intervals.size(); ++i) {
int L = intervals[i][0], R = intervals[i][1];
if (!merged.size() || merged.back()[1] < L) {
merged.push_back({L, R});
}
else {
merged.back()[1] = max(merged.back()[1], R);
}
}
return merged;
}
};
排序后合并即可
力扣 no.57\
给你一个无重叠的, 按照区间起始端点排序的区间列表 intervals, 其中 intervals[i] == [starti, endi] 表示第 i 个区间的开始和结束, 并且 intervals 按照 starti 升序排列, 同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束\
在 intervals 中插入区间 newInterval, 使得 intervals 依然按照 starti 升序排列, 且区间之间不重叠 (如果有必要的话, 可以合并区间)\
返回插入之后的 intervals\
注意 你不需要原地修改 intervals, 你可以创建一个新数组然后返回它
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int left = newInterval[0];
int right = newInterval[1];
bool placed = false;
vector<vector<int>> ans;
for (const auto& interval: intervals) {
if (interval[0] > right) {
// 在插入区间的右侧且无交集
if (!placed) {
ans.push_back({left, right});
placed = true;
}
ans.push_back(interval);
}
else if (interval[1] < left) {
// 在插入区间的左侧且无交集
ans.push_back(interval);
}
else {
// 与插入区间有交集,计算它们的并集
left = min(left, interval[0]);
right = max(right, interval[1]);
}
}
if (!placed) {
ans.push_back({left, right});
}
return ans;
}
};
区间题基础
力扣 no.452\
有一些球形气球贴在一堵用 XY 平面表示的墙面上, 墙面上的气球记录在整数数组 points , 其中 points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间的气球\
一支弓箭可以沿着 x 轴从不同点完全垂直地射出, 在坐标 x 处射出一支箭, 若有一个气球的直径的开始和结束坐标为 xstart,xend, 且满足 xstart ≤ x ≤ xend, 则该气球会被引爆, 可以射出的弓箭的数量没有限制, 弓箭一旦被射出之后, 可以无限地前进
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.empty()) {
return 0;
}
sort(points.begin(), points.end(), [](const vector<int>& u, const vector<int>& v) {
return u[1] < v[1];
});
int pos = points[0][1];
int ans = 1;
for (const vector<int>& balloon: points) {
if (balloon[0] > pos) {
pos = balloon[1];
++ans;
}
}
return ans;
}
};
按照右端点排序, 每次取最左右端点, 然后去掉与它相交的区间\ 我一开始, 是想用左边界排序, 然后取到第一个右边界, 然后去掉与它相交的区间, 但是发现完全没必要
力扣 no.150\ 逆波兰表达式
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stk;
int n = tokens.size();
for (int i = 0; i < n; i++) {
string& token = tokens[i];
if (isNumber(token)) {
stk.push(atoi(token.c_str()));
} else {
int num2 = stk.top();
stk.pop();
int num1 = stk.top();
stk.pop();
switch (token[0]) {
case '+':
stk.push(num1 + num2);
break;
case '-':
stk.push(num1 - num2);
break;
case '*':
stk.push(num1 * num2);
break;
case '/':
stk.push(num1 / num2);
break;
}
}
}
return stk.top();
}
bool isNumber(string& token) {
return !(token == "+" || token == "-" || token == "*" || token == "/");
}
};
简简单单栈, 运算规则与 C 一样, 栈的伴生应用了可以说
力扣 no.155\ 设计一个支持 push ,pop ,top 操作, 并能在常数时间内检索到最小元素的栈
class MinStack {
stack<int> x_stack;
stack<int> min_stack;
public:
MinStack() {
min_stack.push(INT_MAX); //一开始没想到
}
void push(int x) {
x_stack.push(x);
min_stack.push(min(min_stack.top(), x));
}
void pop() {
x_stack.pop();
min_stack.pop();
}
int top() {
return x_stack.top();
}
int getMin() {
return min_stack.top();
}
};
维护两个栈, 一个栈维护最小值, 一个栈正常
力扣 no.71\ 给你一个字符串 path, 表示指向某一文件或目录的 Unix 风格绝对路径 (以 '/' 开头), 请你将其转化为更加简洁的规范路径
class Solution {
public:
string simplifyPath(string path) {
auto split = [](const string& s, char delim) -> vector<string> {
vector<string> ans;
string cur;
for (char ch: s) {
if (ch == delim) {
ans.push_back(move(cur));
cur.clear();
}
else {
cur += ch;
}
}
ans.push_back(move(cur));
return ans;
};
vector<string> names = split(path, '/');
vector<string> stack;
for (string& name: names) {
if (name == "..") {
if (!stack.empty()) {
stack.pop_back();
}
}
else if (!name.empty() && name != ".") {
stack.push_back(move(name));
}
}
string ans;
if (stack.empty()) {
ans = "/";
}
else {
for (string& name: stack) {
ans += "/" + move(name);
}
}
return ans;
}
};
简单的栈
力扣 no.114\ 给你二叉树的根结点 root , 请你将它展开为一个单链表\ 展开后的单链表应该同样使用 TreeNode , 其中 right 子指针指向链表中下一个结点, 而左子指针始终为 null\ 展开后的单链表应该与二叉树先序遍历顺序相同
class Solution {
public:
void flatten(TreeNode* root) {
if(!root||(!root->left&&!root->right)) return;
TreeNode* r=root;
auto s=stack<TreeNode*>();
s.push(nullptr);
while(r!=nullptr){
if(r->right) s.push(r->right);
if(r->left){
r->right=r->left;
r->left=nullptr;
r=r->right;
}
else{
r->right=s.top();
r=s.top();
s.pop();
}
}
return;
}
};
// 前序遍历用栈存,相较最笨的方法没有阶的时空优势
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode *curr = root;
while (curr != nullptr) {
if (curr->left != nullptr) {
auto next = curr->left;
auto predecessor = next;
while (predecessor->right != nullptr) {
predecessor = predecessor->right;
}
predecessor->right = curr->right;
curr->left = nullptr;
curr->right = next;
}
curr = curr->right;
}
}
};
// 官方正解, O(1)空间
// 将右子树放到左子树的最右边
力扣 no.137\ 给你一个整数数组 nums , 除某个元素仅出现一次外, 其余每个元素都恰出现三次, 请你找出并返回那个只出现了一次的元素\ 你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for (int i = 0; i < 32; ++i) {
int total = 0;
for (int num: nums) {
total += ((num >> i) & 1);
}
if (total % 3) {
ans |= (1 << i);
}
}
return ans;
}
};
// 对于每位非ans树的影响为0/3,故统计每一位的和%3
class Solution {
public:
int singleNumber(vector<int>& nums) {
int a = 0, b = 0;
for (int num: nums) {
b = ~a & (b ^ num);
a = ~b & (a ^ num);
}
return b;
}
};
// 正解,用两个数来模拟4进制
官方正解的讲解有点难崩, 用电路讲....\ 直接说数理逻辑不好吗, 是不会还想装吗
力扣 no.94\ 二叉树的中序遍历
class Solution {
public:
void inorder(TreeNode* root, vector<int>& res) {
if (!root) {
return;
}
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root, res);
return res;
}
};
// 递归秒杀
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode *predecessor = nullptr;
while (root != nullptr) {
if (root->left != nullptr) {
// predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
predecessor = root->left;
while (predecessor->right != nullptr && predecessor->right != root) {
predecessor = predecessor->right;
}
// 让 predecessor 的右指针指向 root,继续遍历左子树
if (predecessor->right == nullptr) {
predecessor->right = root;
root = root->left;
}
// 说明左子树已经访问完了,我们需要断开链接
else {
res.push_back(root->val);
predecessor->right = nullptr;
root = root->right;
}
}
// 如果没有左孩子,则直接访问右孩子
else {
res.push_back(root->val);
root = root->right;
}
}
return res;
}
};
// morris中序遍历二叉树 O(1)空间复杂度
// 将x的左子树中最右边的节点的右孩子指向x(且能知晓已经遍历完成左子树)
力扣 no.118\ 杨辉三角
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ret(numRows);
for (int i = 0; i < numRows; ++i) {
ret[i].resize(i + 1);
ret[i][0] = ret[i][i] = 1;
for (int j = 1; j < i; ++j) {
ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
}
}
return ret;
}
};
// 简单递推,生成n行即可
力扣 no.119\ 杨辉三角 2 (只返回第 n 行)
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex + 1);
row[0] = 1;
for (int i = 1; i <= rowIndex; ++i) {
row[i] = 1LL * row[i - 1] * (rowIndex - i + 1) / i;
}
return row;
}
};
// 即(a+b)的n次方各项系数
注意, 如果使用上一道题的方法, 可以用一维数组, 每次迭代从后向前计算, 防止覆盖
力扣 no.144\ 二叉树前序遍历
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> res;
if (root == nullptr) {
return res;
}
TreeNode *p1 = root, *p2 = nullptr;
while (p1 != nullptr) {
p2 = p1->left;
if (p2 != nullptr) {
while (p2->right != nullptr && p2->right != p1) {
p2 = p2->right;
}
if (p2->right == nullptr) {
res.emplace_back(p1->val);
p2->right = p1;
p1 = p1->left;
continue;
} else {
p2->right = nullptr;
}
} else {
res.emplace_back(p1->val);
}
p1 = p1->right;
}
return res;
}
};
// morris前序遍历二叉树 O(1)空间复杂度
力扣 no.145\ 二叉树后序遍历
class Solution {
public:
void addPath(vector<int> &vec, TreeNode *node) {
int count = 0;
while (node != nullptr) {
++count;
vec.emplace_back(node->val);
node = node->right;
}
reverse(vec.end() - count, vec.end());
}
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
if (root == nullptr) {
return res;
}
TreeNode *p1 = root, *p2 = nullptr;
while (p1 != nullptr) {
p2 = p1->left;
if (p2 != nullptr) {
while (p2->right != nullptr && p2->right != p1) {
p2 = p2->right;
}
if (p2->right == nullptr) {
p2->right = p1;
p1 = p1->left;
continue;
} else {
p2->right = nullptr;
addPath(res, p1->left);
}
}
p1 = p1->right;
}
addPath(res, root);
return res;
}
};
// morris后序遍历二叉树 O(1)空间复杂度
这两题的递归 / 迭代解法都很简单, 不写了\ Morris 算法本质就是利用空闲指针
力扣 no.160\ 判断两个链表相交点
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
// 双指针正解真的巧妙,指针走完后交换到另一个链表的头节点
// 把三段距离设为abc,一个走完是a+c,另一个b+c,交换链表,走同样距离刚好是a+b+c,刚好在交点处
用哈希 / 对齐太简单, 不说了
力扣 no.108\ 将有序数组转换为二叉搜索树
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums, 0, nums.size() - 1);
}
TreeNode* helper(vector<int>& nums, int left, int right) {
if (left > right) {
return nullptr;
}
// 选择任意一个中间位置数字作为根节点
int mid = (left + right + rand() % 2) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = helper(nums, left, mid - 1);
root->right = helper(nums, mid + 1, right);
return root;
}
};
板子题
力扣 no.110\ 判断平衡二叉树
class Solution {
public:
int height(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
return -1;
} else {
return max(leftHeight, rightHeight) + 1;
}
}
bool isBalanced(TreeNode* root) {
return height(root) >= 0;
}
};
板子题
力扣 no.111 二叉树最小深度
class Solution {
public:
int minDepth(TreeNode *root) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) {
return 1;
}
int min_depth = INT_MAX;
if (root->left != nullptr) {
min_depth = min(minDepth(root->left), min_depth);
}
if (root->right != nullptr) {
min_depth = min(minDepth(root->right), min_depth);
}
return min_depth + 1;
}
};
DFS/BFS 板子题
力扣 no.168\ Excel 表列名称
class Solution {
public:
string convertToTitle(int columnNumber) {
string ans;
while (columnNumber > 0) {
--columnNumber;
ans += columnNumber % 26 + 'A';
columnNumber /= 26;
}
reverse(ans.begin(), ans.end());
return ans;
}
};
26 进制转换, 但 A0 与 0Z 相等 (实际没 0)
力扣 no.171
class Solution {
public:
int titleToNumber(string columnTitle) {
int ans(0),l=columnTitle.size();
for(int i=l-1;i>=0;i--){
ans+=(columnTitle[i]-'A'+1)*pow(26,l-i-1);
}
return ans;
}
};
26 进制转换, 从后往前, 简单\
从前往后亦可,ans*=26
力扣 no.203\ 移除链表元素
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode dumbnode;
dumbnode.next=head;
ListNode* m=&dumbnode;
for(ListNode* h=head;h;h=h->next){
if(h->val==val){
m->next=h->next;
continue;
}
m=m->next;
}
return dumbnode.next;
}
};
简单, 递归亦可
力扣 no.129\ 求根节点到叶节点数字之和
class Solution {
public:
int sumNumbers(TreeNode* root) {
if(!root) return 0;
int ans(0);
queue<TreeNode*> q;q.push(root);
while(!q.empty()){
TreeNode* p=q.front();q.pop();
if(p->left){
q.push(p->left);
p->left->val+=p->val*10;
if(!p->left->left&&!p->left->right) ans+=p->left->val;
}
if(p->right){
q.push(p->right);
p->right->val+=p->val*10;
if(!p->right->left&&!p->right->right) ans+=p->right->val;
}
}
return ans?ans:root->val;
}
};
DFS/BFS, 但我小修改, 优化时间常系数
力扣 no.236\ 二叉树的最近公共祖先
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if (left == nullptr) return right;
if (right == nullptr) return left;
return root;
}
};
// 递归
class Solution {
public:
unordered_map<int, TreeNode*> fa;
unordered_map<int, bool> vis;
void dfs(TreeNode* root){
if (root->left != nullptr) {
fa[root->left->val] = root;
dfs(root->left);
}
if (root->right != nullptr) {
fa[root->right->val] = root;
dfs(root->right);
}
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
fa[root->val] = nullptr;
dfs(root);
while (p != nullptr) {
vis[p->val] = true;
p = fa[p->val];
}
while (q != nullptr) {
if (vis[q->val]) return q;
q = fa[q->val];
}
return nullptr;
}
};
// 哈希表
力扣 no.117\ 填充每个节点的下一个右侧节点指针 (node 中增加 next 指针域, 缓存层序遍历)
class Solution {
public:
Node* connect(Node* root) {
if (!root) {
return nullptr;
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int n = q.size();
Node *last = nullptr;
for (int i = 1; i <= n; ++i) {
Node *f = q.front();
q.pop();
if (f->left) {
q.push(f->left);
}
if (f->right) {
q.push(f->right);
}
if (i != 1) {
last->next = f;
}
last = f;
}
}
return root;
}
};
// 层序遍历即可
class Solution {
public:
Node* connect(Node* root) {
Node* cur = root;
while(cur)
{
Node* cengHead = new Node(0);
Node* p = cengHead;
while(cur)
{
if(cur->left)
{
p->next = cur->left;
p=p->next;
}
if(cur -> right)
{
p->next = cur->right;
p = p->next;
}
cur = cur->next;
}
cur = cengHead->next;
}
return root;
}
};
// 利用已有next指针, O(1)空间
力扣 no.25\ k 个一组翻转链表
class Solution {
public:
// 翻转一个子链表,并且返回新的头与尾
pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) {
ListNode* prev = tail->next;
ListNode* p = head;
while (prev != tail) {
ListNode* nex = p->next;
p->next = prev;
prev = p;
p = nex;
}
return {tail, head};
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* hair = new ListNode(0);
hair->next = head;
ListNode* pre = hair;
while (head) {
ListNode* tail = pre;
// 查看剩余部分长度是否大于等于 k
for (int i = 0; i < k; ++i) {
tail = tail->next;
if (!tail) {
return hair->next;
}
}
ListNode* nex = tail->next;
// 这里是 C++17 的写法,也可以写成
// pair<ListNode*, ListNode*> result = myReverse(head, tail);
// head = result.first;
// tail = result.second;
tie(head, tail) = myReverse(head, tail);
// 把子链表重新接回原链表
pre->next = head;
tail->next = nex;
pre = tail;
head = tail->next;
}
return hair->next;
}
};
板子题, 模拟翻转, 哑节点啥的
力扣 no.105\ 从前序与中序遍历序列构造二叉树
class Solution {
private:
unordered_map<int, int> index;
public:
TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
return nullptr;
}
int preorder_root = preorder_left;
int inorder_root = index[preorder[preorder_root]];
TreeNode* root = new TreeNode(preorder[preorder_root]);
int size_left_subtree = inorder_root - inorder_left;
root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
for (int i = 0; i < n; ++i) {
index[inorder[i]] = i;
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
};
// 简单的递归
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (!preorder.size()) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[0]);
stack<TreeNode*> stk;
stk.push(root);
int inorderIndex = 0;
for (int i = 1; i < preorder.size(); ++i) {
int preorderVal = preorder[i];
TreeNode* node = stk.top();
if (node->val != inorder[inorderIndex]) {
node->left = new TreeNode(preorderVal);
stk.push(node->left);
}
else {
while (!stk.empty() && stk.top()->val == inorder[inorderIndex]) {
node = stk.top();
stk.pop();
++inorderIndex;
}
node->right = new TreeNode(preorderVal);
stk.push(node->right);
}
}
return root;
}
};
// 迭代的栈内元素管理需要好好考虑
力扣 no.224\ 基本计算器 (加减括号)
class Solution {
public:
int calculate(string s) {
int length = s.size();
int sign = 1;
stack<int> stk;
int res = 0;
for (int i = 0; i < length; i++) {
char ch = s[i];
if (ch >= '0' && ch <= '9') {
long value = ch - '0';
while (i + 1 < length && s[i + 1] >= '0' && s[i + 1] <= '9') {
i++;
value = value * 10 + (s[i] - '0');
}
res += value * sign;
}
if (ch == '+')
sign = 1;
if (ch == '-')
sign = -1;
if (ch == '(') {
stk.push(res);
res = 0;
stk.push(sign);
sign = 1;
}
if (ch == ')') {
int frontsign = stk.top();
stk.pop();
int frontvalue = stk.top();
stk.pop();
res = frontvalue + frontsign * res;
}
}
return res;
}
};
// 栈模拟最快的解法
第一眼中缀转后缀 + 逆波兰\ 但发现只有括号这个优先级, 没有乘除, 所以可以直接计算\ 递归 / 栈都行, 记录当前符号 (需不需要逆转), 遇到括号就递归计算
力扣 no.106\ 从中序与后序遍历序列构造二叉树
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
auto dfs = [](auto&& dfs, auto&& lI, auto&& rI, auto&& lP) {
if (lI == rI) return (TreeNode*)nullptr;
auto loc = find(lI, rI, *lP); // 可以优化成哈希表
return new TreeNode(*lP, dfs(dfs, lI, loc, lP + (rI - loc)), // 注意后序是左右中,倒着是中右左
dfs(dfs, loc + 1, rI, lP + 1));
};
return dfs(dfs, inorder.cbegin(), inorder.cend(), postorder.crbegin());
}
};
// 递归,写得真好
// 跟前一题一样,倒着遍历后序序列即可
力扣 no.199\ 二叉树的右视图
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (root == nullptr) {
return {};
}
vector<vector<int>> ans;
vector<int> percent;
queue<TreeNode*> que;
que.push(root);
int size = 1;
while(size != 0 || !que.empty()) {
size--;
TreeNode* cur = que.front();
percent.push_back(cur->val);
que.pop();
if (cur->left) {
que.push(cur->left);
}
if (cur->right) {
que.push(cur->right);
}
if (size == 0) {
size = que.size();
ans.push_back(percent);
percent = {};
}
}
return ans;
}
vector<int> rightSideView(TreeNode* root) {
// 层序遍历之后返回每一层最后一个即可
vector<vector<int>> vinorder = levelOrder(root);
vector<int> ans;
for (auto x : vinorder) {
ans.push_back(x.back());
}
return ans;
}
};
层序遍历板子题
力扣 no.103\ 二叉树的锯齿形层序遍历
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) {
return ans;
}
queue<TreeNode*> nodeQueue;
nodeQueue.push(root);
bool isOrderLeft = true;
while (!nodeQueue.empty()) {
deque<int> levelList;
int size = nodeQueue.size();
for (int i = 0; i < size; ++i) {
auto node = nodeQueue.front();
nodeQueue.pop();
if (isOrderLeft) {
levelList.push_back(node->val);
} else {
levelList.push_front(node->val);
}
if (node->left) {
nodeQueue.push(node->left);
}
if (node->right) {
nodeQueue.push(node->right);
}
}
ans.emplace_back(vector<int>{levelList.begin(), levelList.end()});
isOrderLeft = !isOrderLeft;
}
return ans;
}
};
板子, 奇数层倒叙即可
力扣 no.530\ 二叉搜索树的最小绝对差
class Solution {
public:
void dfs(TreeNode* root, int& pre, int& ans) {
if (root == nullptr) {
return;
}
dfs(root->left, pre, ans);
if (pre == -1) {
pre = root->val;
} else {
ans = min(ans, root->val - pre);
pre = root->val;
}
dfs(root->right, pre, ans);
}
int getMinimumDifference(TreeNode* root) {
int ans = INT_MAX, pre = -1;
dfs(root, pre, ans);
return ans;
}
};
中序遍历即可
力扣 no.98\ 验证二叉搜索树
class Solution {
public:
bool helper(TreeNode* root, long long lower, long long upper) {
if (root == nullptr) {
return true;
}
if (root -> val <= lower || root -> val >= upper) {
return false;
}
return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
}
bool isValidBST(TreeNode* root) {
return helper(root, LONG_MIN, LONG_MAX);
}
};
递归, 维护上界下界 (根节点的左子树的上界为根节点, 根节点的右子树的下界为根节点)\ 中序遍历同上题
力扣 no.230\ 二叉搜索树中第 K 小的元素
class MyBst {
public:
MyBst(TreeNode *root) {
this->root = root;
countNodeNum(root);
}
// 返回二叉搜索树中第k小的元素
int kthSmallest(int k) {
TreeNode *node = root;
while (node != nullptr) {
int left = getNodeNum(node->left);
if (left < k - 1) {
node = node->right;
k -= left + 1;
} else if (left == k - 1) {
break;
} else {
node = node->left;
}
}
return node->val;
}
private:
TreeNode *root;
unordered_map<TreeNode *, int> nodeNum;
// 统计以node为根结点的子树的结点数
int countNodeNum(TreeNode * node) {
if (node == nullptr) {
return 0;
}
nodeNum[node] = 1 + countNodeNum(node->left) + countNodeNum(node->right);
return nodeNum[node];
}
// 获取以node为根结点的子树的结点数
int getNodeNum(TreeNode * node) {
if (node != nullptr && nodeNum.count(node)) {
return nodeNum[node];
}else{
return 0;
}
}
};
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
MyBst bst(root);
return bst.kthSmallest(k);
}
};
中序遍历同上\ 可以缓存子树结点数, 加速查找\ AVL 树可以进一步优化
力扣 no.173\ 二叉搜索树迭代器
class BSTIterator {
private:
TreeNode* cur;
stack<TreeNode*> stk;
public:
BSTIterator(TreeNode* root): cur(root) {}
int next() {
while (cur != nullptr) {
stk.push(cur);
cur = cur->left;
}
cur = stk.top();
stk.pop();
int ret = cur->val;
cur = cur->right;
return ret;
}
bool hasNext() {
return cur != nullptr || !stk.empty();
}
};
扁平化亦可\ 模拟中序遍历正解
力扣 no.17\ 电话号码的字母组合
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> combinations;
if (digits.empty()) {
return combinations;
}
unordered_map<char, string> phoneMap{
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
string combination;
backtrack(combinations, phoneMap, digits, 0, combination);
return combinations;
}
void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& combination) {
if (index == digits.length()) {
combinations.push_back(combination);
} else {
char digit = digits[index];
const string& letters = phoneMap.at(digit);
for (const char& letter: letters) {
combination.push_back(letter);
backtrack(combinations, phoneMap, digits, index + 1, combination);
combination.pop_back();
}
}
}
};
不那么板子的回溯板子
力扣 no.22\ 数字 n 代表生成括号的对数, 请你设计一个函数, 用于能够生成所有可能的并且 有效的 括号组合
class Solution {
void adde(vector<string> &ans,int i,int n,int x,string& current){
if(i==n){
ans.push_back(current);
return;
}
for(int j=x+1;j<=2*i;j++){
current[j]='(';
adde(ans,i+1,n,j,current);
current[j]=')';
}
}
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
string current="";
for(int i=0;i<n;i++){
current+="))";
}
adde(ans,0,n,-1,current);
return ans;
}
};
典型回溯
力扣 no.201\
给你两个整数 left 和 right , 表示区间 [left, right] , 返回此区间内所有数字按位与的结果
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int shift = 0;
// 找到公共前缀
while (m < n) {
m >>= 1;
n >>= 1;
++shift;
}
return m << shift;
}
};
// 常规位移
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
while (m < n) {
// 抹去最右边的 1
n = n & (n - 1);
}
return n;
}
};
// Brian Kernighan 算法,抹去最右边的 1
求共同二进制前缀
力扣 no.53\ 最大子数组和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre = 0, maxAns = nums[0];
for (const auto &x: nums) {
pre = max(pre + x, x);
maxAns = max(maxAns, pre);
}
return maxAns;
}
};
// 动态规划
class Solution {
public:
struct Status {
int lSum, rSum, mSum, iSum;
};
Status pushUp(Status l, Status r) {
int iSum = l.iSum + r.iSum;
int lSum = max(l.lSum, l.iSum + r.lSum);
int rSum = max(r.rSum, r.iSum + l.rSum);
int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
return (Status) {lSum, rSum, mSum, iSum};
};
Status get(vector<int> &a, int l, int r) {
if (l == r) {
return (Status) {a[l], a[l], a[l], a[l]};
}
int m = (l + r) >> 1;
Status lSub = get(a, l, m);
Status rSub = get(a, m + 1, r);
return pushUp(lSub, rSub);
}
int maxSubArray(vector<int>& nums) {
return get(nums, 0, nums.size() - 1).mSum;
}
};
// 分治
动态规划简单\ 但大量搜索的场景可以用分治优化 (线段树)
力扣 no.206\ 反转链表
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};
贴一个递归, 水一天
力扣 no.148
class Solution {
public:
ListNode* sortList(ListNode* head) {
return sortList(head, nullptr);
}
ListNode* sortList(ListNode* head, ListNode* tail) {
if (head == nullptr) {
return head;
}
if (head->next == tail) {
head->next = nullptr;
return head;
}
ListNode* slow = head, *fast = head;
while (fast != tail) {
slow = slow->next;
fast = fast->next;
if (fast != tail) {
fast = fast->next;
}
}
ListNode* mid = slow;
return merge(sortList(head, mid), sortList(mid, tail));
}
ListNode* merge(ListNode* head1, ListNode* head2) {
ListNode* dummyHead = new ListNode(0);
ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
while (temp1 != nullptr && temp2 != nullptr) {
if (temp1->val <= temp2->val) {
temp->next = temp1;
temp1 = temp1->next;
} else {
temp->next = temp2;
temp2 = temp2->next;
}
temp = temp->next;
}
if (temp1 != nullptr) {
temp->next = temp1;
} else if (temp2 != nullptr) {
temp->next = temp2;
}
return dummyHead->next;
}
};
归并排序, 空间复杂度 \(O(logn)\)\ 如果多点常数时间的操作, 可以用迭代优化空间到 \(O(1)\)\ 但不值当
力扣 no.5\ 最长回文子串
class Solution {
public:
pair<int, int> expandAroundCenter(const string& s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
--left;
++right;
}
return {left + 1, right - 1};
}
string longestPalindrome(string s) {
int start = 0, end = 0;
for (int i = 0; i < s.size(); ++i) {
auto [left1, right1] = expandAroundCenter(s, i, i);
auto [left2, right2] = expandAroundCenter(s, i, i + 1);
if (right1 - left1 > end - start) {
start = left1;
end = right1;
}
if (right2 - left2 > end - start) {
start = left2;
end = right2;
}
}
return s.substr(start, end - start + 1);
}
};
可以用动态规划, 但是转移方程仅需要使用前一个的状态, 故可以用中心扩展法\ 另有 \(O(n)\) 时间的 Manacher 算法
力扣 no.7\ 反转整数
class Solution {
public:
int reverse(int x) {
int rev = 0;
while (x != 0) {
if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {
return 0;
}
int digit = x % 10;
x /= 10;
rev = rev * 10 + digit;
}
return rev;
}
};
判断一下溢出
力扣 no.2545\ 根据第 K 场考试的分数排序
class Solution {
public:
vector<vector<int>> sortTheStudents(vector<vector<int>>& score, int k) {
sort(score.begin(), score.end(), [&](const vector<int>& u, const vector<int>& v) {
return u[k] > v[k];
});
return score;
}
};
Lambda 表达式特性题? sort 原型题?\ 水一个, 弥补负罪感
力扣 no.004\ 寻找两个正序数组的中位数
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.size();
int n = nums2.size();
int left = 0, right = m;
// median1 :前一部分的最大值
// median2 :后一部分的最小值
int median1 = 0, median2 = 0;
while (left <= right) {
// 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
// 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
int i = (left + right) / 2;
int j = (m + n + 1) / 2 - i;
// nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
int nums_im1 = (i == 0 ? INT_MIN : nums1[i - 1]);
int nums_i = (i == m ? INT_MAX : nums1[i]);
int nums_jm1 = (j == 0 ? INT_MIN : nums2[j - 1]);
int nums_j = (j == n ? INT_MAX : nums2[j]);
if (nums_im1 <= nums_j) {
median1 = max(nums_im1, nums_jm1);
median2 = min(nums_i, nums_j);
left = i + 1;
} else {
right = i - 1;
}
}
return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
}
};
第一种解法, 每次选取两数组各 k/2 个数, 去掉较小集合, 更新 k\ 第二种, 稳定选取数量和为 k 的, 二分搜索位置, 直到满足交叉小于关系
力扣 no.008\ atoi
class Solution {
public:
int myAtoi(string s) {
bool b=true;
long long ans=0;
int i(0);
for(i;i<s.size();i++){
if(s[i]==' ') continue;
else if(s[i]=='-'||s[i]=='+'){
b=s[i]=='-'?false:true;++i;
break;
}
else break;
}
for(i;i<s.size();i++){
if(s[i]<'0'||s[i]>'9') break;
ans=ans*10+(s[i]-'0');
if(ans>INT_MAX){
if(b) ans=INT_MAX;
else ans=(long long)INT_MAX+1;
break;
}
}
return b?ans:-ans;
}
};
反思了一下, 不该将 trim 与 +- 放在一起判断
力扣 no.24\ 两两交换链表中的节点
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* temp = dummyHead;
while (temp->next != nullptr && temp->next->next != nullptr) {
ListNode* node1 = temp->next;
ListNode* node2 = temp->next->next;
temp->next = node2;
node1->next = node2->next;
node2->next = node1;
temp = node1;
}
ListNode* ans = dummyHead->next;
delete dummyHead;
return ans;
}
};
水中水
力扣 contest no.429
Q1. 使数组元素互不相同所需的最少操作次数
class Solution {
public:
int minimumOperations(vector<int>& nums) {
int i=nums.size()-1;
int m[105];
for(i;i>=0;i--){
if(!m[nums[i]]) m[nums[i]]=1;
else break;
}
return (i+3)/3;
}
};
easy
Q2. 执行操作后不同元素的最大数量
class Solution {
public:
int maxDistinctElements(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
unordered_map<int,bool> m;
int ans(0);
int j(INT_MIN);
for(int i:nums){
for(j=max(j,i-k);j<=i+k;j++){
if(!m[j]){
m[j]=true;
ans++;
break;
}
}
}
return ans;
}
};
mid
力扣 no.1185\ 一周中的第几天
// 直接计算当前日期到1971年1月1日的天数, 然后模7即可
// 基姆拉尔森计算公式
class Solution {
public:
string dayOfTheWeek(int day, int month, int year) {
if ( month == 1 || month == 2 )
{
month = month + 12 ;
year -- ;
}
int index = 0 ;
index = ( day + 2 * month + 3 * ( month + 1 ) / 5 + year + year / 4 - year / 100 + year / 400 +1) % 7 ;
return index ;
}
};
// 蔡勒公式
class Solution {
public:
string dayOfTheWeek(int d, int m, int y) {
if(m < 3) m += 12, --y;
int c = y/100;
y %= 100;
int D = c/4 - 2*c + y + y/4 + 13*(m+1)/5 + d - 1 + 210;//加上30*7防止出现负数
return D%7;
}
};
// Tomohiko Sakamoto 算法
class Solution {
public:
string dayOfTheWeek(int d, int m, int y) {
static int t[12] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
if (m < 3) y--;
return (y + y / 4 - y / 100 + y / 400 + t[m - 1] + d) % 7;
}
};
力扣no.258
各位相加
```C++
class Solution {
public:
int addDigits(int num) {
return (num - 1) % 9 + 1;
}
};
数学方法, 其实取余 9 就好了, 但是不同的语言有不同的取余规则
力扣 no.1863\ 找出所有子集的异或总和再求和
// 枚举子集,用一个n位的二进制数的每一位表示子集的元素,1表示该元素在子集中,0表示不在子集中
// 按位贡献
class Solution {
public:
int subsetXORSum(vector<int>& nums) {
int res = 0;
int n = nums.size();
for (auto num: nums){
res |= num;
}
return res << (n - 1);
}
};
所有元素该位都为 0, 所有子集异或总和中该位均为,0, 反之, 所有子集异或总和中该位为 0 的个数与为 1 的个数相等, 均为 \(2^{n-1}\)\ 因此按位或看有没有 1, 若有贡献为该位值*\(2^{n-1}\)