牛牛想要一个面试 - 个人主页动态

2023-01-30 15:32

class Solution { public: void merge(int A[], int m, int B[], int n) { int a = m-1; int b = n-1; int right = m + n - 1; while(a>=0 && b>=0) { if(A[a] >= B[b]) { A[right] = A[a]; a--; } else { A[right] = B[b]; b--; } right--; } while(b>=0) { A[right] = B[b]; b--; right--; } } }; 解题思路：双指针

0 点赞评论收藏

2023-01-29 17:30

西安电子科技大学 C++

题解 | #大数加法#

#include <algorithm> #include <string> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 计算两个数之和 * @param s string字符串 表示第一个整数 * @param t string字符串 表示第二个整数 * @return string字符串 */ string solve(string s, string t) { // write code here int m = s.size(); int n = t.size(); ...

0 点赞评论收藏

2023-01-29 16:59

西安电子科技大学 C++

题解 | #验证IP地址#

#include <cctype> class Solution { public: /** * 验证IP地址 * @param IP string字符串 一个IP地址字符串 * @return string字符串 */ bool isIPV4(string IP) { int n = IP.size(); if(n == 0) return false; int spotcount = 0; int num = 0; if(IP[0] == '.') return false; for(int i = 0;i<n;++i) { if(i>0 && IP[i] == '...

0 点赞评论收藏

2023-01-29 16:27

西安电子科技大学 C++

题解 | #最长公共前缀#

#include <string> class Solution { public: /** * * @param strs string字符串vector * @return string字符串 */ string longestCommonPrefix(vector<string>& strs) { // write code here if(strs.size() == 0) return ""; for(int i = 0;i<strs[0].size();++i) { char temp = strs[0][i]; for(int j = 1;j<...

0 点赞评论收藏

2023-01-29 16:09

西安电子科技大学 C++

题解 | #字符串变形#

#include <cctype> #include <fstream> #include <iterator> class Solution { public: void resverse(string &s,int start,int end) { int left = start; int right = end; while(left < right) { swap(s[left],s[right]); left++; right--; } } string trans(string s, int n) { // write code here...

0 点赞评论收藏

2023-01-28 21:14

西安电子科技大学 C++

题解 | #矩阵最长递增路径#

1.DFS #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 递增路径的最大长度 * @param matrix int整型vector<vector<>> 描述矩阵的每个数 * @return int整型 */ void dfs(vector<vector<int>>& matrix,int &count,vector<vector<int>>& visited,int i,int j...

0 点赞评论收藏

2023-01-28 19:43

西安电子科技大学 C++

题解 | #括号生成#

思路：相当于一共�n个左括号和�n个右括号，可以给我们使用，我们需要依次组装这些括号。每当我们使用一个左括号之后，就剩下�−1n−1个左括号和�n个右括号给我们使用，结果拼在使用的左括号之后就行了，因此后者就是一个子问题，可以使用递归：终止条件： 左右括号都使用了n个，将结果加入数组。返回值： 每一级向上一级返回后续组装后的字符串，即子问题中搭配出来的括号序列。本级任务： 每一级就是保证左括号还有剩余的情况下，使用一次左括号进入子问题，或者右括号还有剩余且右括号使用次数少于左括号的情况下使用一次右括号进入子问题。但是这样递归不能保证括号一定合法，我们需要保证左括号出现的次数比右括号多时我们再使...

0 点赞评论收藏

2023-01-28 17:53

西安电子科技大学 C++

题解 | #N皇后问题#

知识点：递归与回溯递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需要从子问题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支。n个皇后，不同行不同列，那么...

0 点赞评论收藏

2023-01-28 16:51

西安电子科技大学 C++

题解 | #字符串的排列#

1.老版写法 #include <string> #include <utility> #include <vector> class Solution { public: void dfs(unordered_set<string> &res,string &str,int index) { if(index == str.size()-1) res.insert(str); else { for(int i = index;i<str.size();++i) { swap(str[i],str[index]); dfs(res,str,...

0 点赞评论收藏

2023-01-27 18:57

西安电子科技大学 C++

题解 | #岛屿数量#

1.深度优先搜索DFS知识点：深度优先搜索（dfs） 深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。思路：矩阵中多处聚集着1，要想统计1聚集的堆数而不重复统计，那我们可以考虑每次找到一堆相邻的1，就将其全部改成0，而将所有相邻的1改成0的步骤又可以使用深度优先搜索（dfs）：当我们遇到矩阵的某个元素为1时，首先将其置为了0，然后查看与它相邻的上下左右四个方向，如果这四个方向任意相邻元素为1，则进入该元素，进入该元素之后我...

0 点赞评论收藏

2023-01-27 17:14

西安电子科技大学 C++

题解 | #有重复项数字的全排列#

这道题与没有重复项数字的全排列的解题思路一样，不过需要进行去重 #include <vector> class Solution { public: void recursion(set<vector<int>> &st, vector<int> &num, int index) { if(index == num.size()-1) { st.insert(num); } else { for(int i = index;i<num.size();++i) { //去重 if(i != index && num[i] == num[i-1...

0 点赞评论收藏

2023-01-27 16:52

西安电子科技大学 C++

题解 | #没有重复项数字的全排列#

1.思路：全排列就是对数组元素交换位置，使每一种排列都可能出现。因为题目要求按照字典序排列输出，那毫无疑问第一个排列就是数组的升序排列，它的字典序最小，后续每个元素与它后面的元素交换一次位置就是一种排列情况，但是如果要保持原来的位置不变，那就不应该从它后面的元素开始交换而是从自己开始交换才能保证原来的位置不变，不会漏情况。如何保证每个元素能和从自己开始后的每个元素都交换位置，这种时候我们可以考虑递归。为什么可以使用递归？我们可以看数组[1,2,3,4]，如果遍历经过一个元素2以后，那就相当于我们确定了数组到该元素为止的前半部分，前半部分1和2的位置都不用变了，只需要对3，4进行排列，这对于后半...

0 点赞评论收藏

2023-01-20 21:02

西安电子科技大学 C++

题解 | #缺失的第一个正整数#

1.排序后查找 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int minNumberDisappeared(vector<int>& nums) { // write code here sort(nums.begin(),nums.end()); int number = 1; for(int i = 0 ; i < nums.size();++i) { if(nums[i] <...

0 点赞评论收藏

2023-01-20 20:55

西安电子科技大学 C++

题解 | #数组中只出现一次的两个数字#

#include <unordered_map> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型vector * @return int整型vector */ vector<int> FindNumsAppearOnce(vector<int>& array) { // write code here unordered_map<int, int> m; for(...

0 点赞评论收藏

2023-01-20 20:43

西安电子科技大学 C++

题解 | #数组中出现次数超过一半的数字#

class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { unordered_map<int,int> m; int n = numbers.size(); for(int i = 0;i<n;++i) { m[numbers[i]]++; if(m[numbers[i]] > n/2) return numbers[i]; } return -1; } }; 思路：使用哈希表

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：