每日一题

336.回文对

题目比较简单,上来可以先判断两个拼接好的字符串是否符合,然后遍历判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
int len=words.size();
vector<vector<int>> all;
for(int i=0;i<len;i++)
{
for(int j=0;j<len;j++)
{
if(i!=j&&Judge(words[i],words[j]))
{
vector<int> temp;
temp.push_back(i);
temp.push_back(j);
all.push_back(temp);
}
}

}
return all;


}
bool Judge(string& w1,string& w2)
{
string str = w1+w2;
int len = str.size();
for(int i=0;i<len;i++)
{
if(str[i]!=str[len-1-i])
return false;
}
return true;
}
};

提交结果,有一半能够通过,其他的超出了时间限制。看到题解说不能直接用str = w1+w2;,移动指针会快一些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
bool Judge(string& w1,string& w2)
{
int len1 = w1.size();
int len2 = w2.size();
int len = len1 +len2;
int i;

for(i=0;i<len/2;i++)
{
if(len1>len2)
{
if(i<len2)
{
if(w1[i]!=w2[len2-1-i])
return false;
}
else
{
if(w1[i]!=w1[len-1-i])
return false;
}
}
else
{
if(i<len1)
{
if(w1[i]!=w2[len2-1-i])
return false;
}
else
{
if(w2[i-len1]!=w2[len2-1-i])
return false;
}
}

}
return true;
}

执行结果:通过
执行用时:1528 ms, 在所有 C++ 提交中击败了7.14%的用户。
内存消耗:21.6 MB, 在所有 C++ 提交中击败了100.00%的用户。

另一个方法使用 manacher算法,竞赛难度就算了。只能做人下人了,哈哈。

后面评论实在太逗了。

100. 相同的树

很简单的一道题,直接递归调用判断就行

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p!=nullptr&& q!=nullptr)
{
return p->val==q->val&&isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
else if(p==nullptr && q== nullptr)
return true;
else
return false;
}
};

226. 翻转二叉树

easy 递归交换左右节点。

344. 反转字符串

遍历头尾交换。

142. 环形链表 II

  1. 暴力搜索 O(n2n^2)
  2. hash表
  3. 利用快慢指针,快指针每次走两步,慢指针每次走一步。

416. 分割等和子集

  • 美好的一天从每日一题结束
  • 动态规划,可以转化为0-1背包问题。
  • 对每一个数,都可以选择取和取。
  • 转移方程
    dp[i][j]={dp[i1][j]dp[i1][jnums[i]],ifjnums[i]dp[i1][j],ifj<nums[i]dp[i][j]=\begin{cases} dp[i-1][j]|dp[i-1][j-nums[i]],&{if}&{j}≥{nums[i]}\\ dp[i-1][j],&{if}&{j}<{nums[i]} \end{cases}
    dp[i][j] 表示从数组的[0,i] 下标范围内选取若干个正整数(可以是0个),是否存在一种选取方案使得被选取的正整数的和等于j。

0-1 背包问题

给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。
问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?

  • 声明一个 大小为 m[n][c] 的二维数组,m[ i ][ j ] 表示 在面对第 i 件物品,且背包容量为 j 时所能获得的最大价值
  • 状态转移方程:
    m[i][j]={max(m[i1][j],m[i1][jw[i]]+v[i]),ifjw[i]m[i][j]=m[i1][j],ifj<w[i]m[i][j]=\begin{cases} max(m[i-1][j],m[i-1][j-w[i]]+v[i]),&{if}&{j}≥{w[i]}\\ m[i][j]=m[i-1][j],&{if}&{j}<{w[i]} \end{cases}

530. 二叉搜索树的最小绝对差

中序遍历可以得到二叉搜索树值的有序序列,元素的最小绝对差一定是相邻两个元素之间的。last记录上次的值,与本次的值求绝对差,边遍历边更新最小绝对差,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
{
MidTra(root);
return _min;
}

}
private:
int last = -1;
int _min = INT_MAX;
void MidTra(TreeNode* root)
{
if(root!=NULL)
{
MidTra(root->left);
if(last!=-1)
{
_min=min(_min,root->val-last);
last=root->val;
}
else
{
last = root->val;
}
MidTra(root->right);
}
}
};

