头像

大明湖的鱼




离线:1天前


最近来访(12)
用户头像
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. 最后相遇的位置就是第一个公共节点。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* n1 = headA;
        ListNode* n2 = headB;
        while(n1!=n2){
            n1 = n1?n1->next:headB;
            n2 = n2?n2->next:headA;
        }
        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];
    }
};



/**
 * Definition for singly-linked list.
 * 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);
        dummy->next = head;
        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].
取dp[i]中的最大值即可。

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

如果用pre和cur滚动记录dp[i]和dp[i-1]的话,空间复杂度可以做到$O(1)$

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;
    }
};

拓展

这样我们只能求出最大和的值,如果题目让我们打印这个连续序列怎么办呢?

答:用start和end分别记录满足当前dp[i]的子序列的开始和结束,end其实就是i。记最后结果为ans,如果ans小于dp[i],让start=end,end=当前i.
大概就是这么个思想,可能边界不够细