leetcode解题思路分析（六十一）519 - 525 题

小鱼儿 2023-01-11 03:47 87阅读 0赞

1.  随机翻转矩阵  
    题中给出一个 n\_rows 行 n\_cols 列的二维矩阵，且所有值被初始化为 0。要求编写一个 flip 函数，均匀随机的将矩阵中的 0 变为 1，并返回该值的位置下标 \[row\_id,col\_id\]；同样编写一个 reset 函数，将所有的值都重新置为 0。尽量最少调用随机函数 Math.random()，并且优化时间和空间复杂度。

**典型的稀疏矩阵，用哈希表或者桶等方式即可，怎么节约怎么来**

class Solution { 
    public:
        int cnt,r,c;//当前有cnt个0 矩阵为 r行c列
        unordered_map<int,int> hash;//键：已经翻过的位置编号 值：该位置的替换编号
                                    //每当某一个位置翻过了 就用当时的最后一个位置去替换
        Solution(int n_rows, int n_cols):cnt(n_rows*n_cols),r(n_rows),c(n_cols) { }
        vector<int> flip() { 
            int x = rand()%cnt;//在0 ~ cnt-1内随机选一个位置
            int res = x;//先假设x位置可以用
            if(hash.count(x)) res = hash[x];//若x被用过了 则用替换x的新编号
            //用当前最后一个位置去替换x位置
            if(hash.count(cnt-1)){ //若当前的最后一个位置也被用过了
                hash[x] = hash[cnt-1], hash.erase(cnt-1);//则更新x为新的cnt-1的编号 并删除cnt-1位置
            }
            else hash[x] = cnt-1;//若最后一个位置没被用过 则直接换到x位置
            cnt--;//替换完毕 总元素减1
            return { res/c, res % c};
        }
        
        void reset() { 
            cnt = r * c;
            hash.clear();//最开始所有编号都没被用过
        }
    };
    
    /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(n_rows, n_cols); * vector<int> param_1 = obj->flip(); * obj->reset(); */

1.  检测大写字母  
    给定一个单词，你需要判断单词的大写使用是否正确。

**没什么意义的题目**

class Solution { 
    public:
        bool detectCapitalUse(string word) { 
            if(word.size()==1) return true;
            string high,low,other;
            for(int i=0;i<word.size();i++)
            { 
                high+=toupper(word[i]);
                low+=tolower(word[i]);
                if(i==0) other+=toupper(word[i]);
                else other+=tolower(word[i]);
            }
            return word==high||word==low||word==other;
        }
    };

1.  最长特殊序列  
    给你两个字符串，请你从这两个字符串中找出最长的特殊序列。  
    「最长特殊序列」定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。  
    子序列 可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。  
    输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。

**没有意义+1**

class Solution { 
    public:
    	int findLUSlength(string a, string b) 
    	{ 
    		return a == b ? -1 : (a.size() > b.size() ? a.size() : b.size());
    	}
    };

1.  最长特殊序列2  
    给定字符串列表，你需要从它们中找出最长的特殊序列。最长特殊序列定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。子序列可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。输入将是一个字符串列表，输出是最长特殊序列的长度。如果最长特殊序列不存在，返回 -1 。

**和上题类似，先按长度排序，然后比较，不是子串则返回长度最长的那个**

class Solution { 
    public:
        bool isSub(string s, string t){ 
            int p = 0;
            for(int i = 0; i < t.length(); i++){ 
                if(t[i] == s[p]){ 
                    p++;
                }
            }
            return p == s.length();
        }
        static bool cmp(string a, string b){ 
            return a.length() > b.length();
        }
        int findLUSlength(vector<string>& strs) { 
            int n = strs.size();
            int cnt = 0;
            sort(strs.begin(), strs.end(), cmp);
            for(int i = 0; i < n; i++){ 
                for(int j = 0; j < n; j++){ 
                    if(!isSub(strs[i], strs[j])){ 
                        cnt++;
                    }
                }
                if(cnt == n-1) return strs[i].length();
                cnt = 0;
            }
            return -1;
        }
    };

1.  连续的子数组和  
    给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n\*k，其中 n 也是一个整数。

**用前缀和保存从i到j的和，然后双指针滑动即可**

class Solution { 
    public:
        bool checkSubarraySum(vector<int>& nums, int k) 
        { 
            int n = nums.size();
            if (n == 0) return true;
            if (k == 0) 
            { 
                for (int i = 1; i < n; i++) { 
                    if (nums[i - 1] == nums[i]&& nums[i] == 0) { 
                        return true;
                    }
                }
                return false;
            }
    
            int left = 0, right = 0;
    
            vector<int> sum(n, 0);
            sum[0] = nums[0];
            for (int i = 1; i < n; i++)
            { 
                sum[i] += sum[i - 1] + nums[i];
            }
    
            while (left <= right)
            { 
                if (left == 0)
                { 
                    if ( right >= 1 && sum[right] % k == 0)
                        return true;
                }
                else if ((right - left >= 1) && (sum[right] - sum[left - 1]) % k == 0)
                    return true;
    
                right++;
                if (right >= n)
                { 
                    left++;
                    if (left == n)
                        break;
                    right = left;
                }
            }
    
            return false;
        }
    };

1.  通过删除字母匹配字典里最长单词  
    给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

**先写一个查找子串的函数，然后挨个找一遍，短的直接跳过不看，长的按字母序比较取小的**

class Solution 
    { 
    private:
        bool isSubStr(string target, string s)
        {    
            //分别从左端开始索引，检测是否为子列
            int i = 0, j = 0;
            while (i < target.size() && j < s.size())
            { 
                if (target[i] == s[j])
                    i++;
                j++;  
            }
            return i == target.size();
        }
    
    public:
    
        string findLongestWord(string s, vector<string>& d) 
        { 
            string str = "";
            for (int i = 0; i < d.size(); i++)
            { 
                int tag = str.length();
                int leng = d[i].length();
                //若字符串更短或者一样长且字母顺序较大的直接舍去
                if (tag > leng || (tag == leng && str.compare(d[i]) < 0))
                    continue;
                
                if (isSubStr(d[i], s))
                { 
                    str = d[i];
                }
            }
            return str;
        }
    };

1.  连续数组  
    给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。

**本题关键点：  
1.使用一个哈希表存储到目前为止的和cnt和对应的索引  
2. 0由-1代替，计算和为0的情况  
3. 如果已经存过cnt, index，下次遇到不存储  
4. 如果遇到两次相同的cnt，则表示两次中间的0和1数量相等。但是必须保存一个初始值(0, -1)，不然第一次遇到和为0的情况无法正确使用相对距离求出长度**

class Solution 
    { 
        std::unordered_map<int, int> m_map;
    public:
        int findMaxLength(vector<int>& nums) 
        { 
            int ret = 0, cnt = 0; 
            m_map[0] = -1;
            
            for (int i = 0; i <nums.size(); i++)
            { 
                cnt += (nums[i] == 0 ? -1 : 1);
    
                if (m_map.count(cnt) == 0)
                { 
                    m_map[cnt] = i;
                }
                else
                { 
                    ret = max(ret, i - m_map[cnt]);
                }
            }
    
            return ret;
        }
    };