招银科技9.6笔试（整数分解，遗憾）

缺乏、安全感 2022-12-04 07:39 85阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70_pic_center]

#include<iostream>
    #include<cmath>
    #include<vector>
    using namespace std;
    int main(){ 
          int n, res = 0;
          cin >> n;
          if (n>2)
          { 
              vector<vector<int>> dp(n+1,vector<int>());//二维动态数组，每一行是数n的分解情况，每一列是数n的每一个一级分解下的总数
              for (int i=3;i<=n;++i)
              { 
                  int col = (int)floor((i-1)/2);//每一列是一个一次分解，如7=6+1， 5+2， 4+3，三列
                  //这个式子保证了不会有4=2+2,6=3+3这种分解情况
                  dp[i] = vector<int>(col);
                  for (int j=0;j<col;++j)
                  { 
                      dp[i][j] = 1;
                      int n2 = j+1;
                      int n1 = i-n2;
                      if (n1>2*n2)//这有这种情况下才继续分解，以保证降序，保证降序是为了保证不重复
                      { 
                          if (!(n1&1)) ++dp[i][j];//n1是偶数
                          for(int k=j;k<dp[n1].size();++k)
                          { 
                              dp[i][j] += dp[n1][k];//加上n1被分解的总可能数
                          }
                      }
                      
                  }
                  
              }
              //统计结果
            for (int i=0;i<dp[n].size();++i)
              res += dp[n][i];
          }
          cout << res;
        return 0;
    }

遇到好多困难啊，写了一个小时，看了别人的思路，然后自己写的代码，但是出现好多问题：

*  官方代码框的代码有非法字符，所以我下午要全部删掉自己写
 *  编译标准落后，头文件预编译指令后不可以有空格
 *  我忘记确定列数后，写`dp[i] = vector<int>(col);`，所以后面直接`dp[i][j]=1`会出现运行时错误，因为访问越界。
 *  我整体方法没对，看了人家的，发现主要有三点很重要：

1.  一级分解数目是`floor((n-1)/2)`,这样就避免了4=2+2这种情况，因为题目要求不能让所有分解数字相同。
2.  分解数字应该降序，才可以防止重复。所以要发现n1>2\*n2才继续分解n1的条件。
3.  如果继续分解n1，则如果n1是偶数，则应该把分解总数额外再加1，因为这时候允许把4分解为2+2了，因为后面还有一个数字的嘛，不会让所有数字相同。

这是一个数学题，这几个条件发现不了，真的做不出来，而且用了一个二维动态规划数组，每一行的列数是行数n被一级分解的方法数，如7=6+1,5+2,4+3，则dp\[7\]有三列。注意第一行dp\[0\]没用哈。  
`dp[7][0]`表示6+1以及这种方式下引申出来的所有分解法的总数，当然要保证n1>2\*n2才分解哦，像4+3就不可以继续分解，所以`dp[4][2]=1`

# 三数之和 #

## 三指针法 ##

class Solution { 
    public:
        vector<vector<int>> threeSum(vector<int>& nums) { 
            sort(nums.begin(), nums.end());
            int n=nums.size();
            vector<vector<int>> res;
            for (int a=0;a<n;++a)
            { 
                if (a>0 && nums[a]==nums[a-1]) continue;//每一层循环需和上一次枚举的值不同
                int target = -nums[a];//即要在a后面找和等于target的两个数
                int c = n-1;//第三个指针，往左遍历，保证第二个指针b在c左侧
                for (int b=a+1;b<n;++b)
                { 
                    if (b>a+1 && nums[b]==nums[b-1]) continue;//每一层循环需和上一次枚举的值不同
                    while (b < c && nums[b] + nums[c] > target) --c;//让指针3左移
                    if (b==c) break;//指针2,3相遇，说明在这种a下，b和c不可能有和为-nums[a]的，应退出循环，遍历下一个a
                    if (nums[b]+nums[c]==target)//找到了，则保存并继续尝试寻找下一个和为target的b，c二元组
                        res.push_back({ nums[a], nums[b], nums[c]});
                }
            }
            return res;
        }
    };

从三重循环改成了二重循环，优化为了平方复杂度。

# 反转链表 #

## 三指针 ##

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    public:
        ListNode* reverseList(ListNode* head) { 
            ListNode * a, * b, *c;
            a = b = head;
            c = nullptr;
            while(a)
            { 
                a = b->next;
                b->next = c;
                c = b;
                b = a;
            }
            return c;
        }
    };

# 笔试题 #

三道编程题，前俩个每一个有五个空，每空需要补全一句代码。第一题是力扣原题LRU缓存，即双向链表和哈希表结合；第二题是遍历链表，其实我没太懂这个题的意思到底是要干嘛，描述不清晰。

下面是第三题，即常规编程题，和上面那个整数分解的题目很像，但是我最后时间不够，咩检查出来三个致命错误，导致AC 0。哎

#include<iostream>
    #include<vector>
    #include<cmath>
    using namespace std;
    int main()
    { 
        int m, k;
        cin >> m >> k;
        int res = 0;
        if (m>0 && k && k!=1)//如果m，k不满足条件则输出0
        { 
            
            vector<vector<int>> dp(m+1, vector<int>());
            for (int i=1;i<=m;++i)
            { 
                int col = static_cast<int>(floor((i-1)/2 + 1));//一级分解数，不包括4=2+2这种对半重复的
                dp[i] = vector<int>(col);
                for (int j=0;j<col;++j)
                { 
                    int n2 = j;//我的提交版写成了i,错了
                    int n1 = i-j;//我的提交版写成了m-i,错了
                    if (n1%k && (n2==0 || n2%k)) ++dp[i][j];
                    if (n2 && n1>2*n2)//继续分解
                    { 
                        for (int q=j+1;q<dp[n1].size();++q)//我的提交版写成了q=j;,错了
                        { 
                            dp[i][j] += dp[n1][q];
                        }
                    }
                }
                
            }
            for (int i=0;i<dp[m].size();++i)
                res += dp[m][i];
        }
        cout << res;
        return 0;
    }

三个错误我写在注释里了，如果多给我十分钟，就全A了，可惜了，就是没有这十分钟。哎。真的很遗憾，巨遗憾吧。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/60995888d41540819a8bfd724cc9459e.png