实现trie

发表于 2019-08-18 | 更新于 2019-08-19

class Trie {
public:
    /** Initialize your data structure here. */
    Trie* next[26] = {NULL};
    bool isLeaf;
    Trie() {
        isLeaf = false;
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie* node = this;
        for (char c : word) {
            int i = int(c - 'a');
            if (node->next[i] == NULL) {
                node->next[i] = new Trie();
            }
            node = node->next[i];
        }
        node->isLeaf = true;
        return;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie* node = this;
        for (char c : word) {
            int i = int(c - 'a');
            if (node->next[i]) {
                node = node->next[i];
            } else {
                return 0;
            }
        }                      
        if (node->isLeaf) {
            return 1;
        }
        return 0;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Trie* node = this;
        for (char c : prefix) {
            int i = int(c - 'a');
            if (node->next[i]) {
                node = node->next[i];
            } else {
                return 0;
            }
        }
     
        return 1;
    }           
};

双指针例题1

发表于 2019-08-17

一个有符号的有序数组,问这些数平方之后有多少个不重复的数?

#include<bits/stdc++.h>
using namespace std;
int func(vector<int> a) {
	int num = 1;
	int pre = abs(a[0]);
	int n = a.size();
	int i = 0, j = n-1;
	while (i < j) {
		if (a[i] > a[j]) {
			if (pre != abs(a[i])) {
				pre = abs(a[i]);
				num++;
			}
			i++;
		} else {
			if (pre != abs(a[j])) {
				pre = abs(a[j]);
				num++;
			}
			j--;
		}
	}
	return num;
}
int main()
{
	int v[] =  {-5,-3,-1,1,1,2};
  	vector<int> a (v, v + 6);
	int num = func(a);
	cout<<num<<endl;
}

最长上升子序列

发表于 2019-08-11

两种方法：
1.dp 时间复杂度O（n^2）
2.贪心 + 二分时间复杂度 O(n*log(n))

1.dp

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        vector<int> b;
        b.push_back(1);
        int maxx = 1;
        for (int i = 1; i < nums.size(); i++) {
            int m = 0;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && b[j] > m) {
                    m = b[j];
                }
            }
            b.push_back(m+1);
            maxx = max(b[i], maxx);
        }
        return maxx;
    }
};

2.贪心 + 二分
a[i]表示第i个数据。
dp[i]表示表示长度为i+1的LIS结尾元素的最小值。
利用贪心的思想，对于一个上升子序列，显然当前最后一个元素越小，越有利于添加新的元素，这样LIS长度自然更长。
因此，我们只需要维护dp数组，其表示的就是长度为i+1的LIS结尾元素的最小值，保证每一位都是最小值，

这样子dp数组的长度就是LIS的长度。

dp数组具体维护过程同样举例讲解更为清晰。
同样对于序列 a(1, 7, 3, 5, 9, 4, 8)，dp的变化过程如下：

dp[0] = a[0] = 1，长度为1的LIS结尾元素的最小值自然没得挑，就是第一个数。（dp = {1}）
对于a[1]=7，a[1]>dp[0]，因此直接添加到dp尾，dp[1]=a[1]。（dp = {1, 7}）
对于a[2]=3，dp[0]< a[2]< dp[1]，因此a[2]替换dp[1]，令dp[1]=a[2]，因为长度为2的LIS，结尾元素自然是3好过于7，因为越小这样有利于后续添加新元素。（dp = {1, 3}）
对于a[3]=5，a[3]>dp[1]，因此直接添加到dp尾，dp[2]=a[3]。（dp = {1, 3, 5}）
对于a[4]=9，a[4]>dp[2]，因此同样直接添加到dp尾，dp[3]=a[9]。（dp = {1, 3, 5, 9}）
对于a[5]=4，dp[1]< a[5]< dp[2]，因此a[5]替换值为5的dp[2]，因此长度为3的LIS，结尾元素为4会比5好，越小越好嘛。（dp = {1, 3, 4, 9}）
对于a[6]=8，dp[2]< a[6]< dp[3]，同理a[6]替换值为9的dp[3]，道理你懂。（dp = {1, 3, 5, 8}）
这样子dp数组就维护完毕，所求LIS长度就是dp数组长度4。
通过上述求解，可以发现dp数组是单调递增的，因此对于每一个a[i]，先判断是否可以直接插入到dp数组尾部，

