qiaoxu123’s gists

qiaoxu123 / dsmp_rx.c

Created December 17, 2018 02:29

	#include <stdio.h>
	#include <string.h>
	#include <stdlib.h>
	#include <unistd.h>
	#include <arpa/inet.h>
	#include <sys/socket.h>
	#include <linux/socket.h>

	#define ETH_P_WSMP 0x88DC

qiaoxu123 / test1.cpp

Created December 22, 2018 02:44

https://leetcode.com/problems/pascals-triangle/ 第一种写法：使用两种for循环，使得当前行中的值是上一行的两个数之和

	//复杂度比较高的写法
	//原创+参考

	class Solution {
	public:
	vector<vector<int>> generate(int numRows) {
	vector<vector<int>> array(numRows);

	for(int i = 0;i < numRows;++i){ //第几行
	array[i].resize(i+1);

qiaoxu123 / test1.cpp

Created December 23, 2018 01:18

考察二叉树的遍历，使用递归形式实现。自己写的基本和最优相同，只不过有些语句没有优化。test1.cpp为自己的，test2.cpp为参考改进过得

	/**
	* 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 {

qiaoxu123 / test1.cpp

Created December 24, 2018 02:15

思路自己能整理出来，但实现方式上存在一些问题。一种是使用自己写的交换程序，另一种是使用std::swap，两者还是存在很多不同。另外还有一种使用非递归进行实现

	/**
	* 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 {

qiaoxu123 / test1.cpp

Last active December 28, 2018 01:16

- 第一种方法：使用额外空间实现，hash表记录遍历过的值，从而找到（暴力解法，复杂度高，用时长） > Runtime: 124 ms, faster than 45.37% --- - 第二种方法：使用set数组实现，用count计数来找出现次数为0的数 > Runtime: 200 ms, faster than 6.42% --- - 第三种方法：参考[Discuss](https://leetcode.com/problems/find-all-numbers-disappeared-

	class Solution {
	public:
	vector<int> findDisappearedNumbers(vector<int>& nums) {
	vector<int> array;
	vector<int> hash;
	hash.resize(nums.size()+1);

	for(int i = 0;i < nums.size();++i)
	hash[nums[i]]++;
	for(int i = 1;i <= nums.size();++i)

qiaoxu123 / test1.cpp

Last active December 26, 2018 01:09

失败。。 - [参考地址1](https://leetcode.com/problems/min-cost-climbing-stairs/discuss/110111/Easy-to-understand-C%2B%2B-using-DP-with-detailed-explanation) - [参考地址2](https://leetcode.com/problems/min-cost-climbing-stairs/discuss/160791/4ms-c%2B%2B-simple-ap

	//测试性能：Runtime: 12 ms, faster than 26.44%

	class Solution {
	public:
	int minCostClimbingStairs(vector<int>& cost) {
	int n=(int)cost.size();
	vector<int> dp(n);
	dp[0]=cost[0];
	dp[1]=cost[1];
	for (int i=2; i<n; ++i)

qiaoxu123 / bit.cpp

Last active December 30, 2018 01:53

思路是有的，但实在搞不清楚自己到底是哪错了? 另外，参考大神的代码，7种解决方法，厉害！[参考地址](https://leetcode.com/problems/majority-element/discuss/51612/6-Suggested-Solutions-in-C%2B%2B-with-Explanations) 其中，Moore解法可以参考这篇[博客](https://blog.csdn.net/chfe007/article/details/42919017) 对于后面几种解

	//真的是很新奇的方法，使用位运算来进行求解
	//Runtime: 24 ms, faster than 30.40%

	class Solution {
	public:
	int majorityElement(vector<int>& nums) {
	int major = 0,n = nums.size();
	for(int i = 0,mask = 1;i < 32;i++,mask <<= 1){
	int bitCounts = 0;
	for(int j = 0;j < n;j++){

qiaoxu123 / first.cpp

Created December 29, 2018 01:11

没有解决，参考solution解决。本质仍然是Binary Tree 的遍历问题

	//效率不算高
	//Runtime: 8 ms, faster than 55.20%

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

qiaoxu123 / Fib.cpp

Last active December 29, 2018 02:56

对问题进行分析，发现解决方案的次数满足斐波那契数列的规律，于是采用该方法实现。 - 可以分别使用递归方式和数组方式实现 > 对LeetCode的OJ有点失望了，第一次效率4ms,第二次直接变为0ms。。

	//使用Fibonacci sequence方法实现
	//效率总体来说还是挺高的
	//Runtime: 0 ms, faster than 100.00%
	class Solution {
	public:
	int climbStairs(int n) {
	int Fib[n] = {0};
	Fib[0] = Fib[1] = 1;
	// if(n <= 2)
	// return n;

qiaoxu123 / pair.cpp

Last active December 31, 2018 07:02

- 第一种解法：比较作弊，直接使用STL中的stack实现； - 第二种解法：使用vector数组实心，应该是比较理想的实现方法。 > 两种解法都需要一个额外的空间来实现最小元素的比较存放。 - 第三种解法：比较特别，使用pair实现，通过这种方法减少了一个栈或者vector的使用，极大地提高了空间利用效率。时间复杂度也减少了好多。

	//Runtime: 16 ms, faster than 99.48%

	class MinStack {
	public:
	/** initialize your data structure here. */
	stack<pair<int,int>> st;

	MinStack() {

	}

xqiao qiaoxu123