leetcode解题思路分析（十一）71-77题

分手后的思念是犯贱 2023-07-04 06:23 12阅读 0赞

1.  简化路径  
    以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。  
    在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径  
    请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

**考虑到可能存在无用或者…/返回上一级的情况，采用栈是一个合理的解法**

class Solution { 
    public:
        string simplifyPath(string path) { 
            if(path.length() == 0) return "";
            stack<string> st;
            string tmp;
            path += "/";
            int now = 0;
            while(now < path.length() - 1)
            { 
                while(path[now] == '/' && now < path.length() - 1) now ++;
                if(now >= path.length() - 1) break;
                if(path[now] == '.' && (path[now + 1] =='.' || path[now + 1] == '/'))
                { 
                    if(path[now + 1] == '.' && (now + 2 > path.length() - 1 || path[now + 2] == '/'))            
                    { 
                        if(!st.empty()) st.pop();
                        now = now + 2;
                        continue;
                    }
                    else 
                        if(path[now + 1] != '.')
                        { 
                            now ++;
                            continue;
                        }
                }
                tmp = "";
                while(path[now] != '/')
                { 
                    tmp += path[now];
                    now ++;
                }
                st.push(tmp);
            }
            tmp = "";
            if(st.empty()) return "/";
            while(!st.empty())
            { 
                tmp = "/" + st.top() + tmp;
                st.pop();
            }
            return tmp;
        }
    };

1.  编辑距离  
    给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。  
    你可以对一个单词进行如下三种操作：  
    插入一个字符  
    删除一个字符  
    替换一个字符

**本题可采用动态规划求解：dp\[i\]\[j\]表示word1 i 位和 word2 i位之间的差距，其决定于i - 1和j - 1之间的关系，由于可以插入/删除/替换，因此包括了dp\[i - 1\]\[j\]， dp\[i\]\[j - 1\], dp\[i - 1\]\[j - 1\]三种**

class Solution { 
    public:
        //集合表示 dp[i][j] 对前i个字符进行操作,转换为目标的前j个字符的操作次数 属性->操作次数最小值
        
        //集合划分 dp[i][j]的来源 考虑对第i个字符进行的操作是什么
        //1 插入操作 从而相等 所以先让前i个字符变为j-1字符，然后在第i处插入j代表的字符 即dp[i][j-1]+1
        //2 删除操作 从而相等 所以先让前i-1个字符变为j字符，然后在第i处删除 即dp[i-1][j]+1
        //3 替换操作 从而相等 if(i处等于j处 不需要替换) 即dp[i-1][j-1]
        // else 需要替换 dp[i-1][j-1]+1 
        //上述取个最小值即可
        int minDistance(string w1, string w2) { 
            int n = w1.size(), m = w2.size();
            vector<vector<int>> dp(n+1,vector<int>(m+1));
            for(int i = 0; i <= n; i++) dp[i][0] = i;//i个字符转化为0个字符 只能一直删i次
            for(int j = 0; j <= m; j++) dp[0][j] = j;//0个字符转化为j个字符 只能一直插入j次
            for(int i = 1; i <= n; i++){ 
                for(int j = 1; j <= m; j++){ 
                    dp[i][j] = min(dp[i][j-1],dp[i-1][j])+1;//插入 删除 时
                    dp[i][j] = min(dp[i][j],dp[i-1][j-1] + (w1[i-1]==w2[j-1] ? 0:1));//替换时
                }
            }
            return dp[n][m];
        }
    };

1.  矩阵置零  
    给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

**本题的做法是对第一行/第一列的值先置0，作为标记位，最后检测并给相应的行/列置零。这样可以减少重复置0的数量**

class Solution { 
    public:
        void setZeroes(vector<vector<int>>& matrix) { 
            int line = matrix.size();
            int col = matrix[0].size();
            if (matrix.size() == 0) return;
            //两个bool用于第一行状态的描述
            bool firstline = false;
            bool firstcol = false;
            //第一行和第一列单独处理
            for (int i=0; i<line; i++) { 
                if (matrix[i][0] == 0) { 
                    firstcol = true;
                    break;
                }
            }
            for (int j=0; j<col; j++) { 
                if (matrix[0][j] == 0) { 
                    firstline = true;
                    break;
                }
            }
            //官方做法，第一位标0
            for (int i=1; i<line; i++) { 
                for (int j=1; j<col; j++) { 
                    if (matrix[i][j] == 0) { 
                        matrix[i][0] = 0;
                        matrix[0][j] = 0;
                    }
                }
            }
            //检查第一行，查到0就更新一整列
            for (int i=1; i<line; i++) { 
                if (matrix[i][0] == 0) { 
                    for (int j=1; j<col; j++) { 
                        matrix[i][j] = 0;
                    }                
                }
            }
            //检查第一列，查到0就更新所在行
            for (int j=1; j<col; j++) { 
                if (matrix[0][j] == 0) { 
                    for (int i=1; i<line; i++) { 
                        matrix[i][j] = 0;
                    }
                }
            }
            //第一行第一列最后处理一下
            if (firstline) { 
                for (int j=0; j<col; j++) { 
                    matrix[0][j] = 0;
                }
            }
            if (firstcol) { 
                for (int i=0; i<line; i++) { 
                    matrix[i][0] = 0;
                }
            }        
        }
    };

