LeetCode刷题21-30

2023-11-29

Word count: 3k | Reading time≈ 13 min

①141.环形链表

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

HashSet中的**add()**方法：
方法返回一个boolean值，表示添加操作是否成功
（如果集合中原来就存在相同的元素，则添加操作失败返回false）

思考：如果遍历的时候出现重复的相同的一个结点，那么就是环形链表了

哈希表法

public boolean hasCycle(ListNode head) {
        Set<ListNode> hash = new HashSet<ListNode>();

        while(head != null){
            if(!hash.add(head)){
                //有重复的，无法添加进去，则表示是回到重复的结点了
                return true;
            }
            //判断完将头结点指向下一个结点
            head = head.next;
        }
        return false; 
    }

「Floyd 判圈算法」（又称龟兔赛跑算法）
假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。
当「乌龟」和「兔子」从链表上的同一个节点开始移动时，
如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；
如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。
等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

注意：如果用do…while…可以将龟兔的起点设置在同一个结点。

快慢指针法

public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }

        ListNode slow = head;
        ListNode fast = head.next;
        while(slow != fast){
            if(fast == null || fast.next == null){
                //兔子到达链表尽头，没有环形
                return false;
            }
            //移动
            slow = slow.next;
            fast = fast.next.next;
        }
        //循环结束 则slow == fast 龟兔相遇了，是环形的
        return true;
    }

②144.二叉树的前序遍历

题目：给你二叉树的根节点 root ，返回它节点值的前序遍历。

思考：递归、根左右

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root,res);
        return res;

    }

    public void preorder(TreeNode root,List<Integer> res){
        if(root == null){
            return;
        }
        res.add(root.val);
        preorder(root.left,res);
        preorder(root.right,res);
    }
}

③145.二叉树的后序遍历

题目：给你一棵二叉树的根节点 root ，返回其节点值的后序遍历。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root,res);
        return res;

    }

    public void postorder(TreeNode root,List<Integer> res){
        if(root == null){
            return;
        }
        postorder(root.left,res);
        postorder(root.right,res);
        res.add(root.val);
    }
}

④160.相交链表

题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

HashSet中的**contains()**方法：
用于判断集合中是否包含指定元素
如果该元素在集合中存在，返回 true，否则返回 false。

哈希表方法

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<ListNode>();
        ListNode tempA = headA;
        while(tempA != null){
            set.add(tempA);
            tempA = tempA.next;
        }

        ListNode tempB = headB;
        while(tempB != null){
            if(set.contains(tempB)){
                return tempB;
            }
            tempB = tempB.next;
        }
        return null;
    }

链表 headA和 headB 的长度分别是 m 和 n 假设链表 headA 的不相交部分有 a 个节点，链表 headB 的不相交部分有 b 个节点，两个链表相交的部分有 c 个节点，则有 a+c==m，b+c=n。

思考：
相交：
如果两个链表长度不同，pA 会遍历完链表 headA，tempB会遍历完链表headB，
两个指针不会同时到达链表的尾节点，
然后指针 pA 移到链表 headB 的头节点，指针 pB移到链表 headA 的头节点，
然后两个指针继续移动，在指针 pA 移动了 a+c+b 次、指针 tempB 移动了 b+c+a 次之后，两个指针会同时到达两个链表相交的节点，
该节点也是两个指针第一次同时指向的节点，此时返回相交的节点。

不相交：
如果 m≠n，则由于两个链表没有公共节点，两个指针也不会同时到达两个链表的尾节点，因此两个指针都会遍历完两个链表，在指针 pA 移动了 m+n 次、指针 pB 移动了 n+m 次之后，两个指针会同时变成空值 null，此时返回 null

