Leetcode题库练习笔记（Medium） 美区国区

两数相加

将链表表示的两个非负整数相加，结果也以链表形式返回
https://leetcode-cn.com/problems/add-two-numbers/

不完备的题解 解决不了数据溢出

通过样例1565 / 1568

直接模拟人工计算时的相加过程，提取出两个链表表示的整数，再相加，变回链表，但是A/B链表长度一旦很长，超过unsigend long long表示范围的话就gg了
注意：queue的用法，判空empty()，队头元素是q.front()

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {queue<int> list_1;queue<int> list_2;ListNode* p1=l1;ListNode* p2=l2;while(p1!=nullptr)      //store data in lists{list_1.push(p1->val);p1=p1->next;}while(p2!=nullptr){list_2.push(p2->val);p2=p2->next;}unsigned long long num1=0,num2=0,i=0;      //calculate value of listswhile(list_1.empty()!=1){num1+=list_1.front()*pow(10,i);list_1.pop();i++;}i=0;while(list_2.empty()!=1){num2+=list_2.front()*pow(10,i);list_2.pop();i++;}unsigned  long long sum=num1+num2;queue<int>res;while(sum!=0){int n=sum%10;res.push(n);    //lower digit pushed first, to be poped firstsum=sum/10;}ListNode* p=new ListNode;ListNode* newlist=p;//save the list headwhile(res.empty()!=1){p->val=res.front();res.pop();if(res.empty()==1){break;}ListNode* q=new ListNode;q->val=0;q->next=nullptr;//initialize the next nodep->next=q;p=p->next;}return newlist;}
};

官方题解

不用转换格式（链表——>整数——>链表），直接边加变构造新的链表，每个节点填入的值是res=A+B+进位的个位，下一个结点的进位是res的十位
公式如下： $res=[\frac{A+B+Carry}{10}]$ 、 $Carr{y}_i=(A+B+Carr{y}_{i-1})\%10$

只要逐位边加边构造链表，就不存在数字过大溢出的问题了

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode *head = nullptr, *tail = nullptr;int carry = 0;while (l1 || l2) {int n1 = l1 ? l1->val: 0;int n2 = l2 ? l2->val: 0;int sum = n1 + n2 + carry;if (!head) {head = tail = new ListNode(sum % 10);} else {tail->next = new ListNode(sum % 10);tail = tail->next;}carry = sum / 10;if (l1) {l1 = l1->next;}if (l2) {l2 = l2->next;}}if (carry > 0) {tail->next = new ListNode(carry);}return head;}
};

8. String to Integer (atoi)

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).
题目要求：实现字符串string类型转换成int类型的函数
原题目地址
暴力枚举法即可

int myAtoi(string s)
{int sign = 1;bool signflag = 0;bool zeroflag = 0;//0表示有可能出现“前面的0”； 1则相反vector<int> st;for (int i = 0; i < s.size(); i++){if (signflag == 0 && s[i] == ' ')continue;else if (signflag == 0 && s[i] == '+')signflag = 1;else if (signflag == 0 && s[i] == '-')signflag = 1, sign = -1;else if (s[i] == '0')//检查是否为“前面的0 ” {if (zeroflag == 1){signflag = 1, st.push_back(0);}else signflag = 1;//跳过 }else if (s[i] > '0' && s[i] <= '9')signflag = zeroflag = 1, st.push_back(s[i] - 48);//注意ASCII转换elsebreak;//其他情况(出现字母etc)，直接跳出循环，输出已扫描到的合法部分}int n = 0;long long num = 0, sum = 0;//循环计次 while (!st.empty()){num = st.back();st.pop_back();num *= pow(10, n);sum += num;n++;if (n > 10)//防止数字过大，中途num溢出{if (sign == 1)return  pow(2, 31) - 1;else return-pow(2, 31);}}long long res = sign * sum;if (res > pow(2, 31) - 1)res = pow(2, 31) - 1;else if (res < -pow(2, 31))res = -pow(2, 31);return res;
}

877. Stone Game

题目：leetcode题目

不完备的解 贪心算法

起初考虑了贪心算法+模拟
但是贪心算法（每一次都最两边之一较大的值）不能保证得到最优解，只有部分问题（Kruskal/prim最小生成树等算法中等同于最优解）

bool stoneGame1(vector<int>& piles) {int n = piles.size();int sumA = 0, sumB = 0, i, j = n - 1, k = 0;vector<bool>flags(n);//record if a pile has been taken(1)for (i = 1; i <= n && j >= k; i++)//simiulate every turn{if (i % 2 == 1)//aliceif (piles[k] > piles[j]){sumA += piles[k]; k++;}else{sumA += piles[j]; j--;}elseif (piles[k] > piles[j]){sumB += piles[k]; k++;}else{sumB += piles[j]; j--;}int restSum = accumulate(piles.begin() + k, piles.begin() + j + 1, 0);if (sumA > sumB + restSum) return true;}return false;
}

经启发后的解 DP

构造动态规划就需要先构造递推方程，也就是先构造DP表项

• 首先，DP表项的角标必须等价于当前状态
• 其次，DP表项的取值必须能直接转换成解并输出
  进而，状态转移表项DP[i,j]就可以表示状态[i,j]下的最优解，成功构造DP后只需要迭代到目标DP表项，比如DP[0][n-1]然后输出即可
  目前就见过的算法题而言，DP表项的角标最多两个(i,j即可一一对应一个状态)，但在算法课上曾见到一道连续矩阵相乘最值的问题，涉及到三个角标

