当前位置:   article > 正文

力扣——程序员面试金典109题刷题笔记1(数组与字符串)_程序员 经典题 优化查字典

程序员 经典题 优化查字典

先从力扣——程序员面试金典109题开始刷,链接如下:
程序员面试金典109题

面试题 01.01. 判定字符是否唯一

//直接暴力双重for循环
class Solution {
public:
    bool isUnique(string astr) {
        if(astr.length()==0 || astr.length()==1){
            return true;
        }
        for(int i=0; i<astr.length(); i++){
            for(int j=i+1; j<astr.length(); j++){
                if(astr[i] == astr[j])
                    return false;
            }
        }
        return true;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
//这里看到的另外一种方法,主要是使用到C++中的find和rfind两个函数
class Solution {
public:
    bool isUnique(string astr) {
        for(int i=0; i<astr.size();i++){
            if(astr.find(astr[i])!=astr.rfind(astr[i])){
                return false;
            }
        }
        return true;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

这里码一个比较全的字符串相关函数,方便后续学习!
字符串相关函数

//看到评论有这样一段,可以作为思考
如果我是面试官,会考虑主要考察什么,就我的工作经验看,大多数主要是招聘工程师的,
面试者如果什么问题都没有,直接写个二重循环搞定,会首先给个50分,如果能写点判断字符串是否为null的,60分。

直接上手什么bitset,什么位运算的,我会先问他,题目中有没有交代字符串的字符一定是26个英文字母?
如果是unicode环境,你是不是要准备2^16/8个字节的空间?
在实际项目中,风险可控,结果可期更重要,绝大多数时候不在乎那点时间和资源。

所以我期望面试者不要急于解答,我希望他先问我问题:

字符串的字符范围,如果我告诉他,26个小写英文字母,那可能一开头直接判断如果字符长度>26, 直接返回False,做到这一点的,80分
如果我告诉他ascii字符集,然后他的代码里有边界检查,并且针对不同的范围有不同的侧重点,
比如说ascii字符集,那也就是128个可能性,16个字节的位运算比较好
如果我告诉他是unicode,没有字符范围,老老实实排序再判断是比较符合我对工程师的要求的,
因为算法性能稳定,没有额外资源要求,一眼看出没什么不可预见的风险,100分。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

面试题 01.02. 判定是否互为字符重排

//排序再比较
class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        sort(s1.begin(),s1.end());
        sort(s2.begin(),s2.end());
        if(s1==s2){
            return true;
        }
        return false;
    }
};

//贴一下排序方式
升序:sort(begin,end,less<data-type>());
降序:sort(begin,end,greater<data-type>()).
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
//很多题都涉及到了ASCII码来做,可以关注学习一下
class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        int ascii[128] = {0};
        int len1 = s1.size();
        int len2 = s2.size();
        if(len1!=len2)
            return false;
        for(int i=0;i<len1;i++) {
            ascii[s1[i]]++;
            ascii[s2[i]]--;
        }
        for(int i=0;i<128;i++)
            if(ascii[i]!=0)
                return false;
        return true;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

面试题 01.03. URL化

URL化。编写一种方法,将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符,并且知道字符串的“真实”长度。

示例 1:
输入:"Mr John Smith    ", 13
输出:"Mr%20John%20Smith"
示例 2:
输入:"               ", 5
输出:"%20%20%20%20%20"
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
class Solution {
public:
    string replaceSpaces(string S, int length) {
        int pos = S.size()-1;
        for(int i= length-1; i>=0; i--){
            if(S[i] == ' '){
                S[pos--] = '0';
                S[pos--] = '2';
                S[pos--] = '%';
            }
            else{
                S[pos--] = S[i];
            }
        }
        return S.substr(pos+1);
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
substr有2种用法:
假设:string s = "0123456789";
string sub1 = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾:sub1 = "56789"
string sub2 = s.substr(5, 3); //从下标为5开始截取长度为3位:sub2 = "567"

  • 1
  • 2
  • 3
  • 4
  • 5

面试题 01.04. 回文排列

给定一个字符串,编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词.

示例1:
输入:"tactcoa"
输出:true(排列有"tacocat""atcocta",等等)
  • 1
  • 2
  • 3
class Solution {
public:
    bool canPermutePalindrome(string s) {
        int ascii[128] = {0};
        int len1 = s.size();
        int flag1 = 0, flag2 = 0;

        for(int i=0;i<len1;i++) {
            ascii[s[i]]++;
        }
        for(int i=0;i<128;i++){
            if(ascii[i]%2 == 0)
                flag1++;
            else
                flag2++;
        }
        if(flag2 > 1)
            return false;
        else
            return true;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

面试题 01.05. 一次编辑

字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串,编写一个函数判定它们是否只需要一次(或者零次)编辑。

示例 1:
输入: 
first = "pale"
second = "ple"
输出: True
 
示例 2:
输入: 
first = "pales"
second = "pal"
输出: False
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
class Solution {
public:
    bool oneEditAway(string first, string second) {
        int s1 = first.size();
        int s2 = second.size();
        if(abs(s1-s2) > 1)
            return false;
        if(s1 < s2)
            return oneEditAway(second, first);
        for(int i = 0, flag =0;i < s1; i++){
            if(first[i] != second[i - (s1 - s2)*flag] && ++flag >1){
                return false;
            }
        } 
        return true;

    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

这里主要就是判断更改的距离是否大于1,如果小于等于1,那么跳过那个位置其它应该是相等的。

面试题 01.06. 字符串压缩

字符串压缩。利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。比如,字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短,则返回原先的字符串。你可以假设字符串中只包含大小写英文字母(a至z)。

字符串压缩。利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。比如,字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短,则返回原先的字符串。你可以假设字符串中只包含大小写英文字母(a至z)。

示例1:
 输入:"aabcccccaaa"
 输出:"a2b1c5a3"
示例2:
 输入:"abbccd"
 输出:"abbccd"
 解释:"abbccd"压缩后为"a1b2c2d1",比原字符串长度更长。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
class Solution {
public:
    string compressString(string S) {
        string res;
        int cnt = 1;
        for(int i = 0; i < S.size(); i++){
            if (i != S.size() - 1 && S[i] == S[i+1]){
                cnt++;
                continue;
            }
            res.push_back(S[i]);
            res.append(to_string(cnt));
            cnt = 1;
        }
        return res.size() >= S.size() ? S : res;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

这道题要注意题目题目说的,要满足压缩后的字符数小于未压缩的,所以要加一个判断。

面试题 01.07. 旋转矩阵

给你一幅由 N × N 矩阵表示的图像,其中每个像素的大小为 4 字节。请你设计一种算法,将图像旋转 90 度。
不占用额外内存空间能否做到?

示例 1:
给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],
原地旋转输入矩阵,使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

示例 2:
给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 
原地旋转输入矩阵,使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        reverse(matrix.begin(), matrix.end());
        for(int i=0; i<matrix.size(); i++){
            for(int j=i+1; j<matrix[0].size(); j++){
                swap(matrix[i][j],matrix[j][i]);
            }
        }
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

C++ reverse函数的用法
reverse函数功能是逆序(或反转),多用于字符串、数组、容器。头文件是 #include < algorithm >
reverse函数用于反转在[first,last)范围内的顺序(包括first指向的元素,不包括last指向的元素),reverse函数无返回值

string str="hello world , hi";
reverse(str.begin(),str.end());//str结果为 ih , dlrow olleh
vector<int> v = {5,4,3,2,1};
reverse(v.begin(),v.end());//容器v的值变为1,2,3,4,5
  • 1
  • 2
  • 3
  • 4

面试题 01.08. 零矩阵

编写一种算法,若M × N矩阵中某个元素为0,则将其所在的行与列清零。

示例 1:
输入:
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出:
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2:
输入:
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出:
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int flag_col0 = false;
        for (int i = 0; i < m; i++) {
            if (!matrix[i][0]) {
                flag_col0 = true;
            }
            for (int j = 1; j < n; j++) {
                if (!matrix[i][j]) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][0] || !matrix[0][j]) {
                    matrix[i][j] = 0;
                }
            }
            if (flag_col0) {
                matrix[i][0] = 0;
            }
        }
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

使用一个标记变量记录第一列是否原本存在 0。这样,第一列的第一个元素即可以标记第一行是否出现 0。但为了防止每一列的第一个元素被提前更新,我们需要从最后一行开始,倒序地处理矩阵元素。

复杂度分析
时间复杂度:O(mn),其中 mm 是矩阵的行数,nn 是矩阵的列数。我们至多只需要遍历该矩阵两次。
空间复杂度:O(1)。我们只需要常数空间存储若干变量。

面试题 01.09. 字符串轮转

字符串轮转。给定两个字符串s1和s2,请编写代码检查s2是否为s1旋转而成(比如,waterbottle是erbottlewat旋转后的字符串)。

示例1:

 输入:s1 = "waterbottle", s2 = "erbottlewat"
 输出:True
示例2:

 输入:s1 = "aa", s2 = "aba"
 输出:False

提示:
字符串长度在[0, 100000]范围内。
说明:
你能只调用一次检查子串的方法吗?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        if (s1.size() != s2.size()) {
            return false;
        }
        string s = s2 + s2;
        return s.find(s1) != string::npos;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

这里用到了array_contains(Array, value)函数

返回结果:如果Array中包含value,则返回True,否则返回False

返回类型:boolean

select array_contains(array(1, 2), 3);  -- 结果为 false
select array_contains(array('A', 'B', 'C'), 'A');  -- 结果为 true
  • 1
  • 2
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/146063
推荐阅读
相关标签
  

闽ICP备14008679号