3. 二维数组查找
描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
思路
- 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，
- 因此从左下角开始查找，当要查找数字比左下角数字大时。右移
- 要查找数字比左下角数字小时，上移
public class Solution {
public boolean Find(int target, int[][] array) {
// 行数
int rowCount = array.length;
// 列数
int colCount = array[0].length;
int i, j;
for (i = rowCount - 1, j = 0; i >= 0 && j < colCount; ) {
if (target == array[i][j])
return true;
if (target < array[i][j]) {
i--;
continue;
}
if (target > array[i][j]) {
j++;
continue;
}
}
return false;
}
}
8. 旋转数组的最小数字
描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路：二分查找法
public int minNumberInRotateArray(int [] array) {
int len = array.length;
if(len==0)
return 0;
if(len==1){
return array[0];
}
int low = 0, high = len - 1;
while(low<high){
int mid = low + (high - low) / 2;
// 如果中间数字大于high，则该数字在右边
if(array[mid]> array[high]){
low = mid + 1;
}else if(array[mid] == array[high]){
// 如果中间数字 = high，无法判断，尝试high-1继续二分查找
high = high - 1;
}else{
// 如果中间数字小于high，则该数字在左边
high = mid;
}
}
return array[low];
}
14. 调整数组顺序使奇数在前偶数在后
思路
考虑定义双指针 ii , jj 分列数组左右两端，循环执行：
指针 ii 从左向右寻找偶数；
指针 jj 从右向左寻找奇数；
将 偶数 nums[i]nums[i] 和 奇数 nums[j]nums[j] 交换。
public int[] exchange(int[] nums) {
int left = 0;
int right = nums.length-1;
while(left < right) {
while(left < right && nums[left] % 2 ==1){
left++;
}
while(left < right && nums[right] % 2 ==0){
right--;
}
swap(nums,left,right);
}
return nums;
}
20. 顺时针打印矩阵
描述
思路
public class Solution {
public ArrayList<Integer> printMatrix(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
if (row == 0 || col == 0) return null;
ArrayList<Integer> list = new ArrayList<Integer>();
int left = 0, top = 0, bottom = row - 1, right = col - 1;
while (left <= right && top <= bottom) {
// 从左到右
for (int i = left; i <= right; i++) {
list.add(matrix[top][i]);
}
// 从上到下
for (int j = top + 1; j <= bottom; j++) {
list.add(matrix[j][right]);
}
// 从右到左
if (top != bottom) {
// 防止单行情况
for (int t = right - 1; t >= left; t--) {
list.add(matrix[bottom][t]);
}
}
// 从下到上
if (left != right) {
// 防止单列情况
for (int k = bottom - 1; k > top; k--) {
list.add(matrix[k][left]);
}
}
top++; left++; right--; bottom--;
}
return list;
}
}
29. 数组中出现超过一半次数的数字
描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路
某个数字出现的次数大于数组长度的一半，意思就是它出现的次数比其他所有数字出现的次数和还要多
- 在遍历数组的时候记录两个值：1. 数组中的数字;2. 次数。
- 遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。
- 遍历结束后，所保存的数字即为所求。最后再判断它是否符合条件。
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array==null||array.length==0)
return 0;
int count = 1;
int res = array[0];
for(int i=0;i<array.length;i++){
if(count==0){
count = 1;
res = array[i];
}else if(res == array[i]){
count++;
}else
count--;
}
if(!CheckMoreThanHalf(array,array.length,res))
return 0;
return res;
}
public boolean CheckMoreThanHalf(int[] array,int len,int result){
int count=0;
for(int i=0;i<len;i++)
if(array[i] == result)
count++;
if(count>len/2){
return true;
}
return false;
}
}
30. 最小的k个数
描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
思路
使用一个数值为K的Set进行实现，当Collections中的最大值与下一个数字进行比较移出。
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
if (!check(input, k))
return list;
Set<Integer> set = new LinkedHashSet<>();
for (int i = 0; i < input.length; i++) {
if (set.size() == k) {
int max = Collections.max(set);
if (input[i] <= max) {
set.remove(max);
set.add(input[i]);
}
} else {
set.add(input[i]);
}
}
for (int i : set)
list.add(i);
Collections.sort(list);
return list;
}
31. 连续子数组的最大和
描述
{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)
思路
- 用cur记录当前值, 用max记录最大值。
- 如果cur<0,则舍弃之前的数，让cur等于当前的数字，否则，cur = cur+当前的数字。
- 若cur和大于max更新max。
public int FindGreatestSumOfSubArray(int[] array) {
if (array == null)
return 0;
int max = array[0];
int cur = array[0];
for (int i = 1; i < array.length; i++) {
cur = cur > 0 ? cur + array[i] : array[i];
if (max < cur) {
max = cur;
}
}
return max;
}
33. 数组排成最小数
描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
思路
先将数组转换成字符串数组，然后对字符串数组按照规则排序，最后将排好序的字符串数组拼接出来。
排序规则：
若ab > ba 则 a > b
若ab < ba 则 a < b
若ab = ba 则 a = b
a = 21，b = 2
因为 212 < 221, 即 ab < ba ，所以 a < b
所以我们通过对ab和ba比较大小，来判断a在前或者b在前的。
public String PrintMinNumber(int [] numbers) {
ArrayList<Integer> list = new ArrayList<>();
for(int i:numbers)
list.add(i);
Collections.sort(list,new Comparator<Integer>(){
public int compare(Integer o1,Integer o2){
String str1 = o1+""+o2;
String str2 = o2+""+o1;
return str1.compareTo(str2);
}
});
StringBuilder sb = new StringBuilder();
for(Integer i:list)
sb.append(i);
return sb.toString();
}
35. 第一个只出现一次的字符
描述
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
思路
利用每个字母的ASCII码作hash来作为数组的index
- 创建一个256长度的int数组time
- 遍历字符，每个字符的ASCII作为time的index，time[index]++
- 找出time中为1的index
public int FirstNotRepeatingChar(String str) {
if(str==null)
return -1;
int MAX = 256;
int[] times = new int[MAX];
for (int i = 0; i < 256; i++)
times[i] = 0;
char[] c = str.toCharArray();
for (int i = 0; i < c.length; i++) {
times[c[i]]++;
}
for (int i = 0; i < c.length; i++) {
if (times[c[i]] == 1)
return i;
}
return -1;
}
36. 数组中的逆序对
描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数
例如：{7，5，6，4} 中存在5个逆序对，{7，5}，{7，6}，{7，4}，{5，4}，{6，4}
思路
(a) 把长度为4的数组分解成两个长度为2的子数组；
(b) 把长度为2的数组分解成两个成都为1的子数组；
(c) 把长度为1的子数组 合并、排序并统计逆序对 ；
(d) 把长度为2的子数组合并、排序，并统计逆序对；
在上图（a）和（b）中，我们先把数组分解成两个长度为2的子数组，再把这两个子数组分别拆成两个长度为1的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7大于5，因此（7,5）组成一个逆序对。同样在第二对长度为1的子数组{6}、{4}中也有逆序对（6,4）。由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组 排序 如上图（c）所示， 以免在以后的统计过程中再重复统计。
接下来我们统计两个长度为2的子数组子数组之间的逆序对。合并子数组并统计逆序对的过程如下图如下图所示。
我们先用两个指针分别指向两个子数组的末尾，并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个数组中的数字，则构成逆序对，并且逆序对的数目等于第二个子数组中剩余数字的个数，如下图（a）和（c）所示。如果第一个数组的数字小于或等于第二个数组中的数字，则不构成逆序对，如图b所示。每一次比较的时候，我们都把较大的数字从后面往前复制到一个辅助数组中，确保 辅助数组（记为copy） 中的数字是递增排序的。在把较大的数字复制到辅助数组之后，把对应的指针向前移动一位，接下来进行下一轮比较。
过程：先把数组分割成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。如果对排序算法很熟悉，我们不难发现这个过程实际上就是归并排序
public class Solution {
public int InversePairs(int[] array) {
if (array == null || array.length == 0) {
return 0;
}
int[] copy = new int[array.length];
for (int i = 0; i < array.length; i++) {
copy[i] = array[i];
}
int count = InversePairsCore(array, copy, 0, array.length - 1);//数值过大求余
return count;
}
private int InversePairsCore(int[] array, int[] copy, int low, int high) {
if (low == high) {
return 0;
}
int mid = (low + high) >> 1;
int leftCount = InversePairsCore(array, copy, low, mid) % 1000000007;
int rightCount = InversePairsCore(array, copy, mid + 1, high) % 1000000007;
int count = 0;
int i = mid;
int j = high;
int locCopy = high;
while (i >= low && j > mid) {
if (array[i] > array[j]) {
count += j - mid;
copy[locCopy--] = array[i--];
if (count >= 1000000007)//数值过大求余
{
count %= 1000000007;
}
} else {
copy[locCopy--] = array[j--];
}
}
for (; i >= low; i--) {
copy[locCopy--] = array[i];
}
for (; j > mid; j--) {
copy[locCopy--] = array[j];
}
for (int s = low; s <= high; s++) {
array[s] = copy[s];
}
return (leftCount + rightCount + count) % 1000000007;
}
}
38. 数字在排序数组中出现次数
思路
方法1：二分查找了，我们用递归的方法实现了查找k第一次出现的下标，用循环的方法实现了查找k最后一次出现的下标。
public int getFirst(int[] a,int k,int start,int end){
if(start>end)
return -1;
int mid = (start+end)/2;
if(a[mid]==k){
if((mid>0&&a[mid-1] != k)||mid==0)
return mid;
else
return getFirst(a,k,start,mid-1);
}else if(a[mid]<k){
return getFirst(a,k,mid+1,end);
}else{
return getFirst(a,k,start,mid-1);
}
}
public int getLast(int[] a,int k,int start,int end){
if(start>end)
return -1;
int mid = (start+end)/2;
if(a[mid]==k){
if((mid<a.length-1&&a[mid+1] != k)||mid==a.length-1)
return mid;
else
return getLast(a,k,mid+1,end);
}else if(a[mid]<k){
return getLast(a,k,mid+1,end);
}else{
return getLast(a,k,start,mid-1);
}
}
public int GetNumberOfK(int [] array , int k) {
int num=0;
if(array!=null&&array.length>0){
int first = getFirst(array,k,0,array.length-1);
int last = getLast(array,k,0,array.length-1);
if(first>-1&&last>-1)
num=(last-first+1);
}
return num;
}
方法2：因为data中都是整数，所以我们不用搜索k的两个位置，而是直接搜索k-0.5和k+0.5这两个数应该插入的位置，然后相减即可。
public int GetNumberOfK(int[] array, int k) {
return biSearch(array, k + 0.5) - biSearch(array, k - 0.5);
}
public int biSearch(int[] array, double k) {
int start = 0, end = array.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (array[mid] > k) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return start;
}
40.数组中只出现一次的数字
描述
一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。
思路
法一：HashMap
法二：异或法
任何一个数字异或它自己都等于0。
如果数组中只一个数字是只出现一次的，其他数字都是成双成对出现的，那么我们从头到尾依次异或数组中的每个数字，最终的结果刚好就是那个只出现一次的数字，因为那些成对出现两次的数字全部在异或中抵消了。
那么回到我们的题目，因为有两个只出现一次的数字，所以我们可以试着把原数组分成两个子数组，使得每个数组包含一个只出现一次的数字，而其他数字都成对出现两次。如果这样拆分成两个数组，那么我们就可以按照之前的办法分别对两个数组进行异或运算找出两个只出现一次的数字。
问题来了，如何进行分组呢？
我们还是从头到尾依次异或数组中的每个数字，那么最终得到的结果就是两个只出现一次的数字异或的结果。由于这两个数字不一样，所以异或的结果至少有一位为1，我们在结果数字中找到第一个为1的位置，记为index位，现在我们以第index位是不是1为标准把原数组拆分成两个子数组，第一个子数组中的数组第index位都为1，第二个子数组中的数组第index位都为0，那么只出现一次的数字将被分配到两个子数组中去，于是每个子数组中只包含一个出现一次的数字，而其他数字都出现两次。这样我们就可以用之前的方法找到数组中只出现一次的数字了。
public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
num1[0] = 0;
num2[0] = 0;
if (array.length == 0)
return;
int num = 0;
for (int i = 0; i < array.length; i++) {
num ^= array[i];
}
int index = 0;
while ((num & 1) == 0 && index < 8) {
num = num >> 1;
index++;
}
for (int i = 0; i < array.length; i++) {
if (isa1(array[i], index))
num1[0] ^= array[i];
else
num2[0] ^= array[i];
}
}
public boolean isa1(int i, int index) {
i = i >> index;
return (i & 1) == 1;
}
41. 和为s的两个数字VS
描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
思路
左右夹逼的方法。a+b=sum，a和b越远乘积越小，因为数组是递增排序，所以一头一尾两个指针往内靠近的方法找到的就是乘积最小的情况。
curSum大于sum说明end过大，小于说明start过小
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(array.length==0 || sum<=0)
return list;
int start = 0;
int end = array.length-1;
int curSum = 0;
while(start<end){
curSum = array[start]+array[end];
if(curSum == sum){
list.add(array[start]);
list.add(array[end]);
break;
}else if(curSum > sum){
end--;
}else{
start++;
}
}
return list;
}
41. 和为s的连续正序列
思路
滑动窗口的方法
- 用两个数字 start 和 end 分别表示序列的最小值和最大值
- 将 start 初始化为1，end 初始化为2。
- 如果从start到end的和大于sum，我们就从序列中去掉较小的值(即增大start)。相反，只需要增大end。
- 一直增加begin到(1+sum)/2并且end小于sum为止
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> ll = new ArrayList<ArrayList<Integer>>();
if (sum < 3)
return ll;
int small = 1;
int big = 2;
int middle = (1 + sum) / 2;
int curSum = small + big;
while (small < middle) {
if (curSum == sum) {
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = small; i <= big; i++)
list.add(i);
ll.add(list);
}
while (curSum > sum && small < middle) {
curSum -= small;
small++;
if (curSum == sum) {
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = small; i <= big; i++)
list.add(i);
ll.add(list);
}
}
big++;
curSum += big;
}
return ll;
}
44, 判断扑克牌是否为顺子（王可以为任何数字）
思路
，是否大于数的间隔
- 数组排序
- 统计王(0)的数量
- 统计相邻数字之间的空缺总数 ，如果总数小于0数量则为顺子
public boolean isContinuous(int[] numbers) {
if (numbers == null || numbers.length == 0)
return false;
Arrays.sort(numbers);
int zeroCount = 0;
for (int i = 0; i < numbers.length; i++)
if (numbers[i] == 0)
zeroCount++;
int spaceCount = 0;
for (int i = zeroCount; i < numbers.length - 1; i++) {
if (numbers[i] == numbers[i + 1])
return false;
spaceCount += numbers[i + 1] - numbers[i] - 1;
}
return (zeroCount >= spaceCount) ? true : false;
}
45. 圆圈中最后剩下的数字
描述
0，1，...，n-1 这n个数字排成圆圈，从数字0开始每次从圆圈中删除第m个数字，求圆圈中剩下的最后一个数字，
思路
方法一：用环形链表模拟圆圈。创建一个总共有 n 个结点的环形链表，然后每次在这个链表中删除第 m 个结点。注意，起步是-1 不是 0。
public int LastRemaining_Solution(int n, int m) {
if (n < 1 || m < 1)
return -1;
LinkedList<Integer> link = new LinkedList<Integer>();
for (int i = 0; i < n; i++)
link.add(i);
int index = -1; //起步是 -1 不是 0
while (link.size() > 1) {
index = (index + m) % link.size(); //对 link的长度求余不是对 n
link.remove(index);
index--;
}
return link.get(0);
}
方法二：整理发现公式
f(n, m) = 0 n=1
f(n, m) = [f(n - 1, m) + n] % n n>1
public int LastRemaining_Solution(int n, int m) {
if(n<1||m<1)
return -1;
int last = 0;
for(int i=2;i<=n;i++)
last = (last+m)%i;
return last;
}
51. 数组中的重复数字
描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
思路
- 哈希表
public boolean duplicate(int numbers[], int length, int[] duplication) {
if (numbers == null || numbers.length != length || length <= 0)
return false;
for (int i = 0; i < length; i++) {
if (numbers[i] > length - 1) {
return false;
}
}
int j = 0;
for (int i = 0; i < length; i++) {
if (i != numbers[i]) {
if (numbers[numbers[i]] == numbers[i]) {
duplication[j] = numbers[numbers[i]];
return true;
} else {
swap(numbers, i ,numbers[i]);
}
}
}
return false;
}
52. 构建乘积数组
描述
给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。
思路
B[i]的意义是A数组不包括i位置的所有乘积
B[i]的值可以看作图中矩阵第 i 行所有元素的乘积。我们可以先算下三角中的连乘，即我们先算出B[i]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。
public int[] multiply(int[] A) {
int length = A.length;
int[] B = new int[length];
if (length != 0) {
B[0] = 1;
//计算下三角连乘
for (int i = 1; i < length; i++) {
B[i] = B[i - 1] * A[i - 1];
}
int temp = 1;
//计算上三角
for (int j = length - 2; j >= 0; j--) {
temp *= A[j + 1];
B[j] *= temp;
}
}
return B;
}
65. 滑动窗口最大值
描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
思路
用一个双向队列，队列第一个位置保存当前窗口的最大值，当窗口滑动一次，判断当前最大值是否过期（当前最大值的位置是不是在窗口之外），新增加的值从队尾开始比较，把所有比他小的值丢掉。这样时间复杂度为O(n)。
public class Solution {
public ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> res = new ArrayList<Integer>();
LinkedList<Integer> deque = new LinkedList<Integer>();
if (num.length == 0 || size == 0)
return res;
for (int i = 0; i < num.length; i++) {
if (!deque.isEmpty() && deque.peekFirst() <= i - size) {
deque.poll();
}
while (!deque.isEmpty() && num[deque.peekLast()] < num[i]) {
deque.removeLast();
}
deque.offerLast(i);
if (i + 1 >= size) {
res.add(num[deque.peekFirst()]);
}
}
return res;
}
}
66. 矩阵中的路径
描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
思路
算法原理：
深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝： 在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为 可行性剪枝 。
算法剖析：
-
递归参数： 当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。
终止条件：
- 返回 falsefalse ： ① 行或列索引越界 或 ② 当前矩阵元素与目标字符不同 或 ③ 当前矩阵元素已访问过 （③ 可合并至 ② ） 。
- 返回 truetrue ： 字符串 word 已全部匹配，即 k = len(word) - 1 。
- 递推工作：
- 标记当前矩阵元素： 将 board[i][j] 值暂存于变量 tmp ，并修改为字符 '/' ，代表此元素已访问过，防止之后搜索时重复访问。
- 搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需一条可行路径） ，并记录结果至 res 。
- 还原当前矩阵元素： 将 tmp 暂存值还原至 board[i][j] 元素。
- 回溯返回值： 返回 res ，代表是否搜索到目标字符串。
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
int[] flag = new int[matrix.length];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (helper(matrix, rows, cols, i, j, 0, str, flag))
return true;
}
}
return false;
}
public boolean helper(char[] matrix, int rows, int cols, int i, int j, int k, char[] str, int[] flag) {
int index = i * cols + j;
if (i < 0 || i >= rows || j < 0 || j >= cols || flag[index] == 1 || matrix[index] != str[k])
return false;
if (k == str.length - 1)
return true;
flag[index] = 1;
if (helper(matrix, rows, cols, i + 1, j, k + 1, str, flag)
|| helper(matrix, rows, cols, i - 1, j, k + 1, str, flag)
|| helper(matrix, rows, cols, i, j + 1, k + 1, str, flag)
|| helper(matrix, rows, cols, i, j - 1, k + 1, str, flag))
return true;
flag[index] = 0;
return false;
}
}
67. 机器人运动范围
描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
思路
回溯法：从(0,0)开始走，每成功走一步用一个flag数组标记当前位置为1，然后从当前位置往四个方向探索，返回1 + 4 个方向的探索值之和。
public class Solution {
public int movingCount(int threshold, int rows, int cols) {
boolean[] visited = new boolean[rows * cols];
for (int i = 0; i < rows * cols; i++)
visited[i] = false;
int count = movingCountCore(threshold, rows, cols, 0, 0, visited);
return count;
}
public int movingCountCore(int threshold, int rows, int cols, int row, int col, boolean[] visited) {
int count = 0;
if (Check(threshold, rows, cols, row, col, visited)) {
visited[row * cols + col] = true;
// 上下左右四个方向是否被探索
count = 1 + movingCountCore(threshold, rows, cols, row, col - 1, visited)
+ movingCountCore(threshold, rows, cols, row, col + 1, visited)
+ movingCountCore(threshold, rows, cols, row - 1, col, visited)
+ movingCountCore(threshold, rows, cols, row + 1, col, visited);
}
return count;
}
// 判断当前数字和是否小于threshold，并且未被访问过
public boolean Check(int threshold, int rows, int cols, int row, int col, boolean[] visited) {
if (row >= 0 && row < rows && col >= 0 && col < cols
&& getDigitSum(row) + getDigitSum(col) <= threshold && !visited[row * cols + col])
return true;
return false;
}
// 数字各位相加之和
public int getDigitSum(int s) {
int sum = 0;
while (s > 0) {
sum += s % 10;
s = s / 10;
}
return sum;
}
}
网友评论