LeetCode 771. Jewels and Stones - Weekly Contest 69

https://leetcode.com/contest/weekly-contest-69/problems/jewels-and-stones/

	class Solution {
	public int numJewelsInStones(String J, String S) {
	if (S == null || S.length() < 1 || J == null || J.length() < 1) {
	return 0;
	}
	int[] L = new int[500];
	for(int i = 0; i < J.length(); i++) {
	L[J.charAt(i)] = 1;
	}
	int count = 0;
	for(int i = 0; i < S.length(); i++) {
	if(L[S.charAt(i)] == 1) {
	count++;
	}
	}
	return count;
	}
	}

view raw LC 771. Jewels and Stones - Weekly Contest 69 - LeetCode.java hosted with ❤ by GitHub

LeetCode 775. Global and Local Inversions - Weekly Contest 69

https://leetcode.com/contest/weekly-contest-69/problems/global-and-local-inversions/

	class Solution {
	public boolean isIdealPermutation(int[] A) {
	if (A == null || A.length < 3) {
	return true;
	}
	int len = A.length;
	for (int i = 0; i < len - 1; i++) {
	if (A[i] == i) {
	continue;
	} else if (A[i] == i+1 && A[i + 1]== i) {
	i++;
	} else {
	return false;
	}
	}
	return true;
	// int globalInversions = 0;
	// for(int i = 0; i < len - 1; i++) {
	// for(int j = i + 1; j < len; j++) {
	// if (A[i] > A[j]) {globalInversions++;}
	// }
	// }
	// int localInversions = 0;
	// for(int i = 0; i < len - 1; i++) {
	// if (A[i] > A[i+1]) {localInversions++;}
	// }
	// return globalInversions == localInversions;
	}
	}

view raw LC 775. Global and Local Inversions - Weekly Contest 69 - LeetCode.java hosted with ❤ by GitHub

LeetCode 159. Longest Substring with At Most Two Distinct Characters - Google - HashMap, Two Pointers, String

The main idea is to maintain a sliding window with 2 unique characters. 

The key is to store the last occurrence of each character as the value in the hashmap.

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/description/

	class Solution {
	public int lengthOfLongestSubstringTwoDistinct(String s) {
	// filter abnormal inputs
	if (s == null) {
	return 0;
	}
	if (s.length() < 3) {
	return s.length();
	}
	// core logic
	int start = 0;
	int end = 0;
	int maxLength = Integer.MIN_VALUE;
	HashMap<Character, Integer> map = new HashMap<>();
	for(int i = 0; i < s.length(); i++) {
	Character key = s.charAt(i);
	if (!map.containsKey(key) && map.size() == 2) {
	// situation 3
	int leftMost = Integer.MAX_VALUE;
	for(int value: map.values()) {
	leftMost = Math.min(leftMost, value);
	}
	start = leftMost + 1;
	map.remove(s.charAt(leftMost));
	}
	map.put(key, end);
	maxLength = Math.max(maxLength, end - start + 1);
	end++;
	}
	return maxLength;
	}
	}

view raw LC 159. Longest Substring with At Most Two Distinct Characters - LeetCode - Google - HashMap, Two Pointers, String.java hosted with ❤ by GitHub

LeetCode 768. Max Chunks to Make Sorted (ver. 2) - Weekly Contest 68

