2018年4月16日 下午3:54

int数组长度（哈希表长度）

1. 字符串哈希——长度为128
2. 数组哈希——数组的长度/小于数组的长度(使用拉链法)

map数组长度

1. 随时添加

总结：

1. map可以实现string/char的直接映射
2. int必须通过下标，而下标是数字，他对字符和字符串就得多一层转换成数字的映射
3. 不过对于char来说，由于ASCII本身就是一个128位映射char—>int，就不用我们人为的转数字了
4. 也可以说：数组本身就是代表着一种映射关系

我在290中用的是map作统计，老师用int128做统计

2018年4月16日 下午3:54

1. 可以从最基本的”原子情况“,不断的迭代成最终的结果。
2. 使用递归默认上述成立

2018年4月16日 下午3:54

1. 这个题我们先重新统计数据，然后对新的数据进行遍历
   1. 而不是在原先的数据上直接进行操作
      

2018年4月15日 下午3:54
Flatten Binary Tree to Linked List - LeetCode

1. 修改数据本身
2. generate的输入是：i代表一颗要处理的子树的根节点
3. generate的输出是：last代表返回这课子树的子树的最后一个节点

   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

   /** * 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: void flatten(TreeNode* root) { if(root == NULL)return ; TreeNode *last = NULL; generate(root, last); } private: //遍历每个节点。求出当前节点的左右两边的前序链表，然后拼接在一起。 //这个不是遍历这么简单了，而是要在遍历的同时改变原始数据。 //generate的输入是：i代表一颗要处理的子树的根节点 //generate的输出是：last代表返回这课子树的子树的最后一个节点 void generate(TreeNode *i, TreeNode *&last){ last = i; if(i->left == NULL && i->right == NULL){ return; } TreeNode *left = i->left; TreeNode *right = i->right; //填上这两个数据 TreeNode *left_last = NULL; TreeNode *right_last = NULL; //求左右两边，填left_last,right_last if(left){ generate(left, left_last); //重新构造数据格式 i->left = NULL; i->right = left; last = left_last; } if(right){//这里不可以使用i->right，我们在上一步中已经更改了i的指向。这道题就是让更改原始数据，所有这点要小心 generate(right, right_last); last->right = right; last = right_last; } } };

2018年4月15日 下午3:54
这两个起到的效果相同、思路是一样样的，只不过代码的写的方式不同而已。

1. 参数使用&==参数不使用&
   1. &可以指向我们递归之外的一个片区域，在每次递归的时候都可以进行更改——很多
   2. &可以指向每次递归本身新建的一个变量空间，目的是通过下次递归来获得这个变量的值，这是就可以理解为这个递归函数的返回值——114
2. 参数可以使用int类型+vectort返回值==也可以使用cam参数是vector类型+void返回值

2018年4月14日 下午3:54

Count of Smaller Numbers After Self - LeetCode

1. 每次遍历的对象是整个序列，而不是原先数组中的某个元素
2. 这里使用了分治的方法。我认为这是一种从少到多不断迭代的一个过程，体现了迭代的思想。
3. 我在这里和林沐给的答案不同。我的这里参数通过int类型来划分区域，函数是带返回值的。
   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 56 57 58 59 60 61 62 63 64 65 66 67 68 69

      class Solution { public: std::vector<int> countSmaller(std::vector<int>& nums) { if(nums.size() == 0){ std::vector<int> temp; return temp; } std::vector<int> count(nums.size()); std::vector<std::pair<int, int>> vec; //遍历nums建立vec(pair) for(int i = 0; i < nums.size() ;i++){ std::pair<int, int> temp; temp.first = nums[i]; temp.second = i; vec.push_back(temp); } merge_sort(0, nums.size()-1, vec, count); return count; } private: std::vector<std::pair<int, int>> merge_sort_two_vec(std::vector<std::pair<int, int>>& vec1, std::vector<std::pair<int, int>>& vec2, std::vector<int> &count){ std::vector<std::pair<int, int>> vec; //遍历vec1,vec2 int i = 0; int j = 0; while(i < vec1.size() && j < vec2.size()){ if(vec1[i].first <= vec2[j].first){ vec.push_back(vec1[i]); count[vec1[i].second] += j;//这是计数的规则 i++; } else{ vec.push_back(vec2[j++]); } } //省下的补齐 while(i < vec1.size()){ count[vec1[i].second] += j;//这是计数的规则 vec.push_back(vec1[i++]); } while(j < vec2.size()){ vec.push_back(vec2[j++]); } return vec; } //遍历整个序列，而不是原先序列中的某个元素 // 这回一个数组作为处理的单独的对象了，而不是数组中的某一个数。 std::vector<std::pair<int, int>> merge_sort(int left, int right, std::vector<std::pair<int, int>>& vec, std::vector<int> &count){ if(right == left){ std::vector<std::pair<int, int>> vec_temp; vec_temp.push_back(vec[left]); return vec_temp; } std::vector<std::pair<int, int>> vec1; std::vector<std::pair<int, int>> vec2; int mid = (left + right)/2; vec1 = merge_sort(left, mid, vec, count); vec2 = merge_sort(mid+1, right, vec, count); //合并的同时要统计count return merge_sort_two_vec(vec1, vec2, count); } };

2018年4月14日 下午3:54

ACM学习心得关于sync_with_stdio(false); - 蓝飞技术部落格 —— 关注前沿，追求卓越。

2018年4月13日 下午3:54

N-Queens - LeetCode

1. 这道题很多细节没有考虑到，导致做出来总是报执行异常。
   1. 以后碰见异常问题、出错问题时要先检查字母是否写错了、循环的边界多多少少、条件判断顺序、or\and
2. 为啥这道题中要以每一行为一个generate()的遍历对象，而不是以每一个行为一个元素？
   1. 要说明白这个问题就需要理解递归其实是可以让程序并行执行的。
   2. 那么，什么是并行，怎样判断并行的元素？？
      1. 78. Subsets先看一下这个对递归的总结。
      2. 在这道题中，我们需要的是在每行的各个元素中，找到每次找到一个可以满足N-Queens的元素。在这一行中可能有很多元素都满足，但是要求，在每次测试某个元素的时候，不能被上一个元素所影响，这就是所说的其他元素要恢复原状。
      3. 总结一下：并行，一般都需要在不同的元素之间进行相同的动作，但是在操作不同的元素的时候，我们是不可以受其他元素的影响，一般的方法就是要将其他元素操作完之后恢复原状。
   3. 我们需要并行的元素是一行的中的各个元素，那么我们就需要将一行作为一个函数，也就是这里的generate的操作对象。

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
56
57
58
59
60
61
62
63
64
65
66

class Solution {
public:
    std::vector<std::vector<std::string>> solveNQueens(int n) {
        std::vector<std::vector<int>> mark;
        std::vector<std::string> location;
        std::vector<std::vector<std::string>> result;

        //初始化mark location
        for(int i = 0; i < n; i++){
            mark.push_back((std::vector<int>() ));//初始化二维数组
            for(int j = 0; j < n; j++){

                mark[i].push_back(0);
            }
            location.push_back("");//初始化的方法
            location[i].append(n, '.');
        }

        generate(0, n, mark, location, result);

        return result;
    }
private:
    void put_down_the_queen(int x, int y, std::vector<std::vector<int>> &mark){
        static const int dx[] = {-1,1,0,0,-1,-1,1,1};
        static const int dy[] = {0,0,-1,1,-1,1,-1,1};

        mark[x][y] = 1;//不要忘了
        for(int i = 0; i < 8 ; i++){
            for(int j = 1; j < mark.size() ; j++){//最多是N-1,不是n，所以j <= mark.size()是错的
                int a = x+j*dx[i];
                int b = y+j*dy[i];
                             
                if(a < 0 || a >= mark.size() || b < 0 || b > mark.size()){//这里是or。错把a,写成b。找了一个小时
                    break;
                }
                mark[a][b] = 1;
            }
        }
    }

    void generate(int i,int n, std::vector<std::vector<int>> &mark,
                  std::vector<std::string> &location,
                  std::vector<std::vector<std::string>> &result){
        if(i == n){
            result.push_back(location);
            return;
        }
        //遍历一行中的每个位置，如果不冲突，那么put_down_the_queen,下一行
        for(int j = 0; j < n; j++){
            if(mark[i][j]==0){
                std::vector<std::vector<int>> temp_mark = mark;
                //放置皇后，接着递归
                put_down_the_queen(i, j, mark);
                location[i][j] = 'Q';
                generate(i+1, n, mark, location,result);

                //恢复
                location[i][j] = '.';
                mark = temp_mark;
            }

        }
    }

};

2018年4月13日 下午3:54
Subsets - LeetCode

回忆一下

写算法的思路总结（数据结构之后）

分析：

1. 这个问题里理解item是最关键的问题
2. 我们在上面几节的学习中没有涉及到递归，很多题总结下来本质就是一个数组的遍历，当然在不同的情况下，遍历的目的不同，可能是为了统计，可能是为了迭代出一个结果。
3. 在这道递归的题中，我理解下来其实也是一个遍历数组的问题，eg遍历[1,2,3]。不使用递归时，我们有一个指针，通过这个指针去一个个的遍历，在递归中，我们每次调用递归函数，在调用的时候参数i++，其实就是指针的作用。
4. 在非递归中，我们统计、迭代、记录过程，在递归中我们也会统计、迭代、记录过程。
5. 在这道题中，item其实就是一个“统计记录”。记录着我们当前操作到了哪里。
6. 他们最大的不同是：一次递归函数中调用了两次generate()函数，这就说明对同一个位置进行两次的操作。在非递归中我们一般对同一个位置只处理一次，因为一个循环是一个单线程，你无法同时让他们对一个位置的数据同处理。递归就提供了这种假的同时处理的可能。

   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: std::vector<std::vector<int>> subsets(std::vector<int>& nums) { std::vector<std::vector<int>> result; std::vector<int> item; result.push_back(item); generate(result, 0, nums, item); return result; } private: //表面的一层 void generate(std::vector<std::vector<int>> &result, int i, std::vector<int> nums,std::vector<int> item ){ if(i >= nums.size()){ return ; } //nums[i]放进入 item.push_back(nums[i]); result.push_back(item); generate(result, i+1, nums, item ); //nums[i]不放进入 item.pop_back(); generate(result, i+1, nums, item );//当到达右下角时，我们不放3，执行这里。结果直接返回了，那么[]空就没有放进入，需要我们自己手动的放 } };

2018年4月12日 下午3:54

Remove K Digits - LeetCode

1. 我错误的解法是：想通过if-else将所有的情况罗列出来。那么此时的问题时：有哪些特殊情况需要考虑？每种情况下如何进行pop和push操作。这样会在和判断中重复pop和push操作，这就是我的代码长的原因。
2. 新的思考方式是：既然情况太多，还很有可能落下，那么干脆就不罗列了。想这么一个问题，拿到一个数我们只会pop和push操作，那么何时pop？何时push？pop，push分别集中在一起，而不是像上面的解法一样是分散的。

下面这个程序从头到尾都没有考虑：

1. 1572 2
   1. 是：
      1. 1，5，7———pop
      2. 1，5，————pop
      3. 1，
      4. 1，2
   2. 不是：
      1. 1，5，7———pop
      2. 1，5，
      3. 1，5，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 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 56

         class Solution { public: std::string removeKdigits(std::string num, int k) { //栈 std::vector<int> S; int i_k = 0; std::string result=""; //扫描进行对比,入栈 for(int i = 0; i < num.length(); i++){ // if(S.size() >= (num.size()-k)) break;//12345 if(i_k < k ){//5,4,3,2,1 if( S.empty()){ S.push_back(num[i]-'0'); } else if(S[S.size()-1] <= num[i]-'0' ){//=号 1223 S.push_back(num[i]-'0'); } else if(S[S.size()-1] > num[i]-'0'){ S.pop_back(); if(!S.empty()||(num[i]-'0')!=0){//100200 S.push_back(num[i]-'0'); } i_k++; } } else{ if(!S.empty()||(num[i]-'0')!=0){//100200 S.push_back(num[i]-'0'); } } } while(S.size() > (num.size()-k)){ int back = S.back(); S.pop_back(); if(S.back() > back){ S.pop_back(); S.push_back(back); } } //返回字符串 for(int i = 0; i < S.size(); i++){ result.append(1,'0'+S[i]);//这里不可以是"" } //判空 if(result == ""){ result = "0"; } return result; } };

ac的

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

class Solution {
public:
    std::string removeKdigits(std::string num, int k) {
        //栈
        std::vector<int> S;
        std::string result="";
        
        //扫描进行对比,入栈
        for(int i = 0; i < num.length(); i++){
            //这时拿上一个数，只有是否进入？进入到哪个位置？
            int number = (num[i]-'0') ;
            //定位置
            while(!S.empty() && k > 0  && number < S.back()){
                S.pop_back();
                k--;
            }
            
            // 何时入栈
            if( number !=0 || !S.empty()){
                S.push_back(num[i]-'0');
            }
            
        }
        
        while(!S.empty() && k>0){
            S.pop_back();
            k--;
        }
        //返回字符串
        for(int i = 0; i < S.size(); i++){
            result.append(1,'0'+S[i]);//这里不可以是""
        }
        
        //判空
        if(result == ""){
            result = "0";
        }
        
        return result;
    }
};