即比较其与dp数组的最大值即最后一位；如果不可以，则找出dp中第一个大于等于a[i]的位置，用a[i]替换之。
这个过程可以利用二分查找，因此查找时间复杂度为O(logN)，所以总的时间复杂度为O(N*logN)

class Solution {
public:
    int binary(vector<int> v, int x) {
        int i = 0, j = v.size() - 1;
        while (i < j) {
            int mid = i + (j - i) / 2;
            if (v[mid] >= x) {
                j = mid;
            } else {
                i = mid + 1;
            }
           
        }
        
        return i;
    }
    
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int len = 0;
        vector<int> dp;
        dp.push_back(nums[0]);
        for (int i = 1; i < n; i++) {
            if (nums[i] > dp[len]) {
                dp.push_back(nums[i]);
                len++;
            } else {
                int id = binary(dp, nums[i]);
                dp[id] = nums[i];
                
            }
        }
        return len + 1;
    }
};

最大 BST 子树

发表于 2019-08-10

给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，其中最大指的是子树节点数最多的。
输入: [10,5,15,1,8,null,7]

10
/ \
5 15
/ \ \
1 8 7
其中最大的BTS子树是 5 1 8

1.判断是不是BTS：

bool bst(TreeNode* root) {
        return pd(root, INT_MIN, INT_MAX);
}
bool pd(TreeNode*root, int low, int high) {
        if (root == NULL) return 1;
        if (root->val > low && root->val <high) {
            return pd (root->left, low, root->val) && pd(root->right, root->val, high);
        }
        return 0;
}

2.统计某个树的结点数量：

int num(TreeNode* root) {
        if (root == NULL) return 0;
        int left = num(root->left);
        int right = num(root->right);
        return left + right + 1;
}

3.实现：

int largestBSTSubtree(TreeNode* root) {
      if (root == NULL) {
          return 0;
      }
      if (bst(root)) {
          return  num(root);
      }
      int left = largestBSTSubtree(root->left);
      int right = largestBSTSubtree(root->right);
      
      return max(left, right);
  }

无重复字符的最长子串

发表于 2019-08-07

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
简单分析：
假设给出一个字符串： abcdechjil
第一个重复字符是c, 然而如果是简单暴力的话，第一次从a开始找，找到第一个重复字符c，break，然后下一次要从b开始找
但是发现一个问题，因为b在 c的左边，所以无论怎么样无重复字符最长字串长度都不会大于从a开始遍历的长度。
所以，下一次直接从重复字符c的下一个字符d开始遍历就ok。

//暴力伪代码
for (int i = 0; i < n； i++)
{   
    for (int j = i + 1; j < n; j++)  
}

1.没用队列

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 1) return 1;
        map<char,int> m;
        int n = s.size();
        int maxx = 0;
        int j = 0;
        for (int i = 0; i < n; i++) {  
            if (m.find(s[i]) != m.end()) {                                  //找到了
                int id = m[s[i]];
                for (int z = j; z < id; z++) {
                    m.erase(s[z]);
                }
                maxx = max(maxx, i - j);
                j = id + 1;
                // flag = 1;
            } else {
                maxx = max(maxx, i - j + 1);
            }
            m[s[i]] = i;
        }
        return maxx;
    }
};

2.用队列

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        queue<int> q;
        map<char, int> m;
        int maxx = 0;
        for (int i = 0; i < s.size(); i++) {
            if (m.find(s[i]) == m.end()) {
                q.push(s[i]);
                m[s[i]] = 1;
                int size = q.size();
                maxx = max(maxx, size);
            } else {
                while (!q.empty() && q.front() != s[i]) {
                    char c = q.front();
                    q.pop();
                    m.erase(c);
                }
                q.pop();
                q.push(s[i]);
            }
        }
        return maxx;
        
    }
};

递增顺序查找树

发表于 2019-08-04

给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
示例：

输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]

   5
  / \
3    6

/ \ \
2 4 8
/ / \
1 7 9

输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

1
\
2
\
3
\
4
\
5
\
6
\
7
\
8
\
9

