leetcode数组常见面试算法题

发表于 | 更新于: | 分类于 | | 本文被围观了 次
数组常见面试算法题

什么叫ARTS？

每周完成一个ARTS：

  1. Algorithm：每周至少做一个 leetcode 的算法题
  2. Review：阅读并点评至少一篇英文技术文章
  3. Tip：学习至少一个技术技巧
  4. Share：分享一篇有观点和思考的技术文章

作者：陈皓
链接：https://www.zhihu.com/question/301150832/answer/529809529
来源：知乎

Reverse String

翻转字符串char[]，O(1)空间复杂度。

1
2
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
方法一
  1. 从数组的头尾同时遍历，交换方法为a=a^b;b=a^b;a=a^b;
  2. 如果中间还剩一个，就不处理。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void reverseString(vector<char>& s) {
        if(s.size()<=1)
            return;
        for(int i=0,j=s.size()-1;i<j;i++,j--) {
            s[i]=s[i]^s[j];
            s[j]=s[i]^s[j];
            s[i]=s[i]^s[j];
        }
    }
};
方法二
  1. 直接调用算法
1
2
3
4
5
6
class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(), s.end());
    }
};

Reverse Integer

32位有符号整形，将数字部分颠倒，如果颠倒后异常，需要处理为0。

1
2
Input: -123
Output: -321
方法一
  1. 需要依次取出各位至数组中。
  2. 然后采用算法颠倒。
  3. 再依次打包成整数，如果溢出，再进行处理。如果a*b>max，则有a>max/b。
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
class Solution {
public:
    bool isOverFlow(int a, int b) {
        if(a>0 && b>0) 
            return (INT_MAX-a)/10<b;
        else if(a<0 && b<0)
            return (INT_MIN-a)/10>b;
        else 
            return false;
    }
    
    int reverse(int x) {
        vector<int> temp;
        int y=0;
        while(x/10) {
            temp.push_back(x%10);
            x/=10;
        }
        temp.push_back(x%10);
        for(int i=0;i<temp.size();i++) {
            if(isOverFlow(temp[i], y))
                return 0;
            y=y*10+temp[i];
        }
        return y;
    }
};
方法二
  1. 依次取个位的数，同时将这个数放在最高位组合出倒数，一次循环完成。
  2. 在循环的过程中，不断检测是否会溢出，如果即将溢出，则直接返回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
class Solution {
public:
    bool isOverflow(int a, int b) {
        if(a>0 && b>0) {
            return a>(INT_MAX-b)/10;
        } else if(a<0 && b<0) {
            return a<(INT_MIN-b)/10;
        } else {
            return false;
        }
    }
    
    int reverse(int x) {
        int res=0;
        while(x) {
            int tmp=x%10;
            if(isOverflow(res, tmp))
                return 0;
            res=res*10+tmp;
            x/=10;
        }
        return res;
    }
};

First Unique Character in a String

给一个字符串，找到第一个不是重复的字母，给出地址，在字符串只考虑小写字母的前提下。

1
2
3
4
5
s = "leetcode"
return 0.

s = "loveleetcode",
return 2.
方法一
  1. 从前往后依次将字母存入int数组[26]，index为字母，value为个数，由于个数可能有很多，得用int数组才行。
  2. 将字符串套入数组检查，找到只出现一次的第一个字母，即value==1，此时的i为地址。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int firstUniqChar(string s) {
        array<int, 26> freq;
        freq.fill(0);
        for(int i=0;i<s.length();i++) {
            freq[s[i]-'a']++;
        }
        for(int i=0;i<s.length();i++) {
            if(freq[s[i]-'a']==1)
                return i;
        }
        return -1;
    }
};
方法二
  1. 从前往后依次存入unordered_map，key为字母，value为个数。
  2. 将字符串套入map中检查，找到只出现一次的第一个字母，map的value==1，此时的i为地址。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> freq;
        for(int i=0;i<s.length();i++) {
            freq[s[i]]++;
        }
        for(int i=0;i<s.length();i++) {
            if(freq[s[i]]==1)
                return i;
        }
        return -1;
    }
};
方法三

