leetcode刷面试题(面试题01合集)

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

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：

输入: s = “leetcode”
输出: false
示例 2：

输入: s = “abc”
输出: true
限制：

0 <= len(s) <= 100
如果你不使用额外的数据结构，会很加分。

//这种方式时间复杂度最高
public boolean isUniqueOld(String astr) {
    for (int i = 0; i < astr.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (astr.charAt(i) == astr.charAt(j)) {
                return false;
            }
        }
    }
    return true;
}

//快排内部会建数组
public boolean isUniqueSort(String astr) {
    char[] c = astr.toCharArray();
    //这个不是很符合，因为快排会创建新数组
    Arrays.sort(c);
    for (int i = 1; i < c.length; i++) {
        if (c[i] == c[i - 1]) {
            return false;
        }
    }
    return true;
}

//使用两个long类型，128位，可以记录char内的所有可能(位运算)
public boolean isUnique(String astr) {
    long left = 0;
    long right = 0;
    for (int i = 0; i < astr.length(); i++) {
        if (astr.charAt(i) >= 64) {
            if ((left & (1 << (astr.charAt(i) - 64))) != 0) {
                return false;
            }
            left += (1 << (astr.charAt(i) - 64));
        } else {
            if ((right & (1 << astr.charAt(i))) != 0) {
                return false;
            }
            right += (1 << astr.charAt(i));
        }
    }
    return true;
}

面试题 01.02. 判定是否互为字符重排
给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

示例 1：

输入: s1 = “abc”, s2 = “bca”
输出: true
示例 2：

输入: s1 = “abc”, s2 = “bad”
输出: false
说明：

0 <= len(s1) <= 100
0 <= len(s2) <= 100

public boolean CheckPermutation(String s1, String s2) {
    if (s1.length() != s2.length()) {
        return false;
    }
    int[] nums = new int[128];
    for (int i = 0; i < s1.length(); i++) {
        nums[s1.charAt(i)]++;
    }
    for (int i = 0; i < s2.length(); i++) {
        nums[s2.charAt(i)]--;
        if (nums[s2.charAt(i)] < 0) {
            return false;
        }
    }
    return true;
}	

面试题 01.03. URL化

URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）

示例1:

输入："Mr John Smith ", 13
输出：“Mr%20John%20Smith”
示例2:

输入：" “, 5
输出：”%20%20%20%20%20"
提示：

字符串长度在[0, 500000]范围内。

//我自己的方法，但是不是很符合在字符组上操作
public String replaceSpaces(String S, int length) {
    StringBuilder sb = new StringBuilder();
    char[] chars = S.toCharArray();
    for (int i = 0; i < length; i++) {
        if (chars[i] == ' ') {
            sb.append("%20");
        } else {
            sb.append(chars[i]);
        }
    }
    return sb.toString();
}	

//字符串尾部有足够的空间存放新增字符, 所以就在原数组上进行操作
public String replaceSpaces(String S, int length) {
    char[] chars = S.toCharArray();
	//从后往前操作
    int end = length - 1;
    int nEnd = chars.length - 1;
    while (end >= 0) {
        if (chars[end] == ' ') {
            end--;
            chars[nEnd--] = '0';
            chars[nEnd--] = '2';
            chars[nEnd--] = '%';
        } else {
            chars[nEnd--] = chars[end--];
        }
    }
    return new String(chars, nEnd + 1, chars.length - 1 - nEnd);
}

面试题 01.04. 回文排列

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

示例1：

输入：“tactcoa”
输出：true（排列有"tacocat"、“atcocta”，等等）

//思想就是，字母个数为奇数个的字母，最多只能有一个
public boolean canPermutePalindrome(String s) {
    int[] nums = new int[128];
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        nums[chars[i]] ^= 1;
    }
    int res = 0;
    for (int i = 0; i < nums.length; i++) {
        res += nums[i];
    }
    return res <= 1;
}

面试题 01.05. 一次编辑

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

示例 1:

输入:
first = “pale”
second = “ple”
输出: True

示例 2:

输入:
first = “pales”
second = “pal”
输出: False

public boolean oneEditAway(String first, String second) {
    if (first.length() == second.length()) {
        return sameLen(first, second);
    }
    if (first.length() == second.length() + 1) {
        return moreOne(first, second);
    }
    if (second.length() == first.length() + 1) {
        return moreOne(second, first);
    }
    return false;
}

private boolean sameLen(String first, String second) {
    for (int i = 0; i < first.length(); i++) {
        if (first.charAt(i) != second.charAt(i)) {
            for (int j = i + 1; j < first.length(); j++) {
                if (first.charAt(j) != second.charAt(j)) {
                    return false;
                }
            }
            return true;
        }
    }
    return true;
}