/**
 * 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* increasingBST(TreeNode* root) {
        if (root == NULL) return root;
        root->right = increasingBST(root->right);
        if (root->left) {
            TreeNode* left = root->left;
            root->left = NULL;
            TreeNode* node = left;
            while (node->right) {
                node = node->right;
            }
            node->right = root;
            return increasingBST(left);
         }
        return root;
        
    }
};

设计容器

发表于 2019-08-04

设计一个支持在平均时间复杂度 O(1) 下，执行以下操作的数据结构。
insert(val)：当元素 val 不存在时，向集合中插入该项。
remove(val)：元素 val 存在时，从集合中移除该项。
getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

class RandomizedSet {
public:
    vector<int> v;
    map<int, int> m;
    bool insert(int val) {
        if (m.find(val) != m.end()) {
            return false;
        }
        v.push_back(val);
        m[val] = v.size() - 1;
        return true;
    }
        bool remove(int val) {
        if (m.find(val) == m.end()) {
            return false;
        } else {
            int i = m[val];                                //
            int last = v[v.size()-1];
            m.erase(val);
            v[i] = last;
            v.pop_back();
            if (v.size() != i)                       //
                m[last] = i;
        }
        return true;
    }
    int getRandom() {
        int n = v.size();
        return v[rand()%n];         
    }
};

二分查找第一个比K大的数

发表于 2019-08-04 | 更新于 2019-08-11

int find(vector<int> a, int k) {
	int l = 0, r = a.size();
	int id;
	while (l <= r) {
	
		int mid = l + (r - l) / 2;
		if (a[mid] > k) { 
			id = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return id;
}

int binary(vector<int> v, int x) {
    int i = 0, j = v.size() - 1;
    while (i < j) {
        int mid = i + (j - i) / 2;
        if (v[mid] >= x) {
            j = mid;
        } else {
            i = mid + 1;
        }
       
    }
    
    return i;
}

虚拟内存

发表于 2019-07-28

功能：

一：进程内存管理
它有助于进程进行内存管理，主要体现在：
1.内存完整性：由于虚拟内存对进程的”欺骗”，每个进程都认为自己获取的内存是一块连续的地址。我们在编写应用程序时，就不用考虑大块地址的分配，总是认为系统有足够的大块内存即可。
2.安全：由于进程访问内存时，都要通过页表来寻址，操作系统在页表的各个项目上添加各种访问权限标识位，就可以实现内存的权限控制。
二：数据共享
通过虚拟内存更容易实现内存和数据的共享。
在进程加载系统库时，总是先分配一块内存，将磁盘中的库文件加载到这块内存中，在直接使用物理内存时，由于物理内存地址唯一，即使系统发现同一个库在系统内加载了两次，但每个进程指定的加载内存不一样，系统也无能为力。
而在使用虚拟内存时，系统只需要将进程的虚拟内存地址指向库文件所在的物理内存地址即可。如上文图中所示，进程 P1 和 P2 的 B 地址都指向了物理地址 C。
而通过使用虚拟内存使用共享内存也很简单，系统只需要将各个进程的虚拟内存地址指向系统分配的共享内存地址即可。
三：SWAP
虚拟内存可以让帮进程”扩充”内存。
我们前文提到了虚拟内存通过缺页中断为进程分配物理内存，内存总是有限的，如果所有的物理内存都被占用了怎么办呢？
Linux 提出 SWAP 的概念，Linux 中可以使用 SWAP 分区，在分配物理内存，但可用内存不足时，将暂时不用的内存数据先放到磁盘上，让有需要的进程先使用，等进程再需要使用这些数据时，再将这些数据加载到内存中，通过这种”交换”技术，Linux 可以让进程使用更多的内存。

二叉搜索树中序后继

发表于 2019-07-26

给定一个结点，找出这个结点的后继结点
中序遍历：左中右
情况分类：
一：结点的右子树不为空
返回右子树的最左结点
二：结点的右子树为空
1.如果这个结点是根结点，直接返回NULL
2.如果这个结点是父节点的左儿子，直接返回父亲结点
3.如果这个结点是父节点的右儿子，不断向上找第一个结点，这个结点是他父亲结点的左儿子

// Definition for a Node.
/*
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/
class Solution {
public:
    Node* inorderSuccessor(Node* node) {
        
        if (node->right) {
            Node* p = node->right;
            while (p->left) {
                p = p->left;
            }
            return p;
        } else {
            if (node->parent == NULL) 
                return NULL;
            if (node->parent->left == node) 
                return node->parent;
            else {
                    Node *p = node->parent;
                    while (p && p->right == node) {
                        node = p;
                        p = p->parent;
                    }
                    return p;
            }
        }
    }
};

Q-同學

Make a diffence

RSS

GitHub