优化点思考，第二轮查找第一个单数的时候不需要重新遍历字符串了，直接遍历更新的字典找到第一个单数。

  1. 遍历字符串，更新字典，包括是哪个字符、字符的位置、字符出现的次数。需要用到pair<int, int>
  2. 遍历字典，找到字符出现次数等于1且字符的位置最小的那个位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char,pair<int,int>> dic;
        int index=s.length();
        for(int i=0;i<s.length();i++) {
            dic[s[i]].first=i;
            dic[s[i]].second++;
        }
        for(auto& x: dic) {
            if(x.second.second==1)
                index=index<x.second.first?index:x.second.first;
        }
        if(index==s.length())
            return -1;
        return index;
    }
};

Valid Anagram

判断s是否为t的同字母异序词

1
2
Input: s = "anagram", t = "nagaram"
Output: true
方法一
  1. 依次遍历字符串s，建立int[26]数组，存入的是该遍历到的字符个数。
  2. 再依次遍历字符串t，检索之前建立的数组，判断遍历到的该字符是否个数为0，否则不是同字母异序词，如果大于0，直接做减减处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length()!=t.length())
            return false;
        array<int, 26> freq;
        freq.fill(0);
        for(int i=0;i<s.length();i++) {
            freq[s[i]-'a']++;
        }
        for(int j=0;j<t.length();j++) {
            if(freq[t[j]-'a'])
                freq[t[j]-'a']--;
            else
                return false;
        }
        return true;
    }
};
方法二
  1. 依次遍历字符串s，建立字典，存入的是该遍历到的字符个数。
  2. 再依次遍历字符串t，检索之前建立的字典，判断遍历到的该字符是否个数为0，否则不是同字母异序词，如果大于0，直接做减减处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length()!=t.length())
            return false;
        unordered_map<int,int> freq;
        for(int i=0;i<s.length();i++) {
            freq[s[i]]++;
        }
        for(int j=0;j<t.length();j++) {
            if(freq[t[j]])
                freq[t[j]]--;
            else
                return false;
        }
        return true;
    }
};

Valid Palindrome

判断字符串是否为回文，假设字符串仅考虑由字母数字组成，忽略大小写，假设空字符为回文。

1
2
Input: "A man, a plan, a canal: Panama"
Output: true
方法一
  1. 双指针方案，从头和从尾依次遍历并对比，出现不同则退出。
  2. 怎么去掉空格，判断大小写，去掉其他符号，注意全都是其他字符串的情况或直接用isalnum函数。
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
30
31
32
33
class Solution {
public:
    char getValue(char& c) {
        if(c>=48 && c<=57)
            return c;
        else if(c>=65 && c<=90) {
            return c;
        } else if(c>=97 && c<=122) {
            return c-32;
        } else 
            return 0;
    }
    
    bool isPalindrome(string s) {
        int len=s.length();
        if(len==0)
            return true;
        for(int i=0,j=len-1;i<j;i++,j--) {
            char a=getValue(s[i]);
            while(a==0&&i<j) {
                a=getValue(s[++i]);
            }
            char b=getValue(s[j]);
            while(b==0&&i<j) {
                b=getValue(s[--j]);
            }
            if(a!=b) {
                return false;
            }
        }
        return true;
    }
};
方法二
  1. 同样是双指针方法，只是写法不同，先找到alnum字符，采用while if结构，如果不是alnum字符，则进入循环，再查找，只有同时满足时，才进行对比。
  2. 进行对比，不同则退出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isPalindrome(string s) {
        int len=s.length();
        if(len==0)
            return true;
        int i=0, j=len-1;
        while(i<j) {
            if(!isalnum(s[i])) {
                i++;
            } else if(!isalnum(s[j])) {
                j--;
            } else {
                if(tolower(s[i])!=tolower(s[j]))
                    return false;
                i++;
                j--;
            }
        }
        return true;
    }
};

String to Integer (atoi)

将字符串转换为数字，如果首部有空格则忽略，其他非数字字符，则返回0，末尾含有字母则忽略，需要考虑负数，数字范围为[−231, 231 − 1]。