24. 两两交换链表中的节点

easy难度,就是简单的链表节点交换问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head==nullptr||head->next==nullptr)
return head;
ListNode *first = head,*second = head->next,*ret = head->next,*last =nullptr;
while(first && second)
{
ListNode *temp = second->next;
second->next = first;
first->next =nullptr;
if(last!=nullptr)
last->next = second;
last = first;
first = temp;
if(first!=nullptr)
{
second = first->next;
if(second==nullptr)
last->next = first;
}
else
break;
}
return ret;
}
};

1002. 查找常用字符

  • 设置一个长度26的vector存储每个字符串中各个字符的计数。
  • 遍历整个字符串向量,分别每个字符串中的字符个数进行计数。
  • 取所有vector的交集(对于字符计数不同的,取此字符较小的计数)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
vector<string> commonChars(vector<string>& A) {
if(A.size()==0)
return vector<string>();
vector<int> cnt(26,0);
for(auto ch :A[0])
cnt[ch-'a']++;
for(int i=1;i<A.size();i++)
{
vector<int> ths(26,0);
for(auto ch :A[i])
{
ths[ch-'a']++;
}
for(int i=0;i<26;i++)
if(cnt[i]!=ths[i])
cnt[i]=min(cnt[i],ths[i]);
}
vector<string> ret;
for(int i=0;i<26;i++)
{
while(cnt[i])
{
ret.push_back(string(1,'a'+i));
cnt[i]--;
}
}
return ret;
}
};

116. 填充每个节点的下一个右侧节点指针

  • 可以采取先序遍历的思想

  • 对于每个节点root,如果有左子节点 root->left,那么左子节点的next是右子节点,root->left->next = root->right

  • 如果有右子节点(有左定有有)root->right,右子节点的next是

    • 若root的next节点不为空,右子节点的next是root->next的左子节点,root->right->next = root->next->left
    • 若root的next节点为空,右子节点的next是NULL,root->right->next = NULL
  • 本题很容易想到使用额外的队列进行树的层次遍历,在此我们可以省略掉这个额外的队列进行循环的层次遍历。

  • next的赋值操作和上一个递归的一致

  • 对于每一层,我们进行下一层的next的赋值操作。我们利用上层对本层完成的next的赋值从左到右对每个节点进行遍历,完成对每个节点的子节点的next的赋值操作,完成全部子节点后进入下一层。继续进行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
Node* connect(Node* root) {
Pre(root);
return root;

}
void Pre(Node *root)
{
if(root)
{
if(root->left)
root->left->next = root->right;
if(root->right)
{
if(root->next)
root->right->next = root->next->left;
else
root->right->next = NULL;
}
Pre(root->left);
Pre(root->right);
}
}
};

977. 有序数组的平方

easy

19. 删除链表的倒数第N个节点

快慢指针,第一个指针先前进N个节点,然后两个指针一起前进,知道第一个指针到达链表的尾部。

844. 比较含退格的字符串

  • 第一次遍历,将需要退格的字符换成’#’, 第二次遍历,判断连个字符串是否相同。
  • 利用栈,遍历对于字符,将字符压入栈中,对于退格符,将栈顶的字符从栈中取出,完成之后,再比较两个栈中的内容。

143. 重排链表

  • 用递归做思路不难,结束条件有点麻烦。
  • 先到达链表的最后一个,将其插入到相应的位置后返回,再到前一个判断后插入,持续如此,到达结束条件之后,直接返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
