NC398 腐烂的苹果
1.题目
2.解析
这是一个广度优先搜索问题，我们可以先找到所有的烂苹果，把它加入到队列中，然后再同时让这几个苹果向外面腐蚀，我们可以用一个boolean数组来表示是否被腐蚀，也可以直接在原数组中将这个位置标为2。然后再将这个数加入到队列中即可，当队列为空时就代表没有可以腐蚀的苹果了。这里有一个小细节，不管这轮有没有腐蚀苹果，我们的时间都会加一，所以到最后的时候，必定没有腐蚀，就多加了一次时间，返回结果时就可以返回原时间减一。
3.代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param grid int整型ArrayList<ArrayList<>>
* @return int整型
*/
int [] dx = new int[] {1, -1, 0, 0};
int [] dy = new int[] {0, 0, 1, -1};
public int rotApple (ArrayList<ArrayList<Integer>> grid) {
// write code here
//找到所有的烂苹果放到queue中
int m = grid.size();
int n = grid.get(0).size();
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid.get(i).get(j) == 2) {
queue.offer(new int[] {i, j});
}
}
}
//开始广度搜索腐烂苹果
int ret = 0;
while (!queue.isEmpty()) {
int sz = queue.size();
while (sz-- != 0) {
int[] tem = queue.poll();
for (int i = 0; i < 4; i++) {
int a = tem[0] + dy[i];
int b = tem[1] + dx[i];
if (a < m && a >= 0 && b < n && b >= 0
&& grid.get(a).get(b) == 1) {
grid.get(a).set(b, 2);
queue.offer(new int[] {a, b});
}
}
}
ret++;
}
//重新扫描一遍有没有1
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid.get(i).get(j) == 1) {
return -1;
}
}
}
return ret - 1; //返回值，注意要减一
}
}JZ62孩子们的游戏
1.题目
2.解析
如图：
3.代码
public int LastRemaining_Solution (int n, int m) {
// write code here
//初始化dp数组
int[] dp=new int[n+1];
dp[1]=0;
//按照方程把数组填满
for(int i=2;i<n+1;i++) {
dp[i]=(dp[i-1]+m)%i;
}
return dp[n];
}3.大数加减（二）
1.题目
2.解析
因为我们要从最后一个节点开始计算，所以我们可以将链表逆序。逆序之后再建立一个新的链表把它根据竖式加一起，最后因为结果是逆序的，所以我们再逆序一下就好了。
3.代码
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode reverse(ListNode head) {//逆序要经历很多次所以直接写成一个方法
ListNode ret = new ListNode(0);//用创建一个头节点的方法，头插法插入链表完成逆序
ListNode cur = head;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = ret.next;
ret.next = cur;
cur = curNext;
}
return ret.next;
}
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
//先逆序两个链表
head1=reverse(head1);
head2=reverse(head2);
//开始大数相加
ListNode ret =new ListNode(0);
ListNode prev =ret;
ListNode cur1 = head1;ListNode cur2 = head2;
int tem = 0;
while (cur1 != null || cur2 != null || tem != 0) {
if (cur1 != null) {
tem += cur1.val;
cur1=cur1.next;
}
if (cur2 != null) {
tem +=cur2.val;
cur2 = cur2.next;
}
prev.next = new ListNode(tem % 10);
prev=prev.next;
tem /= 10;
}
ret = ret.next;
return reverse(ret);
}
}4.NC10 大数乘法
1.题目
2.解析
3.代码
import java.util.*;
public class Solution {
public String solve (String s, String t) {
// write code here
//各个位数相乘
int[] arr = new int[s.length() + t.length() - 1];
for (int i =0 ; i <s.length() ; i++) {
for (int j =0; j < t.length() ; j++) {
arr[i + j] += (int)((s.charAt(i) - '0') * (t.charAt(j) - '0'));
}
}
StringBuilder sb = new StringBuilder();
int tem = 0;
//把各个下标进位
for (int i = arr.length-1; i >=0 ; i--) {
arr[i]+=tem;
tem = arr[i] / 10;
arr[i] = arr[i] % 10;
sb.append(arr[i]);
}
//处理第一位
if (tem != 0) {
sb.append(tem);
}
while(sb.charAt(0)=='0'&&sb.length()!=1) {
sb.deleteCharAt(0);
}
return sb.reverse().toString();
}
}