https://leetcode.com/contest/weekly-contest-68/problems/max-chunks-to-make-sorted-ver-2/

	class Solution {
	/**
	* @param arr an array of Integer
	* @return an integer
	*/
	public int maxChunksToSorted(int[] arr) {
	// filter abnormal cases
	if (arr == null || arr.length == 0) {
	return 1;
	}
	// core logic
	int max = arr[0];
	int cutCounter = 1;
	int[] copy = Arrays.copyOf(arr, arr.length);
	Arrays.sort(copy);
	// System.out.println(Arrays.toString(copy));
	// System.out.println(Arrays.toString(arr));
	HashMap<Integer, Integer> map = new HashMap<>();
	for (int i = 0; i < arr.length - 1; i++) {
	// System.out.println("i = " + i);
	// System.out.println("map = " + map);
	if (stepAndIsEmpty(copy[i], arr[i], map)) {
	// System.out.println("Got a cut! i = " + i);
	// System.out.println("copy[i] = " + copy[i]);
	// System.out.println("arr[i] = " + arr[i]);
	cutCounter++;
	}
	}
	// return the final result
	return cutCounter;
	}
	private boolean stepAndIsEmpty(int keyToAdd, int keyToKill, HashMap<Integer, Integer> map) {
	if (keyToAdd != keyToKill) {
	if (map.containsKey(keyToAdd)) {
	if (map.get(keyToAdd) + 1 == 0) {
	map.remove(keyToAdd);
	} else {
	map.put(keyToAdd, map.get(keyToAdd) + 1);
	}
	} else {
	map.put(keyToAdd, 1);
	}
	if (map.containsKey(keyToKill)) {
	if (map.get(keyToKill) - 1 == 0) {
	map.remove(keyToKill);
	} else {
	map.put(keyToKill, map.get(keyToKill) - 1);
	}
	} else {
	map.put(keyToKill, -1);
	}
	}
	return map.isEmpty();
	}
	}

view raw LC 768. Max Chunks to Make Sorted (ver. 2) - Weekly Contest 68 - LeetCode.java hosted with ❤ by GitHub

LeetCode 769. Max Chunks To Make Sorted (ver. 1) - Weekly Contest 68

https://leetcode.com/contest/weekly-contest-68/problems/max-chunks-to-make-sorted-ver-1/

	class Solution {
	/**
	* @param arr
	* @return
	*/
	public int maxChunksToSorted(int[] arr) {
	// filter abnormal cases
	if (arr == null || arr.length == 0) {
	return 1;
	}
	// core logic
	int[] map = new int[arr.length];
	for (int i = 0; i < arr.length; i++) {
	map[arr[i]] = i;
	}
	int minCut = 0;
	int cutCounter = 1;
	for (int i = 0; i < arr.length - 1; i++) {
	int tmpRquire = Math.max(map[arr[i]], arr[i]);
	minCut = Math.max(minCut, tmpRquire);
	if (minCut <= i) {
	// System.out.println("Got a cut!! minCut = " + minCut);
	// System.out.println("cutCounter = " + cutCounter);
	// System.out.println("tmpRquire = " + tmpRquire);
	// System.out.println("i = " + i);
	minCut = i + 1;
	cutCounter++;
	}
	}
	// return the final result
	return cutCounter;
	}
	}

view raw LC 769. Max Chunks To Make Sorted (ver. 1) - Weekly Contest 68 - LeetCode.java hosted with ❤ by GitHub

LeetCode 766. Toeplitz Matrix - Weekly Contest 68

https://leetcode.com/contest/weekly-contest-68/problems/toeplitz-matrix/

	class Solution {
	/**
	* @param matrix
	* @return
	*/
	public boolean isToeplitzMatrix(int[][] matrix) {
	// filter abnormal cases
	if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
	return true;
	}
	// core logic
	int m = matrix.length;
	int n = matrix[0].length;
	if (MyLogger.isDebugging) {
	for (int[] aMatrix : matrix) {
	System.out.println(Arrays.toString(aMatrix));
	}
	for (int T = m - 1; T >= 0; T--) {
	int i = T;
	int j = 0;
	final int target = matrix[i][j];
	System.out.println("Shu: " + matrix[i][j]);
	i++;
	j++;
	while (isValid(i, j, m, n)) {
	System.out.println("Shu: " + matrix[i][j]);
	if (matrix[i][j] != target) {
	return false;
	}
	i++;
	j++;
	}
	}
	for (int T = 1; T < n; T++) {
	int i = 0;
	int j = T;
	final int target = matrix[i][j];
	System.out.println("heng: " + matrix[i][j]);
	i++;
	j++;
	while (isValid(i, j, m, n)) {
	System.out.println("heng: " + matrix[i][j]);
	if (matrix[i][j] != target) {
	return false;
	}
	i++;
	j++;
	}
	}
	}
	for (int T = m - 1; T >= 0; T--) {
	int i = T;
	int j = 0;
	final int target = matrix[i][j];
	i++;
	j++;
	while (isValid(i, j, m, n)) {
	if (matrix[i][j] != target) {
	return false;
	}
	i++;
	j++;
	}
	}
	for (int T = 1; T < n; T++) {
	int i = 0;
	int j = T;
	final int target = matrix[i][j];
	i++;
	j++;
	while (isValid(i, j, m, n)) {
	if (matrix[i][j] != target) {
	return false;
	}
	i++;
	j++;
	}
	}
	// return the final result
	return true;
	}
	private boolean isValid(int x, int y, int m, int n) {
	return x >= 0 && y >= 0 && x < m && y < n;
	}
	private static class MyLogger {
	static boolean isDebugging = false;
	static boolean isInfoing = true;
	static void debug(Object message) {
	if (isDebugging) {
	System.out.println("MyLogger.Debugging = " + message);
	}
	}
	static void info(Object message) {
	if (isInfoing) {
	System.out.println("MyLogger.Debugging = " + message);
	}
	}
	}
	}