private boolean moreOne(String first, String second) {
    for (int i = 0; i < first.length() - 1; i++) {
        if (first.charAt(i) != second.charAt(i)) {
            //找到多余的之后
            for (int j = i + 1; j < first.length(); j++) {
                if (first.charAt(j) != second.charAt(j - 1)) {
                    return false;
                }
            }
            return true;
        }
    }
    //这就是最后一位多余了
    return true;
}

面试题 01.06. 字符串压缩

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

示例1:

输入：“aabcccccaaa”
输出：“a2b1c5a3”
示例2:

输入：“abbccd”
输出：“abbccd”
解释：“abbccd"压缩后为"a1b2c2d1”，比原字符串长度更长。
提示：

字符串长度在[0, 50000]范围内。

public String compressString(String S) {
    if (S.length() == 0) {
        return S;
    }
    char[] chars = S.toCharArray();
    char c = chars[0];
    int num = 1;
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i < chars.length; i++) {
        if (chars[i] == c) {
            num++;
        } else {
            sb.append(c);
            sb.append(num);
            c = chars[i];
            num = 1;
        }
    }
    sb.append(c);
    sb.append(num);
    return sb.toString().length() < S.length() ? sb.toString() : S;
}

面试题 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]
]

public void rotate(int[][] matrix) {
    int N = matrix.length;
    for (int i = 0; i < N / 2; i++) {
        for (int j = 0; j < (N + 1) / 2; j++) {
            //找到A左上，B右上，C右下，D左下四个点
            // A(i,j)
            // B(j,N - i - 1)
            // C(N - i - 1,N - j - 1)
            // D(N - j - 1,i)
            //先AD交换
            matrix[i][j] = matrix[i][j] + matrix[N - j - 1][i];
            matrix[N - j - 1][i] = matrix[i][j] - matrix[N - j - 1][i];
            matrix[i][j] = matrix[i][j] - matrix[N - j - 1][i];
            //BC交换
            matrix[j][N - i - 1] = matrix[j][N - i - 1] + matrix[N - i - 1][N - j - 1];
            matrix[N - i - 1][N - j - 1] = matrix[j][N - i - 1] - matrix[N - i - 1][N - j - 1];
            matrix[j][N - i - 1] = matrix[j][N - i - 1] - matrix[N - i - 1][N - j - 1];
            //再BD交换
            matrix[j][N - i - 1] = matrix[j][N - i - 1] + matrix[N - j - 1][i];
            matrix[N - j - 1][i] = matrix[j][N - i - 1] - matrix[N - j - 1][i];
            matrix[j][N - i - 1] = matrix[j][N - i - 1] - matrix[N - j - 1][i];

        }
    }
}

//下面方法更好理解
public void rotate(int[][] matrix) {
    int N = matrix.length;
    //上下对折
    for (int i = 0; i < N / 2; i++) {
        for (int j = 0; j < N; j++) {
            matrix[i][j] = matrix[i][j] + matrix[N - i - 1][j];
            matrix[N - i - 1][j] = matrix[i][j] - matrix[N - i - 1][j];
            matrix[i][j] = matrix[i][j] - matrix[N - i - 1][j];


        }
    }
    //右上左下对折
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            matrix[i][j] = matrix[i][j] + matrix[j][i];
            matrix[j][i] = matrix[i][j] - matrix[j][i];
            matrix[i][j] = matrix[i][j] - matrix[j][i];
        }
    }
}

面试题 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]
]

public void setZeroes(int[][] matrix) {
    int N = matrix.length;
    if (N == 0) {
        return;
    }
    int M = matrix[0].length;
	//记录一下当前行是否有0 
    boolean[] rowZero = new boolean[N];
	//记录一下当前列是否有0
    boolean[] colZero = new boolean[M];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (matrix[i][j] == 0) {
                rowZero[i] = true;
                colZero[j] = true;
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (rowZero[i] || colZero[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}

面试题 01.09. 字符串轮转

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

示例1:

输入：s1 = “waterbottle”, s2 = “erbottlewat”
输出：True
示例2:

输入：s1 = “aa”, “aba”
输出：False
提示：

字符串长度在[0, 100000]范围内。
说明:

你能只调用一次检查子串的方法吗？

先开始没看懂旋转的意思，做了几个测试之后明白了，就是前面的挨个往最后移动

public boolean isFlipedString(String s1, String s2) {
    if (s1.length() != s2.length()) {
        return false;
    }
    return (s1 + s1).indexOf(s2) >= 0;
}