数组中的重复数字
题目描述：
输入:
{2, 3, 1, 0, 2, 5}
输出:
2
解法1 数组排序
分析：
将输入数组排序，再判断相邻位置是否存在相同数字，如果存在，对 duplication 赋值返回，否则继续比较。
代码：
import java.util.*;
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个，赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
if (numbers == null || length ==0){
return false;
}
Arrays.sort(numbers);
for (int i=0;i<length-1;i++){
if (numbers[i] == numbers[i+1]){
duplication[0] = numbers[i];
return true;
}
}
return false;
}
}复杂度：
| 时间复杂度 | O(nlogn) |
|---|---|
| 空间复杂度 | O(1) |
问题：
循环时要注意下边比较i和i+1的值时，i的初始值为0，i的最大长度应该是length-1；下边比较i和i-1的值时，i的初始值为1，最大长度应该是length。
解法2 利用 HashSet 或者ArrayList解决
分析：
利用 HashSet 或者ArrayList解决，从头到尾扫描数组，每次扫描到一个数，判断当前数是否存在 HashSet 或ArrayList中，如果存在，则重复，对 duplication 赋值返回，否则将该数加入到 HashSet 或ArrayList中。
代码：
import java.util.*;
public class Solution {
public boolean duplicate(int numbers[],int length,int [] duplication) {
if (numbers == null || length == 0){
return false;
}
Set<Integer> set = new HashSet<>();
for (int i=0; i<length; i++){
if (set.contains(numbers[i])){
duplication[0] = numbers[i];
return true;
}else{
set.add(numbers[i]);
}
}
return false;
}
}复杂度：
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(n) |
解法3 “归位”
分析：
数组的长度为 n 且所有数字都在 0 到 n-1 的范围内，我们可以将每次遇到的数进行”归位”，当某个数发现自己的”位置”被相同的数占了，则出现重复。
扫描整个数组，当扫描到下标为 i 的数字时，首先比较该数字（m）是否等于 i，如果是，则接着扫描下一个数字；如果不是，则拿 m 与第 m 个数比较。如果 m 与第 m 个数相等，则说明出现重复了；如果 m 与第 m 个数不相等，则将 m 与第 m 个数交换，将 m “归位”，再重复比较交换的过程，直到发现重复的数。
举例：
以数组 {2,3,1,0,2,5,3} 为例
当 i = 0 时，nums[i] = 2 != i，判断 nums[i] 不等于 nums[nums[i]]，交换 nums[i] 和 nums[nums[i]]，交换后数组为：{1,3,2,0,2,5,3}
此时 i = 0，nums[i] = 1 != i，判断 nums[i] 不等于 nums[nums[i]]，交换 nums[i] 和 nums[nums[i]]，交换后数组为：{3,1,2,0,2,5,3}
此时 i = 0，nums[i] = 3 != i，判断 nums[i] 不等于 nums[nums[i]]，交换 nums[i] 和 nums[nums[i]]，交换后数组为：{0,1,2,3,2,5,3}
此时 i = 0，nums[i] = 0 = i，继续下一组
当 i = 1，nums[i] = 1 = i，继续下一组
当 i = 2，nums[i] = 2 = i，继续下一组
当 i = 3，nums[i] = 3 = i，继续下一组
当 i = 4，nums[i] = 2 != i，判断 nums[i] 等于 nums[nums[i]]，出现重复，赋值返回
代码：
import java.util.*;
public class Solution {
public boolean duplicate(int[] nums, int length, int[] duplication) {
if (nums == null || length <= 0)
return false;
for (int i = 0; i < length; i++) {
while (nums[i] != i) {
if (nums[i] == nums[nums[i]]) {
duplication[0] = nums[i];
return true;
}
swap(nums, i, nums[i]);
}
}
return false;
}
private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}复杂度：
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(1) |
二维数组中的查找
题目描述：
给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
解法1 暴力法
分析：
挨个遍历数组，如果找到就返回 true。
代码：
public class Solution {
public boolean Find(int target, int [][] array) {
if(array == null || array.length == 0 || array[0].length == 0)
return false;
for(int i=0; i<array.length; i++){
for(int j=0; j<array[0].length; j++){
if(target == array[i][j]){
return true;
}
}
}
return false;
}
}复杂度：
| 时间复杂度 | O(n^2) |
|---|---|
| 空间复杂度 | O(1) |
解法2 从左下找
分析：
该二维数组中的一个数，小于它的数一定在其上边，大于它的数一定在其右边。因此，从左下角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为右上角的所有元素。其中 M 为行数，N 为 列数。
代码：
public class Solution {
public boolean Find(int target, int [][] array) {
if(array == null || array.length == 0 || array[0].length == 0)
return false;
int rows = array.length;
int row = rows - 1;
int cols = array[0].length;
int col = 0;
while(row >= 0 && col < cols){
if(target == array[row][col]){
return true;
}else if(target < array[row][col]){
row--;
}else if(target > array[row][col]){
col++;
}else{
return true;
}
}
return false;
}
}复杂度：
| 时间复杂度 | O(M+N) |
|---|---|
| 空间复杂度 | O(1) |
解法3 从右上找
分析：
该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。其中 M 为行数，N 为 列数。
代码：
public class Solution {
public boolean Find(int target, int [][] array) {
if(array == null || array.length == 0 || array[0].length == 0)
return false;
int rows = array.length;
int row = 0;
int cols = array[0].length;
int col = cols - 1;
while(row < rows && col >= 0){
if(target == array[row][col]){
return true;
}else if(target < array[row][col]){
col--;
}else if(target > array[row][col]){
row++;
}else{
return true;
}
}
return false;
}
}复杂度：
| 时间复杂度 | O(M+N) |
|---|---|
| 空间复杂度 | O(1) |
替换空格
题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”
Input:
“A B”Output:
“A%20B”
解法1 调用自带函数
代码:
public class Solution {
public String replaceSpace(StringBuffer str) {
return str.toString().replace(" ","%20");
}
}解法2 用新的数组存
分析:
当遇到 “ “，就追加 “%20”，否则遇到什么追加什么。
代码:
public class Solution {
public String replaceSpace(StringBuffer str) {
StringBuffer sb = new StringBuffer();
for (int i=0;i<str.length();i++) {
char c = str.charAt(i);
if (c == ' ') {
sb.append("%20");
} else {
sb.append(c);
}
}
return sb.toString();
}
}解法3 填充字符
分析：
① 在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），所以当遍历到一个空格时，需要在尾部填充两个任意字符。
② 令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。从后向前遍是为了在改变 P2 所指向的内容时，不会影响到 P1 遍历原来字符串的内容。
③ 当 P2 遇到 P1 时（P2 <= P1），或者遍历结束（P1 < 0），退出。
代码：
public class Solution {
public String replaceSpace(StringBuffer str) {
int P1 = str.length() - 1;
for (int i=0; i<=P1; i++) {
char c = str.charAt(i);
if (c == ' ') {
str.append(" ");
}
}
int P2 = str.length() - 1;
while (P1 >= 0 && P2 > P1) {
char d = str.charAt(P1--);
if (d == ' ') {
str.setCharAt(P2--, '0');
str.setCharAt(P2--, '2');
str.setCharAt(P2--, '%');
} else {
str.setCharAt(P2--, d);
}
}
return str.toString();
}
}
从尾到头打印链表
题目描述
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
解法1 非递归
分析：
listNode 是链表，只能从头遍历到尾，但是输出却要求从尾到头，这是典型的”先进后出”，我们可以想到栈！
ArrayList 中有个方法是 add(index,value)，可以指定 index 位置插入 value 值，所以我们在遍历 listNode 的同时将每个遇到的值插入到 list 的 0 位置，最后输出 listNode 即可得到逆序链表。
代码：
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList();
ListNode tmp = listNode;
while (tmp != null) {
list.add(0, tmp.val);
tmp = tmp.next;
}
return list;
}
}复杂度
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(n) |
解法2 递归
分析：
借助系统的”栈”帮忙打印。
代码：
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> list = new ArrayList();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if (listNode != null) {
printListFromTailToHead(listNode.next);
list.add(listNode.val);
}
return list;
}
}复杂度
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(n) |
用两个栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
分析：
1、当插入时，直接插入 stack1。
2、当弹出时，当 stack2 不为空，弹出 stack2 栈顶元素，如果 stack2 为空，将 stack1 中的全部数逐个出栈入栈 stack2，再弹出 stack2 栈顶元素。
代码：
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if (stack2.size()<=0) {
while (stack1.size()!=0) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}复杂度
| 时间复杂度 | O(1) |
|---|---|
| 空间复杂度 | O(1) |
变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析：
f(n) = f(n - 1) + f(n - 2) + f(n - 3) + … + f(2) + f(1)
f(n - 1) = f(n - 2) + f(n - 3) + … + f(2) + f(1)
f(n) = 2*f(n - 1)
其本质是斐波那契数列的变种。
代码：
public class Solution {
public int JumpFloorII(int target) {
return 1<<(target - 1);
//if (target <= 1)
// return target;
//int sum = 1;
//for (int i = 2; i <= target; i++) {
// sum = 2 * sum;
//}
//return sum;
}
}复杂度
| 时间复杂度 | O(target) ? |
|---|---|
| 空间复杂度 | O(1) |
矩形覆盖
题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
比如n=3时，2*3的矩形块有3种覆盖方法：
分析：
当n=1时，只有一种方法，f(1)=1;
当n=2时，既可以横着覆盖，也可以竖着覆盖，有两种方法，f(2)=2;
当n=n时，考虑n=n-1和n=n-2的情况，f(n)=f(n - 1) + f(n - 2)
其实质还是斐波那契数列。
代码：
public class Solution {
// 2*1 1. 2*2. 2 2*3. 3. 2*4 5
// n = (n - 1) + (n - 2)
public int RectCover(int target) {
if (target <= 2)
return target;
int one = 1;
int two = 2;
for (int i = 3; i <= target; i++) {
int cur = one + two;
one = two;
two = cur;
}
return two;
}
}复杂度
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(1) |
二进制中1的个数
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
解法1
分析：
1、先将数字转换成二进制字符串
2、用String.split()函数存入一个数组中
3、遍历数组跟1比较，同时计数
4、输出计数值
代码：
public class Solution {
public int NumberOf1(int n) {
String s = Integer.toBinaryString(n);
String[] splits = s.split("");
int a = 0;
for (int i = 0; i < splits.length; i++) {
if (splits[i].equals("1")) {
a++;
}
}
return a;
}
}解法2
分析：
如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
代码：
public class Solution {
// 20->10100 & 10011 = 10000 10000 & 01111 = 00000
public int NumberOf1(int n) {
int count = 0;
while (n != 0) {
count ++;
n = n & (n - 1);
}
return count;
}
}数值的整数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0
解法1 内置函数Math.pow()
代码：
public class Solution {
public double Power(double base, int exponent) {
return Math.pow(base, exponent);
}
}解法2 暴力法
分析：
将数字 base 连续乘 exponent 次。时间复杂度O(n) ，空间复杂度O(1)。
代码：
public class Solution {
// 时间复杂度O(n) 空间复杂度O(1)
public double Power(double base, int exponent) {
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
boolean isNegative = exponent > 0;
int e = Math.abs(exponent);
double result = 1;
for (int i = 1; i <= e; i++) {
result *= base;
}
return isNegative ? result : 1/result;
}
}解法3 二分法
分析：
为了方便讨论，假设指数exponent是正数。那么递归式如下：
- 如果
exponent是偶数，Power(base, exponent) = Power(base, exponent / 2) * Power(base, exponent / 2) - 如果
exponent是奇数，Power(base, exponent) = base * Power(base, exponent / 2) * Power(base, exponent / 2)
对于负指数exponent的情况，取其绝对值先计算。将最后结果取倒数即可。
例如：2的4次方。可以分解为2的二次方乘以2的二次方。
时间复杂度是 O(logN)；由于采用递归结构，空间复杂度是 O(logN)。
代码：
public class Solution {
public double Power(double base, int exponent) {
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
boolean isNegative = exponent > 0;
int e = Math.abs(exponent);
double result = Power(base, e / 2);
if ((e % 2) == 0) {
result = result * result;
} else {
result = result * result * base;
}
return isNegative ? result : 1/result;
}
}链表中第K个节点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
解法1 快慢指针法
分析：
首先定义两个指向链表头的指针p ,q;先令一个指针指向第k节点，然后两个指针同时向后移动，最后q指向的即为倒数第k个节点。当k为零或节点为空返回。
代码：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if (head == null || k == 0) {
return null;
}
ListNode p,q;
p = q = head;
int i = 0;
for (; p != null; i++) {
if (i >= k) {
q = q.next;
}
p = p.next;
}
return i < k ? null : q;
}
}反转链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
分析：
题目所给的是单链表，反转后的样子：最后一个结点指向倒数第二个，倒数第二个指向倒数第三个，……，第二个指向第一个，第一个指向null; 知道了反转后各个结点指向哪之后，就需要开始调整每个结点的next指针。 这就需要把结点挨个从链表上摘下来，做调整； 这个调整过程需要两个指针辅助：pre记录其前一个结点位置，好让该结点的next指针指向前一个结点，但是在指向前一个结点前需要用一个指针next记录后一个结点地址，避免结点丢失。
例子：
- 以head结点为例步骤如下：
- 1.反转后head是指向null，所以未反转的时候其前一个结点应该是null，初始化pre指针为null；
- 2.用next指针记录head的下一个结点head.next；
- 3.从链表上摘下head，即让head.next指向pre；
- 4.此时已完成head结点的摘取及与前一个节点的连接，则我们需要操作下一个结点：故需移动pre和head，让pre指向head，head指向下一个节点。
- 重复这四个操作直到head走完原链表，指向null时，循环结束，返回pre。
代码：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode pre = null;
ListNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}顺时针打印矩阵
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
分析：
定义四个变量代表范围，up、down、left、right，不断收缩矩阵的边界。
- 向右走存入整行的值，当存入后，该行再也不会被遍历，代表上边界的 up 加一，同时判断是否和代表下边界的 down 交错
- 向下走存入整列的值，当存入后，该列再也不会被遍历，代表右边界的 right 减一，同时判断是否和代表左边界的 left 交错
- 向左走存入整行的值，当存入后，该行再也不会被遍历，代表下边界的 down 减一，同时判断是否和代表上边界的 up 交错
- 向上走存入整列的值，当存入后，该列再也不会被遍历，代表左边界的 left 加一，同时判断是否和代表右边界的 right 交错
代码：
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> list = new ArrayList();
if (matrix == null || matrix.length == 0 || matrix[0].length ==0) {
return list;
}
int up = 0;
int down = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
while (true) {
// 最上面一行
for (int col = left; col <= right; col++) {
list.add(matrix[up][col]);
}
// 向下逼近
up ++;
if (up > down) {
break;
}
// 最右边一列
for (int top = up; top <= down; top++) {
list.add(matrix[top][right]);
}
// 向左逼近
right --;
if (right < left) {
break;
}
// 最下边一行
for (int row = right; row >= left; row--) {
list.add(matrix[down][row]);
}
// 向上逼近
down --;
if (down < up) {
break;
}
// 最左边一列
for (int bottom = down; bottom >= up; bottom--) {
list.add(matrix[bottom][left]);
}
// 向右逼近
left ++;
if (left > right) {
break;
}
}
return list;
}
}包含min函数的栈
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。
分析：
使用两个辅助栈，一个为stackTotal用来存放所有元素，一个为stackMin用来存放最小元素，两个栈中的数量始终保持一致，当新元素小于stackMin栈顶元素时，向其栈顶加入新元素，否则，加入之前的栈顶元素。当执行出栈时，两个栈同时弹出栈顶元素。
代码：
import java.util.Stack;
public class Solution {
// 存放所有元素的栈
Stack<Integer> stackTotal = new Stack();
// 存放最小元素的栈
Stack<Integer> stackMin = new Stack();
public void push(int node) {
stackTotal.push(node);
if (stackMin.empty()) {
stackMin.push(node);
} else {
if (node <= stackMin.peek()) {
stackMin.push(node);
} else {
stackMin.push(stackMin.peek());
}
}
}
public void pop() {
stackTotal.pop();
stackMin.pop();
}
public int top() {
return stackTotal.peek();
}
public int min() {
return stackMin.peek();
}
}栈的压入、弹出序列
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
分析：
新建一个栈，将数组A压入栈中，当栈顶元素等于数组B时，就将其出栈，当循环结束时，判断栈是否为空，若为空则返回true.
代码：
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if (pushA.length == 0 || popA.length == 0 || pushA.length != popA.length) {
return false;
}
Stack<Integer> stack = new Stack();
int j = 0;
for (int i = 0; i < pushA.length; i++) {
stack.push(pushA[i]);
while (!stack.empty() && stack.peek() == popA[j]) {
stack.pop();
j++;
}
}
return stack.empty();
}
}从上往下打印二叉树
题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
分析：
本题使用知识点是树和队列。在Java中Queue是和List、Map同等级别的接口，LinkedList中也实现了Queue接口，该接口中的主要函数有：
- 容量不够或队列为空时不会抛异常：offer（添加队尾元素）、peek（访问队头元素）、poll（访问队头元素并移除）
- 容量不够或队列为空时抛异常：add、element（访问队列元素）、remove（访问队头元素并移除）
代码：
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
if (root == null) return list;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
return list;
}
}二叉搜索树的后序遍历序列
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
分析：
上图为二叉搜索树示例：
- 一棵 BST ：左孩子 < 根结点 < 右孩子
- 一棵 BST 的左子树或者右子树都是 BST
后序遍历是：[3, 4, 9, 5, 12, 11, 10]，结合图再从左往右分析后序序列，分析子树，可以发现对于每一棵子树，它的根结点总是对应该子树的后序序列的最后一个数
那么，只需要不断地确定出左子树区间和右子树区间，并且判断：左子树区间的所有结点值 < 根结点值 < 右子树区间所有结点值，这个条件是否满足即可
代码：
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if (sequence == null || sequence.length == 0) {
return false;
}
return helperVerify(sequence, 0, sequence.length - 1);
}
public boolean helperVerify(int[] sequence, int start, int end) {
if (start >= end) return true;
int root = sequence[end];
int i;
for (i = 0; i < end; i++) {
if (sequence[i] > root) {
break;
}
}
for (int j = i; j < end; j++) {
if (sequence[j] < root) {
return false;
}
}
return helperVerify(sequence, start, i - 1) && helperVerify(sequence, i, end - 1);
}
}二叉树中和为某一值的路径
题目描述
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
解法1 递归
代码：
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> list = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if (root == null) return result;
list.add(root.val);
target -= root.val;
if (target == 0 && root.left == null && root.right == null) {
//result.add(list)是把list这个对象的引用地址添加到result了，
//result中的元素就会共用list，而list是我们用来存放当前路径的地方，
//因此我们需要复制一份之后加入result数组中
result.add(new ArrayList<Integer>(list));
}
FindPath(root.left, target);
FindPath(root.right, target);
//使用了list这个列表来存储当前走过的节点，所以为了寻找新的路径，
//递归完返回上一次的时候要删除掉，这样才能保证寻找下一个路径的时候是正确的，
list.remove(list.size() - 1);
return result;
}
}二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解法1
分析
用一个数组来存储中序遍历的节点，然后再从头到尾，建立节点前后的连接关系。
代码：
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null) return null;
// 中序遍历存入list中
ArrayList<TreeNode> list = new ArrayList<>();
PostorderTraversal(pRootOfTree, list);
// 修改指针
return Convert(list);
}
// 中序遍历
public void PostorderTraversal(TreeNode node, ArrayList<TreeNode> list) {
if (node.left != null) PostorderTraversal(node.left, list);
list.add(node);
if (node.right != null) PostorderTraversal(node.right, list);
}
public TreeNode Convert(ArrayList<TreeNode> list) {
TreeNode head = list.get(0);
TreeNode cur = head;
for (int i = 1; i < list.size(); ++i) {
TreeNode node = list.get(i);
node.left = cur;
cur.right = node;
cur = node;
}
return head;
}
}优化（现在看着有点懵）：https://blog.nowcoder.net/n/17c95de2427e49abb207a6a9d37c602d
剪绳子
题目描述
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
解法1 数学公式推导
分析
参考精选题解LeetCode
代码：
class Solution {
public int cuttingRope(int n) {
if (n <= 3) return n - 1;
int a = n / 3, b = n % 3;
if (b == 0) return (int)Math.pow(3, a);
if (b == 1) return (int)Math.pow(3, a - 1) * 4;
return (int)Math.pow(3, a) * 2;
}
}数据流中的中位数
题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
解法1 堆（优先队列）
分析
参考精选题解牛客网
代码：
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
// 小顶堆
private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
// 大顶堆
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
//记录偶数个还是奇数个
int count = 0;
//每次插入小顶堆的是当前大顶堆中最大的数
//每次插入大顶堆的是当前小顶堆中最小的数
//这样保证小顶堆中的数永远大于等于大顶堆中的数
//中位数就可以方便地从两者的根结点中获取了
public void Insert(Integer num) {
//个数为偶数的话，则先插入到大顶堆，然后将大顶堆中最大的数插入小顶堆中
if(count % 2 == 0){
maxHeap.offer(num);
int max = maxHeap.poll();
minHeap.offer(max);
}else{
//个数为奇数的话，则先插入到小顶堆，然后将小顶堆中最小的数插入大顶堆中
minHeap.offer(num);
int min = minHeap.poll();
maxHeap.offer(min);
}
count++;
}
public Double GetMedian() {
//当前为偶数个，则取小顶堆和大顶堆的堆顶元素求平均
if(count % 2 == 0){
return new Double(minHeap.peek() + maxHeap.peek())/2;
}else{
//当前为奇数个，则直接从小顶堆中取元素即可
return new Double(minHeap.peek());
}
}
}表示数值的字符串
题目描述
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。
解法1 正则表达式
分析
参考题解牛客网
^ 和 美元符号框定正则表达式，它指引这个正则表达式对文本中的所有字符都进行匹配。如果省略这些标识，那么只要一个字符串中包含一个数字这个正则表达式就会进行匹配。如果仅包含 ^ ，它将匹配以一个数字开头的字符串。如果仅包含$ ，则匹配以一个数字结尾的字符串。
[-+]?正负号后面的 ? 后缀表示这个负号是可选的,表示有0到1个负号或者正号
\\d*\d的含义和[0-9]一样。它匹配一个数字。后缀 * 指引它可匹配零个或者多个数字。
(?:\\.\\d*)?(?: …)?表示一个可选的非捕获型分组。* 指引这个分组会匹配后面跟随的0个或者多个数字的小数点。
(?:[eE][+\\-]?\d+)?这是另外一个可选的非捕获型分组。它会匹配一个e(或E)、一个可选的正负号以及一个或多个数字。
代码：
import java.util.regex.Pattern;
public class Solution {
public boolean isNumeric(char[] str) {
String pattern = "^[-+]?\\d*(?:\\.\\d*)?(?:[eE][+\\-]?\\d+)?$";
String s = new String(str);
return Pattern.matches(pattern, s);
}
}数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解法1
分析
参考题解牛客网
用preArray记录上一次访问的值，count表明当前值出现的次数，如果下一个值和当前值相同那么count++；如果不同count–，减到0的时候就要更换新的preValue值了，如果存在超过数组长度一半的值，那么最后preValue一定会是该值。
代码：
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if (array == null || array.length == 0) return 0;
int preArray = array[0];
int count = 1;
for (int i = 1; i < array.length; i++) {
if (preArray == array[i]) {
count ++;
} else {
count --;
if (count == 0) {
preArray = array[i];
count = 1;
}
}
}
int num = 0;
for (int i = 0; i < array.length; i++) {
if (preArray == array[i]) {
num ++;
}
}
return (num > array.length / 2) ? preArray : 0;
}
}圆圈中最后剩下的数字
题目描述
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
解法1 模拟链表
分析
参考题解LeetCode
假设当前删除的位置是 index，下一个删除的数字的位置是 index + m。但是，由于把当前位置的数字删除了，后面的数字会前移一位，所以实际的下一个位置是 index + m - 1。由于数到末尾会从头继续数，所以最后取模一下，就是 (index + m - 1)%n。时间复杂度 $O(n^2)$
代码：
import java.util.ArrayList;
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if (n == 0) return -1;
ArrayList<Integer> list = new ArrayList<Integer>(n);
for (int i = 0; i < n; i++) {
list.add(i);
}
int index = 0;
while (n > 1) {
index = (index + m - 1) % n;
list.remove(index);
n--;
}
return list.get(0);
}
}解法2 数学❤️
分析
参考题解LeetCode
代码：
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if (n == 0) return -1;
int ans = 0;
// 最后一轮剩下2个人，所以从2开始反推
for (int i = 2; i <= n; i++) {
ans = (ans + m) % i;
}
return ans;
}
}求1+2+3+…+n
题目描述
求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）
解法1 公式转换
分析
参考题解牛客网
这是一个等差数列，$sum = n * (1 + n) / 2 = (n + n^2) / 2$，Math.pow(n,2)表示 $n^2$；右移一位相当于除以2
代码：
public class Solution {
// n*(n+1)/2 = (n+n^2)/2
public int Sum_Solution(int n) {
int sum = n + (int)Math.pow(n, 2);
return sum>>1;
}
}解法2 递归
分析
参考题解牛客网
在递归算法中，需要终止递归，一般我们会通过if来进行判断，现在不让通过if进行判断，我们可以使用逻辑与&&连接符。A&&B，表示如果A成立则执行B，否则如果A不成立，不用执行B。在n>1的时候，执行递归函数。
代码：
public class Solution {
// 递归
public int Sum_Solution(int n) {
boolean flag = n > 1 && (n += Sum_Solution(n - 1)) > 0;
return n;
}
}扑克牌中的顺子
题目描述
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
输入: [0,0,1,2,5] 输出: True
解法1 集合 Set + 遍历
分析
参考题解LeetCode
遍历五张牌，遇到大小王（即 0）直接跳过。
判别重复： 利用 Set 实现遍历判重， Set 的查找方法的时间复杂度为 O(1)；
获取最大 / 最小的牌： 借助辅助变量 max 和 min，遍历统计即可。
代码：
class Solution {
public boolean isStraight(int[] nums) {
Set<Integer> set = new HashSet<>();
int max = 0, min = 13;
for (int num : nums) {
if (num == 0) continue;
max = Math.max(max, num);
min = Math.min(min, num);
if (set.contains(num)) return false;
set.add(num);
}
return max - min < 5;
}
}解法2 排序 + 遍历
分析
参考题解LeetCode
先对数组执行排序。
判别重复： 排序数组中的相同元素位置相邻，因此可通过遍历数组，判断 nums[i]=nums[i+1] 是否成立来判重。
获取最大 / 最小的牌： 排序后，数组末位元素 nums[4]为最大牌；元素 nums[joker] 为最小牌，其中 jokerjoker 为大小王的数量。
代码：
class Solution {
public boolean isStraight(int[] nums) {
int joker = 0;
// 数组排序
Arrays.sort(nums);
for (int i = 0; i < 4; i++) {
// 统计大小王数量
if (nums[i] == 0) joker++;
// 判别重复
else if (nums[i] == nums[i+1]) return false;
}
// 最大牌 - 最小牌 < 5 则可构成顺子
return nums[4] - nums[joker] < 5;
}
}连续子数组的最大和
题目描述
在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
解法1 动态规划
分析
参考题解牛客网
dp[n]代表以当前元素为截止点的连续子序列的最大和，如果dp[n-1]>0，dp[n]=dp[n]+dp[n-1]，因为当前数字加上一个正数一定会变大；如果dp[n-1]<0，dp[n]不变，因为当前数字加上一个负数一定会变小。使用一个变量max记录最大的dp值返回即可。
代码：
public class Solution {
// 动态规划问题
public int FindGreatestSumOfSubArray(int[] array) {
int max = array[0];
for (int i = 1; i < array.length; i++) {
array[i] += array[i - 1] > 0 ? array[i - 1] : 0;
max = Math.max(max, array[i]);
}
return max;
}
}1～n 整数中 1 出现的次数
题目描述
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
输入：n = 12 输出：5
解法1 数学
分析
参考详细题解LeetCode
代码：
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int digit = 1, res = 0;
int hight = n / 10, cur = n % 10, low = 0;
while (hight != 0 || cur != 0) {
if (cur == 0) res += hight * digit;
else if(cur == 1) res += hight * digit + low + 1;
else res += (hight + 1) * digit;
low += cur * digit;
cur = hight % 10;
hight /= 10;
digit *= 10;
}
return res;
}
} 左旋字符串
题目描述
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。
解法1 字符串切片sbstring
分析
拼接字符串：str.substring(n) + str.substring(0, n);
代码：
public class Solution {
public String LeftRotateString(String str,int n) {
if (str == null || str.length() < n) {
return str;
}
return str.substring(n) + str.substring(0, n);
}
}解法二 列表遍历拼接
分析
新建一个StringBuilder ，记为res；向res添加 “第 n + 1位至末位的字符” ；再向 res添加 “首位至第 n 位的字符” ；将 res转化为字符串并返回。
代码：
class Solution {
public String reverseLeftWords(String s, int n) {
if (s == null || s.length() == 0 || s.length() < n) {
return s;
}
StringBuilder res = new StringBuilder();
for (int i = n; i < n + s.length(); i++) {
res.append(s.charAt(i % s.length()));
}
return res.toString();
}
}和为S的两个数字
题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
解法1 双指针法
分析
初始化： 双指针 i , j分别指向数组 array的左右两端。
循环搜索： 当双指针相遇时跳出；
计算和 int res = array[i] + array[j]
若 res > sum，则指针 j 向左移动，即执行 j –；
若 res < sum，则指针i向右移动，即执行 i = i ++；
若 res = sum ，把两元素添加到list集合中；
代码：
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> list = new ArrayList<>();
if (array.length == 0 || array == null) return list;
int i = 0, j = array.length - 1;
while (i < j) {
int res = array[i] + array[j];
if (res < sum) {
i++;
}else if (res > sum) {
j--;
} else {
list.add(array[i]);
list.add(array[j]);
break;
}
}
return list;
}
}和为S的连续正数序列
题目描述
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
输入：target = 9 输出：[[2,3,4],[4,5]]
解法1 滑动窗口
分析
参考详细题解LeetCode
代码：
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if (sum <= 0) return res;
int left = 1;
int right = 1;
int sumVal = 0;
while (left <= sum / 2) {
if (sumVal < sum) {
sumVal += right;
right++;
}else if (sumVal > sum) {
sumVal = sumVal - left;
left++;
} else {
ArrayList<Integer> list = new ArrayList<>();
for (int i = left; i < right; i++) {
list.add(i);
}
res.add(list);
sumVal -= left;
left++;
}
}
return res;
}
}###平衡二叉树
题目描述
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true
解法1 后序遍历
分析
参考详细题解LeetCode
代码：
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if (root == null) return true;
return depth(root) != -1;
}
private int depth(TreeNode root) {
if (root == null) return 0;
int left = depth(root.left);
if (left == -1) return -1;
int right = depth(root.right);
if (right == -1) return -1;
return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
}
}###两个链表的第一个公共结点
题目描述
输入两个链表，找出它们的第一个公共节点。
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
解法1 双指针法
分析
参考详细题解LeetCode
遍历两遍这两个链表，如果有重复的节点，那么一定能够使遍历的指针相等。
代码：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) return null;
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
if (p1 != p2) {
if (p1 == null) p1 = pHead2;
if (p2 == null) p2 = pHead1;
}
}
return p1;
}
}###链表中环的入口
题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
解法1 双指针（快慢指针）法
分析
参考详细题解LeetCode
定义两个指针开始都指向头结点，然后快指针一次走二步，慢指针一次走一步，当两个指针第一次相遇时，跳出循环，此时让快指针再次重新指向头结点，慢指针位置不变，接下来快慢指针都一步一步走，当快慢指针再次相遇时，跳出循环，此时相遇点即为该链表的环的入口结点。
时间复杂度 O(N)：总体为线性复杂度；
空间复杂度 O(1)：双指针使用常数大小的额外空间。
代码：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if (pHead == null) return pHead;
ListNode fast = pHead, slow = pHead;
while (true) {
if (fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
fast = pHead;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}第一个只出现一次的字符
题目描述
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
s = "abaccdeff" 返回 "b" s = "" 返回 " "
解法1 哈希表
分析
参考详细题解LeetCode
代码：
class Solution {
public char firstUniqChar(String s) {
HashMap<Character, Boolean> map = new HashMap<>();
char[] res = s.toCharArray();
for (char c : res)
map.put(c, !map.containsKey(c));
for (char c : res)
if (map.get(c)) return c;
return ' ';
}
}机器人的运动范围
题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
输入：m = 2, n = 3, k = 1 输出：3
解法1 深度优先遍历（DFS）
分析
参考详细题解LeetCode
矩阵搜索问题一般可使用DFS和BFS解决。本题中有一个限定条件，行坐标和列坐标的数位之和不能大于某个已知给定的K值，因此我们需要先了解数位和的求解方法。
数位和计算
给定一数字x,通过x%10得到x的个位数字，通过x/10得到x的删除个位数的数字，因此，可通过如下代码求得x得数位和。
int sum = 0;
while (x != 0) {
sum += x % 10;
x = x / 10;
}
return sum;数位和增量公式
由于机器人每一次只能向左，右，上，下四个方向移动一格，因此每次只需要计算x到x+1/x-1的数位和增量，本题说明 1<= n, m <= 100 ，以下公式仅在此范围适用。
设x的数位和为sx,x+1的数位和为sx+1
当
（x + 1）% 10 = 0时，sx + 1 = sx - 8，如89，90的数位和分别为17，9；当
（x + 1）% 10 != 0时，sx + 1 = sx + 1,如2，3的数位和分别为2，3。(x + 1) % 10 != 0 ? si + 1 : si - 8;
算法思路：
递归参数：当前元素在矩阵中的行列索引i和j，两者的数位和为si、sj。
终止条件：1、行列索引越界 2、数位和超出目标值 3、当前元素已访问过。满足上面3种条件的一种，则最后返回0
递归流程：标记当前单元格，将其值设置为布尔值记录下来，值设置为true，代表此单元格已被访问过。然后计算当前元素的下、右两个方向元素的数位和，并开启下层递归。
回溯返回值：返回1+右方搜索符合条件的总数+下方搜索符合条件的总数。
代码：
class Solution {
public char firstUniqChar(String s) {
HashMap<Character, Boolean> map = new HashMap<>();
char[] res = s.toCharArray();
for (char c : res)
map.put(c, !map.containsKey(c));
for (char c : res)
if (map.get(c)) return c;
return ' ';
}
}矩阵中的路径
题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true
解法1 深度优先遍历（DFS）
分析
使用DFS递归的回溯剪枝思想，即添加一些判断条件使得程序不再递归下去。首先对于matrix中的每一个都可能是起点，需要遍历。由题可知，只要找到一条路径，即可返回true，最后的0表示从str的第0个字符开始。对于从每一个点开始的子路径，因为使用递归，我们只需知道在这一步该怎么做即可，不用管之后该怎么做。同时找到一个递归的出口即可。
其实如果没有str的长度限制，上面的代码会陷入死循环，但是该题中有str的长度限制，导致dfs最深的深度为str的长度。（类似于TCP中的TTL的作用）但是该题中规定不能访问重复的字符。于是需要一个记录访问的数组visited。
代码：
public class Solution {
boolean[] visited = null;
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
visited = new boolean[matrix.length];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (dfs(matrix, rows, cols, str, i, j, 0)) return true;
}
}
return false;
}
public boolean dfs(char[] matrix, int rows, int cols, char[] str, int i, int j, int k) {
if (matrix[i*cols + j] != str[k] || visited[i*cols+j] == true) return false;
if (k == str.length - 1) return true;
visited[i*cols+j] = true;
if (i > 0 && dfs(matrix, rows, cols, str, i - 1, j, k+1)) return true;
if (j > 0 && dfs(matrix, rows, cols, str, i, j - 1, k+1)) return true;
if (i < rows - 1 && dfs(matrix, rows, cols, str, i + 1, j, k+1)) return true;
if (j < cols - 1 && dfs(matrix, rows, cols, str, i, j + 1, k + 1)) return true;
visited[i*cols+j] = false;
return false;
}
}数组中的逆序对
题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
输入：1,2,3,4,5,6,7,0
输出：7
题目保证输入的数组中没有的相同的数字数据范围： 对于%50的数据,size<=10^4 对于%75的数据,size<=10^5 对于%100的数据,size<=2*10^5
解法1 暴力法
分析
使用两层for循环枚举所有的数对，判断前面的数字大于后面的数字，构成逆序对关系。时间复杂度为O(n^2),空间复杂度O(1)
代码：
public class Solution {
public int InversePairs(int [] array) {
int count = 0;
int len = array.length;
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (array[i] > array[j]) {
count++;
}
}
}
return count;
}
}解法2 暴力法
分析
使用两层for循环枚举所有的数对，判断前面的数字大于后面的数字，构成逆序对关系。
代码：
public class Solution {
public int InversePairs(int [] array) {
int count = 0;
int len = array.length;
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (array[i] > array[j]) {
count++;
}
}
}
return count;
}
}解法1 暴力法
分析
使用两层for循环枚举所有的数对，判断前面的数字大于后面的数字，构成逆序对关系。
代码：
public class Solution {
public int InversePairs(int [] array) {
int count = 0;
int len = array.length;
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (array[i] > array[j]) {
count++;
}
}
}
return count;
}
}###
参考：
