在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
从尾到头打印链表(使用栈或者使用递归) 链表倒转 typedef struct ListNode
ListNode* reverseList1(ListNode *head) { if (head == NULL) return head; ListNode* dummy = new ListNode; dummy->data = -1; dummy->next = head; ListNode *Cur = dummy->next; ListNode *tmp = Cur->next; while (tmp != NULL) { Cur->next = tmp->next; tmp->next = dummy->next; dummy->next = tmp; tmp = Cur->next; } Cur->next = NULL; return dummy->next; }
https://blog.csdn.net/h_xy_zwb/article/details/64124271 DP:O(n^2) string longestPalindrome(string s) { int len=s.size(); vector<vector<int>> flag(len,vector<int>(len,0)); int maxres=0,idx=0; for(int i=0;i<len;i++){ for(int j=0,k=i;j<len&&k<len;j++,k++){ if(k==j) flag[j][k]=1; else if(s[k]==s[j]&&j+1==k) flag[j][k]=2; else if(s[k]==s[j]&&flag[j+1][k-1]>0) flag[j][k]=flag[j+1][k-1]+2; else flag[j][k]=0; if(flag[j][k]>maxres){ maxres=flag[j][k]; idx=j; } } } return s.substr(idx,maxres); } 一个字符串,求最长无重复子串的长度?
最长递增子序列: 思想:在求以ai为末元素的最长递增子序列时,找到所有序号在L前面且小于ai的元素aj,即j<i且aj<ai。如果这样的元素存在,那么对所有aj,都有一个以aj为末元素的最长递增子序列的长度f(j),把其中最大的f(j)选出来,那么f(i)就等于最大的f(j)加上1,即以ai为末元素的最长递增子序列,等于以使f(j)最大的那个aj为末元素的递增子序列最末再加上ai;如果这样的元素不存在,那么ai自身构成一个长度为1的以ai为末元素的递增子序列。
剑指58 .对于string类型的:使用algorithm中的reverse函数,reverse(s.begin(),s.end()); 对于用char定义的字符串:使用string.h中的strrev函数,char s[]="123456";//不能是string类型;strrev(s); 实现:设置两个指针,一头一尾,往中间移动;
一个字符串中{} [ ] ()匹配问题 bool isValid(string s) { std::stack<char> st; for(int i = 0; i < s.size(); ++i) { char ch = s.at(i); if(ch == '(' || ch == '[' || ch == '{') st.push(ch); else if(st.size() > 0 && ((ch == ')' && st.top() == '(') || (ch == ']' && st.top() == '[') || (ch == '}' && st.top() == '{'))) st.pop(); else return false; }
return st.size() == 0; }
可以用位运算实现,如果将所有所有数字相异或,则最后的结果肯定是那两个只出现一次的数字异或的结果,所以根据异或的结果1所在的最低位,把数字分成两半,每一半里都还有只出现一次的数据和成对出现的数据
int IpToInt(string s) { int ret=0; int num=0; for(int i=0;i<s.size();i++) { if(s[i]!='.') {num=num*10+(s[i]-'0');} else { cout<<num<<endl; ret=ret<<8; ret+=num; cout<<ret<<endl; num=0; } } ret=ret<<8; ret+=num; return ret; }
基于归并排序的思想统计逆序对:先把数组分割成子数组,再子数组合并的过程中统计逆序对的数目。统计逆序对时,先统计子数组内部的逆序对的数目,再统计相邻子数组的逆序对数目。
通过n与n-1相& 清楚n最右边的1; int BitCount(int n){ int c=0;//计数器 while(n){ n&=(n-1); ++c; } return c; }
Prim+ Kruskal算法 https://www.cnblogs.com/GHzz/p/9148279.html
递归
手写判断大小端的代码 https://blog.csdn.net/kit_9875507/article/details/44264663 大小端的本质就是不同的存储方式 大端模式:字数据的高字节存储在低地址中,而字数据的低字节则存放在高地址中。 小端模式:字数据的高字节存储在高地址中,而字数据的低字节则存放在低地址中。 根据这个特性,假设我们初始化了一个int变量i为0x12345678,其地址为0x100,根据定义在小端模式下
{ if(checkSystem()) printf("little endian\n"); else printf("big endian\n"); return 0; }
单链表找倒数第n个节点,说所有你能想到的方法。 方法一:遍历链表,记录链表的长度total,再次遍历链表,第total - N - 1个节点就是查找结果,需要遍历两次链表 方法二:使用两个指针,通过移动指针,遍历一次链表,p指针首先移动n-1步,然后p和q同时移动,直到p.next == null,此时q所指向的节点就是所求
怎么把一颗二叉树原地变成一个双向链表?
转换成有序双向链表:https://www.cnblogs.com/wanglei5205/p/8780086.html
怎么判断一个无符号的整数是不是2的n次方? 思路:一个整数如果是2的整数次方,那么它的二进制表示中有且只有一位是1,而其他所有位都是0。把这个整数与这个整数减去1之后进行与运算,那么这个整数当中唯一的 1会变为0,这个整数也变为0;
template <typename T> class NewStack { private : std::stack<T> stack_data; std::stack<T> stack_support; public: NewStack(); ~NewStack(); void push( T value) { stack_data.push (value); if (stack_support.size()==0 || stack_support.top()>value) stack_support.push(value); else: stack_support.push (stack_support.top()); }
void pop() { if (stack_data.size()>0 && stack_support.size()>0) { stack_data.pop; stack_support.pop; } } T min() { if (stack_data.size()>0 && stack_support.size()>0) { return stack_support.top(); } }
使用队列实现栈: class MyStack { public: MyStack() { } void push(int x) { queue<int> temp; //建立一个辅助队列 while(q.empty() == false){ //将队列q中所有元素存入辅助队列中 temp.push(q.front()); q.pop(); } q.push(x); //向队列中压入元素,放在队首 while(temp.empty() == false){ //逐个将辅助队列中的元素送回队列q中 q.push(temp.front()); temp.pop(); } }
int pop() { int a = q.front(); //将队列首元素返回 q.pop(); //删除队首 return a; }
int top() { return q.front(); //返回队首 }
bool empty() { return q.empty(); } private: queue<int> q; }; 用栈实现队列 class MyQueue { public: MyQueue() { } void push(int x) { //将元素放到栈底 stack<int> temp; while(s.empty() == false){ temp.push(s.top()); s.pop(); } s.push(x); while(temp.empty() == false){ s.push(temp.top()); temp.pop(); } } int pop() { int a = s.top(); s.pop(); return a; } int peek() { return s.top(); } bool empty() { return s.empty(); } private: stack<int> s, temp; };
实现strstr函数 给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
整数a和b,求a的b次方的最后三位数
.
https://blog.csdn.net/forlove_you/article/details/51248978
遍历删除,考虑迭代器失效问题
{ if(iter指向的元素是奇数) mapTest.erase(iter); } //错误,erase会让迭代器会失效!
{ if(iter指向的元素是奇数) mapTest.erase(iter++);//正确,iter值传递之后,再++; }
{ if(iter指向的元素是奇数) }
翻转数组和恢复翻转数组 找分界点:找分界点可以用一个指针来,遍历找到第一个下降的点,如果没有找到,说明数组已经是排好的。
二分法: 普通 int binary_search(int*arr,int l,int h,int key){ while (l <= h){ int m = l + (h - l) / 2; if (arr[m] == key) return m; else if (arr[m] > key) h = m - 1; else l = m + 1; } return -1; } lower_bound int binary_search(int*arr, int l, int h, int key){//找到第一个插入的位置 while (l <h){ int m = l + (h - l) / 2; if (arr[m] >= key) return h=m; else l = m + 1; } }
排序 插入排序 void insert_sort(int* arr, int l, int h) { for (int i = l + 1; i <= h; ++i) for (int j = i; j > 0; --j){ if (arr[j] < arr[j - 1]){ iter_swap(&arr[j], &arr[j-1]); } } }
快速排序 int partition(int* arry, int l, int h){ int pivot = arry[h]; while (true){ while (arry[l] < pivot) ++l; while (arry[h] > pivot) --h; if (!(l < h)) return l; iter_swap(&arry[l], &arry[h]); ++l; --h; } } void quick_sort(int* arr, int l, int h) { if (l >= h) return; int m = partition(arr, l, h); quick_sort(arr, l, m-1); quick_sort(arr, m , h); } 堆排序 void percDown(int* arr, int l, int h, int k) { int child, tmp; for (tmp = arr[k]; (k - l) * 2 + l + 1 <= h; k = child) { child = (k - l) * 2 + l + 1; if (child + 1 <= h && arr[child] < arr[child + 1]) ++child; if (arr[child] > tmp) arr[k] = arr[child]; else break; } arr[k] = tmp; }
void heap_sort(int* arr, int l, int h) { for (int i = l + (h - l) / 2; i >= l; --i) { percDown(arr, l, h, i); } for (int i = h; i >= l; --i) { int tmp = arr[l]; arr[l] = arr[i]; arr[i] = tmp; percDown(arr, l, i - 1, l); } }
归并排序 void merge_sort(int* arr, int l, int h) { if (l == h) return; int m = l + (h - l) / 2; merge_sort(arr, l, m); merge_sort(arr, m + 1, h); int * tmp = new int[h - l + 1]; int i = l, j = m + 1, k = 0; while (i <= m && j <= h) { if (arr[i] <= arr[j]) tmp[k++] = arr[i++]; else tmp[k++] = arr[j++]; } while (i <= m) tmp[k++] = arr[i++]; while (j <= h) tmp[k++] = arr[j++]; for (int i = l; i <= h; ++i) { arr[i] = tmp[i - l]; } delete []tmp; } 冒泡排序 void bubble_sort(int* arr, int l, int h) { for (int i = l; i <= h; ++i) { for (int j = l; j <= h - i + l - 1; ++j) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } } 选择排序 void select_sort(int* arr, int l, int h) { for (int i = l; i <= h; ++i) { int id = i; for (int j = i + 1; j <= h; ++j) { if (arr[j] < arr[id]) { id = j; } } int tmp = arr[i]; arr[i] = arr[id]; arr[id] = tmp; } }
手写String class String{ public: String(const char *str = NULL); //普通构造函数 String(const String &other); //拷贝构造函数 String & operator=(String &other) ; //赋值函数 ~String(void); //析构函数 private: char* m_str; }; //普通构造函数 String::String(const char* str){ if(str==NULL) //如果str为NULL,存空字符串{ m_str = new char[1]; //分配一个字节 *m_str = ‘\0′; //赋一个’\0′ }else{ str = new char[strlen(str) + 1];//分配空间容纳str内容 strcpy(m_str, str); //复制str到私有成员m_str中 } } //析构函数 String::~String(){ if(m_str!=NULL) //如果m_str不为NULL,释放堆内存{ delete [] m_str; m_str = NULL; } } //拷贝构造函数 String::String(const String &other){ m_str = new char[strlen(other.m_str)+1]; //分配空间容纳str内容 strcpy(m_str, other.m_str); //复制other.m_str到私有成员m_str中 } //赋值运算符函数 String & String::operator=(String &other){ if(this == &other) //若对象与other是同一个对象,直接返回本{ return *this } delete [] m_str; //否则,先释放当前对象堆内存 m_str = new char[strlen(other.m_str)+1]; //分配空间容纳str内容 strcpy(m_str, other.m_str); //复制other.m_str到私有成员m_str中 return *this; } memcpy函数的实现 void *memcpy(void *dest, const void *src, size_t count) { char *tmp = dest; const char *s = src;
while (count--) *tmp++ = *s++; return dest; } strcpy函数的实现 char *strcpy(char *dst,const char *src) { assert(dst != NULL && src != NULL); char *ret = dst; while((* dst++ = * src++) != '\0') ; return ret; }
BST的第K小的节点
http://www.cnblogs.com/grandyang/p/4620012.html
判断链表是否有环,如果有,返回环的入口节点;求环的长度 思路:采用两个指针walker和runner,walker每次移动一步而runner每次移动两步。当walker和runner第一次相遇时,证明链表有环 ;然后采用两个指针,一个从表头出发,一个从相遇点出发,一次都只移动一步,当二者相等时便是环入口的位置; ListNode *detectCycle(ListNode *head) { auto walker = head; auto runner = head; while(runner && runner->next)//设置快慢指针,并找到相遇点 { walker = walker->next; runner = runner->next->next; if(walker == runner) break; } if(!runner || !runner->next) //单链表无环 return nullptr; auto headWalker = head;//从头节点出发 auto crossWalker = walker; //从相遇点出发 while(headWalker != crossWalker) { headWalker = headWalker->next; crossWalker = crossWalker->next; } return headWalker; //环的入口点 }
基于归并排序的思想统计逆序对:先把数组分割成子数组,再子数组合并的过程中统计逆序对的数目。统计逆序对时,先统计子数组内部的逆序对的数目,再统计相邻子数组的逆序对数目。
翻转数组和恢复翻转数组 找分界点:找分界点可以用一个指针来,遍历找到第一个下降的点,如果没有找到,说明数组已经是排好的。
给定链表头指针,中间结点的指针,如何删除单链表中间节点 快慢指针找中间值, https://blog.csdn.net/cherrybomb1111/article/details/79803972
判断两个单链表是否相交,相交则找出两个链表的第一个公共子节点 思路1:分别遍历两个链表,得到分别对应的长度。然后求长度的差值,把较长的那个链表向后移动这个差值的个数,然后一一比较即可。 思路2:让两个指针分别从两条链表的开头开始往后遍历,当其中一条遍历到末尾时,我们将其跳到另一个条链表的开头继续遍历,一直遍历到两个指针相等为止。相等只有两种情况,一种情况是在交点处相遇,另一种情况是在各自的末尾的空节点处相等。, 为什么一定会相等呢,因为两个指针走过的路程相同,是两个链表的长度之和,所以一定会相等。 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (!headA || !headB) return NULL; ListNode *a = headA, *b = headB; while (a != b) { a = a ? a->next : headB; b = b ? b->next : headA; } return a; }
r行c列的0,1数组,找到最大的全为1的正方形? https://blog.csdn.net/nk_test/article/details/48901853
二叉树两个节点的最近公共祖先,没答出来 https://www.cnblogs.com/grandyang/p/4641968.html
去掉字符串中的空格字符 https://blog.csdn.net/qian2213762498/article/details/81705647 void trim(string &s) { int index = 0; if( !s.empty()) { while( (index = s.find(' ',index)) != string::npos) { s.erase(index,1); } } }
删除字符串开始和结尾处的空格,并将中间的多个连续的空格合并成一个。 void FormatString(char str[], int len) { if(str == NULL || len <= 0) return; int i = 0, j = 0; while(str[i] == ' ')//开头的空格 i++; while(str[i] != '\0') { if(str[i] == ' ' && (str[i+1] == ' ' || str[i+1] == '\0')) { //中间或者结尾的空格 i++; continue; } str[j++] = str[i++]; } str[j] = '\0'; }
char *s1, const char *s2,删除s1中s2出现过的字符 思路:用一个256大小的数组,每个表示字符的状态,把s2读一遍,把每个字母对应的数字变为1表示存在,然后遍历s1,把状态为1的删掉 https://blog.csdn.net/m0_38099899/article/details/81231886
单链表判环 设两个指针,一个每次走一步的慢指针和一个每次走两步的快指针,如果链表里有环的话,两个指针最终肯定会相遇。 是不是:bool hasCycle(ListNode *head) { ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) return true; } return false; } 找环入口:ListNode *detectCycle(ListNode *head) { ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) break; } if (!fast || !fast->next) return NULL; slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return fast; }
判断一个数是不是回文数 bool isPalindrome(int x) { if (x < 0 || (x % 10 == 0 && x != 0)) return false; int revertNum = 0; while (x > revertNum) { revertNum = revertNum * 10 + x % 10; x /= 10; } return x == revertNum || x == revertNum / 10; }
http://www.cnblogs.com/grandyang/p/4125510.html
求一个集合的所有子集,递归实现,非递归实现 http://www.cnblogs.com/grandyang/p/4309345.html
vector<vector<int> > subsets(vector<int> &S) { vector<vector<int> > res(1); sort(S.begin(), S.end()); for (int i = 0; i < S.size(); ++i) { int size = res.size(); for (int j = 0; j < size; ++j) { res.push_back(res[j]); res.back().push_back(S[i]); } } return res; }
旋转有序数组的二分查找 http://www.cnblogs.com/grandyang/p/4325648.html 无重复数字:int search(vector<int>gt;& nums, int target) { int left = 0, right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; else if (nums[mid] < nums[right]) { if (nums[mid] < target && nums[right] >= target) left = mid + 1; else right = mid - 1; } else { if (nums[left] <= target && nums[mid] > target) right = mid - 1; else left = mid + 1; } } return -1; } 有重复数字:http://www.cnblogs.com/grandyang/p/4325840.html bool search(int A[], int n, int target) { if (n == 0) return false; int left = 0, right = n - 1; while (left <= right) { int mid = (left + right) / 2; if (A[mid] == target) return true; else if (A[mid] < A[right]) { if (A[mid] < target && A[right] >= target) left = mid + 1; else right = mid - 1; } else if (A[mid] > A[right]){ if (A[left] <= target && A[mid] > target) right = mid - 1; else left = mid + 1; } else --right; } return false; }
删除数组中的重复元素
有序数组中去除重复项 http://www.cnblogs.com/grandyang/p/4329128.html int removeDuplicates(vector<int>& nums) { if (nums.empty()) return 0; int j = 0, n = nums.size(); for (int i = 0; i < n; ++i) { if (nums[i] != nums[j]) nums[++j] = nums[i]; } return j + 1; }
实现一个计算器计算简单的表达式字符串 +-: http://www.cnblogs.com/grandyang/p/4570699.html +-*/: http://www.cnblogs.com/grandyang/p/4601208.html +-*/(): http://www.cnblogs.com/grandyang/p/8873471.html
memcopy和memove的区别?memcopy和memove的实现? https://blog.csdn.net/li_ning_/article/details/51418400 都是拷贝一定长度的内存的内容,区别是当内存发生局部重叠的时候,memmove保证拷贝的结果是正确的,memcpy不保证拷贝的结果的正确。
memcpy函数的实现 void *memcpy(void *dest, const void *src, size_t count) { char *tmp = dest; const char *s = src;
while (count--) *tmp++ = *s++; return dest; }
给定一个二叉树,节点值为0-9,从根节点到叶子结点组成一个数,求二叉树所有组成的数的和 https://blog.csdn.net/i_am_bird/article/details/78173454
Rand()的范围是多少,要是生成大于范围的的随机数怎么实现 srand(time(0)); rand(); 0~32767
写一个二叉树翻转,然后写个测试(为了写这个测试我还白送一个二叉树层次遍历emmm) https://blog.csdn.net/qq_29762941/article/details/80909342 测试:反转两次,再和原来的二叉树比较是否相同
手写堆排序,然后分析下建堆时间复杂度(从n/2开始向上建堆的话是O(n)) https://blog.csdn.net/yuzhihui_no1/article/details/44258297
strcpy安全性,如何实现安全,strnpy,写一下并测试, https://blog.csdn.net/ZH___xin/article/details/51985562
写sql语句(A表存储有每个电话号码当月通话记录,表B是电话号码集合,求表B每个号码通话次数),大概就是比较简单的连表查询,加count select B.telno, count(B.telno) from A right join B where A.telno = B.telno group by B.telno
假设上面题中A B两个表存在文件,怎么编程统计? 我答的使用hashmap存储电话和次数,时间复杂度呢? 只需要扫描两个文件各一遍O(n+m)
两字符串最长公共子串, 最长公共子序列 https://blog.csdn.net/u012426298/article/details/82796660 打印二叉树每层最右边的节点 层序遍历 LeetCode 199 http://www.cnblogs.com/grandyang/p/4392254.html
手写代码 回形矩阵 http://www.cnblogs.com/grandyang/p/4362675.html 判断在一个矩阵中是否存在一条包含某字符串所有字符的路径 https://blog.csdn.net/qq_21997625/article/details/84640353
3sum 数组中三数之和为0的所有三元组 leetcode 15
微信的附近的人这个功能,如果让你实现,你准备怎么做, 地理位置网格分块,存块ID,然后四叉搜索。你的经纬度换算成网格ID,同网格的人撸出来,临近网格的人撸出来,搞定。把地理位置分块,怎么把经纬度转化成网格 ID 呢。本质上就是hash 客户端固定时间发送经纬度(x,y)到服务器s,服务器存储每个登陆的用户的经纬度到表t中,表t按照经纬度分表,将地图分成一个个的小格子。当用户点击“附近的人”时,对用户(x,y)进行计算,最多一次查询其中的4个格子(子表),计算两点间距离获取结果(有点像桶排序)。性能上可以将表t替换为内存结构,容灾即可。 MongoDB的LBS功能实现附近的人
https://www.nowcoder.com/discuss/165952?type=0&order=0&pos=414&page=1 微信小程序团队一共有 n 名成员,决定出去秋游,在海边遇到出租摩托艇的杰克马,马先生手上有 m 辆待出租的摩托艇,价格分别是 b1 、b2 ... bm; 由于习惯了微信支付,团队中每个人身上的现金都有限,分别是 a1 a2 ... an,对了,一起出门的老板还带有 S 元的团队经费,这个经费是每个人都可以使用的 那么考虑以下两个场景 场景1 团队成员都很有爱,都愿意借钱给其他同事,那么这时候团队最多能租到多少摩托艇 //贪心法;把所有的钱收集起来,按摩托艇的价格从低到高租借摩托艇
场景2 团队成员都十分小气,是不愿意借钱给别人的,那么请考虑以下两个问题 //问题一 老板是否能想到一个策略,使得所有人都能租到摩托艇? //贪心法;钱少的人租借便宜的摩托艇,补贴 public static boolean isAll(int[] n, int[] m, int S){ if (n.length > m.length) { return false; } Arrays.sort(n); Arrays.sort(m); for (int i=0; i<n.length; i++) { int need = n[i] - m[i]; if (need < 0) S += need; } return S >= 0; } //问题二 请问给出一个策略 // - 使得整个团队租到最多的摩托艇 // - 在租到最多摩托艇的情况下,整体的支出尽量的少 //二分法+贪心 private static int n[]; private static int m[]; private static int S; public static int[] isAll(int[] n, int[] m, int S){ Arrays.sort(n); Arrays.sort(m); Main.n = n; Main.m = m; Main.S = S; int l =0, r = m.length; //摩托艇的数量 while (l < r) { int mid = l + r + 1 >> 1; if (can(mid)) { l = mid; } else { r = mid - 1; } } int ans = 0; for (int i=0; i<l; i++) { ans += m[i]; } return new int[] {l, ans}; }
private static boolean can(int count) { int tmpS = S; for (int i = count-1,j = n.length-1; i>=0; i--, j--) {//让最多钱的人买最贵的摩托艇 if (n[j] < m[i]) { tmpS -= (m[i] - n[j]); } if (tmpS < 0) { return false; } } return true; } 判断一个字符串是不是两个有序的字符串交错组成的。 Leetcode 97 编程题:递增数组中找两个数和为某个固定值。设计测试用例 Leetcode 1 给你一个数组和数组元素的个数,求平均值。 int avg(int x, int y) { return (x & y) + ((x ^ y) >> 1); } 两个非常大的数相加 Leetcode 415 |
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论