view raw LC 766. Toeplitz Matrix - Weekly Contest 68 - LeetCode.java hosted with ❤ by GitHub

LCS - Longest Common Subsequence - Dynamic Programming

https://practice.geeksforgeeks.org/problems/longest-common-subsequence/0/?ref=self

	/*package whatever //do not write package name here */
	import java.util.*;
	import java.lang.*;
	import java.io.*;
	class GFG {
	public static void main(String[] args) {
	//code
	Scanner scanner = new Scanner(System.in);
	int T = scanner.nextInt();
	for (int t = 0; t < T; t++) {
	int m = scanner.nextInt();
	int n = scanner.nextInt();
	if (m < 1) {
	System.out.println(n);
	} else if (n < 1) {
	System.out.println(m);
	}
	String string1 = scanner.next();
	String string2 = scanner.next();
	int[][] dp = new int[m][n];
	int globalMax = 0;
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (string1.charAt(i) == string2.charAt(j)) {
	int localMax = 0;
	for (int x = 0; x < i; x++) {
	for (int y = 0; y < j; y++) {
	localMax = Math.max(localMax, dp[x][y]);
	}
	}
	dp[i][j] = localMax + 1;
	globalMax = Math.max(globalMax, dp[i][j]);
	}
	}
	}
	// System.out.println(Arrays.toString(dp));
	System.out.println(globalMax);
	}
	}
	}

view raw LCS - Longest Common Subsequence - Dynamic Programming.java hosted with ❤ by GitHub

LIS - Longest Increasing Subsequence - Dynamic Programming

https://practice.geeksforgeeks.org/problems/longest-increasing-subsequence/0

	/*package whatever //do not write package name here */
	import java.util.*;
	import java.lang.*;
	import java.io.*;
	class GFG {
	public static void main(String[] args) {
	//code
	Scanner scanner = new Scanner(System.in);
	int T = scanner.nextInt();
	for (int t = 0; t < T; t++) {
	int N = scanner.nextInt();
	if (N < 1) {
	System.out.println(0);
	continue;
	}
	int[] A = new int[N];
	for (int i = 0; i < N; i++) {
	A[i] = scanner.nextInt();
	}
	// DP
	int[] dp = new int[N];
	dp[0] = 1;
	int globalMax = 1;
	for (int i = 1; i < N; i++) {
	dp[i] = 1;
	int max = 0;
	for (int j = 0; j < i; j++) {
	if (A[j] < A[i]) {
	max = Math.max(max, dp[j]);
	}
	}
	dp[i] += max;
	globalMax = Math.max(globalMax, dp[i]);
	}
	// System.out.println(Arrays.toString(dp));
	System.out.println(globalMax);
	}
	}
	}

view raw LIS - Longest Increasing Subsequence - Dynamic Programming.java hosted with ❤ by GitHub

HR Hash Tables: Ice Cream Parlor - HackerRank Cracking the Coding Interview Challenges