1.  搜索二维矩阵  
    编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：  
    每行中的整数从左到右按升序排列。  
    每行的第一个整数大于前一行的最后一个整数。

**本题采取两次二分法的方式查找所在行和列**

class Solution 
    { 
      public: bool searchMatrix(vector<vector<int>>& matrix, int target) 
      { 
            if(matrix.size() == 0  || matrix[0].size() == 0)
            { 
                return false;
            }
            int m = matrix.size();
            int n = matrix[0].size();
            int l = 0, r = m - 1;
            int res = -1;
            while(l <= r)
            { 
                int mid = l + ((r-l)>>1);
                if(matrix[mid][n-1] >= target)
                { 
                    res = mid;
                    r = mid - 1;
                }
                else
                { 
                    l = mid + 1;
                }
            }
            if(res == -1)
            { 
                return false;
            }
            l = 0;
            r = n-1;
            while(l <= r)
            { 
                int mid = l + ((r-l)>>1);
                if(matrix[res][mid] == target)
                { 
                    return true;
                }
                else if(matrix[res][mid] < target)
                { 
                    l = mid + 1;
                }
                else
                { 
                    r = mid - 1;
                }
            }
            return false;
        }
    };

1.  颜色分类  
    给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

**本题的解法是利用两个指针指向0的最右边界和2的最左边界，再用一个指针从头到尾遍历，然后交换0，1，2的位置即可**

class Solution { 
      public:
      /* 荷兰三色旗问题解 */
      void sortColors(vector<int>& nums) { 
        // 对于所有 idx < p0 : nums[idx < p0] = 0
        // curr 是当前考虑元素的下标
        int p0 = 0, curr = 0;
        // 对于所有 idx > p2 : nums[idx > p2] = 2
        int p2 = nums.size() - 1;
    
        while (curr <= p2) { 
          if (nums[curr] == 0) { 
            swap(nums[curr++], nums[p0++]);
          }
          else if (nums[curr] == 2) { 
            swap(nums[curr], nums[p2--]);
          }
          else curr++;
        }
      }
    };

1.  最小覆盖字串  
    给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

**本题采用滑动窗口求解：左侧窗口用于收紧大小，右侧用于保证找到所有字母**

class Solution { 
    public:
        string minWindow(string s, string t) { 
            int count[256] = {  0 };
            for (auto c : t) ++count[c];
            int len = 0, minLength = s.length();
            string res;
            for (int l = 0, r = 0; r < s.length(); ++r) { 
                if (--count[s[r]] >= 0) ++len;
                while (len == t.length()) { 
                    if (r - l + 1 <= minLength) { 
                        minLength = r - l + 1;
                        res = s.substr(l, r - l + 1);
                    }
                    if (++count[s[l++]] > 0) --len;
                }
            }
            return res;        
        }
    };

1.  组合  
    给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

**对于求所有可能组合，一定是回溯法求解，即迭代求解选择该数和不选择该数的分支**

class Solution { 
    public:
        vector<vector<int>> result;
        vector<vector<int>> combine(int n, int k) { 
            if (n < k) return result;
            vector<int> arr(k, 0);
            combine(n, k, 0, 0, arr);
            return result;
        }
        void combine(int n, int k, int n_pos, int k_pos, vector<int>& arr) { 
            if (n - n_pos < k - k_pos) return;
            if (k_pos == k) { 
                result.emplace_back(arr);
                return;
            }
            arr[k_pos] = n_pos + 1;                  // 注意数字是从1开始
            combine(n, k, n_pos + 1, k_pos+1, arr);  // 选择n_pos的分支
            combine(n, k, n_pos + 1, k_pos, arr);    // 不选择n_pos的分支
        }
    };