7.7 算法

136.只出现一次的数字

本题主要是进行位运算中的异或，同0异1

func singleNumber(nums []int) int {
	eor := 0
	for _,v := range nums {
		eor = eor ^ v
	}
	return eor
}

260.只出现一次的数字 III

本题也是进行位运算一个经典例题，设需要得出的两个数分别为 a,b 在第一次循环中得到eor为a ^ b。因为由题知a != b，即eor !=0,所以在eor的二进制表示中，至少有一个位数为1。通过 rightOne := eor & (^eor + 1) 提取出eor最右边数为1的数字，然后在循环中进行与运算，得出a，b 其中一个数，然后求的a,b。

func singleNumber(nums []int) []int {
	eor := 0
	for _, val := range nums {
		eor = eor ^ val
	}
	// 此时eor = a ^ b
	// 并且 eor != 0
	// eor 的位中至少有一个位为1的
	rightOne := eor & (^eor + 1) // 提取出最右边的1
	eor_ := 0
	for _, val := range nums {
		if val&rightOne == 0 {
			eor_ = eor_ ^ val
		}
	}
	return []int{eor_, eor ^ eor_}
}

169.多数元素

暴力解法a：先对该数组排序，利用count统计元素连续出现的次数，如果count > n/2，则找到众数了

方法b: 将nums数组进行升序或降序排序，那索引为[n/2]的元素，一定是众数。

// 暴力解法a
func majorityElement(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	// 先对数组进行排序
	sort.Ints(nums)
	l := len(nums) / 2
	count := 1
	for i := 1; i < len(nums); i++ {
		if nums[i] == nums[i-1] {
			count++
			if count > l {
				return nums[i]
			}
		} else {
			count = 1
		}
	}
	return 0
}

// 方法b：
func majorityElement(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	// 先对数组进行排序
	sort.Ints(nums)
	return nums[len(nums) / 2]
}

189.轮转数组

这题刚开始使用暴力解法时，我是用temp每次循环去存储最右侧的元素，之后再将数组整体往右移动一位，最后再将temp存储的元素放到元素的第一位，整体上来说没问题，但是耗时太久了。

看了题解换了一个思路，就先将整个数组进行翻转，然后翻转前k个和后l-k个就可以完成该题。

func rotate(nums []int, k int) {
	k %= len(nums)
	// 先将整个数组进行反转，然后反转前k个和后l-k个
	reverse(nums)
	reverse(nums[:k])
	reverse(nums[k:])
}
func reverse(nums []int) {
	for i, j := 0, len(nums) - 1; i <= len(nums) - 1; i++ {
		if i >= j {
			break
		}
		swap(nums, i, j)
		j--
	}
}
func swap(nums []int, i, j int) {
	nums[i] = nums[i] ^ nums[j]
	nums[j] = nums[i] ^ nums[j]
	nums[i] = nums[i] ^ nums[j]
}

专题

1.有效的数组声明语句：

int[] nums; int nums[];

2.类的方法进行本类调用时：

先要理解什么是类的方法，所谓类的方法就是指类中用 static 修饰的方法（非static 为实例方法）

A.this指的是当前对象，类方法依附于类而不是对象this会编译出错
B 类方法是指用static修饰的方法，普通方法叫对象方法。
C.类方法中也可以调用其他类的类方法。同时可以通过创建对象来调用普通方法
D.类方法中可以创建对象，所以可以调用实例方法

3.Java中的instanceof、?、&、&&的相关说法：

instanceof 可用于判断某个实例变量是否属于某种类的类型
& 在逻辑运算中是非短路逻辑与，在位运算中是按位与
&& 逻辑运算：逻辑与

注意：instanceof 用来判断某个实例变量是否属于某种类的类型。这句话不准确，instanceof可以用来判断某个实例变量是否属于某种类的类型，但它的功能不局限于此，比如还可以判断某个类是否属于某个类的子类的类型。

一、&与&&的异同点。相同点：二者都表示与操作，当且仅当运算符两边的操作数都为true时，其结果才为true，否则为false。不同点：在使用&进行运算时，不论左边为true或者false，右边的表达式都会进行运算。如果使用&&进行运算时，当左边为false时，右边的表达式不会进行运算，因此&&被称作短路与。二、|与||的异同点。相同点：二者都表示或操作，当运算符两边的操作数任何一边的值为true时，其结果为true，当两边的值都为false时，其结果才为false。不同点：同与操作类似，||表示短路或，当运算符左边的值为true时，右边的表达式不会进行运算。

4.Java中用于实现线程间的通知与唤醒

wait()、notify()和notifyAll()是 Object类中的方法，从这三个方法的文字描述可以知道以下几点信息：

1）wait()、notify()和notifyAll()方法是本地方法，并且为final方法，无法被重写。

2）调用某个对象的wait()方法能让当前线程阻塞，并且当前线程必须拥有此对象的monitor（即锁）

3）调用某个对象的notify()方法能够唤醒一个正在等待这个对象的monitor的线程，如果有多个线程都在等待这个对象的monitor，则只能唤醒其中一个线程；

4）调用notifyAll()方法能够唤醒所有正在等待这个对象的monitor的线程；

有朋友可能会有疑问：为何这三个不是Thread类声明中的方法，而是Object类中声明的方法（当然由于Thread类继承了Object类，所以Thread也可以调用者三个方法）？其实这个问题很简单，由于每个对象都拥有monitor（即锁），所以让当前线程等待某个对象的锁，当然应该通过这个对象来操作了。而不是用当前线程来操作，因为当前线程可能会等待多个线程的锁，如果通过线程来操作，就非常复杂了。

上面已经提到，如果调用某个对象的wait()方法，当前线程必须拥有这个对象的monitor（即锁），因此调用wait()方法必须在同步块或者同步方法中进行（synchronized块或者synchronized方法）。调用某个对象的wait()方法，相当于让当前线程交出此对象的monitor，然后进入等待状态，等待后续再次获得此对象的锁（Thread类中的 sleep() 方法使当前线程暂停执行一段时间，从而让其他线程有机会继续执行，但它并不释放对象锁）；notify() 方法能够唤醒一个正在等待该对象的monitor的线程，当有多个线程都在等待该对象的monitor的话，则只能唤醒其中一个线程，具体唤醒哪个线程则不得而知。同样地，调用某个对象的 notify() 方法，当前线程也必须拥有这个对象的monitor，因此调用 notify() 方法必须在同步块或者同步方法中进行。nofityAll() 方法能够唤醒所有正在等待该对象的monitor的线程，这一点与notify()方法是不同的。

Condition是在java 1.5中才出现的，它用来替代传统的Object的 wait()、notify() 实现线程间的协作，相比使用Object的wait()、notify()，使用Condition1的 await()、signal() 这种方式实现线程间协作更加安全和高效。因此通常来说比较推荐使用 Condition，阻塞队列实际上是使用了 Condition 来模拟线程间协作。Condition是个接口，基本的方法就是 await()和signal() 方法；

Condition依赖于Lock接口，生成一个 Condition 的基本代码是 lock.newCondition() 调用Condition的await()和signal()方法，都必须在lock保护之内，就是说必须在 lock.lock() 和 lock.unlock 之间才可以使用 Conditon中的await()对应Object的wait()；

Condition中的signal()对应Object的notify()； Condition中的signalAll()对应Object的notifyAll()

#每日一刷#

备战校招 - 努力中文章被收录于专栏

备战校招每日学习记录