? ? ? 学习了Set接口和Map接口，感觉里面的HashSet和HashMap很有用，不过要勤加复习，避免忘记，记得如何将集合转为数组。反之也要记得。
?快乐数
题目链接：https://leetcode-cn.com/problems/happy-number/???
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果 可以变为??1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。
示例 1：
输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入：n = 2
输出：false
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/happy-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
? ? 这道题前几天看一脸懵逼，不知如何下手，不知道怎么才能用到Set解这道题。
思路：我们需要有一个函数来计算各位平方和?，在通过实例测试的过程中，会发现几种情况，①最终它的平方和为1，这个很好解决。②最终它会形成一个循环，不可能是快乐数，要检查是否是环，这是用到了hashSet存储不重复的特征③他可能是不循环的，这个无从检验。
创建一个HashSet存储每次各位平方和，然后看Set里面时候包含，包含的话false，最终变为1则为true。
class Solution {
private int next(int n){
int prev=0;
while(n>0){
int d=n%10;
n=n/10;
prev=prev+d*d;
}
return prev;
}
public boolean isHappy(int n) {
Set<Integer> hashset=new HashSet<>();
while(n!=1&&!hashset.contains(n)){
hashset.add(n);
n=next(n);
}
return n==1;
}
}
两个数组的交集
题目链接：
https://leetcode-cn.com/problems/intersection-of-two-arrays/
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
最后编译报错误不知为何，难搞啊。
import java.util.HashSet;
import java.util.Set;
public class exerciseTest {
public static void main(String []args){
int []nums1=new int[]{4,7,9,7,6,7};
int []nums2=new int[]{5,0,0,6,1,6,2,2,4};
Set<Integer> res=new HashSet<>();
int len1=nums1.length;
int len2=nums2.length;
int max=Math.max(len1,len2);
int min=Math.min(len1,len2);
Set<Integer> set=new HashSet<>();
for(int i=0;i<max;i++){
//将数组长度比较长的数组数组存入set，然后遍历数组短的，
//如果能够add进去则说明不重复，如果add不进去
//则说明重复，这是在将重复的数据放入存放结果的res，最后将res转为数组
if(len1>len2){
set.add(nums1[i]);
}
else{
set.add(nums2[i]);
}
}
for(int i=0;i<min;i++){
if(len1>len2){
if(!set.add(nums2[i]))
{
res.add(nums2[i]);
}
}
else{
if(!set.add(nums1[i]))
{
res.add(nums1[i]);
}
}
}
int []result=new int[res.size()];
int start=0;
for(int item:res){
result[start]=item;
start++;
}
for(int x:result){
System.out.println(x);
}
}
}
?官方题解：
将两个数租的元素都放入set里面，然后遍历短的数组，如果有重复就加入intersection，然后再将存放结果的intersection，转为数组。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<Integer>();
Set<Integer> set2 = new HashSet<Integer>();
for (int num : nums1) {
set1.add(num);
}
for (int num : nums2) {
set2.add(num);
}
return getIntersection(set1, set2);
}
public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {
if (set1.size() > set2.size()) {
return getIntersection(set2, set1);
}
Set<Integer> intersectionSet = new HashSet<Integer>();
for (int num : set1) {
if (set2.contains(num)) {
intersectionSet.add(num);
}
}
int[] intersection = new int[intersectionSet.size()];
int index = 0;
for (int num : intersectionSet) {
intersection[index++] = num;
}
return intersection;
}
}
268. 丢失的数字
难度简单421收藏分享切换为英文接收动态反馈
给定一个包含?[0, n]?中?n?个数的数组?nums?，找出?[0, n]?这个范围内没有出现在数组中的那个数。
进阶：
- 你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
示例 1：
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：
输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
示例 4：
输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
?比较简单，直接贴代码了
class Solution {
public int missingNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
int n = nums.length;
for (int i = 0; i <= n; i++) {
set.add(i);
}
Arrays.sort(nums);
for (int i = 0; i < n; i++) {
if(set.contains(nums[i])) {
set.remove(nums[i]);
}
}
return set.iterator().next();
}
}
217. 存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回?true?。如果数组中每个元素都不相同，则返回?false?。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例?3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
这个也比较简单，建议刚学了hashmap的可以直接来用。
class Solution {
public boolean containsDuplicate(int[] nums) {
HashMap<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
if(map.containsKey(nums[i])){
return true;
}
map.put(nums[i],i);
}
return false;
}
}
?
3. 无重复字符的最长子串
给定一个字符串?s?，请你找出其中不含有重复字符的?最长子串?的长度。
示例?1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是?"wke"，所以其长度为 3。
? 请注意，你的答案必须是 子串 的长度，"pwke"?是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
这道题用到了滑动窗口这个思想，在计算机网络中滑动窗口用于控制拥塞，滑动窗口善于处理连续子串或数组。
这道题的难点是，左窗口如何移动，因如何移动
1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,
此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；
2、如果当前字符 ch 包含在 map中，此时有2类情况：
1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，
那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；
2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，
而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0；
随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时
应该不变，left始终为2，子段变成 ba才对。
为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).
另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，
因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length()==0){
return 0;
}
int left=0;
int max=0;
HashMap<Character,Integer> map=new HashMap<>();
for(int i=0;i<s.length();i++){
if(map.containsKey(s.charAt(i))){
left=Math.max(left,map.get(s.charAt(i))+1);
}
map.put(s.charAt(i),i);
max=Math.max(max,i-left+1);
}
return max;
}
}
请根据每日 气温 列表 temperatures?，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用?0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出:?[1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出:?[1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/daily-temperatures
著作权归领扣网络所有。商业转载请联系官方授权
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int length = temperatures.length;
int[] ans = new int[length];
Stack <Integer> stack = new Stack<Integer>();
for (int i = 0; i < length; i++) {
int temperature = temperatures[i];
while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
int prevIndex = stack.pop();
ans[prevIndex] = i - prevIndex;
}
stack.push(i);
}
return ans;
}
}
，非商业转载请注明出处。
|