发表于 | 更新于

Iterm:

iTerm2设置及使用

Git:

R

Sumery:
1、撤销修改
场景1：当你改乱了工作区某个文件的内容，想直接丢弃工作区的修改时，用命令git checkout file
场景2：当你不但改乱了工作区某个文件的内容，还添加到了暂存区时，想丢弃修改，分两步，第一>步用命令git reset HEAD file，就回到了场景1，第二步按场景1操作。
（git reset命令既可以回退版本，也可以把暂存区的修改回退到工作区。当我们用HEAD时，表示最>新的版本。）
2、 soft hard mixed区别

1、初始化
git init //创建
git clone /path/to/repository //检出
git config –global user.email “you@example.com“ //配置email
git config –global user.name “Name” //配置用户名
git remote add origin url

2、操作
git add // 文件添加，A → B
git add . // 所有文件添加，A → B
git commit -m “代码提交信息” //文件提交，B → C
git commit –amend //与上次commit合并, *B → C
git push origin master //推送至master分支, C → D
git pull //更新本地仓库至最新改动， D → A
git fetch //抓取远程仓库更新， D → C
git log //查看提交记录
git status //查看修改状态
git diff//查看详细修改内容
git show//显示某次提交的内容

3、撤销操作
git reset //某个文件索引会回滚到最后一次提交， C → B
git reset//索引会回滚到最后一次提交， C → B
git reset –hard // 索引会回滚到最后一次提交， C → B → A
git checkout // 从index复制到workspace， B → A
git checkout – files // 文件从index复制到workspace， B → A
git checkout HEAD – files // 文件从local repository复制到workspace， C → A

4、分支
git checkout -b branch_name //创建名叫“branch_name”的分支，并切换过去
git checkout master //切换回主分支
git branch -d branch_name // 删除名叫“branch_name”的分支
git push origin branch_name //推送分支到远端仓库
git merge branch_name // 合并分支branch_name到当前分支(如master)
git rebase //衍合，线性化的自动， D → A

5、冲突处理
git diff //对比workspace与index
git diff HEAD //对于workspace与最后一次commit
git diff <source_branch> <target_branch> //对比差异
git add //修改完冲突，需要add以标记合并成功

Sumery:
1、撤销修改
场景1：当你改乱了工作区某个文件的内容，想直接丢弃工作区的修改时，用命令git checkout file
场景2：当你不但改乱了工作区某个文件的内容，还添加到了暂存区时，想丢弃修改，分两步，第一步用命令git reset HEAD file，就回到了场景1，第二步按场景1操作。
（git reset命令既可以回退版本，也可以把暂存区的修改回退到工作区。当我们用HEAD时，表示最新的版本。）
2、 soft hard mixed区别

发表于

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).
示例2:
输入: s1= “ab” s2 = “eidboaoo”
输出: False

经典滑动窗口：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.size() > s2.size()) {
            return false;
        }
        int windowsize = s1.size();                         
        vector<int> hashmap1(26, 0);
        vector<int> hashmap2(26, 0);
        for (int i = 0; i < windowsize; i++) {
            hashmap1[s1[i] - 'a']++;
            hashmap2[s2[i] - 'a']++;
        }
        for (int i = windowsize; i < s2.size(); i++) {
            if (hashmap1 == hashmap2) {
                return 1;
            }
            hashmap2[s2[i - windowsize] - 'a']--;               //窗口右移
            hashmap2[s2[i] - 'a']++;
        }
        return hashmap1 == hashmap2;
    }
};

发表于

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd”
输出: “bb”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int getNum(string s, int i, int j) {
        while (i >= 0 && j < s.size() && s[i] == s[j]) {
            i--;
            j++;
        }
        return j - i - 1;
    }
    string longestPalindrome(string s) {
         if (s.size() == 0)
            return s;
        int st = 0, e = 0;
        for (int i = 0; i < s.size() - 1; i++) {
            int len1 = getNum(s, i, i);
            int len2 = getNum(s, i, i+1);
            int len = max(len1, len2);
            if (len > e - st) {
                st = i - (len - 1) / 2;
                e = i + len / 2;
            }
        }
        return s.substr(st, e - st + 1);
    }
    
};

发表于 | 更新于

应用场景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}

发表于

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

1.dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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）子树，其中最大指的是子树节点数最多的。
输入: [10,5,15,1,8,null,7]

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

1.判断是不是BTS：

1
2
3
4
5
6
7
8
9
10
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.统计某个树的结点数量：

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

3.实现：

1
2
3
4
5
6
7
8
9
10
11
12
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);
  }

发表于

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

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

1.没用队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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.用队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
        
    }
};

发表于

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

输入：[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 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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;
        
    }
};