https://www.hackerrank.com/challenges/ctci-ice-cream-parlor/problem

	import java.io.*;
	import java.util.*;
	import java.text.*;
	import java.math.*;
	import java.util.regex.*;
	public class Solution {
	/**
	* @param arr
	* @param money
	*/
	static void solve(int[] arr, int money) {
	// Complete this function
	if (arr == null || arr.length < 1) {
	System.out.println(-1 + " " + -1);
	return;
	}
	// core logic
	HashMap<Integer, Integer> hashMap = new HashMap<>();
	for (int i = 0; i < arr.length; i++) {
	if (arr[i] < money) {
	if (hashMap.containsKey(money - arr[i])) {
	int index = hashMap.get(money - arr[i]);
	System.out.println((index + 1) + " " + (i + 1));
	return;
	}
	if (!hashMap.containsKey(arr[i])) {
	hashMap.put(arr[i], i);
	}
	}
	}
	}
	public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	int t = in.nextInt();
	for(int a0 = 0; a0 < t; a0++){
	int money = in.nextInt();
	int n = in.nextInt();
	int[] arr = new int[n];
	for(int arr_i = 0; arr_i < n; arr_i++){
	arr[arr_i] = in.nextInt();
	}
	solve(arr, money);
	}
	in.close();
	}
	}

view raw HR Hash Tables: Ice Cream Parlor - HackerRank Cracking the Coding Interview Challenges.java hosted with ❤ by GitHub

LC 375. Guess Number Higher or Lower II - LeetCode Google DynamicProgramming MinMax

https://leetcode.com/problems/guess-number-higher-or-lower-ii/description/

	class Solution {
	/**
	* @param n
	* @return
	*/
	public int getMoneyAmount(int n) {
	if (n < 2) {
	return 0;
	}
	// core logic
	table = new int[n + 1][n + 1];
	return dp(1, n);
	}
	private int[][] table;
	private int dp(int start, int end) {
	if (start >= end) {
	return 0;
	}
	if (table[start][end] != 0) {
	return table[start][end];
	}
	int min = Integer.MAX_VALUE;
	for (int i = start; i <= end; i++) {
	int res = i + Math.max(dp(start, i - 1), dp(i + 1, end));
	min = Math.min(min, res);
	}
	table[start][end] = min;
	return min;
	}
	}

view raw LC 375. Guess Number Higher or Lower II - LeetCode Google DynamicProgramming MinMax.java hosted with ❤ by GitHub

LC 374. Guess Number Higher or Lower - LeetCode Google BinarySearch

https://leetcode.com/problems/guess-number-higher-or-lower/description/

	/* The guess API is defined in the parent class GuessGame.
	@param num, your guess
	@return -1 if my number is lower, 1 if my number is higher, otherwise return 0
	int guess(int num); */
	public class Solution extends GuessGame {
	public int guessNumber(int n) {
	if (n < 2) {
	return n;
	}
	// core logic
	int start = 1;
	int end = n;
	while(start + 1 < end) {
	int mid = (end - start) / 2 + start;
	int tmpResult = guess(mid);
	if (tmpResult == -1) {
	end = mid;
	} else if (tmpResult == 1) {
	start = mid;
	} else {
	return mid;
	}
	}
	if (guess(start) == 0) {
	return start;
	} else {
	return end;
	}
	}
	}

view raw LC 374. Guess Number Higher or Lower - LeetCode Google BinarySearch.java hosted with ❤ by GitHub

LC 278. First Bad Version - LeetCode Facebook BinarySearch

https://leetcode.com/problems/first-bad-version/description/

	/* The isBadVersion API is defined in the parent class VersionControl.
	boolean isBadVersion(int version); */
	public class Solution extends VersionControl {
	public int firstBadVersion(int n) {
	if (n < 2) {
	return n;
	}
	// core logic
	int start = 1;
	int end = n;
	while(start + 1 < end) {
	int mid = (end - start) / 2 + start;
	if (isBadVersion(mid)) {
	end = mid;
	} else {
	start = mid;
	}
	}
	if (isBadVersion(start)) {
	return start;
	} else {
	return end;
	}
	}
	}

view raw LC 278. First Bad Version - LeetCode Facebook BinarySearch.java hosted with ❤ by GitHub

LC 683. K Empty Slots - LeetCode Hard Google TreeSet

https://leetcode.com/problems/k-empty-slots/description/

	class Solution {
	public int kEmptySlots(int[] flowers, int k) {
	if (flowers == null || flowers.length < 1) {
	return -1;
	}
	// core logic
	TreeSet<Integer> bloomingTreeSet = new TreeSet<>();
	int day = 0;
	for(int flower: flowers) {
	day++;
	bloomingTreeSet.add(flower);
	Integer higher = bloomingTreeSet.higher(flower);
	Integer lower = bloomingTreeSet.lower(flower);
	if (higher != null && higher - flower - 1 == k ||
	lower != null && flower - lower - 1 == k ) {
	return day;
	}
	}
	return -1;
	}
	}

