qiaoxu123’s gists

qiaoxu123 / myCode.cpp

Created March 8, 2019 01:09

> 使用recursive方法进行二分，利用BST的特性

	//Runtime: 24 ms, faster than 89.44%
	//Memory Usage: 21.1 MB, less than 56.68%

	class Solution {
	public:
	TreeNode* sortedArrayToBST(vector<int>& nums) {
	return sortedArrayToBST(nums,0,nums.size());
	}
	TreeNode* sortedArrayToBST(vector<int>& nums,int start,int end){
	if(end <= start) return NULL;

qiaoxu123 / in-order.cpp

Last active March 7, 2019 08:14

> 二叉搜索树验证。对于binary search tree的概念都懂，但是如何通过程序验证还是第一次，问题百出。 - Approach 1 ： recursive - Approach 2 ： in-order traversal

	//Runtime: 20 ms, faster than 99.86%
	//Memory Usage: 20.8 MB, less than 21.53%

	class Solution {
	public:
	bool isValidBST(TreeNode* root) {
	TreeNode* prev = NULL;
	return validate(root,prev);
	}
	bool validate(TreeNode* node,TreeNode* &prev){

qiaoxu123 / queue.cpp

Created March 5, 2019 01:21

> 考察二叉树的宽度遍历算法，在这使用了queue来实现

	//Runtime: 8 ms, faster than 100.00%
	//Memory Usage: 13.9 MB, less than 55.99%

	class Solution {
	public:
	vector<vector<int>> levelOrder(TreeNode* root) {
	vector<vector<int>> result;
	if(!root) return result;
	queue<TreeNode*> q;
	q.push(root);

qiaoxu123 / two_pointer.cpp

Created March 4, 2019 00:36

> 链表遍历题目。主要考虑使用双指针进行倒计时，保证两个指针的间隔正好是n即可。

	//Runtime: 8 ms, faster than 100.00%
	//Memory Usage: 9.7 MB, less than 54.37%

	class Solution {
	public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
	ListNode* start = new ListNode(0);
	start->next = head;

	ListNode* fast = start;

qiaoxu123 / code.cpp

Last active March 3, 2019 23:51

> 很简单的链表节点删除题目，在这因为给出的是要被删除的节点，因此需要将它的值替换，将它的下一个节点进行删除，从而实现链表节点的-1操作

	//Runtime: 12 ms, faster than 100.00%
	//Memory Usage: 9.2 MB, less than 42.80%

	class Solution {
	public:
	void deleteNode(ListNode* node) {
	node->val = node->next->val;
	node->next = node->next->next;
	}
	};

qiaoxu123 / MyCode1.cpp

Last active March 1, 2019 00:44

> 字符串查找匹配题目，数据结构字符串章节本科时候讲过该题目 - 第一种方法是循环匹配，如果不相同就调一位继续全部匹配。效率非常低 - 第二种方法是，当发现不匹配后，不再从头开始继续匹配，而是从原有字符串中找到首字符相同的进行匹配。 - 第三种是参考答案，思路基本相同，但是精简了计算，效率猛增

	//Runtime: 1632 ms, faster than 5.88%
	//Memory Usage: 9.6 MB, less than 26.21%

	class Solution {
	public:
	int strStr(string haystack, string needle) {
	if(needle.length() == 0) return 0;

	int res;

qiaoxu123 / MyCode.cpp

Created February 28, 2019 01:44

> 一个简答的字符串遍历和统计题目题目本身不难，但是之前一直没有自己认真写过，所以花了好多时间。大体思路是，统计字符串数组中每一个前缀字母的个数，使用遍历的方法。

	//Runtime: 8 ms, faster than 99.70%
	//Memory Usage: 9.5 MB, less than 74.22%

	class Solution {
	public:
	string longestCommonPrefix(vector<string>& strs) {
	if(strs.size() == 0) return "";
	string str;
	int count = 0;
	int j = 0;

qiaoxu123 / advanced.cpp

Last active February 27, 2019 02:05

> 对数字数量进行计算，并据此生成新的字符串的过程主要难点在于循环的把握，以及数字转字符串函数的使用代码二也是同样的思路，但是通过算法进行了优化，减少了循环进行了性能提升

	//Runtime: 4 ms, faster than 100.00%
	//Memory Usage: 8.6 MB, less than 95.80%

	class Solution {
	public:
	string countAndSay(int n) {
	string res = "1",cur = "1";
	while(--n){
	char ch = res[0];
	int count = 0;

qiaoxu123 / isalnum.cpp

Created February 26, 2019 00:34

	//Runtime: 8 ms, faster than 99.85%
	//Memory Usage: 9.1 MB, less than 77.05%

	class Solution {
	public:
	bool isPalindrome(string s) {
	for (int i = 0, j = s.size() - 1; i < j; i++, j--) { // Move 2 pointers from each end until they collide
	while (isalnum(s[i]) == false && i < j) i++; // Increment left pointer if not alphanumeric
	while (isalnum(s[j]) == false && i < j) j--; // Decrement right pointer if no alphanumeric
	if (toupper(s[i]) != toupper(s[j])) return false; // Exit and return error if not match

qiaoxu123 / array.cpp

Last active February 25, 2019 00:55

> 很简单的字符串查找比较题目 - Approach 1：Brute Force > 暴力求解，将字符串读取到数组中使用，然后挨个进行对比 - Approach 2 : set > 使用set数组进行字符的查找，然后判断是否相同。相比方法一，性能有一些提升 - Approach 3：array > 由于题目声明只是用小写字母，因此可以使用array代替set实现 - Approach 4：sort > 使用sort对两个字符串进行排序，思路简单但是实现很耗时

	//Runtime: 12 ms, faster than 97.85%
	//Memory Usage: 9.2 MB, less than 58.97%

	class Solution {
	public:
	bool isAnagram(string s, string t) {
	if(s.length() != t.length()) return false;
	int counts[26] = {0};
	for(int i = 0;i < s.length();++i){
	counts[s[i] - 'a']++;

xqiao qiaoxu123