双指针

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //如果有相交结点，那么两者都不能为空
        if(headA == null || headA == null){
            return null;
        }

        ListNode pA = headA , pB = headB;
        while(pA != pB){
            //如果为null则去遍历另一条链表，否则便利自己的下一个结点
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

⑤168.Excel表列名称

题目：给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。

思考：
A B C D E F G H I J K L M N O P Q I S T U V W X Y Z
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
AA AB AC AD
27 28 29 30

AA = 1x26 + 1x1 = 27
AB = 1x26 + 2x1 = 28
AC = 1x26 + 3x1 = 29
ABC = 1x26x26 + 2x26 + 3x1 = 731

731 - 1 = 730
730 % 26 = 2
2 + 65 = 67 → C
730 ÷ 26 = 28 … 2
28

28 - 1 = 27
27 % 26 = 1
1 + 65 = 66 → B
27 ÷ 26 = 1 … 1
1

1 - 1 = 0
0 % 26 = 0
0 + 65 = 65 → A
0 ÷ 26 = 0
0

26进制从0开始：
0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

sb.append((char)(columnNumber % 26 + ‘A’));
获取当前位的字母在26个大写字母中的位置（范围为0-25），然后加上’A’的ASCII码值（65），转换为相应的字母。
这样就完成了将数字转换为字母的过程。

public String convertToTitle(int columnNumber) {
        StringBuilder sb = new StringBuilder();
        while(columnNumber != 0){
            columnNumber --;
            sb.append((char)(columnNumber % 26 + 'A'));
            columnNumber /= 26;
        }
        return sb.reverse().toString();
    }

⑥171.Excel表列序号

题目：给你一个字符串 columnTitle ，表示 Excel 表格中的列名称。返回该列名称对应的列序号。

是上一题的反向解法
int k = columnTitle.charAt(i) - ‘A’ + 1;

从后往前

public int titleToNumber(String columnTitle) {
       int result = 0;
       int multiply = 1;
       //从后往前
       for(int i = columnTitle.length() - 1; i>=0 ; i--){
           int k = columnTitle.charAt(i) - 'A' + 1;
           result += k * multiply;
           multiply *= 26;
       }
       return result;
   }

从前往后

public int titleToNumber(String columnTitle) {
        int result = 0;
        //从前往后
        for(int i = 0 ; i <= columnTitle.length()-1 ; i++){
            result = result * 26 + (columnTitle.charAt(i) - 'A' + 1);
        }
        return result;
    }

⑦190.颠倒二进制位

题目：颠倒给定的 32 位无符号整数的二进制位。

思考：
二进制的位运算
得到二进制数n的最后一位(n & 1)或者(n | 0)
将最后一位数挪到最前面一位(n & 1) << (31 - i)
n向右移动一位，将倒数第2位挪动到最后一位，方便得到

rev |= (n & 1) << (31 - i);中|分析
这是因为在位或运算中，只有当两个操作数的对应位都是 0 时，结果才为 0；如果至少有一个操作数的对应位是 1，那么结果就是 1。
在这个例子中，移位后的结果（即 (n & 1) << (31 - i)）可能是 0 或 1。
如果移位后的结果是 0，那么 rev |= ... 就变成了 rev = rev;，即不会更新 rev 的值；
如果移位后的结果是 1，那么 rev |= ... 就变成了 rev = rev | (n & 1) << (31 - i);，即会将 rev 的对应位更新为 1。
因此，使用或运算符可以确保只有在移位后的结果是 1 时，才会更新 rev 的对应位。

如果不使用或运算符，而是直接使用加法运算符 rev += …，
那么在移位后的结果为 1 时，rev 的值不会发生变化；
而在移位后的结果为 0 时，rev 的值会加上一个很大的负数（因为移位后的结果乘以 2^i），
这会导致 rev 的值变得非常大，甚至超出 int 类型的范围。
因此，使用或运算符可以确保正确地更新 rev 的值。

逐位颠倒(位运算)

//逐位颠倒
   public int reverseBits(int n) {
       if (n == 0) return 0;
       int rev = 0;
       for(int i = 0; i < 32; i++){
           rev |= (n & 1) << (31 - i);
           n >>>= 1;
       }
       return rev;
   }

位运算分治

不会

Integer.reverse方法

public int reverseBits(int n) {
   //直接返回二进制的翻转
       return Integer.reverse(n);
   }

⑧191.位1的个数

题目：编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

还是位运算

public int hammingWeight(int n) {
       int result = 0;
       for(int i = 0; i < 32;i++){
           if((n&1) == 1){
           result ++; 
           }
           n >>>= 1;
       }
       return result;
   }

⑨202.快乐数

题目：编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

思考：
只有这两种情况：

最终会得到1
会进入循环

哈希表

class Solution {
  public int getNext(int n){
        int sum = 0;
        while(n > 0){
          int last = n % 10;//得到最后一位数字
          sum += last*last;
          n /= 10;//得到除了最后一位的剩余数字
        }
        return sum;
      }

    public boolean isHappy(int n) {
      //如果出现重复数字，则陷入死循环，不可能是快乐数
      Set<Integer> hash = new HashSet<Integer>();
      while(n != 1 && !hash.contains(n)){
        hash.add(n);
        n = getNext(n);
      }
      return n==1;
    }
}

双指针法

public boolean isHappy(int n) {
  int slow = n;
  int fast = getNext(n);

  while(fast != 1 && slow != fast){
    slow = getNext(slow);
    fast = getNext(getNext(fast));
  }
  return fast == 1;
}

⑩203.移除链表元素

题目：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

递归

public ListNode removeElements(ListNode head, int val) {
       if(head == null){
           return head;
       }
       head.next = removeElements(head.next,val);
       //如果相同就删除当前结点，返回下一节点
       //如果不相同就保留当前头结点
       return head.val == val ? head.next : head;
   }

思考：在 ListNode dummyHead = new ListNode(0); 中，创建了一个值为 0 的 ListNode 类型的对象，此对象并不是实际的链表节点，只是为了方便操作链表，
在开始遍历链表前使用 dummyHead.next = head; 来连接 dummyHead 和 head，让 dummyHead 成为链表的头结点。
这样就不需要特别处理链表头部的删除操作，而是将删除操作应用于链表的实际节点即可。

随着在 while 循环内部进行删除操作，删除的是链表的实际节点，而不是虚拟头节点。
当 while 循环结束后，dummyHead.next 已经指向删除节点后的新链表头部，可以将其作为返回值，也就是返回了经过删除操作后的链表的头节点。

迭代

public ListNode removeElements(ListNode head, int val) {
        ListNode inter = new ListNode(0);
        inter.next = head;

        ListNode temp = inter;

        while(temp.next != null){
            if(temp.next.val == val){
                temp.next = temp.next.next;
            }else{
                temp = temp.next;
            }
        }
        return inter.next;
    }

Donate

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.