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];
}
}