view raw LC 683. K Empty Slots - LeetCode Hard Google TreeSet.java hosted with ❤ by GitHub

LC 35. Search Insert Position - LeetCode

This question requires a straightforward scan.
We can't help but notice there's only two situations:
0. empty array, so go ahead and insert into 0;
1. if you see nums[i] equal to the target, congratulations and return the i! Also, if you see nums[i] larger, go ahead and return the i because it will be inserted into i.
2. If you can't find such a fit in the Rule No.1. Go ahead and append it to the very end of the Array. And that would be nums.length;

So my clever reader now you can go ahead and give it a try yourself.
:)

	class Solution {
	public int searchInsert(int[] nums, int target) {
	if (nums == null || nums.length < 1) {
	return 0;
	}
	// O(n) traverse
	for(int i = 0; i < nums.length; i++) {
	if (target <= nums[i]) {
	return i;
	}
	}
	return nums.length;
	}
	}

view raw LC 35. Search Insert Position - LeetCode.java hosted with ❤ by GitHub

LC 102. Binary Tree Level Order Traversal - LeetCode

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	/**
	* @param root
	* @return
	*/
	public List<List<Integer>> levelOrder(TreeNode root) {
	// filter abnormal cases
	if (root == null) {
	return new LinkedList<>();
	}
	// core logic
	Queue<Entry> queue1 = new LinkedList<>();
	Queue<Entry> queue2 = new LinkedList<>();
	queue1.add(new Entry(root, 1));
	List<List<Integer>> resultList = new LinkedList<>();
	while (true) {
	if (queue1.isEmpty()) {
	return resultList;
	}
	List<Integer> row = new LinkedList<>();
	rowProcessing(queue1, queue2, row);
	resultList.add(row);
	Queue<Entry> tmp = queue1;
	queue1 = queue2;
	queue2 = tmp;
	}
	}
	private void rowProcessing(Queue<Entry> queue1, Queue<Entry> queue2, List<Integer> row) {
	while (!queue1.isEmpty()) {
	Entry currentEntry = queue1.remove();
	row.add(currentEntry.node.val);
	if (currentEntry.node.left != null) {
	queue2.add(new Entry(currentEntry.node.left, currentEntry.depth + 1));
	}
	if (currentEntry.node.right != null) {
	queue2.add(new Entry(currentEntry.node.right, currentEntry.depth + 1));
	}
	}
	}
	class Entry {
	TreeNode node;
	int depth;
	public Entry(TreeNode node, int depth) {
	this.node = node;
	this.depth = depth;
	}
	@Override
	public String toString() {
	return "Entry{" +
	"node=" + node +
	", depth=" + depth +
	'}';
	}
	}
	}

view raw LC 102. Binary Tree Level Order Traversal - Weekly Contest 67 - LeetCode.java hosted with ❤ by GitHub

LC 765. Couples Holding Hands - Weekly Contest 67 - LeetCode

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples' initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example 1:

Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.
Example 2:

Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.
Note:

len(row) is even and in the range of [4, 60].
row is guaranteed to be a permutation of 0...len(row)-1.

	class Solution {
	/**
	* @param row
	* @return
	*/
	public int minSwapsCouples(int[] row) {
	// filter abnormal cases
	if (row == null || row.length == 0) {
	return 0;
	}
	// core logic
	int swapCounter = 0;
	HashMap<Integer, Integer> lookup = new HashMap<>();
	for (int i = 0; i < row.length; i++) {
	lookup.put(row[i], i);
	}
	for (int i = 0; i < row.length; i += 2) {
	if (!isPair(row[i], row[i + 1])) {
	swap(row, i + 1, lookup.get(getPartner(row[i])), lookup);
	swapCounter++;
	}
	}
	// return the final result
	return swapCounter;
	}
	private int getPartner(int i) {
	if (i % 2 == 0) {
	return i + 1;
	} else {
	return i - 1;
	}
	}
	private void swap(int[] row, int i, int j, HashMap<Integer, Integer> lookup) {
	int tmp = row[i];
	lookup.put(row[i], j);
	lookup.put(row[j], i);
	row[i] = row[j];
	row[j] = tmp;
	}
	private boolean isPair(int a, int b) {
	return a / 2 == b / 2;
	}
	}