1
2
3
4
5
6
7
8
9
10
11
Input: "   -42"
Output: -42
  
Input: "4193 with words"
Output: 4193
  
Input: "words and 987"
Output: 0
  
Input: "-91283472332"
Output: -2147483648
方法一
  1. 从头遍历字符串，如果发现有空格则跳过，如果发现时正负符号，则赋给符号变量。
  2. 再接着遍历，只对数字进行处理，同时计算数值大小（提前计算是否溢出，如果溢出了，边界值应该怎么给），如果发现有非数字字符，则退出遍历，返回计算结果。
  3. 难点：判断是非溢出，及其处理措施？如果a>=0,b>=0，则a*10+b>INT_MAX转化为a>(INT_MAX-b)/10；如果a<0,b<=0(一定要包括0)，则a*10+b<INT_MIN转化为a<(INT_MAIN-b)/10；对于没有溢出的情况计算结果为a=a*10+b.
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    bool overFlowValue(int& a, int b) {
        if(a>=0 && b>=0 && a>(INT_MAX-b)/10) {
            a = INT_MAX;
            return true;
        } else if(a<0 && b<=0 && a<(INT_MIN-b)/10) {
            a = INT_MIN;
            return true;
        } else {
            a = a*10+b;
            return false;
        }
    }
    
    int myAtoi(string str) {
        int flag=1, value=0, got=0;
        for(int i=0;i<str.length();i++) {
            if(got && (str[i]==43 || str[i]==45 || str[i]==32))
                break;
            if(!got && str[i]==32)
                continue;
            if(!got && str[i]==43) {
                got=1;
                continue;
            } else if(!got && str[i]==45) {
                got=1;
                flag=-1;
                continue;
            }
            if(flag==-1 && value>0)
                value*=-1;
            if(str[i]>=48 && str[i]<=57) {
                got=1;
                if(overFlowValue(value, (str[i]-48)*flag)) {
                    break;
                }
            } else {
                break;
            }
        }
        return value;
    }
};
方法二
  1. 对前缀进行完善，空格分while循环进行判断，正负号只判断一次，最后再进行数字判断。
  2. 对溢出部分进行完善，如何判断a*10+b>INT_MAX？
  3. a*10>INT_MAX
  4. a*10==INT_MAX && b>INT_MAX%10
  5. 针对以上两种情况，如果符号位为正，则返回INT_MAX，如果符号位为负，则返回INT_MIN。比如[-10,9]，当取直为10时，10>9，如果是负数，返回-10，如果是正数，返回9.
  6. 其他情况，返回a*10+b
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:
    int myAtoi(string str) {
        int flag=1, value=0;
        int i=0;
        while(str[i]==' ') i++;
        if(str[i]=='-') {
            flag=-1;
            i++;
        } else if(str[i]=='+') {
            i++;
        }
        for(;i<str.length();i++) {
            if(str[i]>='0' && str[i]<='9') {
                if(value>INT_MAX/10 ||(value==INT_MAX/10 && str[i]-'0'>(INT_MAX%10))) {
                    if(flag==1)
                        return INT_MAX;
                    else
                        return INT_MIN;
                }
                value=value*10+(str[i]-'0');
            } else {
                break;
            }
        }
        return value*flag;
    }
};

Implement strStr()

找到当前字符串在另外一个字符串中出现的位置，空字符串按照0处理，找不到返回-1。

1
2
3
4
5
Input: haystack = "hello", needle = "ll"
Output: 2
  
