sz2376@columbia.edu
BAN USERpublic ArrayList<Integer> spiralOrder(int[][] matrix) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<Integer> result = new ArrayList<Integer>();
if(matrix.length==0||matrix[0].length==0)
return result;
spiralOrderHelper(matrix, result, 0, 0, matrix.length-1, matrix[0].length-1);
return result;
}
private void spiralOrderHelper(int[][] matrix, ArrayList<Integer> result, int rs, int cs, int re, int ce) {
if(rs>re||cs>ce)
return;
if(re==rs) {
for(int i=cs; i<=ce; i++) {
result.add(matrix[rs][i]);
}
return;
}
if(ce==cs) {
for(int i=rs; i<=re; i++) {
result.add(matrix[i][cs]);
}
return;
}
for(int i=cs; i<=ce; i++) {
result.add(matrix[rs][i]);
}
for(int i=rs+1; i<=re; i++) {
result.add(matrix[i][ce]);
}
for(int i=ce-1; i>=cs; i--) {
result.add(matrix[re][i]);
}
for(int i=re-1; i>rs; i--) {
result.add(matrix[i][cs]);
}
spiralOrderHelper(matrix, result, rs+1, cs+1, re-1, ce-1);
}
public boolean isMatch(String input, String expected) {
if(input==""&&expected=="")
return true;
if(input.length()>expected.length())
return false;
char missed = 0;
int i = 0;
int j = 0;
while(i<input.length()) {
if(input.charAt(i)==expected.charAt(j)) {
i++;
j++;
}else {
if(missed!=0&&expected.charAt(j)!=missed)
return false;
else {
missed = expected.charAt(j);
for(int k=0; k<=i; k++) {
if(input.charAt(k)==missed)
return false;
}
}
j++;
}
}
if(j==expected.length())
return true;
else {
for(int k=j; k<expected.length(); k++) {
if(expected.charAt(k)!=missed)
return false;
}
return true;
}
}
it does not work for {1 2 10 19} and {2 4 15 18}
- sz2376@columbia.edu November 23, 2013My approach:
public int immediateGreater(int num) {
char[] string = String.valueOf(num).toCharArray();
int length = string.length;
if(length<=1)
return -1;
int[] temp = new int[length];
for(int i=0; i<temp.length; i++) {
temp[i] = 10;
}
int realLength = 1;
temp[0] = string[length-1]-'0';
for(int i=length-2; i>=0; i--) {
if(string[i]>=string[i+1]) {
temp[realLength] = string[i]-'0';
realLength++;
}else {
int min = string[i+1]-'0';
int pos = i+1;
for(int j=0; j<realLength; j++) {
if(temp[j]<min&&temp[j]>(string[i]-'0')) {
min = temp[j];
pos = j;
}
}
int y = string[i] - '0';
string[i] = (char)(min+48);
temp[pos] = y;
java.util.Arrays.sort(temp);
pos = 0;
for(int j=realLength; j>0; j--) {
string[string.length-j] = (char) (temp[pos++]+48);
}
return Integer.parseInt(new String(string));
}
}
return -1;
}
You are wrong. It is not possible that one team can win the entire 12 points. For team 6 and team 7, there must be two points assigned to them because there are two matches between them, so there must be one winner for each match.
- sz2376@columbia.edu November 20, 2013The solution is 11 and I think the logic behind is as below:
Fact1: there are totally 56 matches, so the total number of winning and the number of losing should be 56. (for each match there should be a winner and a loser)
Fact2: each team would have 14 matches with the others, so for each team, the number of winning plus the number of losing should be 14.
In order to find the min number of winning times to ensure to get into semi, we assume the first four teams are supposed to get in. We let the number of winning for the first four teams be x, so they number of losing for them is (14-x). If the x is not large enough, we would find at least one team, let's say team 5, have the number of winning more than x. We need to avoid this happen. Let's assume the team 5 be our bottleneck and we let it has the winning as large as possible. We cannot ignore the last three teams at the same time. there are two matches between team 6 and team 7; two matches between team 7 and team 8, so there should be at least four winning time for team 6,7,8. So the first five teams should split at most 52 winnings. So the number of winning left for team 5 is at most 52-4*x. We let 52-4*x<x, we have x>10.4, so the solution is 11.
public int maxSubArray(int[] array) {
int max = 0;
if(array.length<2)
return max;
for(int i=0; i<array.length; i++) {
if(array[i]==0)
array[i] = -1;
}
int[] temp = new int[array.length];
temp[0] = array[0];
for(int i=1; i<array.length; i++) {
temp[i] = temp[i-1] + array[i];
}
for(int i:temp) {
if(i==0)
max = i+1;
}
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
for(int i=0; i<array.length; i++) {
if(!hm.containsKey(temp[i])) {
hm.put(temp[i], i);
}else {
int pot = i - hm.get(temp[i]);
if(pot>max)
max = pot;
}
}
return max;
}
idea from: geekforgeeks
- sz2376@columbia.edu November 20, 2013How could this solution get 5 votes? This does not work even when there are 26 elements in the array......
- sz2376@columbia.edu November 19, 2013
- sz2376@columbia.edu December 01, 2013