view raw LC 765. Couples Holding Hands.java hosted with ❤ by GitHub

LC 764. Largest Plus Sign - Weekly Contest 67 - LeetCode

In a 2D grid from (0, 0) to (N-1, N-1), every cell contains a 1, except those cells in the given list mines which are 0. What is the largest axis-aligned plus sign of 1s contained in the grid? Return the order of the plus sign. If there is none, return 0.

An "axis-aligned plus sign of 1s of order k" has some center grid[x][y] = 1 along with 4 arms of length k-1 going up, down, left, and right, and made of 1s. This is demonstrated in the diagrams below. Note that there could be 0s or 1s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1s.

Examples of Axis-Aligned Plus Signs of Order k:

Order 1:
000
010
000

Order 2:
00000
00100
01110
00100
00000

Order 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000
Example 1:

Input: N = 5, mines = [[4, 2]]
Output: 2
Explanation:
11111
11111
11111
11111
11011
In the above grid, the largest plus sign can only be order 2.  One of them is marked in bold.
Example 2:

Input: N = 2, mines = []
Output: 1
Explanation:
There is no plus sign of order 2, but there is of order 1.
Example 3:

Input: N = 1, mines = [[0, 0]]
Output: 0
Explanation:
There is no plus sign, so return 0.
Note:

N will be an integer in the range [1, 500].
mines will have length at most 5000.
mines[i] will be length 2 and consist of integers in the range [0, N-1].
(Additionally, programs submitted in C, C++, or C# will be judged with a slightly smaller time limit.)


首先是把十字架的需求分解成四个方向。
这样理解就有思路了。
接着一看可以上动归。
四个方向分别开个dp数组，动态规划，全是O(N^N)的时空复杂度。
最后扫一遍得出结果，最边缘的地方特殊情况放最后处理。

最终时空复杂度O(N^N)

	class Solution {
	/**
	* @param N
	* @param mines
	* @return
	*/
	public int orderOfLargestPlusSign(int N, int[][] mines) {
	// filter abnormal cases
	if (mines == null || mines.length == 0) {
	return (N + 1) / 2;
	}
	// core logic
	int m = mines.length;
	int[][] matrix = new int[N][N];
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	matrix[i][j] = 1;
	}
	}
	for (int[] mine : mines) {
	matrix[mine[0]][mine[1]] = 0;
	}
	int[][] dpUp = new int[N][N];
	int[][] dpDown = new int[N][N];
	int[][] dpLeft = new int[N][N];
	int[][] dpRight = new int[N][N];
	for (int i = 1; i < N; i++) {
	for (int j = 0; j < N; j++) {
	if (matrix[i - 1][j] == 0) {
	dpUp[i][j] = 0;
	} else {
	dpUp[i][j] = dpUp[i - 1][j] + 1;
	}
	}
	}
	for (int i = N - 2; i >= 0; i--) {
	for (int j = 0; j < N; j++) {
	if (matrix[i + 1][j] == 0) {
	dpDown[i][j] = 0;
	} else {
	dpDown[i][j] = dpDown[i + 1][j] + 1;
	}
	}
	}
	//left
	for (int j = 1; j < N; j++) {
	for (int i = 0; i < N; i++) {
	if (matrix[i][j - 1] == 0) {
	dpLeft[i][j] = 0;
	} else {
	dpLeft[i][j] = dpLeft[i][j - 1] + 1;
	}
	}
	}
	//right
	for (int j = N - 2; j >= 0; j--) {
	for (int i = 0; i < N; i++) {
	if (matrix[i][j + 1] == 0) {
	dpRight[i][j] = 0;
	} else {
	dpRight[i][j] = dpRight[i][j + 1] + 1;
	}
	}
	}
	// Final Scan
	int maxK = 0;
	for (int i = 1; i < N - 1; i++) {
	for (int j = 1; j < N - 1; j++) {
	if (matrix[i][j] == 1) {
	maxK = Math.max(maxK, 1 + Math.min(Math.min(dpUp[i][j], dpDown[i][j]), Math.min(dpLeft[i][j], dpRight[i][j])));
	}
	}
	}
	if (maxK < 1) {
	for (int i = 0; i < N; i++) {
	if (matrix[i][0] == 1 || matrix[i][N - 1] == 1) {
	maxK = 1;
	return maxK;
	}
	}
	for (int j = 1; j < N - 1; j++) {
	if (matrix[0][j] == 1 || matrix[N - 1][j] == 1) {
	maxK = 1;
	return maxK;
	}
	}
	}
	// return the final result
	return maxK;
	}
	}

