精选算法面试-数组II

一.示例

1.1 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例1

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

实现1

//双端指针
public int removeElement(int[] nums, int val) {
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            if(nums[j] != val){
                nums[i] = nums[j];
                i++;
            }
        }
        return i;
    }

实现2

//双端指针，减少移动
public int removeElement(int[] nums, int val) {
    int i = 0;
    int n = nums.length;
    while (i < n) {
        if (nums[i] == val) {
            nums[i] = nums[n - 1];
            // 尾部元素 
           n--;
        } else {
            i++;
        }
    }
    return n;
}

1.2 赎金信

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意

你可以假设两个字符串均只含有小写字母。

canConstruct("a", "b") -> false

canConstruct("aa", "ab") -> false

canConstruct("aa", "aab") -> true

实现1

public boolean canConstruct(String ransomNote, String magazine) {
        char[] chars1 = ransomNote.toCharArray();
        char[] chars2 = magazine.toCharArray();
       
        int[] recoder = new  int[26];
        for (int i = 0; i < chars2.length; i++) {
            recoder[chars2[i] - 'a'] ++;
        }
        for (int i = 0; i < chars1.length; i++) {
            recoder[chars1[i] - 'a'] --;
            if(recoder[chars1[i] - 'a'] < 0){
                return false;
            }
        }
        return true;
    }

实现2

public boolean canConstruct(String ransomNote, String magazine) {
  char[] chars1 = ransomNote.toCharArray();
  char[] chars2 = magazine.toCharArray();
  int[] recoder = new  int[26];
  for (int i = 0; i < chars2.length; i++) {
    recoder[chars2[i] - 'a'] ++;
  }
  for (int i = 0; i < chars1.length; i++) {
    recoder[chars1[i] - 'a'] --;
    //匹配的子串，减少到负数，不匹配
        if(recoder[chars1[i] - 'a'] < 0){
          return false;
        }
  }
  return true;
}

参考

https://leetcode-cn.com/problems/remove-element/

https://leetcode-cn.com/problems/ransom-note/