1.使用字典树，前缀树 struct Trie { int sum = 0; vector<Trie*> child = {nullptr,nullptr}; Trie() = default; }; class Solution { public: void add(int num) { Trie* curr = root; for(int k = Highsize;k>=0;--k) { int bit = (num >> k) &1; if(curr->child[bit] == nullptr) curr->child[bit] = new T...

使用二分查找注意：题目是找峰值元素，不是找最大值 所以找到的波峰不一定是最大值，但它一定是一个峰的峰顶具体做法：step 1：二分查找首先从数组首尾开始，每次取中间值，直到首尾相遇。step 2：如果中间值的元素大于它右边的元素，说明往右是向下，我们不一定会遇到波峰，但是那就往左收缩区间。step 3：如果中间值小于右边的元素，说明此时往右是向上，向上一定能有波峰，那我们往右收缩区间。step 4：最后区间收尾相遇的点一定就是波峰。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param ...

1.使用二分查找 class Solution { public: bool binarySearch(vector<int> &nums,int target) { int low = 0; int high = nums.size()-1; while(low <= high) { int mid = (low + high)/2; if(nums[mid] > target) high = mid-1; else if(nums[mid] < target) low = mid+1; else return true; } return false; } b...

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型 */ int search(vector<int>& nums, int target) { // write code here int low = 0; int high = nums.size()-1; while(low <= high) { int mid = (low + high)/2; if(...

/** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @return ListNode类 */ ListNode* deleteDuplicates(ListNode* head) { // write code here if(!head || !head->next) return head; ListNode *res = new ListNode(0); res->next = h...

/** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @return ListNode类 */ ListNode* deleteDuplicates(ListNode* head) { // write code here if(!head || !head->next) return head; ListNode* pre = head; ListNode* curr = head->n...

可以将每个结点都指向其后后指针，再拼接起来，就可以实现 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ ListNode* oddEvenList(ListNode* head) { ...

1. 解法1:翻转链表，用vector存储正序和逆序的结果，看看两个vector是否相等 38ms /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 the head * @return bool布尔型 */ //反转链表 ListNode* ReverseList(ListNode* pHead) { if(!pHead) return pHead; ListNode *pre = nullptr;...

1.使用vec存储值，排序后构建新的链表 class Solution { public: /** * * @param head ListNode类 the head node * @return ListNode类 */ ListNode* sortInList(ListNode* head) { //取巧的方法 52ms /* 1.用 vector 先存储链表中各个节点的值 2.使用 sort 对 vector 进行排序 3.将 vector 中的值按顺序串联成新的链表 */ ListNode *res = new ListNode(0); ListNode *pre = res; ve...

暴力解法：将相加结果覆盖到链表head1上 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ //反转链表 ListNode* ReverseList(ListN...

        解题思路1：找到两个链表的长度差，然后将较长的链表指针先走n步，然后两个指针分别走剩余的步数，就会同时到达第一个公共结点。 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) { ListNode *p1 = pHe...

/** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @param n int整型 * @return ListNode类 */ ListNode* removeNthFromEnd(ListNode* head, int n) { // write code here ListNode *res = new ListNode(0); res->next = head; ListNode *pr...

解题思路：使用双指针具体做法：step 1：准备一个快指针，从链表头开始，在链表上先走kkk步。step 2：准备慢指针指向原始链表头，代表当前元素，则慢指针与快指针之间的距离一直都是kkk。step 3：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数kkk个元素的位置。 class Solution { public: ListNode* FindKthToTail(ListNode* pHead, int k) { // write code here ListNode *fast = pHead; ListNode *slow = pHead; for(int i = ...

1.暴力解法：找到环中的任一位置，然后遍历链表，找到第一个在环中的结点，这个结点就是入口结点 50ms class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { ListNode* fast = pHead; ListNode* slow = pHead; //如果没有环，则返回空指针 if(fast == nullptr || fast->next == nullptr) { return nullptr; } while(fast && fast->next) { //如果没有环，则返回空指针 i...