147 对链表进行插入排序

136 只出现一次的数字

思路1:排序
不合题意 写来玩

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i=0;i<nums.length-1;i=i+2){
            if(nums[i]!=nums[i+1]){
                return nums[I];
            }
        }
        return nums[nums.length-1];
    }
}

思路2:hash
不合题意 写来玩
记住类型转换！直接强制转换即可
Java Object对象类型与值类型之间的相互转化：
https://blog.csdn.net/weixin_41999297/article/details/106126309
或者规定迭代器的类型不是object就好

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> s=new HashSet<>();
        for(int i=0;i<nums.length;i++){
            if(!s.add(nums[i])){
                s.remove(nums[i]);
            }
        }
        Iterator it = s.iterator();
        while(it.hasNext()){
            return (int)it.next();
        }
        return -1;
    }
}

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> s=new HashSet<>();
        for(int i=0;i<nums.length;i++){
            if(!s.add(nums[i])){
                s.remove(nums[i]);
            }
        }
        Iterator<Integer> it = s.iterator();
        while(it.hasNext()){
            return it.next();
        }
        return -1;
    }
}

思路3:
使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字。

思路4:
使用集合存储数组中出现的所有数字，并计算数组中的元素之和。由于集合保证元素无重复，因此计算集合中的所有元素之和的两倍，即为每个元素出现两次的情况下的元素之和。由于数组中只有一个元素出现一次，其余元素都出现两次，因此用集合中的元素之和的两倍减去数组中的元素之和，剩下的数就是数组中只出现一次的数字。

!!!!思路5:位运算 ^异或
ps：在运用按位异或操作符之前得先了解一下，什么是按位异或操作符？

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
}

时间复杂度n 空间1

139

坑:substring()

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp=new boolean[s.length()+1];//默认为false；
        dp[0]=true;
        for(int i=1;i<dp.length;i++){
            for(int j=0;j<i;j++){
                if(dp[j]&&wordDict.contains(s.substring(j,i))){//记住substring是[)所以写i-1是错误的!!
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[dp.length-1];
    }
}