算法--2023.1.10

1.力扣136--只出现一次的数字

class Solution {
    //只有一个数字出现一次，所有其他数字均出现两次，将所有数字异或一下即可
    public int singleNumber(int[] nums) {
        int n = nums.length;
        int res = 0;
        for(int i = 0;i<n;i++){
            res = res ^ nums[i];
        }
        return res;
    }
}

2.力扣139--单词拆分

class Solution {
    //动态规划
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>();
        int n = s.length();
        for(String cur : wordDict){
            set.add(cur);
        }
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        //序列动态规划，判断最后一个单词，如果最后可以形成一个完整单词，则当前状态就是这个单词前一个单词的状态，
        //如果前面状态也是true，停止遍历
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=i&&!dp[i];j++){
                String temp = s.substring(j-1,i);
                if(set.contains(temp)){
                    dp[i] = dp[j-1];
                }
            }
        } 
        return dp[n];
    }
}

　3.力扣141--环形链表

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        //快慢指针，如果两个指针能相遇，说明存在环，如果不能快指针到达null，说明不存在环
        while(fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}

4.力扣142--环形链表2

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                ListNode pre = head;
                while(pre != slow){
                    pre = pre.next;
                    slow = slow.next;
                }
                return pre;
            }
        }
        return null;
    }
}