额外题目第4天｜132 673 841 127 684 657

132 我发现困难题往往是在中等题的基础上再多了一步 分割最少次数的回文子串 这道题就是在之前动态规划法找回文子串 (leetcode第5题) 的基础上更多

这题还是用动规来写 思路参考代码随想录

dp数组表示的意义是从0到i最少切割的次数 

递推公式是 取0到i中间值 j 如果从 j+1到i是回文 那dp[i]=min(dp[i], dp[j]+1) 

初始化先让所有的切割数为个数 如果本身是回文那就是0 （注意 所有判断是否是回文都看isPal数组 最开始动规走一遍就可以之后直接调用了）

遍历顺序即从前往后 i在外 j在内

class Solution {
public:int minCut(string s) {vector<vector<bool>> isPal(s.size(), vector<bool>(s.size(), false));for (int i=0; i<s.size(); i++) isPal[i][i]=true;for (int i=s.size(); i>=0; i--) {for (int j=i+1; j<s.size(); j++) {if (s[i]==s[j]) {isPal[i][j] = j==i+1 ? true :isPal[i+1][j-1];}}}vector<int> dp(s.size());for (int i=0; i<s.size(); i++) dp[i]=i;for (int i=0; i<s.size(); i++) {if (isPal[0][i]) {dp[i]=0;continue;}for (int j=0; j<i; j++) {if (isPal[j+1][i]) {dp[i]=min(dp[i], dp[j]+1);}}}return dp[s.size()-1];}
};

673 这题思路还是cr to 代码随想录 但有一点点误区我之前没搞清楚的就是 不管这里动规数组是什么 它定义的找到的最长递增序列都是以当前下标指向的nums为结尾的 所以在遍历的时候也只考虑当前下标大于前面下标的情况

dp数组表示最长递增子序列的长度 count是最长的个数

递推数组  

如果dp[j]+1 == dp[i] 说明找到了另外的一条和现在长度一样的路 但是经过当前 j 指向的元素 count[i]+=count[j]

如果dp[j]+1 > dp[i] 说明经过j的话有更长的路 count[i] = count[j]

dp都取max(dp[i], dp[j]+1)

class Solution {
public:int findNumberOfLIS(vector<int>& nums) {vector<int> dp (nums.size(), 1); //以i指向为结尾的最长递增子序列长度vector<int> count (nums.size(), 1); //最长递增子序列个数int max_len=1;for (int i=0; i<nums.size(); i++) {for (int j=0; j<i; j++) {if (nums[i]>nums[j]) {if (dp[j]+1>dp[i]) {count[i]=count[j];}else if (dp[j]+1==dp[i]) {count[i]+=count[j];//not understand}dp[i]=max(dp[i], dp[j]+1);}max_len = max(max_len, dp[i]);}}int result=0;for (int i=0; i<nums.size(); i++) {if (dp[i]==max_len) result+=count[i];}return result;}
};

841 前两天刚写过的图论题 有点像数的层序遍历 用visited数组来记录是否进入过 que数组来按顺序访问

class Solution {
public:bool canVisitAllRooms(vector<vector<int>>& rooms) {vector<bool> visited(rooms.size(), false);queue<int> que;que.push(0);visited[0]= true;while (!que.empty()) {vector<int> keys = rooms[que.front()]; que.pop();for (int i=0; i<keys.size(); i++) {if (!visited[keys[i]]) {que.push(keys[i]);visited[keys[i]] = true;}}}for (int i=0; i<visited.size(); i++) {if (!visited[i]) return false;}return true;}
};

127 也是几天前刚刚做过的图论题 思路是记得的 模版稍微有点模糊 但也做出来了

这种图论题要记得有visited数组来记录 一来记录到目前单位是几步 二来防止重复计数 这里用的是unordered_map 其实也是当作数组来用 一样的 只是因为这里的index是个string

遍历就是用queue来前进前出的处理 处理当前word时 找出他所有的距离一步的新词 看是否在set里面且没有被遍历过 如果是这样就记录当前到他的步数并加入queue 反之不管

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> wordSet (wordList.begin(), wordList.end());if (wordSet.find(endWord)==wordSet.end()) return 0;queue<string> que;que.push(beginWord);unordered_map<string, int> visited;visited[beginWord] = 1;while (!que.empty()) {string curr_word = que.front(); que.pop();for (int i=0; i<curr_word.size(); i++) {int count = visited[curr_word];string new_word = curr_word;for (int j=0; j<26; j++) {new_word[i] = 'a'+j;if (new_word==endWord) return count+1;if (wordSet.find(new_word)!=wordSet.end() && visited[new_word]==0) {visited[new_word]=count+1;que.push(new_word);}}}}return visited[endWord];}
};

