二叉树的最近公共祖先

发表于 2019-07-26

/**
 * Definition for a binary tree node.
 * struct c {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* result;
    bool isInside(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) {
            return 0;
        }
        bool left, right;
        left = isInside(root->left, p, q);
        right = isInside(root->right, p, q);
        if ((right && left) || ((root == p || root == q) && (left || right))) {
             result = root;
             return 0;
         }
         if (left || right || root == p || root == q)
             return 1;
         return 0;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        isInside(root, p, q);
        return result;
    }
};

一个进栈的所有出栈序列

发表于 2019-07-26

//给出出栈顺序  求所有进栈的序列 || 给出入栈顺序 求出栈顺序 
void print(stack<int> v) { 
	while (v.size() != 0) {
		cout<<v.top()<<" ";
		v.pop();
	}
	cout<<endl;
}
//a存放入栈序列，b模拟入栈， c存放可能的出栈的序列
void dfs(stack<int> a, stack<int> b, stack<int> c) {           
	
	if (a.size() == 0 && b.size() == 0 ) {
		print(c);	
		return;
	} 
	
	if (a.size() != 0) {		//入栈 
		int val = a.top();
		b.push(val);
		a.pop();
		dfs(a, b, c);
		b.pop();
		a.push(val);
	} 
	if (b.size() != 0) {		//出栈 
		int val = b.top();
		c.push(val);
		b.pop();
		dfs(a, b, c);
		c.pop();
		b.push(val);
	}
	
	return;
}

二叉树展开成链表

发表于 2019-07-26

给定一个二叉树，原地将它展开为链表。
例如，给定二叉树
1
/ \
2 5
/ \ \
3 4 6
展开为：
1-2-3-4-5-6

/**
 * 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:
    TreeNode* last;
    void flatten(TreeNode* root) {
        if (root == NULL) return;
        flatten(root->right);
        flatten(root->left);
        root->right = last;
        root->left = NULL;
        last = root;
    }
};

链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list

环形链表

发表于 2019-07-26

一个含有循环链表的链表怎么求它开始循环的入口？
给出一个循环链表的例子：
1->2->3->4->5->3 最后5又指向了3，也就是说3->4->5->3形成了一个环
假设非环形的长度是x, 环形的长度是y, 链表总长度是n = x + y
思路：
两个指针， fast一次走两步， slow一次走一步，总有一次他们会在环的某一个位置相遇。
于是可以列出关系表达式：
fast = 2slow (一个走一步，一个走两步，走了相同的时间)
fast = slow + ny (fast比slow多走了n圈的环)
2slow = slow + ny -> slow = ny
得出了关键的表达式： slow = ny, 假设一下slow处于环形起点的时候，n*y 圈之后还会回到起点。但是，slow是从链表的起点开始的，所以从入口要回退x步，就是fast和slow相遇的点，也就是说非环形的链表长度x 等于 fast和slow最后相遇的节点到环形入口的长度。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == NULL || fast->next == NULL) 
            return NULL; 
        fast = head;
   
        while(fast != slow) {
            fast = fast->next;
            slow = slow->next;
        } 
        return fast;
    }
};

删除链表重复元素

发表于 2019-07-26 | 更新于 2019-08-04

输入: 1->2->3->3->4->4->5
输出: 1->2->5

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* h = NULL;
        ListNode* pre = NULL;
        ListNode* cur = head;
        ListNode* r = NULL;
        while (cur != NULL) {
            if (juge(pre, cur) && juge(cur, cur->next)) {
                if (h == NULL) {
                    h = new ListNode(cur->val);
                    r = h;
                } else {
                    r->next = new ListNode(cur->val);
                    r = r->next;
                }
            }
            pre = cur;
            cur = cur->next;
        }
        return h;
    }
    bool juge(ListNode* node1, ListNode* node2) {
        if (node1 == NULL || node2 == NULL || node1->val != node2->val) {
            return true;
        }
        return false;
    }
};

k个一组翻转链表

发表于 2019-07-26

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

class Solution {
public:
    ListNode* reverse(ListNode* root) {
        ListNode* pre = NULL;
        ListNode* node = root;
        ListNode* next;
        while (node != NULL) {
            next = node->next;
            node->next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }
    
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == NULL || head->next == NULL || k == 1) return head;
        ListNode* result = new ListNode(-1);
        ListNode* r = result;
        
        while (head != NULL) {
            int i;
            ListNode* start = head;
            ListNode* next;
            for (i = 1; i < k && head != NULL; i++) head = head->next;
            if (i <= k && head == NULL) {
                r->next = start;
                break;
            } else {
                next = head->next;
                head->next = NULL;
                r->next = reverse(start);
                r = start;
                head = next;
            }
        }
        return result->next;
    }
};

LRU

发表于 2019-07-25 | 更新于 2019-08-04

class LRUCache {
public:
    list<int> link;
    map<int, int> m;
    int capacity;
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if(m.find(key) == m.end()) {
            return -1;
        } else {
            link.remove(key);
            link.push_front(key);
        }
        return m[key];
    }
    
    void put(int key, int value) {
        if (m.find(key) != m.end()) {       //已存在
            m[key] = value;
            link.remove(key);
            link.push_front(key);
        } else {                            //不存在
            if (m.size() >= capacity) {
                int keyLast = link.back();
                link.pop_back();
                m.erase(keyLast);
                
                link.push_front(key);
                m[key] = value;
            } else {
                m[key] = value;
                link.push_front(key);
            }
        }
    }
};

快速排序三数取中

发表于 2019-07-25 | 更新于 2019-07-28

给一个有序的数组，那代码的时间复杂度就是O(n^2)拉。
最好就是取一个要排序数组中所有值的中值，（很难）

class Solution {
public:

    int partition(vector<int>& nums, int left, int right) {
       
       int mid = (left + right) / 2;
        if (nums[left] > nums[right]) 
            swap(nums[left], nums[right]);
        if (nums[mid] > nums[right])
            swap(nums[mid], nums[right]);
        if (nums[mid] > nums[left])
            swap(nums[mid], nums[left]);                //把中值换到最左边
        
        int val = nums[left];   
        int i = left, j = right;                        //填坑法
        while (i < j) {
           while (i < j && nums[j] >= val) j--;
           nums[i] = nums[j]; 
           while (i < j && nums[i] <= val) i++;
            nums[j] = nums[i];
        }
        nums[i] = val; 
        return i;
    }
 
    void sort(vector<int>& nums, int left, int right) {
        if (left >= right)
            return;
        int mid = partition(nums, left, right);
        sort(nums, left, mid-1);
        sort(nums, mid + 1, right);
    }
    vector<int> sortArray(vector<int>& nums) {
        
        sort(nums, 0, nums.size()-1);
        return nums;
    }
};

没有优化的快排贴一下：

int pattern(int l,int r)
{
	int i = l,j = r;
	while(i<j)
	{
		while(i<j && a[i]<=a[j])
			j--;
		if(i<j)
			swap(a[i],a[j]);
		while(i<j && a[i]<=a[j])
			i++;
		if(i<j)
			swap(a[i],a[j]);
	}
	return i;
}

void sort(int i,int j)
{
	if(i<j)
	{
		int mid = pattern(i,j);
		sort(i,mid-1);
		sort(mid+1,j);
	}
}

冒泡优化

发表于 2019-07-17

优化1 没有进行过交换结束
优化2 通过记录最后交换的位置，及终点的位置
优化3 波浪排序+优化1+优化2

#if 0
#include<bits/stdc++.h>                       
using namespace std;                      
int a[10000];
int n;
void sort(int a[], int n) {
	bool flag = 0;
	int k = n-1;
	int last;
	for (int i = 0; i < n-1; i++) {
		flag = 0;
		for (int j = 0; j < k; j++) {
			sum++;
			if (a[j] > a[j+1]) {
				flag = 1;
				last = j;
				swap(a[j], a[j+1]);
			}
		}
		if (flag == 0) {
			break;
		}
		k = last;
	}
}
int main()
{
	while(1) {
		sum = 0;
		cin>>n;
		for (int i = 0; i < n; i++) {
			a[i] = rand() % n;
		}		
		sort(a, n);
		for(int i = 0; i < n; i++)
			 cout<<a[i]<<" "; 
	
	}
} 

#endif

#if 0                      //波浪排序 就上两种优化
#include<bits/stdc++.h>
using namespace std;
int a[100000],n;
void sort(int a[], int n) {
	int left = 0, right = n-1;
	int flag = 0;
	int last;
	while (left < right) {
		for (int i = left; i < right; i++) {
			sum++;
			if (a[i] > a[i+1]) {
				swap(a[i], a[i+1]);
				flag = 1;
				last = i;
			}
		}
		if (flag == 0) break;
		right = last;
		flag = 0;
		for (int j = last; j > left; j--) {
			sum++;
			if (a[j] < a[j-1]) {
				swap(a[j], a[j-1]);
				flag = 1;
				last = j;
			}
		}
		if (flag == 0) break;
		left = last;
	}
}
int main()
{
	while(1) {
		cin>>n;
		for (int i = 0; i < n; i++) {
			a[i] = rand() % n;
		}		
		sort(a, n);
		for(int i = 0; i < n; i++)
			 cout<<a[i]<<" "; 
	
	}
}  
#endif

链表|排序

发表于 2019-07-16 | 更新于 2019-07-18

一：归并实现
1.递归写法
2.非递归写法，数组模拟递归（STL里源码思路）
二:插入实现

归并递归写法：

class Solution {
public:
    ListNode* merge(ListNode* left, ListNode* right) {
        ListNode* result = new ListNode(-1);
        ListNode* r = result;
        while (left != NULL && right != NULL) {
            if (left->val <= right->val) {
                r->next = left;
                r = r->next;
                left = left->next;
            } else {
                r->next = right;
                r = r->next;
                right = right->next;
            }
        }
        if (left != NULL) r->next = left;
        if (right != NULL) r->next = right;
        return result->next;
    }
    ListNode* sortList(ListNode* head) {
        if (head == NULL || head ->next == NULL) return head;
        ListNode* pre = NULL;
        ListNode* fast = head, *slow = head;
        while (fast != NULL && fast->next != NULL) {
            pre = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        pre->next = NULL;
        ListNode* left = sortList(head);
        ListNode* right = sortList(slow);
        return merge(left, right);
    }
};

归并非递归写法：
第二种着实很难理解，模拟了很久。敬畏敬畏。大道至简，就是这样哇。

class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* result = new ListNode(-1);
        ListNode* r = result;
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                r->next = l1;
                r = r->next;
                l1 = l1->next;
            } else {
                r->next = l2;
                r = r->next;
                l2 = l2->next;
            }
        }
        if (l1) {
            r->next = l1;
        }
        if (l2) {
            r->next = l2;
        }
        return result->next;
    }
    ListNode* table[64] = {NULL};
    int fill = 0;
    int i = 0;
    ListNode* carry;
    ListNode* sortList(ListNode* head) {
        if  (head == NULL || head->next == NULL) return head;
        while (head != NULL) {
            ListNode* next = head->next;
            head->next = carry;
            carry = head;
            i = 0;
            while (i < fill && table[i]) {
                table[i] = merge(carry, table[i]);
                carry = NULL;
                swap(carry, table[i++]);
            }
            swap(carry, table[i]);
            if(i == fill) fill++;
            head = next;
        }   
         ListNode* result;
        for (int i = 1; i < fill; i++) {
            table[i] = merge(table[i], table[i-1]);
        }
        return table[fill-1];
    }
};

插入排序：

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* result = new ListNode(INT_MIN);
        ListNode* r = result;
        ListNode* next;
        while (head != NULL) {
            next = head->next;
            ListNode* r = result;
            while (r != NULL && r->next != NULL && r->next->val < head->val) {
                r = r->next;
            }
            head->next = r->next;
            r->next = head;
            
            head = next;
        }
        return result->next;
    }
};

Q-同學

Make a diffence

RSS

GitHub