首页 > 编程学习 > 按照题型

按照题型

发布时间:2022/5/14 19:01:51

在做题之前,先考虑边界(数组为空的情况,直接结束)。

数组

1.hash

需要对数组两层枚举:一层枚举,另外一层用map实现的hash,考虑一下是否可以边枚举边构造map,一旦遇到结果直接退出,这样可以减少时间。

2.双指针

使用之前看先排序能否减少复杂度。

3.矩阵转换类

4.dfs

求子序列

5.特殊矩阵

/*
如果一个矩阵从上往下,从左往右依次递增,查找元素的话可以从左下角元素(或者右上角)坐标开始,这两个位置比较特殊。以左下角为例,如果该元素大于当前元素j++,如果小于该元素i--,直到找到该元素
*/
//变换得到某个矩阵
先在纸上画一下转置后的,与题目比对一下看能否发现什么

6.其他

在一个有序的序列中找和为m的两个元素,i从0枚举,j从最后一个元素枚举,如果和小于m则i++,否则j–,直到不满足i<j为止。需要注意i和j的移动是不同步的。


字符串

1.先排序

字符串异位词(类似eat aet)匹配,可以先排序,然后建立一个
map<string, vector> mp,以排序后的值作为键值。

2.dfs

比如:写出n对匹配的括号,每个位置有两种选择’(‘和’)’,选择’('参数+1,否则-1,剪枝可以根据<0剪枝,<0说明已经发生了匹配,不用继续往下一层搜索了。

2.滑动窗口

/*给定一个字符串s和一些长度相同的单词words。找出s中恰好可以由words中所有单词串联形成的子串的起始位置,注意不考虑顺序(leetcode 30)*/
可以用words.size()*words[0].size()作为滑动窗口,在统计的时候可以把words[i]作为一个单位,定义map<string, int>来统计是否和<words[i], 1>相等

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





解法:初始化left=right=0,滑动窗口内的全是不重复的字符,如果right指向的字符出现在了滑动窗口中,就把left指向滑动窗口中重复那个单词的后一个位置,同时更新重复元素的hash值。
难点:滑动窗口怎么维护?
可以用map保存right出现的所有单词,出现在滑动窗口判断方法:
hash.find(s[right]) != hash.end() && hash[s[right]] >= left
第二个条件为了保证重复的单词出现在了滑动窗口里面而不是left左边。如果重复了,更新left的位置:
left = hash[s[right]] + 1;
再更新map:
hash[s[right]] = right;

3.子串

//回文子串
求最长的回文子串:从左依次遍历字符串,根据回文的特点,要么个数是奇数要么是偶数,不断更新最大值,以及result子串。
huiwen(i, i, s);  //奇数个数,以元素i为中心
huiwen(i, i+1, s);  //偶数个数,以元素i 和 i+1为中心

/*给定一个字符串s ,计算具有相同数量0和1的非空(连续)子字符串的数量,并且这些子字符串中的所有0和所有1都是组合在一起的。重复出现的子串要计算它们出现的次数。
输入: "00110011"
输出: 6
解释:有6个子串具有相同数量的连续1和0:“0011”, “01”,
“1100",“10”, “0011和“01”。
请注意,一些重复出现的子串要计算它们出现的次数。
另外,“00110011"不是有效的子串,因为所有的0 (和1)没有组合在一起
*/
思路:从该元素是否可以作为结尾考虑记录下相同字母出现的个数,如果前一个字母出现的个数大于等于当前字母出现的个数,则说明只存在一种以当前元素结尾的情况,此时+1,整个算法从前往后遍历一遍即可。
class Solution {
public:
    int countBinarySubstrings(string s) {
        //pre记录前面一组的个数,cur记录当前个数
        int pre = 0, cur = 1, total = 0;
        for (int i = 1; i < s.length(); i++){
            if (s[i] == s[i - 1]) cur++;
            else{
                pre = cur;
                cur = 1;
            }
            if (pre >= cur) {
                total++;
            }
        }
        return total;
    }
};

5.其他

int最大值表示:~(1<<31)
int最小值表示:(1<<31)

//去除字符串的所有空格
 while (true){
     if (s.find(" ") != string::npos) {
         s.erase(s.find(" "), 1);
     }else break;
 }




//对中缀表达式求解
step1:先构造2个栈,一个data,一个fuhao
step2:从左向右扫描表达式:
	如果是操作数,直接入data栈
	如果是左括号,直接入fuhao栈
	如果是右括号,不断出栈fuhao里面的元素,直到出栈一个左括号未知,每出栈一个元素,data就弹出来两个数,先弹出来的在右边,后弹出来的在左边进行运算,结果放到data栈顶。
	如果是操作符,如果大于fuhao栈顶运算符的优先级入栈,否则不断出栈直到可以入栈为止,每出栈一个操作符,就做上面的运算。
step3:扫描完以后,如果fuhao栈内还有元素就不断出栈,进行上面的运算,最后data栈剩下的元素就是运算结果了。

Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000