void reorderList(ListNode* head) {
if(!head)
return;
cur = head;
ret = false;
inser(head->next);
}
ListNode *cur=nullptr;
bool ret;
void inser(ListNode *node)
{
if(!node)
{
return;
}
inser(node->next);
if(ret)
return;
if(node->next==nullptr)
{
if(cur->next!=node)
node->next = cur->next;
cur->next = node;
}
else if(node->next == cur->next)
{
cur = cur->next->next;

if(cur==node||cur->next == node)
{
node->next=nullptr;
ret = true;
}
else
{
node->next = cur->next;
cur->next = node;
}
}
}
};
  • 可以先找链表中点,使用快慢指针,慢指针走一步,快指针走两步。slow = slow->next, fast = fast->next->next;
  • 将后半部分链表逆序排序
  • 合并两个链表

925. 长按键入

  • 使用两个指针,分别指向两个字符串,然后就很显然了。。。。

763. 划分字母区间

  • 遍历字符串,进行分段。设置一个位置P用作新段的开始,一个栈S用作记录分段
  • 找到当前位置 i 的字符出现在字符串中的最后一次出现的位置 E,
    • 如果当前字符是一个新段的开始,压入 E-i+1 然后 P = E+1
    • 否则,判断这个位置E和新段开始P的大小,如果大于或等于P,将栈顶的分段大小加上 E-P+1 然后 P=E+1
  1. 第二步中找字符出现的字符串中的最后一次出现的位置 E 时,可以用字典或HASH表遍历一遍字符串提前记录下来。 这样时间复杂度就是O(n)O(n),而不是O(n2)O(n^2)
  2. 可以使用双指针代替使用栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
vector<int> partitionLabels(string S) {
int len = S.size();
int start = 0;
int dict[26]={0};
stack<int> sta;
for(int i=len-1;i>=0;i--)
{
dict[S[i]-'a'] = dict[S[i]-'a']>0?dict[S[i]-'a']:i;
}
for(int i=0;i<len;i++)
{
int j=dict[S[i]-'a'];
if(i==start)
{
sta.push(j-start+1);
start = j+1;
}
else
{
if(j>=start)
{
int pre = sta.top();
sta.pop();
sta.push(pre + j-start+1);
start = j+1;
}
}
}
vector<int> v(sta.size());
for(auto &vi:v)
{
vi = sta.top();
sta.pop();
}
reverse(v.begin(),v.end());
return v;
}
};

第一次medium运行时间0ms,超过100%还是挺开心的。

234. 回文链表

  • 首先快慢指针找到链表中间节点。
  • 反转其中一半链表
  • 比较

其中第一步和第二步可以合并,在寻找链表中间节点的时候可以将前半部分的链表反转,之后就可以直接比较了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode *slow = head,*fast = head;
ListNode *tail = NULL;
while(fast&&fast->next)
{
ListNode *temp = slow;
slow = slow->next;
fast = fast->next->next;
temp->next = tail;
tail = temp;
}
if(fast)
slow = slow->next;
while(tail && slow)
{
if(tail->val!=slow->val)
return false;
tail = tail->next;
slow = slow->next;
}
return true;
}
};

1024. 视频拼接 (2020-1024?)

  • 可使用贪心算法或动态规划,本题使用贪心算法最优
  • 动规:dp[j]=min(dp[j],dp[i]+1)dp[j] = min(dp[j],dp[i]+1)
  • 动规和贪心前半部分结合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int T) {
vector<int> dt(T,0);
vector<int> dp(T+1,-1);
for(auto c :clips)
{
if(c[0]<T&&c[1]>dt[c[0]])
dt[c[0]] = c[1];
}
for(int i=0;i<=dt[0]&&i<=T;i++)
dp[i] = 1;
for(int i=1;i<T;i++)
{
if(dp[i]<0)
return -1;
if(dt[i]>i)
{
for(int j=i+1;j<=dt[i] &&j<=T;j++)
{
if(dp[j]>0)
dp[j] = min(dp[j],dp[i]+1);
else
dp[j] = dp[i]+1;
}
}
}
return dp[T];
}
};
  • 贪心:先记录每个位置能到达的最远点。遍历,记录当前能到达的最远点far,和当前使用段的结束点ed。进行判断,结束或记录所使用的最少段cnt
