锐客网

  1. 首页 > 睿知 > it技术 > >

刷题|手撕代码+++！！！

链表二叉树刷题


手撕

  • 数组
    • 1. 两数之和
    • 2. 第k大
    • 3. 出现次数topk
    • 4. 合并两有序数组
    • 5. 移除元素
    • 6. 数组的交集
    • 7. 旋转数组的最小数字
    • 8.变态跳台阶
    • 9. 二进制1的个数
    • 10. 三数之和为0
    • 11. 前K大
  • 链表
    • 1. 反转链表
    • 2. 删除倒数第k个结点
    • 3. 合并两个有序链表
    • 4. 旋转链表
    • 5. 移除链表元素
  • 字符串
    • 1. 有效括号
    • 2. 字符串相加
    • 3.只反转单词
    • 4. 倒置字符串
    • 5.替换空格
    • 6. 最长不重复子串
  • 二叉树
    • 1. 二叉树的中序遍历
    • 2. 平衡二叉树
    • 3. 重建二叉树
  • 两个栈实现队列
【刷题|手撕代码+++！！！】
数组 1. 两数之和
class Solution { public: vector twoSum(vector& nums, int target) { //建立一个unordred_map,key是nums[i],value 是i //遍历表，找到target-nums[i]，并且不是自身。 unordered_map hashtable; for(int i = 0; i < nums.size(); i++) { hashtable[nums[i]] = i; } for(int i = 0; i < nums.size(); i++) { if(hashtable.find(target-nums[i]) != hashtable.end() && hashtable[target - nums[i]] != i) { return {i, hashtable[target - nums[i]]}; } } return {}; } };

2. 第k大
class Finder { public: int findKth(vector a, int n, int K) { // write code here //快排+二分，递归调用 QuickSort(a, n , K , 0, n-1); }int QuickSort(vector& a, int n, int K, int start, int end) { int base = a[start]; int i = start; int j = end; int res = 0; while(i < j) { while(i < j && a[j] >= base) { j--; } while(i < j && a[i] <= base) { i++; } if(i < j) { swap(a[i],a[j]); } } swap(a[start],a[j]); if(n - j == K) {return a[j]; }else if(n - j > K) {res=QuickSort(a,n,K,j + 1, end); } else if(n - j < K) {res =QuickSort(a,n,K,start,j-1); } return res; } }; int main() { int a[5] = { 1,2,7,8,5 }; int k = 3; quickFindMaxK(a, 0, 4, k); for (int i = 0; i < k; i++) cout << a[i] << " "; cout << endl; }

3. 出现次数topk
：建立一个小顶堆，然后遍历「出现次数数组」： 如果堆的元素个数小于 kk，就可以直接插入堆中。 如果堆的元素个数等于 kk，则检查堆顶与当前出现次数的大小。如果堆顶更大，说明至少有 kk 个数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中。 遍历完成后，堆中的元素就代表了「出现次数数组」中前 kk 大的值class Solution { public: static bool cmp(pair& m, pair& n) { return m.second > n.second; }vector topKFrequent(vector& nums, int k) { unordered_map occurrences; for (auto& v : nums) { occurrences[v]++; }// pair 的第一个元素代表数组的值，第二个元素代表了该值出现的次数 priority_queue, vector>, decltype(&cmp)> q(cmp); for (auto& [num, count] : occurrences) { if (q.size() == k) { if (q.top().second < count) { q.pop(); q.emplace(num, count); } } else { q.emplace(num, count); } } vector ret; while (!q.empty()) { ret.emplace_back(q.top().first); q.pop(); } return ret; } };

4. 合并两有序数组
class Solution { public: void merge(vector& nums1, int m, vector& nums2, int n) { //1. 扩大数组为m+n，指针p从后往前遍历 //2. 分别从后往前遍历俩数组，大的替换p //3. 循环条件，p>= 0; int p = m + n -1; int p1 = m -1; int p2 = n -1; while(p >= 0) { if(p1 < 0) { nums1[p] = nums2[p2]; p2--; } else if(p2 <0) { nums1[p] == nums1[p1]; p1--; } else if(nums1[p1] <= nums2[p2]) { nums1[p] = nums2[p2]; p2--; } else { nums1[p] = nums1[p1]; p1--; } p--; } } };

5. 移除元素
class Solution { public: int removeElement(vector& nums, int val) { if(nums.size()==0) { return 0; } int right = nums.size() - 1; for(int i = 0; i <= right; i++) { while(right >= 0 && nums[right] == val) { right--; } if(nums[i] == val && i < right) { nums[i] = nums[right]; nums[right] = val; }} return right + 1; } };

6. 数组的交集
class Solution { public: vector intersection(vector& nums1, vector& nums2) { map m; vector v; for(auto e : nums2) { m[e]++; }for(auto e : nums1) { if(m[e] > 0) { m[e] = 0; v.push_back(e); } } return v; } };

7. 旋转数组的最小数字
class Solution { public: int minNumberInRotateArray(vector rotateArray) { if(rotateArray.size() == 0) { return 0; } int first = 0, last = rotateArray.size() - 1; while(first < last) { int mid = first + ((last - first)>>1); if(rotateArray[first] < rotateArray[last]) { return rotateArray[first]; } else{ if(rotateArray[mid] > rotateArray[last]) { first = mid + 1; }else{ if(rotateArray[mid] <= rotateArray[last]) { last = mid; }} } } return rotateArray[first]; } };

8.变态跳台阶
class Solution { public: int jumpFloorII(int number) { if(number == 0 || number == 1) return number; int a = 1,b; for(int i = 2; i <= number; i++) { b = a << 1; a = b; } return b; } };

9. 二进制1的个数
class Solution { public: intNumberOf1(int n) { int count = 0; while(n!= 0) { count++; n = n & (n-1); } return count; }};

10. 三数之和为0
#include #include #include using namespace std; class Solution { public: vector > threeSum(vector &num) { vector tmp(3); vector > rs; sort(num.begin(), num.end()); for (int i = 0; i < num.size(); i++) { for (int j = i+1, k = num.size()-1; j < k; ) { if (num[i]+num[j]+num[k] < 0) j++; else if (num[i]+num[j]+num[k] >0) k--; else { tmp[0] = num[i]; tmp[1] = num[j]; tmp[2] = num[k]; rs.push_back(tmp); j++, k--; while (j > vt; int a[] = {-2,13,-5,-4,-7,8,0,-9,6,7,0,-4,2,1,-2,4}; int len = sizeof(a)/sizeof(int); vector t(a, a+len); Solution solu; vt = solu.threeSum(t); for (auto x:vt) { cout<<"("; for (auto y:x) cout<

11. 前K大
#include #include #define N 100010 using namespace std; void swap(int &a, int &b) { int temp = a; a = b; b = temp; } void quicksort(int a[], int s, int e, int k) { // s 是数组的开始，e是数组的最后一个元素，k要求的前k个最大值 int m = a[s]; if (s >= e) return; int i = s, j = e; while (i != j) { while (j > i&&a[j] >= m) { j--; } swap(a[i], a[j]); while (j > i&&a[i] <= m) { i++; } swap(a[i], a[j]); } //quicksort(a, s, i - 1); //quicksort(a, i + 1, e); if ((e - j) == k) { // 如果已经有k个数在key的右边，则目标完成 return; } else if ((e - j) > k) { // 对右边的从j到e的数进行操作 quicksort(a, j, e, k); } else { // 对从s到j的数 quicksort(a, s, j, e - j - k); } } int main() { int n, k; int a[N]; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); scanf("%d", &k); quicksort(a, 0, n - 1, k); sort(a+n-k, a + n); for (int i = n-1; i >= n-k; i--) { printf("%d\n", a[i]); } return 0; }

链表 1. 反转链表
/** * Definition for singly-linked list. * struct ListNode { *int val; *ListNode *next; *ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *cur = NULL; ListNode *pre = head; while(pre != NULL) { ListNode *t = pre -> next; pre -> next = cur; cur = pre; pre = t; } return cur; } };

2. 删除倒数第k个结点
/** * Definition for singly-linked list. * struct ListNode { *int val; *ListNode *next; *ListNode() : val(0), next(nullptr) {} *ListNode(int x) : val(x), next(nullptr) {} *ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { //新建一个前继结点； //快指针先走n步，再同时走，直到末尾-》next不为空，可以定位到删除元素的前一个结点 ListNode*dummy = new ListNode(0); dummy -> next = head; ListNode* fast = dummy, *slow = dummy; while(n--) { if(fast!= nullptr) { fast = fast -> next; }} while(fast->next != nullptr) { fast = fast -> next; slow = slow -> next; } slow -> next = slow -> next -> next; return dummy-> next; } };

3. 合并两个有序链表
/** * Definition for singly-linked list. * struct ListNode { *int val; *ListNode *next; *ListNode() : val(0), next(nullptr) {} *ListNode(int x) : val(x), next(nullptr) {} *ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { //迭代方式； //1. 新建一个链表头，初始化一个哨兵结点。 //2. 循环条件：两个链表都不为空； 比较两个链表结点大小，将小的结点链接在新节点后。 //3. 当一个链表为空时，将剩余链表结点链接。 ListNode* head = new ListNode(-1); ListNode* prev = head; while(l1 != nullptr && l2 != nullptr) { if(l1 -> val <= l2 -> val) { prev -> next = l1; l1 = l1 -> next; } else { prev -> next = l2; l2= l2 -> next; } prev = prev-> next; } if(l1 == nullptr) prev -> next = l2; else if(l2 == nullptr) prev -> next = l1; return head -> next; } };

4. 旋转链表
/** * Definition for singly-linked list. * struct ListNode { *int val; *ListNode *next; *ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* rotateRight(ListNode* head, int k) { if(head == NULL) {return NULL; } ListNode* left = head, *right = head; int n = 0; ListNode* p = head; while(p) { p = p -> next; n++; } k %= n; while(k--) { if(right != NULL) { right = right -> next; }} while(right->next != NULL) { right = right -> next; left = left -> next; } right -> next = head; head = left -> next; left -> next = NULL; return head; } };

5. 移除链表元素
/** * Definition for singly-linked list. * struct ListNode { *int val; *ListNode *next; *ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode *dummy = new ListNode(0); dummy->next = head; ListNode *pre = dummy, *cur = head; while(cur != NULL) { if(cur -> val == val) { pre -> next = cur -> next; cur = cur -> next; }else { cur = cur -> next; pre = pre -> next; } } return dummy -> next; } };

字符串 1. 有效括号
class Solution { public: bool isValid(string s) { stack st; for(int i = 0; i < s.size(); i++) { switch(s[i]) { case '(': st.push('('); break; case '[': st.push('['); break; case '{': st.push('{'); break; case ')': if(st.empty()) return false; else if(st.top() == '(') { st.pop(); } else{return false; } break; case ']': if(st.empty()) return false; else if(st.top() == '[') { st.pop(); } else{return false; } break; case '}': if(st.empty()) return false; else if(st.top() == '{') { st.pop(); } else{return false; } break; } } if(st.empty()) return true; else return false; } };

2. 字符串相加
class Solution { public: string addStrings(string num1, string num2) { int str1 = num1.size() -1; int str2 = num2.size() -1; string ans; int result = 0, add = 0; int x = 0, y = 0; while(str1 >= 0 || str2 >= 0 || add != 0) { if(str1 >= 0) { x = num1[str1] - '0'; } else{ x = 0; } if(str2 >= 0) { y = num2[str2] - '0'; } else{ y = 0; } result = x + y + add; ans.push_back('0' + result % 10); add = result / 10; str1--; str2--; } reverse(ans.begin(), ans.end()); return ans; } };

3.只反转单词
class Solution { public: string reverseWords(string s) { if(s.size() == 0) { return s; } int n = s.size(); int front = 0; int back = 0; for(int i = 0; i < n - 1; i++) { if(s[back] != ' ') { back++; } else { reverse(s.begin() + front, s.begin() + back); front = back + 1; back = front; } } back++; reverse(s.begin() + front, s.begin() + back); return s; } };

4. 倒置字符串
#include #include #include using namespace std; int main() { string s; getline(cin,s); reverse(s.begin(),s.end()); int len = s.size(); int front = 0, back = 0; for(int i =0; i < len - 1; i++) { if(s[i] != ' ') { back++; } else{ reverse(s.begin()+front,s.begin()+back); front = back + 1; back = front; }} back++; reverse(s.begin()+front,s.begin()+back); cout<<

5.替换空格
class Solution { public: void replaceSpace(char *str,int length) { if(str == nullptr || length < 0) { return; } int count = 0; for(int i = 0; i < length; i++) { if(str[i] == ' ') { count++; } } if(count == 0) { return; } int new_length = length + count*2; for(int i = length; i >= 0; i--) { if(str[i] != ' ') { str[new_length] = str[i]; new_length--; }else{ str[new_length--] = '0'; str[new_length--] = '2'; str[new_length--] = '%'; }} } };

6. 最长不重复子串
class Solution { public: int lengthOfLongestSubstring(string s) { //滑动窗口思想 //哈希表存放字符出现的次数， //左右双指针，右指针增加找到符合不重复字符的窗口，左指针增加改变窗口大小来回 //循环条件：出现重复元素 unordered_map window; int left = 0, right = 0; int res = 0; int n = s.size(); while(right < n) { char c1 = s[right]; window[c1]++; right++; while(window[c1] > 1) { char c2 = s[left]; window[c2]--; left++; } res = max(res,right - left); }return res; } };

二叉树 1. 二叉树的中序遍历
/** * 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: vector inorderTraversal(TreeNode* root) { stack s; vector v; TreeNode* rt = root; while(rt || s.size()) { while(rt) { s.push(rt); rt = rt -> left; } rt = s.top(); s.pop(); v.push_back(rt -> val); rt = rt -> right; } return v; } };

2. 平衡二叉树
/** * 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: int height(TreeNode* root) { if(root == NULL) { return 0; } else return max(height(root -> right), height(root -> left)) + 1; } bool isBalanced(TreeNode* root) { if(root == NULL) { return true; } else { return abs(height(root -> right) - height(root -> left)) <= 1 && isBalanced(root -> left) && isBalanced(root -> right); } } };

3. 重建二叉树
/** * Definition for binary tree * struct TreeNode { *int val; *TreeNode *left; *TreeNode *right; *TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* reConstructBinaryTree(vector pre,vector vin) { if(pre.size() == 0 || vin.size() == 0) { return NULL; } TreeNode* head = new TreeNode(pre[0]); vector pre_left, pre_right, vin_left, vin_right; int vinlen = vin.size(); int temp = 0; for(int i = 0; i < vinlen; i++) { if(vin[i] == pre[0]) { temp = i; break; } } for(int i = 0; i < temp ; i++) { pre_left.push_back(pre[i+1]); vin_left.push_back(vin[i]); } for(int i = temp+1; i < vinlen; i++) { pre_right.push_back(pre[i]); vin_right.push_back(vin[i]); } head ->left = reConstructBinaryTree(pre_left, vin_left); head ->right = reConstructBinaryTree(pre_right, vin_right); return head; } };

两个栈实现队列
class Solution { public: void push(int node) { stack1.push(node); }int pop() { if(stack2.empty()) { while(!stack1.empty()) { stack2.push(stack1.top()); stack1.pop(); } } int ret = stack2.top(); stack2.pop(); return ret; }private: stack stack1; stack stack2; };

    推荐阅读


    上一篇：烧脑算法|手撕六大经典排序算法（Java代码实现）

    下一篇：java核心技术|面试手撕代码总结（一）-排序篇