view raw LC 764. Largest Plus Sign.java hosted with ❤ by GitHub

LC 762. Prime Number of Set Bits in Binary Representation - Weekly Contest 67 - LeetCode

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Input: L = 6, R = 10
Output: 4
Explanation:
6 -> 110 (2 set bits, 2 is prime)
7 -> 111 (3 set bits, 3 is prime)
9 -> 1001 (2 set bits , 2 is prime)
10->1010 (2 set bits , 2 is prime)
Example 2:

Input: L = 10, R = 15
Output: 5
Explanation:
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)
Note:

L, R will be integers L <= R in the range [1, 10^6].
R - L will be at most 10000.

	class Solution {
	/**
	* @param L
	* @param R
	* @return
	*/
	public int countPrimeSetBits(int L, int R) {
	if (L > R) {
	return 0;
	}
	// core logic
	int counter = 0;
	for (int i = L; i <= R; i++) {
	if (isPrime(numberOfBits(i))) {
	counter++;
	}
	}
	return counter;
	}
	private int numberOfBits(int i) {
	int counter = 0;
	while (i > 0) {
	counter += i % 2;
	i /= 2;
	}
	return counter;
	}
	private static HashSet<Integer> primeSet = new HashSet<>();
	static {
	{
	primeSet.add(2);
	primeSet.add(3);
	primeSet.add(5);
	primeSet.add(7);
	primeSet.add(11);
	primeSet.add(13);
	primeSet.add(17);
	primeSet.add(19);
	primeSet.add(23);
	primeSet.add(29);
	primeSet.add(31);
	}
	}
	private boolean isPrime(int i) {
	return primeSet.contains(i);
	}
	}

view raw 762. Prime Number of Set Bits in Binary Representation.java hosted with ❤ by GitHub

LC 763. Partition Labels - Weekly Contest 67 - LeetCode

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:
Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
Note:

S will have length in range [1, 500].
S will consist of lowercase letters ('a' to 'z') only.


这题要求最多的partition。
那么我们从左到右遍历一遍，用贪心算法。
能分马上分。除非这个字母在后边还出现而不可分离。
那么聪明的读者可能想到了，我怎么知道这个/些字符在后边还有没有，有的话在多后？
我这里采用的是先扫一遍用HashMap把每个char的起始坐标给缓存起来，
第二遍直接查缓存，进而得出结果。

时间复杂度就是O(n)

	class Solution {
	/**
	* @param S
	* @return
	*/
	public List<Integer> partitionLabels(String S) {
	if (S == null) {
	return new LinkedList<>();
	}
	// core logic
	HashMap<Character, Pair> lookup = new HashMap<>();
	for (int i = 0; i < S.length(); i++) {
	if (lookup.containsKey(S.charAt(i))) {
	lookup.get(S.charAt(i)).end = i;
	} else {
	lookup.put(S.charAt(i), new Pair(i, i));
	}
	}
	LinkedList<Integer> ends = new LinkedList<>();
	for (int i = 0; i < S.length(); ) {
	int end = Math.max(i, lookup.get(S.charAt(i)).end);
	while (i < end) {
	i++;
	end = Math.max(end, lookup.get(S.charAt(i)).end);
	}
	ends.add(end + 1);
	i++;
	}
	LinkedList<Integer> results = new LinkedList<>();
	results.add(ends.get(0));
	for (int i = 1; i < ends.size(); i++) {
	results.add(ends.get(i) - ends.get(i - 1));
	}
	return results;
	}
	private class Pair {
	int start;
	int end;
	public Pair(int start, int end) {
	this.start = start;
	this.end = end;
	}
	@Override
	public String toString() {
	return "Pair{" +
	"start=" + start +
	", end=" + end +
	'}';
	}
	}
	}

view raw LC 763. Partition Labels.java hosted with ❤ by GitHub