1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i < T; i++) 
{
far = max(far, dt[i]);
if (i == far)
return -1;
if (i == ed)
{
cnt++;
ed = far;
}
}

845. 数组中的最长山脉

  • 今天是中等难度,不过感觉像是简单的题目。
  • 从0开始,然后判断就行了。每次在中间记录一下山顶,确定不是只有上坡或者下坡。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int longestMountain(vector<int>& A) {
int len = A.size();
int i=0,start=0,max=0,heil=0;
while(i<len)
{
start = i;
while(i+1<len &&A[i+1]>A[i]) i++;
int mid = i;
while(i+1<len &&A[i+1]<A[i]) i++;
if(i==start)
{
i++;
}
else
{
if(i>mid&&mid>start&& max<i-start+1)
max = i-start+1;
}
}
return max;

}
};

1365. 有多少小于当前数字的数字

  • 计数排序,然后统计
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
int dict[101]={0};
for(auto n:nums)
{
dict[n]++;
}
for(int i=1;i<101;i++)
{
dict[i]+=dict[i-1];
}
vector<int> ret(nums);
for(auto &r:ret)
{
if(r!=0)
r=dict[r-1];
}
return ret;
}
};

144. 二叉树的前序遍历

  • 非递归遍历,while + stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
vector<int> v;
while(root||!s.empty())
{
if(root)
{
v.push_back(root->val);
s.push(root);
root = root->left;
}
else
{
TreeNode *temp = s.top();
s.pop();
root = temp->right;
}
}
return v;
}
};

1207. 独一无二的出现次数

  • 对输入数组进行计数
  • 对计数的数组进行排序
  • 相邻两个数比较,如果有相同的就表明出现次数不是独一无二的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
bool uniqueOccurrences(vector<int>& arr) {
vector<int> cnt(2001);
for(int i=0;i<arr.size();i++)
{
if(arr[i]>=0)
cnt[arr[i]]++;
else
cnt[2001+arr[i]]++;
}
sort(cnt.begin(),cnt.end());
for(int i=0;i<2000;i++)
{
if(cnt[i]!=0 &&cnt[i]==cnt[i+1])
return false;
}
return true;

}
};

第二、三步也进行一次计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
bool uniqueOccurrences(vector<int>& arr) {
vector<int> cnt(2001);
vector<int> dt(1001);
for(int i=0;i<arr.size();i++)
{
if(arr[i]>=0)
cnt[arr[i]]++;
else
cnt[2001+arr[i]]++;
}
for(int i=0;i<2001;i++)
{
dt[cnt[i]]++;
if(dt[cnt[i]]>1 &&cnt[i]!=0)
return false;

}
return true;
}
};

129. 求根到叶子节点数字之和

  • 递归求和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int sumNumbers(TreeNode* root) {
return Func(root,0);
}
private:
int Func(TreeNode *root,int num)
{
if(!root)
return 0;
num = num*10 +root->val;
if(root->left==NULL&&root->right==NULL)
{
return num;
}
else
return Func(root->left,num)+Func(root->right,num);
}
};

463. 岛屿的周长

  • 从左往右,从上往下遍历即可
  • 如果地图是一个岛屿,周长 +4 ,如果这个岛屿左边也是岛屿,周长 -2,如果这个岛屿上方也是岛屿,周长 -2,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int rows = grid.size();
if(rows==0)
return 0;
int cols = grid[0].size();
int sum = grid[0][0]*4;
for(int j=1;j<cols;j++)
{
if(grid[0][j]==1)
{
sum+=4;
if(grid[0][j-1]==1)
sum-=2;
}
}
for(int i=1;i<rows;i++)
{
if(grid[i][0]==1)
{
sum += grid[i][0]*4;
if(grid[i-1][0]==1)
sum-=2;

}
for(int j=1;j<cols;j++)
{
if(grid[i][j]==1)
{
sum+=4;
if(grid[i][j-1]==1)
sum-=2;
if(grid[i-1][j]==1)
sum-=2;
}

}
}
return sum;
}
};