2021-6-10-LeetCode记录
| 难度 | 数量 |
|---|---|
2021-6-9-LeetCode记录
2021-6-9 LeetCode记录
| 难度 | 数量 |
|---|---|
| 总计 | 2 |
| Easy | 2 |
今天做了5月底的两道每日一题。
2的幂：位运算问题。
$2^n$的二进制表示的特点是：最高位为1，剩余位为0。
$2^n-1$的二进制表示的特点是：最高位为0，剩余位为1。（以$2^n$的长度为基准）
下面以8为例：
$2^n$：8，1000
$2^n-1$：7，0111
因此只需保证(n & n - 1) == 0，同时n > 0即可满足条件。
1 | class Solution { |
4的幂：与上题相似的位运算问题，可以通过两种方法求解。
利用$4^n$的位数性质：
在$2^n$性质的基础上，$4^n$的特点是最高位总是奇数位。因此构造出一个偶数位全1的整数$(10101010101010101010101010101010)_2$，表示为16进制为$(AAAAAAAA)_{16}$。
将上述数字与$4^n$与操作之后应该得0，可以以此来判断。
1
2
3
4
5
6class Solution {
public:
bool isPowerOfFour(int n) {
return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
}
};利用$4^n$的余数性质：
对于$2^n$，满足同时为$4^n$的子集也满足模3余1，而不满足的子集满足模3余2。
例如：16%3 = 1， 而8 % 3 = 2；
1
2
3
4
5
6class Solution {
public:
bool isPowerOfFour(int n) {
return n > 0 && (n & (n - 1)) == 0 && (n % 3) == 1;
}
};
2021-5-27-LeetCode记录
2021-5-26 LeetCode记录
2021-5-26 LeetCode记录
| 难度 | 数量 |
|---|---|
| 总计 | 6 |
| Easy | 5 |
| Medium | 1 |
今天做的都是剑指Offer里面的题目。
10-I.斐波那契数列与10-II.青蛙跳台阶问题：两题都是类似于斐波那契数列的动态规划类题目，比较好的方法是通过常数级别的变量存储动态规划需要的数据并循环求解。
时间复杂度：$O(n)$
空间复杂度：$O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
int fib(int n) {
int first = 0, second = 1, res = 0;
if (n == 0){
return 0;
}
else if (n == 1){
return 1;
}
else{
for (int i = 2;i <= n;i++){
res = first + second;
res %= 1000000007;
first = second;
second = res;
}
}
return res;
}
};03.数组中的重复数字：这道题有两种解法。一是利用额外空间建立哈希表来记录元素重复情况，二是利用题目中的数字分布规律（所有数字在0~n-1的范围内）性质来在不用额外空间的情况下求解。
第二种方法的思路是：遍历数组并将元素与其值代表的下标位置进行交换，若其中已存放该值的话则说明有重复。
时间复杂度：$O(n)$
空间复杂度：$O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
for (int i = 0;i<nums.size();i++){
if (nums[i] == i){
continue;
}
// 出现重复
if (nums[i] == nums[nums[i]]){
return nums[i];
}
swap(nums[i], nums[nums[i]]);
}
return -1;
}
};04.二维数组中的查找本题是在一个每一行左-右递增、每一列上-下递增的二维数组中进行元素查找。
理想的方法是将其视作以右上角或左下角为根的二叉查找树。
时间复杂度：$O(M+N)$
空间复杂度：$O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0) return false;
// 以右上角为根结点
int x = 0, y = matrix[0].size() - 1;
while (x < matrix.size() && y >= 0){
// 大于当前结点则右移
if (matrix[x][y] > target) y--;
// 小于当前结点则下移
else if (matrix[x][y] < target) x++;
// 等于则退出
else return true;
}
return false;
}
};11.旋转数组的最小数字利用旋转数组的性质，进行二分查找。
具体方法是维护左右指针，每次将中点与末尾对比，随后更新左右指针。
时间复杂度：$O(log_2N)$
空间复杂度：$O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
int minArray(vector<int>& numbers) {
int i = 0, j = numbers.size()-1;
while (i != j){
int m = (i+j)/2;
//
if (numbers[m]>numbers[j]) i = m + 1;
else if (numbers[m]<numbers[j]) j = m;
else j = j - 1;
}
return numbers[i];
}
};09.用两个栈实现队列用两个栈来实现队列，一个栈用于入队操作、一个栈用于出队操作。
入队时加在栈尾，出队时将入队栈翻转并出队栈顶。
时间复杂度：添加$O(1)$、删除$O(n)$
空间复杂度：$O(N)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class CQueue(object):
def __init__(self):
self.stack_add = []
self.stack_del = []
def appendTail(self, value):
self.stack_add.append(value)
def deleteHead(self):
if self.stack_del:
return self.stack_del.pop()
if not self.stack_add:
return -1
while self.stack_add:
self.stack_del.append(self.stack_add.pop())
return self.stack_del.pop()
写在博客即将开通一周年之际
写在博客即将开通一周年之际
去年6月25日开通了这个博客，却并没有像想象中那样经常更新。甚至前面编写过的一些主题都以烂尾告终了。(比如EOJ系列、控制手机系列)
最主要的问题是即便开通了一个公开发表的渠道，也并没有想清楚要以什么样的内容和频率来输出内容。
当初设想的内容包括：课程相关资料、学习新技术的笔记、EOJ题解、其他有趣的方面。
然而课程相关资料虽然非常适合引流，但是对我而言并没有建设性的意义（没有冒犯做过这类工作的前辈的意思，这个工作很有意义，仅仅是不适合我而已。）。
而EOJ题解，实际上按我的水平来说还称不上题解的高度，只能说是解题经验分享。而且现在也不再做EOJ了。（所以之前写过的两篇就先隐藏了。）
接下来可能会专注于LeetCode解题经验分享和学习新技术的笔记，可能的话希望一天能至少维持LeetCode一道题的频率。
戒除手机滥用经验贴（第一周）
控制玩手机的第一周！（7/19-7/25）
虽然终于开始放暑假了，但是由于大量课程需要返校考试的缘故仍然需要控制手机的使用时间，以达到较好的学习效果。
实际上，控制屏幕使用时间也并非应该是期末周或是需要集中学习时才采取的策略。为了平日里能够更加专注于自我提升或者娱乐，减少手机的使用时间是必要的。
然而，为什么说减少手机使用时间可以更加专注于娱乐？在观察了过去三周的手机屏幕使用数据后，得出了以下的结论：
每周的总使用时间达58-69小时，日均8-10小时。占据比例最大的是社交类软件（57%-62%），总屏幕使用时间占据每周总时间（7*24h）的近34%-41%。
可以认为一周除去睡觉的时间外大部分时间都在使用手机，而大部分时间都用在了浏览社交软件上，实际上这并不能达到良好的娱乐体验，只是在无意义地刷新与浏览碎片化的信息。
出于上述的背景和原因，我对手机使用时间进行了控制。具体的措施是：社交软件使用时间限制在3小时/每天之内，12：30-7：00之间禁用手机。（这一功能可以通过iOS系统中的“屏幕使用时间”功能来实现）
成果如下图所示，由于控制使用时间的举措从周二开始，因此社交类软件总使用时间并未能够降至24小时之内。但较其上周已经有了显著的降低，总时间降幅达42%。
实际上，要想做到社交软件限制在每天3小时内是有一定难度的。在AppStore中，微信、小红书、微博、知乎等软件都被归类于社交软件。
作为一名新晋追星族，此前从未下载过的小红书与微博成为了我近期了解偶像动态必备的App。尤其是微博，每天会数次访问以查看快乐女士李斯丹妮的微博及衍生言论、图片等。在控制时间之前，我常常会仔细浏览粉丝群（目前已经是一个3000人的大群了，消息频率极高）中的消息，查看Timeline上的小视频、微博等碎片化信息。
微信已经是现代人难以离开的社交软件，许多人（俺）因为担心错过消息而频繁检查微信消息，顺便浏览公众号、朋友圈等。为了控制手机的使用，我再次关闭了朋友圈。（此前在正式学期期间常常会关闭朋友圈数周之久以专注于学习。）
知乎上新奇的知识与讨论常能让人沉迷其中，但在我意识到知乎会让人不断浏览无用的知识后，知乎App在我的手机中已经近3年没有长期留存过了。（刚放假想轻松几天时可能会下载）
在设定了手机使用时间的限制之后，最大的难题就是将社交软件使用时间限制在3小时之内。无意识地浏览信息会让使用时间在不知不觉中骤增，导致在下午或傍晚时手机就提醒你只剩5分钟可以使用社交软件，然而剩余的时间并不足以维系当日正常的社交活动。
为了达到社交<3小时的目标，我选择每次拿起手机后急促地处理微信未读消息、简单浏览微博（只看快乐女士李斯丹妮本人的微博是否更新，不关心衍生话题与粉丝群）、关闭朋友圈。这样的举措使得我的手机使用时间大大减少，同时在一定范围内限制了我熬夜的恶习。
当然，手机上设定的限制只需要简单操作就可以取消，要完全借助外力戒除手机的滥用是非常困难的。
如果你也想控制手机的使用的话，不妨想一想你为什么要这样做？应该如何行动，又如何能够保持自律不打破自己设定的规则呢？
对我而言，原因和行动已在前文中阐释。而自律的方法，或许就是保持规则的神圣感，在任何情况下都不试图去打破它。