class Solution {
public boolean backspaceCompare(String S, String T) {
return build(S).equals(build(T));
}
public String build(String S) {
Stack<Character> ans = new Stack();
for (char c: S.toCharArray()) {
if (c != '#')
ans.push(c);
else if (!ans.empty())
ans.pop();
}
return String.valueOf(ans);
}
}
class Solution {
public boolean backspaceCompare(String S, String T) {
int i = S.length() - 1, j = T.length() - 1;
int skipS = 0, skipT = 0;
while (i >= 0 || j >= 0) { // While there may be chars in build(S) or build (T)
while (i >= 0) { // Find position of next possible char in build(S)
if (S.charAt(i) == '#') {skipS++; i--;}
else if (skipS > 0) {skipS--; i--;}
else break;
}
while (j >= 0) { // Find position of next possible char in build(T)
if (T.charAt(j) == '#') {skipT++; j--;}
else if (skipT > 0) {skipT--; j--;}
else break;
}
// If two actual characters are different
if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j))
return false;
// If expecting to compare char vs nothing
if ((i >= 0) != (j >= 0))
return false;
i--; j--;
}
return true;
}
}
class Solution {
public int maxDistToClosest(int[] seats) {
int N = seats.length;
int[] left = new int[N], right = new int[N];
Arrays.fill(left, N);
Arrays.fill(right, N);
for (int i = 0; i < N; ++i) {
if (seats[i] == 1) left[i] = 0;
else if (i > 0) left[i] = left[i-1] + 1;
}
for (int i = N-1; i >= 0; --i) {
if (seats[i] == 1) right[i] = 0;
else if (i < N-1) right[i] = right[i+1] + 1;
}
int ans = 0;
for (int i = 0; i < N; ++i)
if (seats[i] == 0)
ans = Math.max(ans, Math.min(left[i], right[i]));
return ans;
}
}
class Solution {
public int maxDistToClosest(int[] seats) {
int N = seats.length;
int prev = -1, future = 0;
int ans = 0;
for (int i = 0; i < N; ++i) {
if (seats[i] == 1) {
prev = i;
} else {
while (future < N && seats[future] == 0 || future < i)
future++;
int left = prev == -1 ? N : i - prev;
int right = future == N ? N : future - i;
ans = Math.max(ans, Math.min(left, right));
}
}
return ans;
}
}
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0, ten = 0;
for (int bill: bills) {
if (bill == 5)
five++;
else if (bill == 10) {
if (five == 0) return false;
five--;
ten++;
} else {
if (five > 0 && ten > 0) {
five--;
ten--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}
}
class Solution {
public int binaryGap(int N) {
int[] A = new int[32];
int t = 0;
for (int i = 0; i < 32; ++i)
if (((N >> i) & 1) != 0)
A[t++] = i;
int ans = 0;
for (int i = 0; i < t - 1; ++i)
ans = Math.max(ans, A[i+1] - A[i]);
return ans;
}
}
class Solution {
public int binaryGap(int N) {
int last = -1, ans = 0;
for (int i = 0; i < 32; ++i)
if (((N >> i) & 1) > 0) {
if (last >= 0)
ans = Math.max(ans, i - last);
last = i;
}
return ans;
}
}
class Solution {
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
List<Integer> leaves1 = new ArrayList();
List<Integer> leaves2 = new ArrayList();
dfs(root1, leaves1);
dfs(root2, leaves2);
return leaves1.equals(leaves2);
}
public void dfs(TreeNode node, List<Integer> leafValues) {
if (node != null) {
if (node.left == null && node.right == null)
leafValues.add(node.val);
dfs(node.left, leafValues);
dfs(node.right, leafValues);
}
}
}
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
class Solution {
public boolean isMonotonic(int[] A) {
int store = 0;
for (int i = 0; i < A.length - 1; ++i) {
int c = Integer.compare(A[i], A[i+1]);
if (c != 0) {
if (c != store && store != 0)
return false;
store = c;
}
}
return true;
}
}
class Solution {
public TreeNode increasingBST(TreeNode root) {
List<Integer> vals = new ArrayList();
inorder(root, vals);
TreeNode ans = new TreeNode(0), cur = ans;
for (int v: vals) {
cur.right = new TreeNode(v);
cur = cur.right;
}
return ans.right;
}
public void inorder(TreeNode node, List<Integer> vals) {
if (node == null) return;
inorder(node.left, vals);
vals.add(node.val);
inorder(node.right, vals);
}
}
class Solution {
TreeNode cur;
public TreeNode increasingBST(TreeNode root) {
TreeNode ans = new TreeNode(0);
cur = ans;
inorder(root);
return ans.right;
}
public void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
node.left = null;
cur.right = node;
cur = node;
inorder(node.right);
}
}
class Solution {
public int[] sortArrayByParity(int[] A) {
Integer[] B = new Integer[A.length];
for (int t = 0; t < A.length; ++t)
B[t] = A[t];
Arrays.sort(B, (a, b) -> Integer.compare(a%2, b%2));
for (int t = 0; t < A.length; ++t)
A[t] = B[t];
return A;
/* Alternative:
return Arrays.stream(A)
.boxed()
.sorted((a, b) -> Integer.compare(a%2, b%2))
.mapToInt(i -> i)
.toArray();
*/
}
}
class Solution {
public int[] sortArrayByParity(int[] A) {
int i = 0, j = A.length - 1;
while (i < j) {
if (A[i] % 2 > A[j] % 2) {
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
if (A[i] % 2 == 0) i++;
if (A[j] % 2 == 1) j--;
}
return A;
}
}
class Solution {
public int smallestRangeI(int[] A, int K) {
int min = A[0], max = A[0];
for (int x: A) {
min = Math.min(min, x);
max = Math.max(max, x);
}
return Math.max(0, max - min - 2*K);
}
}
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
int[] count = new int[10000];
for (int c: deck)
count[c]++;
int g = -1;
for (int i = 0; i < 10000; ++i)
if (count[i] > 0) {
if (g == -1)
g = count[i];
else
g = gcd(g, count[i]);
}
return g >= 2;
}
public int gcd(int x, int y) {
return x == 0 ? y : gcd(y%x, x);
}
}
class Solution {
public String reverseOnlyLetters(String S) {
StringBuilder ans = new StringBuilder();
int j = S.length() - 1;
for (int i = 0; i < S.length(); ++i) {
if (Character.isLetter(S.charAt(i))) {
while (!Character.isLetter(S.charAt(j)))
j--;
ans.append(S.charAt(j--));
} else {
ans.append(S.charAt(i));
}
}
return ans.toString();
}
}
class Solution {
public int[] sortArrayByParityII(int[] A) {
int N = A.length;
int[] ans = new int[N];
int t = 0;
for (int x: A) if (x % 2 == 0) {
ans[t] = x;
t += 2;
}
t = 1;
for (int x: A) if (x % 2 == 1) {
ans[t] = x;
t += 2;
}
return ans;
}
}
class Solution {
public int[] sortArrayByParityII(int[] A) {
int j = 1;
for (int i = 0; i < A.length; i += 2)
if (A[i] % 2 == 1) {
while (A[j] % 2 == 1)
j += 2;
// Swap A[i] and A[j]
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
return A;
}
}
class RecentCounter {
Queue<Integer> q;
public RecentCounter() {
q = new LinkedList();
}
public int ping(int t) {
q.add(t);
while (q.peek() < t - 3000)
q.poll();
return q.size();
}
}
class Solution {
int ans;
public int rangeSumBST(TreeNode root, int L, int R) {
ans = 0;
dfs(root, L, R);
return ans;
}
public void dfs(TreeNode node, int L, int R) {
if (node != null) {
if (L <= node.val && node.val <= R){
ans += node.val;
dfs(node.left, L, R);
dfs(node.right, L, R);
}else if (L > node.val){
dfs(node.right, L, R);
}else if (node.val > R){
dfs(node.left, L, R);
}
}
}
}
class Solution {
public int rangeSumBST(TreeNode root, int L, int R) {
int ans = 0;
Stack<TreeNode> stack = new Stack();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
if (L <= node.val && node.val <= R)
ans += node.val;
if (L < node.val)
stack.push(node.left);
if (node.val < R)
stack.push(node.right);
}
}
return ans;
}
}
class Solution {
public boolean validMountainArray(int[] A) {
int N = A.length;
int i = 0;
// walk up
while (i+1 < N && A[i] < A[i+1])
i++;
// peak can't be first or last
if (i == 0 || i == N-1)
return false;
// walk down
while (i+1 < N && A[i] > A[i+1])
i++;
return i == N-1;
}
}
class Solution {
public int minDeletionSize(String[] A) {
int ans = 0;
for (int c = 0; c < A[0].length(); ++c)
for (int r = 0; r < A.length - 1; ++r)
if (A[r].charAt(c) > A[r+1].charAt(c)) {
ans++;
break;
}
return ans;
}
}
由题意可得，结果出现N次，则其他数字出现一次
1.将数组两两分组，若某一组两个数字相同，这就是结果
2.遍历一遍没有结果的话，说明N个这个结果恰好分散在N组数中
于是，只要判断前四个数出现两次的即可
class Solution {
public int repeatedNTimes(int[] A) {
for (int k = 1; k <= 3; ++k)
for (int i = 0; i < A.length - k; ++i)
if (A[i] == A[i+k])
return A[i];
throw null;
}
}
class Solution {
List<Integer> vals;
public boolean isUnivalTree(TreeNode root) {
vals = new ArrayList();
dfs(root);
for (int v: vals)
if (v != vals.get(0))
return false;
return true;
}
public void dfs(TreeNode node) {
if (node != null) {
vals.add(node.val);
dfs(node.left);
dfs(node.right);
}
}
}
class Solution {
public boolean isUnivalTree(TreeNode root) {
boolean left_correct = (root.left == null ||
(root.val == root.left.val && isUnivalTree(root.left)));
boolean right_correct = (root.right == null ||
(root.val == root.right.val && isUnivalTree(root.right)));
return left_correct && right_correct;
}
}
class Solution {
public List<Integer> powerfulIntegers(int x, int y, int bound) {
Set<Integer> seen = new HashSet();
for (int i = 0; i < 18 && Math.pow(x, i) <= bound; ++i)
for (int j = 0; j < 18 && Math.pow(y, j) <= bound; ++j) {
int v = (int) Math.pow(x, i) + (int) Math.pow(y, j);
if (v <= bound)
seen.add(v);
}
return new ArrayList(seen);
}
}
class Solution {
public int largestPerimeter(int[] A) {
Arrays.sort(A);
for (int i = A.length - 3; i >= 0; --i)
if (A[i] + A[i+1] > A[i+2])
return A[i] + A[i+1] + A[i+2];
return 0;
}
}
class Solution {
public int[] sortedSquares(int[] A) {
int N = A.length;
int j = 0;
while (j < N && A[j] < 0)
j++;
int i = j-1;
int[] ans = new int[N];
int t = 0;
while (i >= 0 && j < N) {
if (A[i] * A[i] < A[j] * A[j]) {
ans[t++] = A[i] * A[i];
i--;
} else {
ans[t++] = A[j] * A[j];
j++;
}
}
while (i >= 0) {
ans[t++] = A[i] * A[i];
i--;
}
while (j < N) {
ans[t++] = A[j] * A[j];
j++;
}
return ans;
}
}
class Solution {
public int[] sumEvenAfterQueries(int[] A, int[][] queries) {
int S = 0;
for (int x: A)
if (x % 2 == 0)
S += x;
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; ++i) {
int val = queries[i][0], index = queries[i][1];
if (A[index] % 2 == 0) S -= A[index];
A[index] += val;
if (A[index] % 2 == 0) S += A[index];
ans[i] = S;
}
return ans;
}
}
class Solution {
public List<Integer> addToArrayForm(int[] A, int K) {
int N = A.length;
int cur = K;
List<Integer> ans = new ArrayList();
int i = N;
while (--i >= 0 || cur > 0) {
if (i >= 0)
cur += A[i];
ans.add(cur % 10);
cur /= 10;
}
Collections.reverse(ans);
return ans;
}
}
class Solution {
Map<Integer, Integer> depth;
Map<Integer, TreeNode> parent;
public boolean isCousins(TreeNode root, int x, int y) {
depth = new HashMap();
parent = new HashMap();
dfs(root, null);
return (depth.get(x) == depth.get(y) && parent.get(x) != parent.get(y));
}
public void dfs(TreeNode node, TreeNode par) {
if (node != null) {
depth.put(node.val, par != null ? 1 + depth.get(par.val) : 0);
parent.put(node.val, par);
dfs(node.left, node);
dfs(node.right, node);
}
}
}
class Solution {
public List<String> commonChars(String[] A) {
int[] wordCounts = new int[26];
for(char c : A[0].toCharArray()){
wordCounts[c-'a']++;
}
for(int i=1;i<A.length;i++){
int[] tmp = new int[26];
for(char c : A[i].toCharArray()){
tmp[c-'a']++;
}
for(int j=0;j<tmp.length;j++){
//合并所有的，如果为0则为0，这样才可以过滤掉为0的和重复次数多的
wordCounts[j] = Math.min(wordCounts[j],tmp[j]);
}
}
List<String> ans =new ArrayList<>();
for(int i=0;i<wordCounts.length;i++){
if(wordCounts[i]>0){
for(int j=0;j<wordCounts[i];j++){
ans.add(""+(char)(i+'a'));
}
}
}
return ans;
}
}
1.K>0，则执行 2,否则执行 4
2.取数组 A 中的最小值，并取反
3.K-- 执行 1
4.对数组 A 求和
class Solution {
public int largestSumAfterKNegations(int[] A, int K) {
int[] number = new int[201];//-100 <= A[i] <= 100,这个范围的大小是201
for (int t : A) {
number[t + 100]++;//将[-100,100]映射到[0,200]上
}
int i = 0;
while (K > 0) {
while (number[i] == 0)//找到A[]中最小的数字
i++;
number[i]--;//此数字个数-1
number[200 - i]++;//其相反数个数+1
if (i > 100) {//若原最小数索引>100,则新的最小数索引应为200-i.(索引即number[]数组的下标)
i = 200 - i;
}
K--;
}
int sum = 0;
for (int j = i; j <number.length ; j++) {//遍历number[]求和
sum += (j-100)*number[j];//j-100是数字大小,number[j]是该数字出现次数.
}
return sum;
}
}
class Solution {
public int bitwiseComplement(int N) {
int ans = 0;
int t = 0;
if(N==0){
return 1;
}
while (N != 0) {
ans += ((N % 2) == 0 ? 1 : 0) * Math.pow(2, t);
t++;
N /= 2;
}
return ans;
}
}
class Solution {
public int bitwiseComplement(int N) {
int ans = 0;
int t = 0;
if(N==0){
return 1;
}
List<Integer> temp = new ArrayList<>();
while(N!=0){
temp.add(N%2);
N /= 2;
}
for(int i=temp.size()-1;i>=0;i--){
ans = ans*2 + temp.get(i)^1;
}
return ans;
}
}
class Solution {
public int numPairsDivisibleBy60(int[] time) {
// (a+b)%60=(a%60+b%60)%60
int[] index = new int[60];
int ans = 0;
for(int n : time){
# 60-n%60可能为60，这样会越界，所以在%60
ans += index[(60-n%60)%60];
index[n%60]++;
}
return ans;
}
}
class Solution {
public boolean canThreePartsEqualSum(int[] A) {
int l = A.length;
for(int i = 1;i<l;i++){
A[i] += A[i-1];
}
if(A[l-1]%3!=0){
return false;
}
boolean first = false;
boolean second = false;
for(int sum : A){
if(sum==A[l-1]/3){
first = true;
}
if(first&&sum==(A[l-1]/3)*2){
return true;
}
}
return false;
}
}
class Solution {
public List<Boolean> prefixesDivBy5(int[] A) {
int pre = 0;
List<Boolean> ans = new ArrayList<>();
for(int i = 0;i<A.length;i++){
pre = pre*2+A[i];
// 可能溢出
pre %= 5;
ans.add(pre == 0);
}
return ans;
}
}
class Solution {
public String removeOuterParentheses(String S) {
char[] sc = S.toCharArray();
int l = 0;
StringBuilder sb= new StringBuilder();
for(char c : sc){
if(c==')'){
l--;
}
if(l>=1){
sb.append(c);
}
if(c=='('){
l++;
}
}
return sb.toString();
}
}
class Solution {
int sum = 0;
public int sumRootToLeaf(TreeNode root) {
if(root == null){
return 0;
}
sumNode(root,0);
return sum;
}
private void sumNode(TreeNode root, int num){
if(root == null){
return;
}
num += root.val;
if(root.left == null && root.right == null){
sum += num;
}
sumNode(root.left, num*2);
sumNode(root.right, num*2);
return;
}
}
class Solution {
public boolean divisorGame(int N) {
boolean[] f = new boolean[N + 5];
f[1] = false;
f[2] = true;
for (int i = 3; i <= N; ++i) {
for (int j = 1; j < i; ++j) {
if ((i % j) == 0 && !f[i - j]) {
f[i] = true;
break;
}
}
}
return f[N];
}
}
class Solution {
public int twoCitySchedCost(int[][] costs) {
// Sort by a gain which company has
// by sending a person to city A and not to city B
Arrays.sort(costs, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o1[1] - (o2[0] - o2[1]);
}
});
int total = 0;
int n = costs.length / 2;
// To optimize the company expenses,
// send the first n persons to the city A
// and the others to the city B
for (int i = 0; i < n; ++i) total += costs[i][0] + costs[i + n][1];
return total;
}
}
class Solution {
public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
LinkedList<int[]> queue = new LinkedList<>();
queue.add(new int[]{r0, c0});
boolean[][] check = new boolean[R][C];
check[r0][c0] = true;
int[][] ans = new int[R * C][2];
int j = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] spot = queue.removeFirst();
ans[j++] = spot;
int posR = spot[0];
int posC = spot[1];
// 上
if (posR >= 1 && !check[posR - 1][posC]) {
queue.add(new int[]{posR - 1, posC});
check[posR - 1][posC] = true;
}
// 下
if (posR + 1 <= R - 1 && !check[posR + 1][posC]) {
queue.add(new int[]{posR + 1, posC});
check[posR + 1][posC] = true;
}
// 左
if (posC - 1 >= 0 && !check[posR][posC - 1]) {
queue.add(new int[]{posR, posC - 1});
check[posR][posC - 1] = true;
}
// 右
if (posC + 1 <= C - 1 && !check[posR][posC + 1]) {
queue.add(new int[]{posR, posC + 1});
check[posR][posC + 1] = true;
}
}
}
return ans;
}
}
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> queue = new PriorityQueue<>((x ,y)->(y-x));
for(int s : stones){
queue.offer(s);
}
while(queue.size()>=2){
int x1=queue.poll();
int x2 = queue.poll();
queue.offer(x1-x2);
}
return queue.size()==1?queue.peek():0;
}
}
class Solution {
public String removeDuplicates(String S) {
StringBuilder sb = new StringBuilder();
int sbLength = 0;
for (char character : S.toCharArray()) {
if (sbLength != 0 && character == sb.charAt(sbLength - 1))
sb.deleteCharAt(sbLength-- - 1);
else {
sb.append(character);
sbLength++;
}
}
return sb.toString();
}
}
class Solution {
public int heightChecker(int[] heights) {
int[] counts = new int[101];
for(int h : heights){
counts[h]++;
}
int j =0;
int ans =0;
for(int i=1;i<counts.length;i++){
while(counts[i]-- > 0){
if(heights[j++]!=i){
ans++;
}
}
}
return ans;
}
}
class Solution {
public void duplicateZeros(int[] arr) {
int i = 0;
int j = 0;
int l = arr.length;
while (j < l) {
if (arr[i] == 0) {
j++;
}
i++;
j++;
}
//最后一次导致不满足j<l，所以回到之前
i--;
j--;
while (i >= 0) {
if (j < l) {
arr[j] = arr[i];
}
if (arr[i] == 0) {
arr[--j] = arr[i];
}
i--;
j--;
}
}
}
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
// 存储arr1中的元素的出现频次，下标是arr1中的元素，值是出现的频次
int[] countArr = new int[1001];
// 答案，因为arr2的元素都在arr1中，所以长度为arr1的长度
int[] ans = new int[arr1.length];
// 计算频次
for (int a1 : arr1) {
countArr[a1]++;
}
int j = 0;
for (int value : arr2) {
while (countArr[value] > 0) {
ans[j++] = value;
countArr[value]--;
}
}
// 剩下的已经排序了，直接放入就行
for (int i = 0; i < countArr.length; i++) {
// 此处要双循环，因为可以是多次
while (countArr[i] > 0) {
// 注意此处是下标i是答案
ans[j++] = i;
countArr[i]--;
}
}
return ans;
}
}
class Solution {
public int tribonacci(int n) {
if (n < 3) return n == 0 ? 0 : 1;
int tmp, x = 0, y = 1, z = 1;
for (int i = 3; i <= n; ++i) {
tmp = x + y + z;
x = y;
y = z;
z = tmp;
}
return z;
}
}
class Solution {
public int countCharacters(String[] words, String chars) {
// 用于存储个字母出现的次数
int[] charCounts = new int[26];
for(char c : chars.toCharArray()){
charCounts[c-'a']++;
}
int ans =0;
for(String word : words){
int[] tmp = charCounts.clone();
int count = 0;
for(char c : word.toCharArray()){
if(tmp[c-'a']-->0){
count++;
}
}
if(count==word.length()){
ans+=count;
}
}
return ans;
}
}
class Solution {
public int distanceBetweenBusStops(int[] distance, int start, int destination) {
int pSum = 0;
int nSum = 0;
if (start > destination) {
int tmp = start;
start = destination;
destination = tmp;
}
for (int i = 0; i < distance.length; i++) {
if (i >= start && i < destination) {
pSum += distance[i];
} else {
nSum += distance[i];
}
}
return Math.min(pSum, nSum);
}
}
class Solution {
public List<List<Integer>> minimumAbsDifference(int[] arr) {
Arrays.sort(arr);
int min = arr[1] - arr[0];
List<List<Integer>> ans = new ArrayList<>();
for(int i = 1;i<arr.length;i++){
if(arr[i]-arr[i-1]==min){
ans.add(Arrays.asList(arr[i-1],arr[i]));
}else if(arr[i]-arr[i-1]<min){
ans.clear();
ans.add(Arrays.asList(arr[i-1],arr[i]));
min = arr[i]-arr[i-1];
}
}
return ans;
}
}
class Solution {
public int minCostToMoveChips(int[] chips) {
//注意题中说的是chips里面存储的是位置
//奇数位置移动到奇数位置代价为0，偶数到偶数也是0
//那么就可以把所有的数移动到相邻的奇偶位置上，例如奇移动到1偶移动到2，总花费是0
//接下来有两总情况，一种是把奇移动到偶，一种是把偶移动到奇，所以该题求的就是奇偶数个数的最小值
int odd=0;
int even=0;
for(int c : chips){
if((c&1)==1){
odd++;
}else{
even++;
}
}
return Math.min(odd,even);
}
}
class Solution {
public int balancedStringSplit(String s) {
int cr = 0;
int ans = 0;
char[] cs = s.toCharArray();
for(int i=0;i<cs.length;i++){
if(cs[i]=='R'){
cr++;
}else{
cr--;
}
if(i>0&&cr==0){
ans++;
}
}
return ans;
}
}
class Solution {
public boolean checkStraightLine(int[][] coordinates) {
int x1 = coordinates[1][0]-coordinates[0][0];
int y1 = coordinates[1][1]-coordinates[0][1];
for(int i = 2; i < coordinates.length;i++){
int xi = coordinates[i][0]-coordinates[0][0];
int yi = coordinates[i][1]-coordinates[0][1];
if(x1*yi!=y1*xi){
return false;
}
}
return true;
}
}
class Solution {
public int oddCells(int n, int m, int[][] indices) {
int[] rows = new int[n];
int[] cols = new int[m];
for(int[] indice : indices){
rows[indice[0]]++;
cols[indice[1]]++;
}
int or = 0;
int oc = 0;
for(int row : rows){
if(row%2!=0){
or++;
}
}
for(int col : cols){
if(col%2!=0){
oc++;
}
}
return or*(m-oc)+oc*(n-or);
}
}
