lintcode阶梯训练第一关（九章）

时间：2023-02-24 10:27:33

13、字符串查找

  • 题目
    对于一个给定的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1。
    样例
    如果 source = “source” 和 target = “target”，返回 -1。
    如果 source = “abcdabcdefg” 和 target = “bcd”，返回 1。

  • 代码

class Solution{
    public int strStr(String source, String target) {
        if (source == null || target == null) {
            return -1;
        }
        int j;
        for (int i = 0; i < source.length() - target.length() + 1; i++) {
            for (j = 0; j < target.length(); j++) {
                if (source.charAt(i + j) != target.charAt(j)) {
                    break;
                }
            }
            if (j == target.length()) {
                return i;
            }
        }
        return -1;
    }
}
  • Bug
    没注意i的边界条件，导致i+j越界
#python
class Solution:
    def strStr(self, source, target):
        if source is None or target is None:
            return -1
        return source.find(target)

15、全排列

  • 题目
    给定一个数字列表，返回其所有可能的排列。
    注意事项
    你可以假设没有重复数字。
    样例
    给出一个列表[1,2,3]，其全排列为：
    [
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
    ]

  • 代码

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null) {
            return result;
        }
        if (nums.length == 0) {
            result.add(new ArrayList<Integer>());
            return result;
        }
        List<Integer> list = new ArrayList<>();
        dfsHelper(nums, list, result);
        return result;
    }
    private void dfsHelper(int[] nums,
                           List<Integer> list,
                           List<List<Integer>> result) {
        if (list.size() == nums.length) {
            result.add(new ArrayList<Integer>(list));
        }
        for (int i = 0; i < nums.length; i++) {
            if (list.contains(nums[i])) {
                continue;
            }
            list.add(nums[i]);
            dfsHelper(nums, list, result);
            list.remove(list.size() - 1);
        }
    }
}
  • Bug
    nums.length == 0时的执行内容写错

16、带重复元素的排列

  • 题目
    给出一个具有重复数字的列表，找出列表所有不同的排列。
    样例
    给出列表 [1,2,2]，不同的排列有：
    [
    [1,2,2],
    [2,1,2],
    [2,2,1]
    ]

  • 代码

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null) {
            return result;
        }
        if (nums.length == 0) {
            result.add(new ArrayList<Integer>());
            return result;
        }
        List<Integer> list = new ArrayList<>();
        int[] flag = new int[nums.length];
        Arrays.fill(flag, 0);
        Arrays.sort(nums);
        dfsHelper(nums, flag, list, result);
        return result;
    }
    private void dfsHelper(int[] nums, int[] flag,
                           List<Integer> list,
                           List<List<Integer>> result) {
        if (list.size() == nums.length) {
            result.add(new ArrayList<Integer>(list));
        }
        for (int i = 0; i < nums.length; i++) {
            if (flag[i] == 1 || (i != 0 && nums[i] == nums[i - 1] && flag[i - 1] == 0)) {
                continue;
            }
            list.add(nums[i]);
            flag[i] = 1;
            dfsHelper(nums, flag, list, result);
            list.remove(list.size() - 1);
            flag[i] = 0;
        }
    }
}
  • Bug
    少了flag[i] == 1时也应该跳过，即跳过遍历过的元素。

17、子集

  • 题目
    给定一个含不同整数的集合，返回其所有的子集
    注：子集中的元素排列必须是非降序的，解集必须不包含重复的子集
    样例
    如果 S = [1,2,3]，有如下的解：
    [
    [3],
    [1],
    [2],
    [1,2,3],
    [1,3],
    [2,3],
    [1,2],
    []
    ]

  • 代码

class Solution{
    public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        if (nums == null || nums.length == 0) {
            return results;
        }
        Arrays.sort(nums);
        ArrayList<Integer> list = new ArrayList<Integer>();
        dfs(nums, 0, list, results);
        return results;
    }
    private void dfs(int[] nums,
                     int startIndex,
                     ArrayList<Integer> list,
                     ArrayList<ArrayList<Integer>> results) {
        results.add(new ArrayList<Integer>(list));
        for (int i = startIndex; i < nums.length; i++) {
            list.add(nums[i]);
            dfs(nums, i + 1, list, results);
            list.remove(list.size() - 1);
        }
    }
}

18、带重复元素的子集

  • 题目
    给定一个可能具有重复数字的列表，返回其所有可能的子集
    注意事项
    子集中的每个元素都是非降序的
    两个子集间的顺序是无关紧要的
    解集中不能包含重复子集
    样例
    如果 S = [1,2,2]，一个可能的答案为：
    [
    [2],
    [1],
    [1,2,2],
    [2,2],
    [1,2],
    []
    ]

  • 代码

class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] nums) {
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        if (nums == null || nums.length == 0) {
            return results;
        }
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        dfsHelper(nums, 0, list, results);
        return results;
    }
    private void dfsHelper(int[] nums, int pos,
                           ArrayList<Integer> list,
                           ArrayList<ArrayList<Integer>> results) {
        results.add(new ArrayList<Integer>(list));
        for (int i = pos; i < nums.length; i++) {
            if (i != pos && nums[i] == nums[i - 1]) {
                continue;
            }
            list.add(nums[i]);
            dfsHelper(nums, i + 1, list, results);
            list.remove(list.size() - 1);
        }
    }
}

594、strStr II

  • 题目
    Implement strStr function in O(n + m) time.
    strStr return the first index of the target string in a source string. The length of the target string is m and the length of the source string is n.
    If target does not exist in source, just return -1.
    样例
    Given source = abcdef, target = bcd, return 1.

  • 代码

class Solution {
    static final int BASE = 1000000;
    public int strStr2(String source, String target) {
        if (source == null || target == null) {
            return -1;
        }
        int targetCode = 0;
        int m = target.length();
        if (m == 0) {
            return 0;
        }
        for (int i = 0; i < m; i++) {
            targetCode = (targetCode * 31 + target.charAt(i)) % BASE;
        }
        int power = 1;
        for (int i = 0; i < m; i++) {
            power = power * 31 % BASE;
        }
        int hashCode = 0;
        for (int i = 0; i < source.length(); i++) {
            hashCode = (hashCode * 31 + source.charAt(i)) % BASE;
            if (i < m - 1) {
                continue;
            }
            if (i >= m) {
                hashCode = hashCode - (source.charAt(i - m) * power) % BASE;
                if (hashCode < 0) {
                    hashCode += BASE;
                }
            }
            if (hashCode == targetCode) {
                if (source.substring(i - m + 1, i + 1).equals(target)) {
                    return i - m + 1;
                }
            }
        }
        return -1;
    }
}
标签：