//动态规划 构造dp[i][j] 为面对piles[i~j]时当前玩家能拿到的分数最大值（max{石头总和}）
//由此看出构造DP表项的两大要素：
//1、精准指明当前状态(往往1~2个角标) 2、表项取值本身==当前最优解（像这样要输出bool的解则要准确取值，直接判T/F）
bool stoneGame(vector<int>& piles) {const int N = 501;int dp[N][N] = { 0 };int sum = accumulate(piles.begin(), piles.end(), 0);int n = piles.size();int i = 0, j = n - 1,k=1;for (k = 1; j >= i; k++){int last1=0, last2=0;if (i > 0)last1 = dp[i - 1][j];if (j < n - 1)last2 = dp[i][j + 1];if (last1 + piles[i] > last2 + piles[j]){dp[i][j] = last1 + piles[i];if (k % 2 == 1 && dp[i][j] > sum / 2)return true;i++;}else{dp[i][j] = last2 + piles[j];if (k % 2 == 1 && dp[i][j] > sum / 2)return true;j--;}}return false;
}

官方数学巧解 不具普适性

组合数学可以构造证明：先下手的A永远有必胜策略，可以将piles[i] (i=0, 2, 4, …)涂成黑色，将piles[i] (i=1, 3, 5, …)涂成红色，先出手的一方总可以保证只取一种颜色的堆直到结束，而两种颜色石头数量之和必然有一方大于另一方（因为总数是奇数，不存在平局），所以借由2元上色的方式构造证明了先手必赢。

    bool stoneGame(vector<int>& piles) {return true}

547. 省份数量

题目：leetcode国区——省份数量

个人解法：BFS遍历

牢记BFS特征：用栈存储一个节点所有的邻接点(包括自己)，先入栈后出栈，出栈时标记该点已经被访问

void bfs(vector<vector<int>>& isConnected, int start, vector<int>& flags)
{int i, j;int n = isConnected.size();vector<int>Neighbors;Neighbors.push_back(start);while (Neighbors.size() > 0){int newN = Neighbors.back();Neighbors.pop_back();flags[newN] = 1;for (j = 0; j < n; j++)if (isConnected[newN][j] && flags[j] == 0){Neighbors.push_back(j);}}
}int findCircleNum(vector<vector<int>>& isConnected) {int i, res = 0,j;int n = isConnected.size();vector<int> flags(n);for (i = 0; i < n; i++){if (flags[i] == 1)continue;bfs(isConnected,i,flags);res++;}return res;
}

个人解法2：DFS遍历

牢记DFS特征：递归，dfs()里调用dfs()
使用Python可以用语法糖扩大栈空间

void dfs(vector<vector<int>>& isConnected, int start, vector<int>&flags)
{int i;bool not_counted = 1;int n = isConnected.size();flags[start] = 1;for (i = 0; i < n; i++){if (isConnected[i][start] && flags[i] == 0){dfs(isConnected, i, flags);}}
}int findCircleNum(vector<vector<int>>& isConnected) {int i, res = 0, j;int n = isConnected.size();vector<int> flags(n);for (i = 0; i < n; i++){if (flags[i] == 1)continue;dfs(isConnected, i, flags);res++;}return res;}

简化此题：很多时候DFS写不出来总是因为dfs()的参数太多，容易想错：
实际只需要传入一个参数：被dfs()的端点本身，一般是int表示，如这里的int start

• 如果问题数据规模小：其他参数一律写成全局变量，一开始申请足够空间
• 如果问题数据规模大：dfs()用函数模声明和定义成主要函数(这里的findCircleNum）的嵌套定义的函数

function<type(args_type)>funcName=[](args)
{/*function body*/};    //别忘了分号

用function<T>定义的函数可以定义在其他函数里面或者外面，很适合定义dfs()！

5. 最长回文子串

题目：

要点

• 构造最优子结构
  
  进一步细化
  
  边界条件是长度为1或2的字串：
  
• 迭代填表的时候需要确保子问题的解已经计算出来（注意迭代顺序）
  外层约束是j，内层是i，确保子问题的解$dp[i+1][j-1]$在调用的时候已被计算完毕
  

6106. 统计无向图中无法互相到达点对数(连通分支问题)

题目：

本质上是找图的连通分支（由多少个连通的子图组成）

用DFS找出所有连通分支，统计每个连通分支的点数，所求两两组合数目res=res+新发现的连通分支点数$\times$之前所有(分支的)点数之和
牢记dfs()函数的写法：

• 如果问题数据规模小：其他参数一律写成全局变量，一开始申请足够空间
• 如果问题数据规模大：dfs()用函数模声明和定义成主要函数(这里的findCircleNum）的嵌套定义的函数
  dfs()的参数一般只需一个x就够

long long countPairs(int n, vector<vector<int>>& edges) {//转换数据结构vector<vector<int>>g(n);for (auto& e : edges){int x = e[0], y = e[1];g[x].push_back(y);g[y].push_back(x);}vector<bool>visit(n);//int block = 0;   //统计连通分支的个数，但是用不上long long  prev = 0; //之前遇到的分支的点总和int count = 0;//每个分支内有多少点function<void(int)>dfs = [&](int x) //！函数内嵌套函数 (这样可以少开visit空间){if (visit[x] == 0){visit[x] = 1;count++;for (int p : g[x])//对于x的每一个邻接点执行dfsdfs(p);//block++;}};long long res = 0;for (int i = 0; i < n; i++){if (!visit[i]){count = 0;dfs(i);//进入dfs，算出这个分支区的countres += count * prev;//res+=新的分支点数*之前记录的所有点数prev += count;}}return res;
}