算法刷题(七):LC中级算法(数组和字符串)

 

文章目录

 

三数之和

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

示例 2:

输入:nums = []
输出:[]

示例 3:

输入:nums = [0]
输出:[]

提示:

0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvpj16/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


思路:
两数和的双指针法熟悉吗?开头一个指针,末尾一个指针,头尾加起来大于0,说明太大,末尾后退;头尾加起来小于0,说明太小,开头前进;加起来刚好等于0,那就存起来,头尾都靠近一位。

那么现在是三指针,其实也好办,开头一个标志位,则以标志位后面一位为两数和中的头,尾不变,一轮走完之后标志位后移一位,以此类推、

这里需要注意去重,如果标志位和前一位一样,则标志位再后移一位。
如果“头指针”的值和前面一位相同,则再前进一位。
如果“尾指针”的值和前面一位相同,则再后退一位。


代码实现:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        int num = nums.size(); 
        sort(nums.begin(),nums.end());
        if(nums.empty() || nums.front()>0 || nums.back()<0)
            return {};
        for(int i = 0;i<num-2;i++){
            if(nums[i]>0) break;
            if(i>0&&nums[i] == nums[i-1]) continue;
            int head = i+1;
            int tail = num-1;
            while(head<tail){
                if(nums[head]+nums[tail] == -nums[i]){
                    if(head == i+1 || tail == num-1){
                        result.push_back(vector<int>{nums[i],nums[head],nums[tail]});
                        head++;tail--;
                    }
                    else if(nums[head] == nums[head-1]){
                        head++;
                    }
                    else if(nums[tail] == nums[tail+1]){
                        tail--;
                    }
                    else{
                        result.push_back(vector<int>{nums[i],nums[head],nums[tail]});
                        head++;tail--;
                    }
                }
                else if(nums[head]+nums[tail]<-nums[i]){
                    head ++;
                }
                else{
                    tail--;
                }
            }
        }
        return result;
    }
};

矩阵置零

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

进阶:

一个直观的解决方案是使用  O(mn) 的额外空间,但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗?

示例 1:
算法刷题(七):LC中级算法(数组和字符串)

输入:matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[1,0,1],[0,0,0],[1,0,1]]

示例 2:

算法刷题(七):LC中级算法(数组和字符串)

输入:matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示:

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/set-matrix-zeroes
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


思路:
这个思路相对简单一些,遇到0就把那一行和那一列的非0元素置为INT_MIN,等都处理完之后,就把INT_MIN置为0。

代码实现:

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> row(m), col(n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!matrix[i][j]) {
                    row[i] = col[j] = true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};


字母异位词分组

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明:

所有输入均为小写字母。
不考虑答案输出的顺序。

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvaszc/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


思路:
那这个思路其实也很简单的了,将字符串排序之后作为主键,为排序字符串作为值,插入哈希表中。

然后遍历取出。

那这个思路不是很简单的呢?

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {
        vector<vector<string>> res;
        map<string,vector<string>> vec;
        if(strs.empty()) return res;
        for(int i=0;i<strs.size();i++)
        {
            string temp=strs[i];
            sort(temp.begin(),temp.end());
            vec[temp].push_back(strs[i]);
        }
        map<string,vector<string>>::iterator it;
        for(auto it=vec.begin();it!=vec.end();it++)
        {
            res.push_back(it->second);
        }
        return res;
    }
};

无重复字符的最长子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

示例 4:

输入: s = ""
输出: 0

提示:

0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xv2kgi/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


思路:
用一个标志数组来标志当前已遍历到那些字符串,并记录一个当前最长长度,与一个遍历长度。。

当出现重复字符的时候,回溯到上一个出现该字符的地方,将遍历长度减去回溯长度,继续遍历。

看代码吧:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

	    if (s.size() == 0)
	        return 0;
	    
	    int max_flag = 0;   //最大字符串长度
	    int max_new = 0;    //本次遍历字符串长度
	    int keep_site = 0;  //本次字符串开始位置
	    bool flag[255] = { false };
	
	    for (char c : s) {
	        if (!flag[c]) {
	            flag[c] = true;
	            max_new++;
	        }
	        else {
	            int temp = 0;
	            for (;; ) {
	
	                temp++;
	                
	                if (s[keep_site] == c) {
	                    keep_site++;
	                    break;
	                }
	
	                //将途中字符修正回来
	                if (flag[s[keep_site]])
	                    flag[s[keep_site]] = false;
	
	                keep_site++;
	            }
	            max_new = max_new - temp + 1;
	        }
	        max_flag = max(max_flag, max_new);
	            
	    }
	    return max_flag;
	}
};

先刷到这里,后面两题:最长回文子串,和递增三元组,思路不是很清晰。。。

 

上一篇:Linix学习一


下一篇:硬件基础04 - 电感