684 冗余连接问题 查并集的几个private function:

init() 所有的father[i]=i;

find return父节点

connect (int u, int v)  连接两个节点 u <- v

isSame 判断两个节点是否是同父节点

class Solution {
private:int n=1005;vector<int> father = vector<int> (n,0);void init() {for (int i=0; i<n; i++) father[i]=i;}int find (int u) {if (father[u]==u) return u;return father[u]=find(father[u]);}void connect(int u, int v) {u=find(u);v=find(v);if (u==v) return;father[v]=u;}bool isSame (int u, int v) {u=find(u);v=find(v);return u==v;}
public:vector<int> findRedundantConnection(vector<vector<int>>& edges) {init();for (int i=0; i<edges.size(); i++) {if (isSame(edges[i][0], edges[i][1])) return edges[i];connect(edges[i][0], edges[i][1]);}return edges[0];}
};

 657 用了一个unordered_map 从四个char指向对应的移动x y变化值 遍历一遍moves数组 最后判断是否还在原点

class Solution {
public:bool judgeCircle(string moves) {unordered_map<char, vector<int>> dir;dir['R'] = {0,1};dir['L'] = {0,-1};dir['U'] = {-1,0};dir['D'] = {1,0};int loc[] = {0,0};for (int i=0; i<moves.size(); i++) {loc[0] += dir[moves[i]][0];loc[1] += dir[moves[i]][1];}return loc[0]==0 && loc[1]==0;}
};

31 这道题思路重点在于 要找到他的下一个排列（除了自己是最大值这个特殊情况）

首先要尽量保持前面的位数先不动  ->用 i 从后往前找要动的值 （这个值 在他后面有比他大的数）

现在找要跟他换的值 在后面比他大的值里面要找到最小的一个 -> 用 j 从后往前找的第一个就是最小的

why？因为如果最右边的不是最小的 = 说明 j 的左边和 i 的右边 中间有比 j 指向小的 那么i就应该指向这个数而不是现在的 i 了

其实就是遍历 i 时 从 i 到末尾是个递减序列

i 和 j 换过之后 接下来要让 i+1 位到最后是递增数列 sort或者reserve这一段就可以

class Solution {
public:void nextPermutation(vector<int>& nums) {for (int i=nums.size()-1; i>=0; i--) {for (int j=nums.size()-1; j>i; j--) {if (nums[j]>nums[i]) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;sort(nums.begin()+i+1, nums.end());return;}}}sort(nums.begin(), nums.end());}
};

463 才写过的岛屿周长问题 如果上下左右出边界或者是海洋就那条边+1在周长里

class Solution {
public:int islandPerimeter(vector<vector<int>>& grid) {int result=0;int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};for (int i=0; i<grid.size(); i++) {for (int j=0; j<grid[0].size(); j++) {if (grid[i][j]==1) {for (int k=0; k<4; k++) {int x=i+dir[k][0];int y=j+dir[k][1];if (x<0||x>=grid.size()||y<0||y>=grid[0].size()||grid[x][y]==0) result++;}}}}return result;}
};

1356 先写一个function来计算每个数换成二进制之后1的个数 然后先根据1的个数来排列 相等时根据数值排序 （再写一个compare function）

class Solution {
private: int how_many_ones (int n) {int count = 0;while (n>0) {count+=n%2;n=n/2;}return count;}
public:vector<int> sortByBits(vector<int>& arr) {unordered_map<int, int> count; for (int i=0; i<arr.size(); i++) {count[arr[i]] = how_many_ones(arr[i]);}sort(arr.begin(), arr.end(), [&count](const int &a, const int &b) {if (count[a]==count[b]) return a<b;return count[a]<count[b];});return arr;}
};