第35天--算法（牛客网剑指offer2）
1.JZ13 机器人的运动范围
int ans = 0;
public int movingCount(int threshold, int rows, int cols) {
boolean dp[][] = new boolean[rows][cols];
process(dp,threshold,0,0,rows,cols);
return ans;
}
public void process(boolean dp[][],int threshold,int i,int j,int rows,int cols) {
if(i < 0 || j < 0 || i == rows || j == cols || minus(i,j) > threshold || dp[i][j]) {
return;
}
dp[i][j] = true;
ans ++;
process(dp,threshold,i + 1,j,rows,cols);
process(dp,threshold,i - 1,j,rows,cols);
process(dp,threshold,i,j + 1,rows,cols);
process(dp,threshold,i,j - 1,rows,cols);
}
public int minus(int x,int y) {
int ansX = 0;
int ansY = 0;
while(x != 0) {
ansX += x % 10;
x /= 10;
}
while(y != 0) {
ansY += y % 10;
y /= 10;
}
return ansX + ansY;
}
2.JZ14 剪绳子
public int cutRope(int target) {
if(target == 1 || target == 2) {
return 1;
}
if(target == 3) {
return 2;
}
if(target == 4) {
return 4;
}
int ans = 1;
while(target >= 5) {
target -= 3;
ans *= 3;
}
ans *= target;
return ans;
}
3.JZ15 二进制中1的个数
public int NumberOf1(int n) {
int ans = 0;
while(n != 0) {
n &= (n - 1);
ans ++;
}
return ans;
}
4.JZ16 数值的整数次方
public double Power(double x,int y) {
if(y == 0) {
return 1D;
}
if(x == 1) {
return 1D;
}
if(x == -1) {
if((y & 1) == 0) {
return 1D;
}else {
return -1D;
}
}
if(y == Integer.MIN_VALUE) {
return 0;
}
double t = x;
double ans = 1;
boolean isFu = y < 0;
y = isFu ? -y : y;
while(y != 0) {
if((y & 1) != 0) {
ans *= t;
}
t *= t;
y >>= 1;
}
return isFu ? 1D / ans : ans;
}
5.JZ17 打印从1到最大的n位数(看似很垃圾的题，其实如果考大数就不简单了，大数解法先不写了-。-)
public int[] printNumbers (int n) {
int ans[] = new int[(int) Math.pow(10,n) - 1];
for(int i = 0;i < ans.length;i ++) {
ans[i] = i + 1;
}
return ans;
}
6.JZ18 删除链表的节点
public ListNode deleteNode (ListNode head, int val) {
ListNode temp1 = head;
ListNode temp2 = head.next;
if(head.val == val) {
return head.next;
}
while(temp2.next != null) {
if(temp2.val == val) {
temp1.next = temp1.next.next;
break;
}else {
temp1 = temp1.next;
temp2 = temp2.next;
}
}
return head;
}
7.JZ19 正则表达式匹配(代码没问题，过不去牛客网是因为测试用例有问题!!! 能过去LeetCode)
public boolean isMatch (String str, String pattern) { char s1[] = str.toCharArray(); char p1[] = pattern.toCharArray(); int M = s1.length; int N = p1.length; boolean dp[][] = new boolean[M + 1][N + 1]; dp[M][N] = true; if(M > 0 && N > 0) { if(s1[M - 1] == p1[N - 1] || p1[N - 1] == '.') { dp[M - 1][N - 1] = true; } } for(int pi = N - 2;pi >= 0;pi --) { if(pi + 1 < p1.length && p1[pi + 1] == '*') { dp[M][pi] = dp[M][pi + 2]; } } for(int si = M - 1;si >= 0;si --) { for(int pi = N - 2;pi >= 0;pi --) { if(pi + 1 > p1.length || p1[pi + 1] != '*') { dp[si][pi] = (s1[si] == p1[pi] || p1[pi] == '.') && dp[si + 1][pi + 1]; continue; } if(s1[si] != p1[pi] && p1[pi] != '.') { dp[si][pi] = dp[si][pi + 2]; continue; } if(dp[si][pi + 2]) { dp[si][pi] = true; continue; } int i = si; while(i < s1.length && (s1[i] == p1[pi] || p1[pi] == '.')) { if(dp[i + 1][pi + 2]) { dp[si][pi] = true; } i ++; } } } return dp[0][0]; } 8.JZ20 表示数值的字符串 public boolean isNumber (String s) { s = s.trim(); if(s.length() == 0) { return false; } if(s.charAt(0) == '+' || s.charAt(0) == '-') { s = s.substring(1); } s = s.replace('E','e'); if(s.indexOf('e') >= 0) { int index = s.indexOf('e'); String first = s.substring(0,index); String second = s.substring(index + 1); if(second.length() > 0) { if(second.charAt(0) == '+' || second.charAt(0) == '-') { second = second.substring(1); } } return isValidNumber(first) && isPureValidNumber(second); } return isValidNumber(s); } public boolean isValidNumber(String s) { if(s.indexOf('.') >= 0) { int index = s.indexOf('.'); String first = s.substring(0,index); String second = s.substring(index + 1); if(first.length() > 0 && second.length() > 0) { return isPureValidNumber(first) && isPureValidNumber(second); }else if(first.length() > 0) { return isPureValidNumber(first); }else { return isPureValidNumber(second); } } return isPureValidNumber(s); } public boolean isPureValidNumber(String s) { if(s.length() == 0) { return false; } for(int i = 0;i < s.length();i ++) { if(s.charAt(i) < '0' || s.charAt(i) > '9') { return false; } } return true; }9.JZ21 调整数组顺序使奇数位于偶数前面(一)
public int[] reOrderArray (int[] array) {
int nEven[] = new int[array.length];
int even[] = new int[array.length];
int i1 = 0;
int i2 = 0;
for(int i = 0;i < array.length;i ++) {
if((array[i] & 1) == 0) {
even[i2 ++] = array[i];
}else {
nEven[i1 ++] = array[i];
}
}
i1 --;
i2 --;
for(int i = 0;i <= i1;i ++) {
array[i] = nEven[i];
}
for(int i = i1 + 1,j = 0;i < array.length;i ++,j ++) {
array[i] = even[j];
}
return array;
}
10.JZ22 链表中倒数最后k个结点
public ListNode FindKthToTail (ListNode pHead, int k) {
ListNode temp1 = pHead;
while(k != 1) {
k --;
if(temp1 != null) {
temp1 = temp1.next;
}
}
if(temp1 == null) {
return null;
}
ListNode temp2 = pHead;
while(temp1.next != null) {
temp1 = temp1.next;
temp2 = temp2.next;
}
return temp2;
}