1.3万

LincolnZhen

handsomepyp
Vesper.
BT7274
JXM

zhangzihao
RyanMoriarty
zhkpi

class Solution {
public:
int m,n;
bool find(vector<vector<char>>& board,string word,vector<vector<int>>&visited,int depth,int i,int j){
if(depth ==word.size()) return true;
if(i<0 ||i>m-1 || j<0 || j>n-1 ||board[i][j] != word[depth] || visited[i][j]) return false;
// depth++;
visited[i][j] =1;
int ans =
find(board,word,visited,depth+1,i-1,j)
|| find(board,word,visited,depth+1,i+1,j)
|| find(board,word,visited,depth+1,i,j-1)
|| find(board,word,visited,depth+1,i,j+1);
visited[i][j] =0;
return ans;
}
bool exist(vector<vector<char>>& board, string word) {
m = board.size();
n = board[0].size();
vector<vector<int>> visited(m,vector<int>(n,0));
for(int i = 0 ;i< m;i++){
for(int j = 0 ;j < n;j++){
if(board[i][j]!=word[0]) continue;
else if( find(board,word,visited,0,i,j))return true;
}
}
return false;
}

};


#### 库函数版本

class Solution {
public:
string reverseWords(string s) {
stack<string> st1;
istringstream input(s);
string t;
string ans;
while(input>>t) st1.push(t);  //空格被认为是分隔符
while(!st1.empty()){
ans.append(st1.top());
ans.append(" ");     //append效率要比+高
st1.pop();
}
if(ans.length()==0) return ans;
ans.pop_back(); //删掉最后加入的空格
return ans;
}
};


#### 面试官更想看到的手写版本

class Solution {
public:
string reverseWords(string s) {
int n = s.size();
if(n==0) return s;
string ans;
int right = n-1;
while(right>=0){
while(right>=0 && s[right]==' ')right--;
if(right<0) break;   //去掉输入全是空格的情况
int left = right;
while(left>=0 && s[left]!=' ')left--;
ans.append(s.substr(left+1,right-left));
ans.append(" ");
right = left;
}
if(ans.size()==0) return ans;
ans.pop_back();
return ans;
}
};


class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int left = 0,right = nums.size()-1;
vector<int >ans;
while(left<right){
if(left<right && nums[left]+nums[right]>target) right--;
else if(left<right && nums[left]+nums[right]<target) left++;
else {
ans.emplace_back(nums[left]);
ans.emplace_back(nums[right]);
break;
}
}
return ans;
}
};


#### stl yyds 时间复杂度 $O(N)$ 空间复杂度$O(1)$

class Solution {
public:
vector<int> exchange(vector<int>& nums) {
partition(nums.begin(),nums.end(),[](const int n){return n&1;}); //匿名函数实现，也可n%2
return nums;
}
};


partition 可直译为“分组”，partition() 函数可根据用户自定义的筛选规则，重新排列指定区域内存储的数据，使其分为 2 组，第一组为符合筛选条件的数据，另一组为不符合筛选条件的数据。

#### 手动实现快排划分,

class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int i = 0,j = nums.size()-1;
while(i<j){
while(i<j && nums[j]%2==0)j--;   //i<j的判断不能丢
while(i<j && nums[i]%2==1)i++;
if(i<j){
int tmp = nums[j];
nums[j] = nums[i];
nums[i] = tmp;
}
}
return nums;
}
};


#### 思路

1. 假设公共长度为c，链表A的剩余长度为a，链表B的剩余长度为b 。有 a+c+b = b+c+a
2. 指向头节点的两个指针同时往后走，若n1走到头，则将其指向链表B的头节点，再继续同步往后走；同理n2走到头将其指向链表A的头节点。
3. 最后相遇的位置就是第一个公共节点。

#### 代码

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while(n1!=n2){
}
return n1;
}
};


class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> mp;
int start = -1;
int res= 0;
for(int i = 0 ;i < s.size();i++){
if(mp.find(s[i]) != mp.end()){
if(mp[s[i]]>=start) start = mp[s[i]]+1;
mp[s[i]] = i;   //更新最新的位置
}
else {
if(start == -1) start = i;
mp.insert({s[i],i});
}
res = max(res,i-start+1);
}
return res;
}
};


#### 思路

1. 关键在于确定dp[0]和dp[1]的大小，分别代表了无字符和只有一个字符的可能性
2. 接着就是写转移方程
3. 其实是跳台阶问题。
4. 可以转字符串处理，可以取余转数字处理
class Solution {
public:
int translateNum(int num) {
string s = to_string(num);
int n = s.size();
vector<int> dp(n+1,0);
dp[0] = 1;
dp[1] = 1;
for(int i =2;i<=n;i++){
int num = (s[i-2]-'0')*10 + s[i-1]-'0';
if(num>=10 && num<=25) dp[i] = dp[i-2]+dp[i-1];
else dp[i]=dp[i-1];
}
return dp[n];
}
};


/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
ListNode* dummy = new ListNode(1);
ListNode* cur = dummy;
while(cur && cur->next){
if(cur->next->val == val){
cur->next = cur->next->next;
break;
}
cur = cur->next;
}
return dummy->next;
}
};


#### 一共四种情况

1. 只有一个元素
2. 只有一行
3. 只有一列
4. m*n的数组
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
if(grid[0].size()==0) return 0;
int m = grid.size();
int n = grid[0].size();
int ans = grid[0][0];
int dp[m][n];
dp[0][0] = grid[0][0];
for(int i = 0;i<m;i++){
for(int j = 0 ;j< n;j++){
if(i==0 && j==0) continue;
else if(i==0) dp[i][j] = dp[i][j-1]+grid[i][j];
else if(j==0) dp[i][j] = dp[i-1][j] + grid[i][j];
else dp[i][j] = max(dp[i-1][j],dp[i][j-1])+grid[i][j];
// ans = max(dp[i][j],ans);
}
}
return dp[m-1][n-1];
}
};



#### 思路

dp[i]表示以nums[i]为结尾的子数组的最大和；如果dp[i-1]<0，说明加上前面的是负收益，不如不加，让dp[i] = nums[i]，如果dp[i-1]>=0 ，让dp[i] = dp[i-1]+nums[i].

#### 时间复杂度 $O(n)$ 空间复杂度$O(n)$

class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.size() == 0) return 0;
int n = nums.size();
int dp[n+1];
int maxn = nums[0];
dp[0] = nums[0];
for(int i = 1;i<n;i++){
if(dp[i-1]>0) dp[i] = dp[i-1]+ nums[i];
else dp[i] = nums[i];
maxn = max(maxn,dp[i]);
}
return maxn;
}
};