LeetCode383
赎金信.
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成,返回 true ;否则返回 false。
(题目说明:为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
注意:
你可以假设两个字符串均只含有小写字母。
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
思路:和判断是否是异位词一样,通过哈希表的指定位置++ --来完成操作。
代码:
package com.dwj.LeetCode.HashList; /** * 赎金信 * 给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成,返回 true ;否则返回 false。 */ public class RansomLetter { class Solution { public boolean canConstruct(String ransomNote, String magazine) { // 定义一个哈希映射数组 int[] record = new int[26]; // 遍历 for(char c : magazine.toCharArray()){ record[c - 'a'] += 1; } for(char c : ransomNote.toCharArray()){ record[c - 'a'] -= 1; } // 如果数组中存在负数,说明ransomNote字符串总存在magazine中没有的字符 for(int i : record){ if(i < 0){ return false; } } return true; } } }
LeetCode18 四数之和
题意:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。
注意:
答案中不可以包含重复的四元组。
示例: 给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。 满足要求的四元组集合为: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
思路:和三数之和的思路类似,只不过多加了一层for循环。不一样的是,在这里,target的目标值不再是指定的0。target可以是正数,也可以是负数。所以对去重的要求更加苛刻。
如果是三数之和,由于是经过排序后进行计算,最左的值i如果大于target0,那么后面加的数再小也比当前值大,直接舍弃这种可能。
四数之和的剪枝,不能只考虑值是否比target大,因为target存在负数的可能性,所以同时还需要判断target是否是正数,nums【i】是否是正数。
代码:
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { // nums[i] > target 直接返回, 剪枝操作 if (nums[i] > 0 && nums[i] > target) { return result; } if (i > 0 && nums[i - 1] == nums[i]) { continue; } for (int j = i + 1; j < nums.length; j++) { if (j > i + 1 && nums[j - 1] == nums[j]) { continue; } int left = j + 1; int right = nums.length - 1; while (right > left) { long sum = (long) nums[i] + nums[j] + nums[left] + nums[right]; if (sum > target) { right--; } else if (sum < target) { left++; } else { result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; left++; right--; } } } } return result; } }
标签:right,target,nums,int,代码,随想录,Day06,字符串,left From: https://www.cnblogs.com/dwj-ngu/p/16808366.html