Machine Learning notes

Supervised Machine Learning (providing labels)

Regression v.s. Classification:
one for the continuous data, the other for the discrete data.

LintCode 897. Island City - Weekly9

http://www.lintcode.com/en/problem/island-city/

You could use UnionFind, I just don't bother doing it.

As the islands are not dynamic UnionFind is unnecessary.

Just use plain old DFS, trigger it with a simple scan for cities that's not visited, then paint all visited cities with 2(or maybe not, it doesn't matter now).

Then count the number of triggers.

Boom!

	public class Solution {
	/**
	* @param grid: an integer matrix
	* @return: an integer
	*/
	int numIslandCities(int[][] A) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return 0;
	}
	this.m = A.length;
	this.n = A[0].length;
	this.A = A;
	this.visited = new boolean[m][n];
	int counter = 0;
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (A[i][j] == 2 && !visited[i][j]) {
	dfs(i, j);
	counter++;
	}
	}
	}
	// return the final result
	return counter;
	}
	int[][] A;
	boolean[][] visited;
	int m;
	int n;
	private void dfs(int i, int j) {
	if (i < 0 || j < 0 || i >= m || j >= n) {
	return;
	}
	if (A[i][j] == 0) {
	return;
	}
	if (visited[i][j]) {
	return;
	}
	visited[i][j] = true;
	A[i][j] = 2;
	dfs(i - 1, j);
	dfs(i + 1, j);
	dfs(i, j - 1);
	dfs(i, j + 1);
	}
	}

view raw LintCode 897. Island City - Weekly9 - LintCode.java hosted with ❤ by GitHub

LintCode 898. Leftmost One - Weekly9

http://www.lintcode.com/en/problem/leftmost-one/

An interesting questions, i find it sufficient applying binary search.

	public class Solution {
	/**
	* @param arr: The 2-dimension array
	* @return: Return the column the leftmost one is located
	*/
	int getColumn(int[][] A) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return 0;
	}
	this.m = A.length;
	this.n = A[0].length;
	int min = A.length - 1;
	for (int i = 0; i < m; i++) {
	int index = binarySearch(A[i]);
	min = Math.min(min, index);
	}
	// return the final result
	return min;
	}
	int m;
	int n;
	int binarySearch(int[] A) {
	int left = 0;
	int right = A.length - 1;
	while (left + 1 < right) {
	int mid = (right - left) / 2 + left;
	if (A[mid] == 1) {
	right = mid;
	} else {
	left = mid;
	}
	}
	if (A[left] == 1) {
	return left;
	} else {
	return right;
	}
	}
	}

view raw LintCode 898. Leftmost One - Weekly9 - LintCode.java hosted with ❤ by GitHub

LintCode 895. Friend Request - Weekly9

http://www.lintcode.com/en/problem/friend-request/

It's a stupid question. Don't bother optimize with sorting or anything.

Just brute force is more than sufficient.

Nothing more to say...sigh...

	public class Solution {
	/**
	* @param ages: The ages
	* @return: The answer
	*/
	public int friendRequest(int[] ages) {
	// Write your code here
	if (ages == null || ages.length == 0) {
	return 0;
	}
	// Arrays.sort(ages);
	int answer = 0;
	for (int b = 0; b < ages.length; b++) {
	int delta = 0;
	if (ages[b] >= 100) {
	for (int a = 0; a < ages.length; a++) {
	if (a == b) {
	continue;
	}
	// System.out.println("a, b = " + a + ", " + b + "; ages[a], ages[b] = " + ages[a] + ", " + ages[b]);
	if (ages[a] < ages[b] || ages[a] / 2 + 7 >= ages[b]) {
	} else {
	delta++;
	}
	}
	} else {
	for (int a = 0; a < ages.length; a++) {
	if (a == b) {
	continue;
	}
	// System.out.println("a, b = " + a + ", " + b + "; ages[a], ages[b] = " + ages[a] + ", " + ages[b]);
	if (ages[a] > 100 || ages[a] < ages[b] || ages[a] / 2 + 7 >= ages[b]) {
	} else {
	delta++;
	}
	}
	}
	// System.out.println(delta);
	answer += delta;
	}
	return answer;
	}
	}

view raw LintCode 895. Friend Request - Weekly9 - LintCode.java hosted with ❤ by GitHub

LintCode 896. PrimeProduct - Weekly9

http://www.lintcode.com/en/problem/prime-product/

it's a tricky question if you are trying to if-else for 2 to 9 for-loops.

but we can simply use the DFS search.

