weixin_44587168的博客

原创 LeetCode-18：四数之和

一、题目描述二、解题思路三数之和会了，这道题就会了。还是先排序，做去重复的初步准备其实也就是三数之和外层再套一个遍历而已但是不能直接就在nums[i]>targetnums[i]>targetnums[i]>target就返回，因为这个targettargettarget是人家任意指定的，有可能比数组里最小的还小，三数之和里人家指定了就是000，这块有点不同，否则会被卡用例：三、解题代码class Solution {public: vector<vec

原创 LeetCode-15：三数之和

一、题目描述二、解题思路首先，题目要求不能包含重复的三元组，所以要想到通过排序选择三元组的方法来去重；对排序数据进行遍历如果nums[a]>0nums[a] > 0nums[a]>0，后面的元素都比nums[a]nums[a]nums[a]大，不可能三数之和为000，直接返回重复元素跳过，避免重复左指针L=a+1L=a+1L=a+1，右指针R=size−1R = size - 1R=size−1：相当于固定一个元素，去凑另两个若和大于000：说明太大了，右指针左移若和

原创 Leetcode-429：N叉树的层序遍历

题目描述解题思路这个就是标准的BFSBFSBFS解决步骤，注意返回结果的每一个子向量，都是一层上的元素，不同的向量里的元素所在的层次不同。解题代码class Solution {public: vector<vector<int>> levelOrder(Node* root) { vector<vector<int>> ret; if(!root) return ret; ret.pus

原创 图的深度优先遍历和广度优先遍历

不多说，直接上代码common.h#pragma once#include <iostream>#include <limits.h>#include <queue>#include <utility>#include <vector>class Graph{public: int vecnum; int edgenum; bool *visited; std::vector<std::v

原创 C++模拟n门问题

这个门数可以自己更改#include <cstdlib>#include <ctime>#include <iomanip>#include <iostream>#include <vector>using namespace std;#define LEN 999999#define How_Many_Doors 100bool Test(bool IsChange){ vector<bool> Doo

原创 2020.08.06京东笔试题（基因+回文）

原创 浙大版《数据结构（第2版）》题目集习题4.5 顺序存储的二叉树的最近的公共祖先问题 (25分)

二、解题思路这个题利用了二叉树孩子结点和其父节点下标的索引关系：若顺序树的索引从1开始，那么子节点的索引除以二就是其父节点的索引，注意一定是要使得树的索引从1开始才有这个性质三、解题代码#include <iostream>#include <vector>using namespace std;int main(){ int n; cin >> n; auto T = new int[n]; if(!T) exit(0)..

原创 LeetCode-224: 基本计算器

一、题目描述二、解题思路将中缀表达式转换为后缀表达式。三、解题代码class Solution{private: static unordered_map<char, int> icp, isp; stack<char> stk; string src; string sln; void Back(); int calc(int tmp1, char oper, int tmp2);public: int ca

原创 浙大版《数据结构（第2版）》题目集习题3.11 表达式转换 (25分)

一、题目描述算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。输入格式:输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。输出格式:在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。输入样例:2+3*(7-4)+8/4输出样例:2 3 7 4 - * + 8 4 / +二、解

原创 数据结构与算法题目集（中文）7-15 QQ帐户的申请与登陆 (25分)

一、解题思路采用unordered_map建立起QQ号和pwd的映射，仅此而已二、解题代码#include <iostream>#include <string>#include <unordered_map>using namespace std;int main(){ int N; cin >> N; unordered_map<string, string> ump; for(int i = .

原创 浙大版《数据结构（第2版）》题目集最长连续递增子序列 (20分)

一、解题思路采用双指针法，就像切割字符串一样，来处理这个序列。首先定义一对前后指针left和right，分别表示本递增区间的起始位置和终止位置然后定义一个slnStart，来确定当前最优解（当前找到的最长递增序列）的起始位置定义一个maxLength，其含义为当前找到的最长长度，设置初始值为1，意思是即使向量全逆序，也至少要输出一个元素然后呢，挨个扫描向量的元素，查看下一个元素是不是递增的，直到找到本递增区间的终止位置然后，根据得到的left和right值，就可以确定这个递增区间的长度，位ri.

原创 浙大版《数据结构（第2版）》题目集5.13 词频统计 (30分)

请编写程序，对一段英文文本，统计其中所有不同单词的个数，以及词频最大的前10%的单词。所谓“单词”，是指由不超过80个单词字符组成的连续字符串，但长度超过15的单词将只截取保留前15个单词字符。而合法的“单词字符”为大小写字母、数字和下划线，其它字符均认为是单词分隔符。输入格式:输入给出一段非空文本，最后以符号#结尾。输入保证存在至少10个不同的单词。输出格式:在第一行中输出文本中所有不同单词的个数。注意“单词”不区分英文大小写，例如“PAT”和“pat”被认为是同一个单词。随后按照词频递减的顺

原创 浙大版《数据结构（第2版）》题目集5.10 线性探测法的查找函数 (20分)

一、题目描述#include <stdio.h>#define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */typedef int ElementType; /* 关键词类型用整型 */typedef int Index; /* 散列地址类型 */typedef Index Position; /* 数据所在位置与散列地址是同一类型 *//* 散列单元状态类型，分别对应：有合法元素、空单元、有已删除元素 */

原创 浙大版《数据结构（第2版）》题目集1.9 有序数组的插入 (20分)

本题要求将任一给定元素插入从大到小排好序的数组中合适的位置，以保持结果依然有序。函数接口定义：bool Insert( List L, ElementType X );其中List结构定义如下：typedef int Position;typedef struct LNode *List;struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素的位置 */};L是用户传入的一个线性表，

原创 LeetCode-1018：可被 5 整除的二进制前缀

class Solution {public: vector<bool> prefixesDivBy5(vector<int>& A) { vector<bool> sln; unsigned int dp_2 = 0, dp_1 = 0; for(size_t i = 0; i < A.size(); i++){ dp_1 = dp_2 * 2 + A.at(i);

原创 王道SqList编程题答案

SqList1. DelMinint DelMin(SqList &L){ if(!L.length){ cout << "Error!" << endl; exit(0); } int min = L.data[0], loc = 0; for(int i = 1; i < L.length; i++){ if(L.data[i] < min){ loc

原创 浙大版《数据结构（第2版）》题目集3.13 双端队列 (25分)

双端队列（deque，即double-ended queue的缩写）是一种具有队列和栈性质的数据结构，即可以（也只能）在线性表的两端进行插入和删除。若以顺序存储方式实现双端队列，请编写例程实现下列操作：Push(X,D)：将元素X插入到双端队列D的头；Pop(D)：删除双端队列D的头元素，并返回；Inject(X,D)：将元素X插入到双端队列D的尾部；Eject(D)：删除双端队列D的尾部元素，并返回。函数接口定义：bool Push( ElementType X, Deque D );E

原创 三相高频PWM在电动汽车双向充放电中的应用

原创 LeetCode-560: 和为K的子数组

First. Problem’s DescriptionSecond. Problem’s SolutionUse a HashTable to store the pre_sum of the array, use unordered_map<sum, how_many> ump;When we start, insert pair<int, int>(0, 1)into the unordered_map first, that represents even if t

原创 LeetCode-1：两数之和

一、题目描述二、解题思路这道题当然可以暴力，这样时间复杂度为O(n2)O(n^2)O(n2)。所以我采用哈希表来解决。遍历一次数组，将其与下标的pair(val,index)pair(val, index)pair(val,index)插入到哈希表中。所以我们根据当前的数字去找target−nums[i]target - nums[i]target−nums[i]是否在哈希表里即可。但是如果出现target−nums[i]==nums[i]target - nums[i] == nums[i]tar

原创 LeetCode-287：寻找重复数

一、题目描述二、解题思路这是剑指Offer的原题。。。。。。评论区用的都是有环链表的方法一个萝呗一个坑儿，如果没有重复那么下标与元素值应该可以达成一一对应那么如果当前下标和元素值不同，那么我们就不断地调整，也就是说把这个元素调到它应该在的位置如果发现了它要去的那个地方被一个和它相等的元素占了，那就直接返回over时间复杂度O(n)，空间复杂度S(1)三、解题代码class Solution {public: int findDuplicate(vector<int&g

原创 LeetCode-4：寻找两个正序数组的中位数

一、题目描述二、解题思路  题目要求时间复杂度为O(log(m+n))O(log(m + n))O(log(m+n))，很明显需要采用二分法来解决。  如果我们可以在这两个有序序列中找到第KKK个数字，那么我们只要能找到中间的一个或两个数字，就一定可以得到这道题的解。  所以问题退化为寻找两个有序序列的按序第KKK个数字。  在寻找中间的数字的过程中，需要区分以下两个序列长度和为奇数偶数的区别：如果为奇数，那么中间的数字只有一个，那就是第(len1+len2+1)/2(len1 + len

原创 LeetCode-696：计数二进制子串

一、题目描述二、解题思路找每次连续的1或者0的个数，存入vector，之后每次选取紧邻着的两个中较小的那个相加给res比如：100011111001110，得到vector = {1, 3, 5, 2, 3, 1}，所以res = 1 + 3 + 2 + 2 + 1三、解题代码class Solution {public: int countBinarySubstrings(string s) { int l = 0, r = 0; int a[2];

原创 LeetCode-432：全 O(1) 的数据结构

一、题目描述二、解题思路三、解题代码class AllOne{private: class Node { public: string str; int num; Node(string s, int n) { str = s; num = n; } friend bool operator<(const Node &amp

原创 2020年华中科技大学计算机科学与技术学院研究生入学考试复试专业实践能力考核试题——监控相机布局问题

一、题目描述二、解题思路因为我并没有接触和了解过提示中列举出来的除了贪心算法之外的算法，所以我采用贪心算法来解决GetDataFromTXT()函数将txt中的数据读入哈希表，建立起摄像头ID和覆盖区域的映射建立一个当前仍没有被覆盖的点位集合，对于运行到这步的程序，也就是全部待监控点位的集合Calculate()函数选出一个摄像头，这个摄像头可以覆盖最多的监控盲区，即取每个由摄像头ID映射出来的该摄像头覆盖区域集合和当前盲区集合的交集取所有交集中元素最多的那个摄像头ID，

原创 C语言按行读取文件/写数组到文件

#include <cstdio>#include <cstdlib>int main(){ int row, col; FILE *fp = fopen("In.txt", "r"); FILE *fd = fopen("Out.txt", "w"); if (!fp || !fd) { printf("File doesn't exist\n"); exit(0); } fscanf(

原创 LeetCode-355：设计推特

class Twitter{private: vector<pair<int, int>> Msg; unordered_map<int, set<int>> Fler;public: Twitter() { } void postTweet(int userId, int tweetId) { Msg.push_back(make_pair(userId, tweetId));

原创 LeetCode-25：K 个一组翻转链表

一、题目描述二、解题思路  这道题，最简单的方法就是从头节点开始，每次查看当前剩下的节点是不是多于K个，如果是的话就进行反转，否则就不进行并返回。  这样当然可以，但是有性能瓶颈：每次都需要查看剩余元素个数，相当于遍历了两次链表才可以完成反转，还不考虑反转的操作占用时间。  我想出来的办法是每次都进行反转，不考虑最后的不足K个的那段不需要反转的问题。那么就势必要解决最后这一点零头的问题。  通过前后指针，记录下当前被反转段的头节点和尾节点，反正都是要用循环的，顺手就可以判断是不是少于K个。如果少

原创 LeetCode-1048：最长字符串链

一、题目描述二、解题思路这个提示很重要，它限定了字符串的最大长度题目里并没有说字符串的长度是递增的，有可能是乱序长度排列的，而我的一次错误提交也证实了这一猜想。那么首先我们应该将字符串按照长度进行聚类，注意这里会用到1 <= words[i].length <= 16这个条件。可以建立起vector<vector<int>> LenDic(17)然后，此题是动态规划类型的题目，那么如何进行动态规划呢？确定dp数组，明确数组值的含义dp[i]表示以wor

原创 详解堆排序

#include #include #include #include using namespace std;template void AdjustDown(T A[], int k, int len){auto i = 2 * k + 1;while (i <= len){if (i < len && A[i] > A[i + 1])i++;if (A[k] > A[i]){swap(A[k], A[i]);k = i;i =

原创 LeetCode-297: 二叉树的序列化与反序列化

class Codec{public: // Encodes a tree to a single string. string serialize(TreeNode *root) { if (!root) return ""; vector<TreeNode *> vec; string ret = "["; queue<TreeNode *> que; .

原创 LeetCode-173: 二叉搜索树迭代器

First. Problem’s DescriptionSecond. Problem’s SolutionBST has a non-decreasing inorder-traversing series. We can use a list to store the nodes and where we call next(), we delete the beginning node in the list.Three. Code For Solutionclass BSTIterator

原创 LeetCode面试题 03.01: 三合一

First. Problem’s DescriptionSecond. Problem’s SolutionI don’t think there is any point that’s difficult to solve.Three. Code For Solutionclass TripleInOne {private: int *Data; int sSize = -1; unsigned int s_begin[3]; unsigned int s_cu

原创 LeetCode面试题 16.02: 单词频率

First. Problem’s DescriptionSecond. Problem’s SolutionWe can simply use a unordered_map to solve this problem, which core is powered by HashBy the way, the default initial value is 000Three. Code For Solutionclass WordsFrequency {private: unorde

原创 LeetCode-146：LRU缓存机制

一、题目描述class LRUCache{private: unordered_map<int, list<pair<int, int>>::iterator> ump; list<pair<int, int>> Lst; int MaxSize; int HowMuch;public: LRUCache(int capacity) { HowMuch = 0;

原创 PTA数据结构与算法题目集（中文）-6-7: 在一个数组中实现两个堆栈

一、题目描述本题要求在一个数组中实现两个堆栈。函数接口定义：Stack CreateStack( int MaxSize );bool Push( Stack S, ElementType X, int Tag );ElementType Pop( Stack S, int Tag );其中Tag是堆栈编号，取1或2；MaxSize堆栈数组的规模；Stack结构定义如下：typedef int Position;struct SNode { ElementType *Data;

原创 LeetCode-184：部门工资最高的员工

SELECT d.Name as Department, e.Name as Employee, e.SalaryFROM Employee e, Department dWHERE e.DepartmentID = d.Id AND(e.Salary, e.DepartmentID) IN (SELECT MAX(SALARY), DepartmentID FROM Employee group by DepartmentID);

原创 PTA数据结构与算法题目集（中文）6-2：顺序表操作集

一、题目描述#include <stdio.h>#include <stdlib.h>#define MAXSIZE 5#define ERROR -1typedef enum {false, true} bool;typedef int ElementType;typedef int Position;typedef struct LNode *Lis...

原创 PTA数据结构与算法题目集（中文）7-26：Windows消息队列

一、题目描述二、解题思路每次都要找优先级最高的，这明显是采用优先队列来解决，结合Hash表快速对优先级所对应的消息进行快速定位，最后把输出信息保存到一个队列里，结束时一起输出，但是不保存到队列直接输出也可以三、解题代码#include <iostream>#include <queue>#include <string>#include <...

原创 LeetCode-648：单词替换

一、题目描述二、解题思路用双指针法切割字符串，得到每一个单词，然后开始遍历字典首先判断单词首字母和字典当前元素的首字母是否相等，相等继续进行下一步，否则肯定不是判断当前单词的前缀是否等于字典当前元素如果以上两个条件都满足，就把单词替换成词根，注意这个动作完成后不能直接break因为有可能存在继承词有许多可以形成词根的情况，我们需要找到最短的，比如：["catt","cat","bat...