力扣242、349、202、1、24、19、160、142-java刷题笔记

  一、242. 有效的字母异位词

��1.1题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"输出: true

示例 2:

输入: s = "rat", t = "car"输出: false

1.2思路分析

方法1：传统方法

将字符串转换为字符数组，然后分别对两个数组进行排序，然后在调用equals方法进行比较；

方法2：哈希表

因为题目的需求是找"是否存在"的问题，因此可以考虑使用哈希表，对两个字符串中的字符作为数组的下表，其出现的频次作为数组的值，然后根据出现的频次就可以判断两个字符串是否相等。

1.3代码实现

 方法1暴力求解

class Solution {    public boolean isAnagram(String s, String t) {        // 注意字符串数组在获取数组长度时调用length（）        int length1 = s.length();        int length2 = t.length();        if(length1 != length2){            return false;        }        // 调用toCharArray()方法将字符串转换为字符数组        char[] s1 = s.toCharArray();        char[] s2 = t.toCharArray();        // 调用Array.sort()方法对数组进行排序        Arrays.sort(s1);        Arrays.sort(s2);        // 使用Arrays.equals()方法对数组中的值进行比较        return  Arrays.equals(s1,s2);    }}

方法2哈希表

class Solution {    public boolean isAnagram(String s, String t) {        // 使用哈希表对字符串中的每个字符出现的频次进行统计        // 定义一个新数组        if (s.length() != t.length()) {            return false;        }        // 因为result中每个值存的是对应的字符出现的频次因此，其长度定义为26        int[] result = new int[26];        // 对字符串中的字符出现的频次进行统计        for (int i = 0; i  
二、349. 两个数组的交集 
 2.1题目 
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
  
示例 1：
 
输入：nums1 = [1,2,2,1], nums2 = [2,2]输出：[2]
 
示例 2：
 
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出：[9,4]解释：[4,9] 也是可通过的
 
 2.2思路分析 
该题也可以转化为是否存在问题，即当两个数组中存在相同值时，此时则可以理解为两个数组存在交集；但是输出中要求不能出现冗余，因此考虑使用HashSet。
 
2.3代码实现 
首先判断这两个数组中是否有值，若没有值，直接返回一个空数组，然后定义两个集合，一个用于存放待判断的数组，另一个存放最后的结果，最后再将集合转化为数组返回。
 
class Solution {    public int[] intersection(int[] nums1, int[] nums2) {        // 判断nums1与nums2中是否有值        if(nums1.length == 0 ||nums2.length== 0 || nums2 ==null ||nums1 == null){            return new int[0];        }        // 因为数组中有重复的值，因此我们使用 HashSet对数组去重       HashSet  set1 =  new HashSet();    //    定义一个结果hashset       HashSet result = new HashSet();       for(int i:nums1){        //    将nums1中的数值添加到set1中并去重           set1.add(i);       }       for(int i:nums2){           if(set1.contains(i)){               result.add(i);           }       }    //    int [] arr = new int[result.]    return result.stream().mapToInt(x->x).toArray();    }}
 
 
三、202. 快乐数
 
3.1题目
 
编写一个算法来判断一个数 n 是不是快乐数。
 
「快乐数」 定义为：
 

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

  如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

  示例 1：

  输入：n = 19输出：true解释：12 + 92 = 8282 + 22 = 6862 + 82 = 10012 + 02 + 02 = 1

  示例 2：

  输入：n = 2输出：false

  3.2思路分析

  该题的难点在于如何判断是否进入***循环，那么什么时候迭代过程会进入***循环呢，即当当前的数值在以往的迭代过程中出现过，因此该题同样可以考虑使用HashSet。

  3.3代码实现

  首先定义一个求和的函数；然后再根据条件迭代即可，注意：(n % 10)*(n % 10)取模的平方时需要对其带括号。

  class Solution {    public boolean isHappy(int n) {        // 先判断该数是不是1，若是1则直接返回        if(n == 1){            return true;        }        // 需要判断该数是否为无限循环即存在过问题，因此可以定义一个哈希表        // 返回值是无须的因此可以使用unordered_set set(c++) 或直接使用set         HashSet set1 =new HashSet ();        //循环的条件为 判断值是否存在于hashset中且 n !=1        while(n != 1 && !set1.contains(n)){            set1.add(n);            n = addsum(n);        }        return n == 1;    }    // 对n的各个位置进行平方求和    public int addsum(int n){        int temp = 0;        while(n > 0){            // int res = n % 10;            temp += (n % 10)*(n % 10);            n = n/10;        }    return temp;    }}

     四、1. 两数之和

   4.1题目

  给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

  你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

  你可以按任意顺序返回答案。

  示例 1：

  输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

  示例 2：

  输入：nums = [3,2,4], target = 6输出：[1,2]

  示例 3：

  输入：nums = [3,3], target = 6输出：[0,1]

  4.2思路分析

  方法1：暴力求解

  使用两次for循环来遍历求解

  方法2：哈希表

  我们可以将题目转化为寻找target-nums[1]的值是否在nums中存在的问题，又因为题目最后的返回值需要满足条件的下标，因此可以考虑使用HashMap，我们将数组中的值作为HashMap中的key，值的下标作为HashMap中的value。

  4.3代码实现

   方法1暴力求解

  class Solution {    public int[] twoSum(int[] nums, int target) {        int temp = 0;        // int [] k = new int[2] ;        for(int i = 0; i0){            cur1 = cur1.next;            gap--;        }        while(cur1!=null && cur2 != null){            if(cur1 == cur2){                return cur1;            }            cur1 = cur1.next;            cur2 = cur2.next;        }      return null;    }}

  八、142. 环形链表 II

   8.1题目

  给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

  如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

  不允许修改 链表。

  示例 1：

  输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。

  示例 2：

  输入：head = [1,2], pos = 0输出：返回索引为 0 的链表节点解释：链表中有一个环，其尾部连接到第一个节点。

  示例 3：

  输入：head = [1], pos = -1输出：返回 null解释：链表中没有环。

   8.2思路分析

  第一步：判断链表中是否有环

  定义快慢指针，让快指针以比慢指针快2倍的速度移动，若快指针可以和慢指针相遇则证明该链表有环。

  第二步：找到初始相遇的节点。

  假设头节点到初始相遇节点的长度为x，环入口节点到相遇节点的长度为y，相遇节点到换入口的长度为z。

  则我们根据快慢指针的移动速度可以列入下表达式：；

  进一步化简得;

  而，我们取个极限情况，即n=1时，此时。

  因此我们可以进一步定义两个指针，一个指针由头指针开始向后运动，另一个指针由相遇位置开始移动，当两个新定义得指针再次相遇时，此时得相遇点则为快慢指针得初始相遇点。

  8.3代码实现

  /** * Definition for singly-linked list. * class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {    public ListNode detectCycle(ListNode head) {        // 使用快慢指针，快指针以2倍速的方式取去追赶慢指针，当快指针等于慢指针时        // 说明此时有环        ListNode fast = head;        ListNode slow = head;        // 因为快指针一次走两步因此需要判断fast.next是否为空，若不为空则继续循环        while(fast != null && fast.next != null){            slow = slow.next;            fast = fast.next.next;            if(slow == fast){              ListNode index1 = head;              ListNode index2 = fast;              while(index1 != index2){                  index1 = index1.next;                  index2 = index2.next;              }              return index1;          }        }       return null;     }}