Jayce's Blog

PROBLEM剑指 Offer 09. 用两个栈实现队列 难度 简单 MY ANSWER栈in负责append，栈out负责delete。append时直接push进in就好，delete时先检查out是否为空，out空的话再检查in是否为空，in也空的话返回-1，否则将in里的一个个出栈并压到out里，最后弹出一个。若out非空，则直接弹出一个。 class CQueue {public: stack<int> in; stack<int> out; CQueue() {} void appendTail(int value) { in.push(value); } int deleteHead() { if(!out.empty()) { int tmp = out.top(); out.pop(); return tmp; } ...

PROBLEM剑指 Offer 07. 重建二叉树 难度 中等 MY ANSWER递归思路如图，顺着设计递归解决。使用哈希表来查询root在inorder中的索引减少时间复杂度。递归函数settree中，参数root为根节点在preorder中的索引，参数left为inorder中根节点的子树的左边界，参数right为inorder中根节点的子树的右边界。时间复杂度O(n)，空间复杂度O(n)。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: unordered_map<int, int> index; vector<int> pr ...

PROBLEM剑指 Offer 06. 从尾到头打印链表 难度 简单 MY ANSWER递归反转链表，然后从末尾往前遍历。时间复杂度O(n)，空间复杂度O(n)。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: void reverseNext(ListNode* head) { if(!head->next) { return; } if(head->next->next) { reverseNext(head->next); } head-> ...

PROBLEM剑指 Offer 05. 替换空格 难度 简单 MY ANSWER调用string库函数replace来进行替换。时间复杂度、空间复杂度因不知道库函数实现无法计算，按评测结果来看应该是O(n)和O(1). class Solution {public: string replaceSpace(string s) { for(int i = 0; i < s.length(); i++) { if(s[i] == ' ') { s = s.replace(i, 1, "%20"); } } return s; }}; BETTER SOLUTION不调用库函数就老老实实按字符处理。首先统计空格数量，然后调用resize修改s长度，从末尾开始往前进行原地修改。时间复杂度O(n)，空间复杂度O(1). class Soluti ...

PROBLEM剑指 Offer 04. 二维数组中的查找 难度 中等 MY ANSWER相当于二叉搜索树。从右上角开始遍历，若值比target大则向左走，若小则向下走，无路可走时说明没有该整数，返回false。注意设置 j 初值时要考虑空矩阵的判断，否则过不了。时间复杂度O(n+m)，空间复杂度O(1)。 class Solution {public: bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) { int i = 0, j = matrix.size() ? matrix[0].size() - 1 : 0; while(i < matrix.size() && j >= 0) { if(matrix[i][j] == target) { return true; } ...

PROBLEM剑指 Offer 03. 数组中重复的数字 难度 简单 MY ANSWER哈希表使用哈希表来实现类似桶排序的方法。先查询表中有无该数，若有则返回，若无则放入表中。时间复杂度O(n)，空间复杂度O(n)。 class Solution {public: int findRepeatNumber(vector<int>& nums) { unordered_map<int, int> hashtable; for (int i = 0; i < nums.size(); i++) { auto it = hashtable.find(nums[i]); if(it != hashtable.end()) { return nums[i]; } else { hashtable[nums[i]] = 1 ...

今天得到高人指点迷津。故从今天开始刷题，先来第一题体验一下。 PROBLEM1.两数之和 难度 简单 MY ANSWER暴力两个for搞定，时间复杂度O（n^2)，空间复杂度O（1）。 class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { int a,b; vector<int> tmp; for(int i = 0; i < nums.size(); i++) { for(int j = i + 1; j < nums.size(); j++) { if(nums[i] + nums[j] == target) { a = i; b = j; tmp.push_back( ...

暑假的最后一周在忙碌的学生助理工作中结束，周末想着给大号上个钻，结果死活打不上去，选择摆烂了。虽然暑假基本没干啥事，不过还是简单写个小结吧。 数据库700页的教材，看了150页，算是意料之中。听说数据库老师有点逆天，已经做好看教材自学的准备了。 C#与U3DC#在看菜鸟教程进行粗略学习，未进行实操。U3D在跟着缓慢更新的坛友教程学习，也未进行实操，纯纯的摆烂人了属于是。甩锅给前不久才有钱买的ssd，给笔记本装上以后才不用担心C盘大小和总空间的问题。现在C盘250，D盘500，应该够用了吧。为此把系统重装了，环境需要慢慢重新配置，总算可以装VS了。 梯子算是被vultr给骗了，首充优惠送的余额一个月就过期，相当于免费送一个月梯子。3.5刀一个月实在有点贵，等余额用完后再考虑怎么搞吧。 戒网瘾下定决心远离竞技类游戏了，得把时间专注于学习上，偶尔的101开黑、画画、aimlab、osu啥的可以保留一下。 新学期计划 教材和ppt的阅读尽量跟上上课进度 课余进行U3D相关学习 多跑步多锻炼，保持充足睡眠 最后用最爱的水母之歌做结尾吧！ D⊂≈≈≈≈ D⊂≈≈≈≈ D⊂≈≈≈≈ 水母 水母随 ...

期末7月上旬首先是考试周，第一周七门，第二周周二考一学期没学的系统分析与设计。基本每天熬得挺晚的，平时没学好只能考前抱抱佛脚了。考完成绩也不出意外，只能说是差强人意。有几科还行，有几科因为瞎写作业平时分炸了，总的来说比上学期进步一点点。 搭梯子和博客考完干的两件事就是把梯子和个人博客搭了起来，主要参考了： https://www.itblogcn.com/article/406.html https://www.cnblogs.com/liuxianan/p/build-blog-website-by-hexo-github.html#%E6%90%AD%E5%BB%BAgithub%E5%8D%9A%E5%AE%A2 https://blog.csdn.net/wapchief/article/details/54602515 有了VPS后就不用担心VPN供应商跑路了，还能三端科学上网，价格便宜。博客用的butterfly主题，挺好看的，配置也很多，以后慢慢美化和完善吧。 学生助理暑假留校，去应聘了校内系科院的学生助理，赚点零花钱。一周就上几天班，也不算特别忙，空余时间正好留来学 ...

不推嘉然小姐十年了。 她的名气和出场费都一涨再涨，我原地踏步的工资买不上专辑也打不起榜。终于年前被公司安排下岗，找工作时我才在路边广告发现初代工具人已经当上了厂长。时间太久，一切都变了。 到处投简历的时候我想起了一名人上人的预言：“这些人只配在下水道里度过相对比较失败的人生。”像是一条跳过龙门的锦鲤，金鳞被羽耀武扬威地站在门沿上，对其他还在跳的鲤鱼说：“你不行！”我当时很想反驳，可他说中了。我知道我确实不行。我之所以跳了跳，只是为了看下自己能跳成什么样罢了。其实每条鲤鱼的龙门都不是一样高的。我见过龙门在水下的鲤鱼。看起来是鱼，其实生而为龙。也有的生而为鱼肉。也见过好运的鲤鱼，门被各种大手摁到河里了。我也期待过好运，只是没来而已。说起来这就是人性吧。我不讨厌天道酬勤，但是讨厌别人的好运——只是因为我没有好运罢了。我也有亲人和宠物会生病；我眼神也挺纯真啊。 讨厌嘉然小姐十年了。讨厌的更是越来越深的无力感。身在泥潭的人是没力气冲锋的吧。三流的人生只会让上等人不屑一顾吧。我坐井观天，天穹星海依然耀眼。可我爬不出井底。那我就不再看星星了。世界那么大，但没我的份。 忘记嘉然小姐十年了。可路上看见街 ...