Then eliminate duplication, and apply ordering.

	public class Solution {
	/**
	* @param arr: The prime array
	* @return: Return the array of all of prime product
	*/
	int[] getPrimeProduct(int[] A) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return new int[0];
	}
	this.A = A;
	this.set = new HashSet<>();
	helper(0, 1, 0);
	TreeSet<Integer> treeSet = new TreeSet<>(set);
	int[] answer = new int[treeSet.size()];
	for (int i = 0; i < answer.length; i++) {
	answer[i] = treeSet.pollFirst();
	}
	// return the final result
	return answer;
	}
	private void helper(int index, int product, int counter) {
	if (index == A.length) {
	if (counter > 1) {
	set.add(product);
	}
	} else {
	helper(index + 1, product * A[index], counter + 1);
	helper(index + 1, product, counter);
	}
	}
	int[] A;
	HashSet<Integer> set;
	}

view raw LintCode No896_PrimeProduct - Weekly9 - LintCode.java hosted with ❤ by GitHub

LeetCode 794. Valid Tic-Tac-Toe State - Weekly Contest 74

https://leetcode.com/contest/weekly-contest-74/problems/valid-tic-tac-toe-state/




It's a simulation, just be patient and careful.

think of all the possibilities. Classified them. use | stand for the column strike, use - for the row strike.

use the \ and / for the diagonals.

	class Solution {
	boolean validTicTacToe(String[] A) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return false;
	}
	int XCount = 0;
	int OCount = 0;
	for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 3; j++) {
	if (A[i].charAt(j) == 'X') {
	XCount++;
	} else if (A[i].charAt(j) == 'O') {
	OCount++;
	}
	}
	}
	int XWinCount = 0;
	int OWinCount = 0;
	if (A[1].charAt(1) != ' ') {
	if (A[1].charAt(1) == 'X') {
	// * / \
	if (A[2].charAt(0) == 'X' && A[0].charAt(2) == 'X') {
	XWinCount++;
	}
	if (A[2].charAt(2) == 'X' && A[0].charAt(0) == 'X') {
	XWinCount++;
	}
	// + - |
	if (A[1].charAt(0) == 'X' && A[1].charAt(2) == 'X') {
	XWinCount++;
	}
	if (A[2].charAt(1) == 'X' && A[0].charAt(1) == 'X') {
	XWinCount++;
	}
	} else {
	// * / \
	if (A[2].charAt(0) == 'O' && A[0].charAt(2) == 'O') {
	OWinCount++;
	}
	if (A[2].charAt(2) == 'O' && A[0].charAt(0) == 'O') {
	OWinCount++;
	}
	// + - |
	if (A[1].charAt(0) == 'O' && A[1].charAt(2) == 'O') {
	OWinCount++;
	}
	if (A[2].charAt(1) == 'O' && A[0].charAt(1) == 'O') {
	OWinCount++;
	}
	}
	}
	if (A[0].charAt(0) != ' ') {
	if (A[0].charAt(0) == 'X') {
	// | -
	if (A[2].charAt(0) == 'X' && A[1].charAt(0) == 'X') {
	XWinCount++;
	}
	if (A[0].charAt(1) == 'X' && A[0].charAt(2) == 'X') {
	XWinCount++;
	}
	} else {
	// | -
	if (A[2].charAt(0) == 'O' && A[1].charAt(0) == 'O') {
	OWinCount++;
	}
	if (A[0].charAt(1) == 'O' && A[0].charAt(2) == 'O') {
	OWinCount++;
	}
	}
	}
	if (A[2].charAt(2) != ' ') {
	if (A[2].charAt(2) == 'X') {
	// | -
	if (A[0].charAt(2) == 'X' && A[1].charAt(2) == 'X') {
	XWinCount++;
	}
	if (A[2].charAt(0) == 'X' && A[2].charAt(1) == 'X') {
	XWinCount++;
	}
	} else {
	// | -
	if (A[0].charAt(2) == 'O' && A[1].charAt(2) == 'O') {
	OWinCount++;
	}
	if (A[2].charAt(0) == 'O' && A[2].charAt(1) == 'O') {
	OWinCount++;
	}
	}
	}
	// System.out.println(XCount);
	// System.out.println(OCount);
	if (XCount != OCount && XCount != (OCount + 1)) {
	return false;
	}
	if (XWinCount + OWinCount > 1) {
	return false;
	}
	if (XWinCount == 1) {
	return XCount == OCount + 1;
	} else if (OWinCount == 1) {
	return XCount == OCount;
	}
	return true;
	}
	}

view raw LC 794. Valid Tic-Tac-Toe State - Weekly Contest 74 - LeetCode.java hosted with ❤ by GitHub