Input: haystack = "aaaaa", needle = "bba"
Output: -1
方法一
  1. 两个字符串都从0开始遍历，同时进行比较，如果比较有相同字符，则needle指针加加，如果没有相同字符，则needle置0，haystack指针回退到刚开始对比的下一个位置（重要）。
  2. 如果任意一个遍历完，则退出，如果是needle遍历完，还要返回haystack的指针位置-needle长度的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.length()==0)
            return 0;
        for(int i=0,j=0;i<haystack.length();) {
            if(haystack[i]==needle[j]) {
                j++;
                i++;
                if(j==needle.length())
                    return i-j;
            } else {
                i=i-j+1;
                j=0;
            }
        }
        return -1;
    }
};
方法二
  1. 使用两个while循环结构，这样就不需要特意进行回退了，但是时间复杂度变大了。
  2. 两个字符串都从0开始遍历，均在内循环进行，同时进行比较，如果有相同的字符，则内循环加加，否则退出内循环。
  3. 如果外循环遍历完，则退出，如果内循环遍历完，则当前的外循环位置即为需要的地址。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.length()==0)
            return 0;
        for(int i=0;i<haystack.length();i++) {
            for(int j=0;j<needle.length();j++) {
                if(haystack[i+j]!=needle[j])
                    break;
                if(j==needle.length()-1)
                    return i;
            }
        }
        return -1;
    }
};

Count and Say

count-and-say序列是整数序列，前五个术语如下：

1
2
3
4
5
1.     1
2.     11
3.     21
4.     1211
5.     111221

第二个数：一个1，第三个数，两个1，第四个数，一个2，一个1，第五个数，一个1，一个2，两个1.

给出5，要求返回111221.

方法一
  1. 从原始字符串前面开始遍历，个数++，遇到不同的数或者原始字符串末尾，则将上一个字符出现的次数以及是哪个字符添加的新字符串末尾。
    1. 如果只是不同的数，清空个数。
    2. 如果遇到末尾，则将新字符串赋值给原字符串，并清空新字符串／个数，最后退出遍历。
  2. 依次递归到第n个，返回此时的字符串。
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
30
class Solution {
public:
    string countAndSay(int n) {
        string oldRes="1";
        string newRes="";
        if(n==1)
            return oldRes;
        int num=0;
        for(int x=1;x<n;x++) {
            for(int i=0;i<oldRes.length();i++) {
                num++;
                if(i<oldRes.length()-1 && oldRes[i]!=oldRes[i+1]) {
                    newRes.append(to_string(num));
                    newRes.push_back(oldRes[i]);
                    num=0;
                    continue;
                }
                if(i==oldRes.length()-1) {
                    newRes.append(to_string(num));
                    newRes.push_back(oldRes[i]);
                    num=0;
                    oldRes=newRes;
                    newRes.clear();
                    break;
                }
            }
        }
        return oldRes;
    }
};
方法二
  1. 优化点：for循环可以转化为while循环
  2. 将赋值的部分提取出来，关键在于怎么找到变化的临界点或者字符串的末尾，只要任意一个不满足就表明是边界了，故用&&语句比较合适。
  3. 使用+语句，减少语句。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string countAndSay(int n) {
        if(n==0)
            return "";
        if(n==1)
            return "1";
        string oldStr="1";
        string newStr;
        while(--n) {
            newStr="";
            for(int i=0,num;i<oldStr.length();i++) {
                num=1;
                while(i<oldStr.length()-1 && oldStr[i]==oldStr[i+1]) {
                    i++;
                    num++;
                }
                newStr+=to_string(num)+oldStr[i];
            }
            oldStr=newStr;
        }
        return oldStr;
    }
};

Longest Common Prefix

找出字符串数组的共有前缀：

1
2
Input: ["flower","flow","flight"]
Output: "fl"
方法一
  1. 设置公共前缀str为第一个字符串。
  2. 再str与下一个进行对比，更新公共str。
  3. 直到对比完所有字符串。
  4. 如果发现str为空，直接退出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0)
            return "";
        string str=strs[0];
        for(int i=1;i<strs.size();i++) {
            int j=0;
            while(j<str.length() && str[j]==strs[i][j]) {
                j++;
            }
            str=str.substr(0, j);
        }
        return str;
    }
};
方法二
  1. 先对数组进行长度的排序。
  2. 只对第一个和最后一个进行对比，找出公共部分即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0)
            return "";
        sort(strs.begin(), strs.end());
        int i=0;
        while(i<strs[0].length() && strs[0][i]==strs[strs.size()-1][i]) {
            i++;
        }
        return strs[0].substr(0,i);
    }
};
nephen wechat
欢迎您扫一扫上面的微信公众号，订阅我的博客！
坚持原创技术分享，您的支持将鼓励我继续创作！