二刷整合，//考虑使用快慢指针
分享于 点击 3729 次 点评：233
二刷整合，//考虑使用快慢指针
数组：内存空间连续，数据类型统一，下标从0开始
二分查找
704
class Solution {
public int search(int[] nums, int target) {
// 方法一：暴力解法
// for(int i = 0; i < nums.length; i++){
// if(nums[i] == target){//找到目标值
// return i;
// }
// }
// return -1;
// 方法二：二分查找（元素有序且无重复元素），使用迭代，执行速度快，但是内存消耗大
// return binarySearch(nums, target, 0, nums.length-1);
// 方法三：二分查找，统一使用左闭右闭区间
// 上来先处理边界条件
if(target < nums[0] || target > nums[nums.length - 1]){
return -1;
}
int left = 0;
int right = nums.length - 1;//右闭区间
int mid = (left + right) >> 1;
while(left <= right){//因为取得数组区间左右都是闭的，所以取等号的时候也能满足条件，还不需要退出循环
if(target == nums[mid]){
return mid;
}else if(target < nums[mid]){
right = mid -1;//往左区间缩
}else{
left = mid +1;
}
mid = (left + right) >> 1;
}
return -1;
}
// public int binarySearch(int[] nums, int target, int start, int end){
// int mid = (start+end)/2;
// int find = -1;
// if(start > end){//没有找到
// return -1;
// }
// if(target == nums[mid]){
// return mid;
// }else if(target < nums[mid]){
// find = binarySearch(nums, target, start, mid-1);
// }else{
// find = binarySearch(nums, target, mid+1, end);
// }
// return find;
// }
}
搜索插入位置
35
class Solution {
public int searchInsert(int[] nums, int target) {
// 有序数组，考虑用二分查找
int left = 0;
int right = nums.length - 1;
int mid = (left + right) >> 1;
if(target < nums[left]){
return left;
}
if(target > nums[right]){
return right + 1;
}
while(left <= right){
if(target == nums[mid]){
return mid;
}else if(target < nums[mid]){
right = mid -1;
}else{
left = mid + 1;
}
mid = (left + right) >> 1;
}
return left;//找不到，返回需要插入的位置
}
}
在排序数组中查找元素的第一个和最后一个位置
34
class Solution {
public int[] searchRange(int[] nums, int target) {
// 非递减说明是升序的，但可以有重复元素
int[] arr = {-1, -1};
if(nums.length == 0){
return arr;
}
int left = 0;
int right = nums.length - 1;
int mid = (left + right) >> 1;
if(target < nums[left] || target > nums[right]){
return arr;//边界值
}
int leftPoint;//目标数组的开始位置
int rightPoint;//目标数组的结束位置
while(left <= right){
if(target == nums[mid]){
leftPoint = mid;
rightPoint = mid;
while(leftPoint >= 0 && target == nums[leftPoint]){
arr[0] = leftPoint;
leftPoint--;//向左寻找重复元素
}
while(rightPoint <= (nums.length - 1) && target == nums[rightPoint]){
arr[1] = rightPoint;
rightPoint++;//向右寻找重复元素
}
return arr;//返回找到的目标值的位置
}else if(target < nums[mid]){
right = mid - 1;
}else{
left = mid + 1;
}
mid = (left + right) >> 1;
}
return arr;//没有找到
}
}
69、x的平方根
class Solution {
public int mySqrt(int x) {
// 使用二分查找
int left = 0;
int right = x;
int mid = (left + right) / 2;
while(left <= right){
if((long)mid * mid < x){
left = mid + 1;
}else if((long)mid * mid > x){
right = mid - 1;
}else{
return mid;
}
mid = (left + right) / 2;
}
return right;
}
}
367、有效的完全平方数
class Solution {
public boolean isPerfectSquare(int num) {
int left = 0, right = num;
while(left <= right){
int mid = (left + right) >> 1;
if((long) mid * mid == num){
return true;
}else if((long) mid * mid < num){
left = mid + 1;
}else{
right = mid - 1;
}
}
return false;
}
}
移除元素
27
class Solution {
public int removeElement(int[] nums, int val) {
// 原地移除，所有元素
// 数组内元素可以乱序
// 方法一：暴力解法，不推荐，时间复杂度O(n^2)
// int right = nums.length;//目标数组长度，右指针
// for(int i = 0; i < right; i++){
// if(val == nums[i]){
// right--;//找到目标数值，目标数长度减一，右指针左移
// for(int j = i; j < right; j++){
// nums[j] = nums[j + 1];//数组整体左移一位（数组元素不能删除，只能覆盖）
// }
// i--;//左指针左移
// }
// }
// return right;
// 方法二：快慢指针，时间复杂度O(n)
// int solwPoint = 0;
// for(int fastPoint = 0; fastPoint < nums.length; fastPoint++){
// if(nums[fastPoint] != val){
// nums[solwPoint] = nums[fastPoint];
// solwPoint++;
// }
// }
// return solwPoint;
// 方法三：注意元素的顺序可以改变，使用相向指针，时间复杂度O(n)
int rightPoint = nums.length - 1;
int leftPoint = 0;
while(rightPoint >= 0 && nums[rightPoint] == val){
rightPoint--;
}
while(leftPoint <= rightPoint){
if(nums[leftPoint] == val){
nums[leftPoint] = nums[rightPoint--];
}
leftPoint++;
while(rightPoint >= 0 && nums[rightPoint] == val){
rightPoint--;
}
}
return leftPoint;
}
}
26、删除排序数组中的重复项
class Solution {
public int removeDuplicates(int[] nums) {
// 相对顺序一致，所以不能使用相向指针。
// 考虑使用快慢指针
if(nums.length == 1){
return 1;
}
int slowPoint = 0;
for(int fastPoint = 1; fastPoint < nums.length; fastPoint++){
if(nums[slowPoint] != nums[fastPoint]){
nums[++slowPoint] = nums[fastPoint];
}
}
return slowPoint + 1;
}
}
283、移动零
class Solution {
public void moveZeroes(int[] nums) {
// 要保持相对顺序，不能用相向指针
int slowPoint = 0;
for(int fastPoint = 0; fastPoint < nums.length; fastPoint++){
if(nums[fastPoint] != 0){
nums[slowPoint++] = nums[fastPoint];//所有非零元素移到左边
}
}
for(; slowPoint < nums.length; slowPoint++){
nums[slowPoint] = 0;//把数组末尾置零
}
}
}
844、比较含退格的字符串
class Solution {
public boolean backspaceCompare(String s, String t) {
// 从前往后的话不确定下一位是不是"#"，当前位需不需要消除，所以采用从后往前的方式
int countS = 0;//记录s中"#"的数量
int countT = 0;//记录t中"#"的数量
int rightS = s.length() - 1;
int rightT = t.length() - 1;
while(true){
while(rightS >= 0){
if(s.charAt(rightS) == '#'){
countS++;
}else{
if(countS > 0){
countS--;
}else{
break;
}
}
rightS--;
}
while(rightT >= 0){
if(t.charAt(rightT) == '#'){
countT++;
}else{
if(countT > 0){
countT--;
}else{
break;
}
}
rightT--;
}
if(rightT < 0 || rightS < 0){
break;
}
if(s.charAt(rightS) != t.charAt(rightT)){
return false;
}
rightS--;
rightT--;
}
if(rightS == -1 && rightT == -1){
return true;
}
return false;
}
}
有序数组的平方
977
class Solution {
public int[] sortedSquares(int[] nums) {
// 用相向的双指针
int[] arr = new int[nums.length];
int index = arr.length - 1;
int leftPoint = 0;
int rightPoint = nums.length - 1;
while(leftPoint <= rightPoint){
if(Math.pow(nums[leftPoint], 2) > Math.pow(nums[rightPoint], 2)){
arr[index--] = (int)Math.pow(nums[leftPoint], 2);
leftPoint++;
}else{
arr[index--] = (int)Math.pow(nums[rightPoint], 2);
rightPoint--;
}
}
return arr;
}
}
长度最小的子数组
209
class Solution {
public int minSubArrayLen(int target, int[] nums) {
// 注意是连续子数组
// 使用滑动窗口，实际上还是双指针
int left = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
for(int right = 0; right < nums.length; right++){//for循环固定的是终止位置
sum += nums[right];
while(sum >= target){
result = Math.min(result, right - left + 1);//记录最小的子数组
sum -= nums[left++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
904、水果成篮
class Solution {
public int totalFruit(int[] fruits) {
// 此题也可以使用滑动窗口
int maxNumber = 0;
int left = 0;
Map<Integer, Integer> map = new HashMap<>();//用哈希表记录被使用的篮子数量，以及每个篮子中的水果数量
for(int right = 0; right < fruits.length; right++){
map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);//往篮子里面放水果
while(map.size() > 2){//放进去的水果不符合水果类型
map.put(fruits[left], map.get(fruits[left]) - 1);
if(map.get(fruits[left]) == 0){
map.remove(fruits[left]);
}
left++;
}
maxNumber = Math.max(maxNumber, right - left + 1);
}
return maxNumber;
}
}
螺旋矩阵 II
59
class Solution {
public int[][] generateMatrix(int n) {
// 方法一：直接按序输出
int[][] arr = new int[n][n];
int top = 0;
int buttom = n - 1;
int left = 0;
int right = n - 1;;
int index = 1;
while(left <= right && top <= buttom && index <= n*n){
for(int i = left; i <= right; i++){
arr[top][i] = index++;
}
top++;
for(int i = top; i <= buttom; i++){
arr[i][right] = index++;
}
right--;
for(int i = right; i >= left; i--){
arr[buttom][i] = index++;
}
buttom--;
for(int i = buttom; i >= top; i--){
arr[i][left] = index++;
}
left++;
}
return arr;
}
}
54
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int top = 0;
int buttom = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
List<Integer> list = new ArrayList<Integer>();
while(left <= right && top <= buttom){
for(int i = left; i <= right; i++){
if(top <= buttom)
list.add(matrix[top][i]);
}
top++;
for(int i = top; i <= buttom; i++){
if(left <= right)
list.add(matrix[i][right]);
}
right--;
for(int i = right; i >= left; i--){
if(top <= buttom)
list.add(matrix[buttom][i]);
}
buttom--;
for(int i = buttom; i >= top; i--){
if(left <= right)
list.add(matrix[i][left]);
}
left++;
}
return list;
}
}
29 、顺时针打印矩阵
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix.length == 0){
return new int[0];
}
int top = 0;
int buttom = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
int[] arr = new int[matrix.length*matrix[0].length];
int index = 0;
while(left <= right && top <= buttom){
for(int i = left; i <= right; i++){
if(top <= buttom)
arr[index++] = matrix[top][i];
}
top++;
for(int i = top; i <= buttom; i++){
if(left <= right)
arr[index++] = matrix[i][right];
}
right--;
for(int i = right; i >= left; i--){
if(top <= buttom)
arr[index++] = matrix[buttom][i];
}
buttom--;
for(int i = buttom; i >= top; i--){
if(left <= right)
arr[index++] = matrix[i][left];
}
left++;
}
return arr;
}
}
链表：插入快，查询慢，存储不连续
分为单链表，双链表和循环链表
在链表中使用虚拟头结点，可以减少增删改查中对头结点的特殊处理
移除链表元素
203
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 方法一：设置虚节点方式，推荐方式
ListNode dummy = new ListNode(-1,head);
ListNode pre = dummy;
ListNode cur = head;
while(cur != null){
if(cur.val == val){
pre.next = cur.next;
}else{
pre = cur;
}
cur = cur.next;
}
return dummy.next;
// 方法二：时间复杂度O(n)，空间复杂度O(1)
if(head == null){//空链表的情况
return head;
}
while(head != null && head.val == val){//头结点为val的情况
head = head.next;
}
ListNode temp = head;
while(temp != null && temp.next != null){
while(temp != null && temp.next != null && temp.next.val == val){
if(temp.next.next != null){
temp.next = temp.next.next;
}else{//最后一个节点为val的情况
temp.next = null;
}
}
temp = temp.next;
}
return head;
}
}
707、设计链表
class MyLinkedList {
int size;
ListNode head;
ListNode tail;
// 初始化链表,构建虚拟的头结点和尾节点
public MyLinkedList() {
size = 0;
head = new ListNode(0);
tail = new ListNode(0);
head.next = tail;
tail.prev = head;
}
public int get(int index) {
ListNode cur = head;
if(index > size - 1 || index < 0){
return -1;
}
while(index >= 0){
cur = cur.next;
index--;
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0,val);
}
public void addAtTail(int val) {
addAtIndex(size,val);
}
public void addAtIndex(int index, int val) {
if(index > size){
return;
}
if(index < 0 ){
index = 0;
}
size++;
ListNode temp = new ListNode(val);
ListNode cur = head;
while(index > 0){
cur = cur.next;
index--;
}
temp.next = cur.next;
cur.next = temp;
temp.prev = cur;
}
public void deleteAtIndex(int index) {
ListNode cur = head;
if(index > size - 1 || index < 0){
return;
}
while(index > 0){
cur = cur.next;
index--;
}
cur.next = cur.next.next;
size--;
}
}
class ListNode {
int val;
ListNode next;
ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
反转链表
206
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 方法一：在头结点不断插入
// if(head == null){
// return head;//空节点不需要反转
// }
// ListNode temp = head.next;//临时节点前移一位
// head.next = null;//代反转链表的头结点拆出来
// ListNode newHead = head;//待反转链表的头结点赋给新的链表
// while(temp != null){
// head = temp;//找出待反转链表的新头结点
// temp = temp.next;//临时节点前移一位
// head.next = null;//待反转链表的新头拆出来
// head.next = newHead;//待反转链表的心头指向新的链表
// newHead = head;//得到新的链表的新头
// }
// return newHead;
// 方法二：压栈，利用栈的先入后出
// if(head == null){
// return head;
// }
// Stack<ListNode> stack = new Stack<>();
// ListNode temp = head;
// while(head != null){
// temp = head.next;
// head.next = null;
// stack.push(head);
// head = temp;
// }
// ListNode newHead = new ListNode();
// temp = newHead;
// while(!stack.isEmpty()){
// temp.next = stack.pop();
// temp = temp.next;
// }
// return newHead.next;
// 方法三：递归
return reverse(null, head);
// 方法四：从后往前递归
// if(head == null){
// return null;
// }
// if(head.next == null){
// return head;
// }
// ListNode newHead = reverseList(head.next);
// head.next.next = head;
// head.next = null;
// return newHead;
}
public ListNode reverse(ListNode pre, ListNode cur){
if(cur == null){
return pre;
}
ListNode temp = cur.next;
cur.next = pre;
return reverse(cur,temp);
}
}
两两交换链表中的节点
24
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
// 方法一：从前往后进行迭代
// if(head == null){
// return null;
// }
// if(head.next == null){
// return head;
// }
// ListNode temp = head.next;//依次记录偶数节点的位置
// head.next = head.next.next;//交换相邻的节点
// temp.next = head;
// temp.next.next = swapPairs(temp.next.next);//迭代交换下一个相邻的节点
// return temp;
// 方法二：双指针
if(head == null){
return null;
}
if(head.next == null){
return head;
}
ListNode temp = head.next;
ListNode pre = head.next;//记录新的头结点
while(temp != null){
head.next = head.next.next;//交换相邻的节点
temp.next = head;
if(head.next == null || head.next.next == null){
break;
}else{
head = head.next;//指向下一个相邻节点的奇数节点
temp.next.next = temp.next.next.next;//上一个相邻节点的偶数节点指向下一个节点的偶数节点
temp = head.next;//下一个相邻节点的偶数节点
}
}
return pre;
}
}
删除链表的倒数第 N 个结点
19
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 方法一：快慢指针，返回头结点说明head的头结点不能动，所以把链表的地址赋给另外一个对象
// 添加虚拟头结点，方便操作。比如需要删除的是头结点的时候不需要单独考虑这种特殊情况
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode cur = dummyHead;
ListNode temp = dummyHead;
for(int i = 0; i < n; i++){
temp = temp.next;
}
while(temp.next != null){
cur = cur.next;
temp = temp.next;
}
cur.next = cur.next.next;
return dummyHead.next;
}
}
链表相交
02.07
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode dummyHeadA = headA;
int countA = 0;
int countB = 0;
ListNode dummyHeadB = headB;
while(dummyHeadA.next != null){
dummyHeadA = dummyHeadA.next;
countA++;
}
while(dummyHeadB.next != null){
dummyHeadB = dummyHeadB.next;
countB++;
}
if(dummyHeadA != dummyHeadB){
return null;//尾节点不相交则说明不相交
}
dummyHeadA = headA;
dummyHeadB = headB;
int index = (countA - countB) > 0 ? (countA - countB) : -(countA - countB);//两个链表的长度差
for(int i = 0; i < index; i++){//让较长的链表先移动index位
if((countA - countB) > 0){
dummyHeadA = dummyHeadA.next;
}else{
dummyHeadB = dummyHeadB.next;
}
}
while(dummyHeadA != dummyHeadB){//两个链表逐次向前移动，找出相交的第一个节点
dummyHeadA = dummyHeadA.next;
dummyHeadB = dummyHeadB.next;
}
return dummyHeadA;
}
}
环形链表 II
142
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
int count = 0;
while(fast != null && fast.next != null){//判断是否有环
fast = fast.next.next;
slow = slow.next;
count++;
if(fast == slow){
// 找环的入口
while(head != slow){
head = head.next;
slow = slow.next;
}
return head;
}
}
return null;
}
}
哈希表：也叫散列表，用来快速判断一个元素是否出现在集合中，实际上是用空间换时间
有效的字母异位词
242
class Solution {
public boolean isAnagram(String s, String t) {
// 方法一：使用hashmap
// if(s.length() != t.length()){
// return false;
// }
// HashMap<Character, Integer> map = new HashMap<>();
// for(int i = 0; i < s.length(); i++){
// map.put(s.charAt(i), (map.getOrDefault(s.charAt(i), 0) + 1));
// }
// for(int i = 0; i < t.length(); i++){
// if(map.containsKey(t.charAt(i))){
// if(map.get(t.charAt(i)) == 1){
// map.remove(t.charAt(i));
// }else{
// map.put(t.charAt(i), (map.get(t.charAt(i)) - 1));
// }
// }else{
// return false;
// }
// }
// return true;
// 方法二：用数组来构造哈希表，字典解法
if(s.length() != t.length()){
return false;
}
int[] arr = new int[26];
for(int i = 0; i < s.length(); i++){
int index = s.charAt(i) - 'a';
arr[index] = arr[index] + 1;
}
for(int i = 0; i < t.length(); i++){
int index = t.charAt(i) - 'a';
if(arr[index] != 0){
arr[index] = arr[index] - 1;
}else{
return false;
}
}
return true;
}
}
两个数组的交集
349
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
// 使用hashset，无序，且不能存储重复数据，符合题目要求
HashSet<Integer> set = new HashSet<>();
HashSet<Integer> record = new HashSet<>();
for(int i = 0; i < nums1.length; i++){
set.add(nums1[i]);
}
for(int i = 0; i < nums2.length; i++){
if(set.remove(nums2[i])){
record.add(nums2[i]);
}
}
return record.stream().mapToInt(x -> x).toArray();
}
}
快乐数
202
class Solution {
public boolean isHappy(int n) {
// 使用hashset，当有重复的数字出现时，说明开始重复，这个数不是快乐数
HashSet<Integer> set = new HashSet();
int sum = 0;
while(true){
while(n != 0){
sum = sum + (n%10)*(n%10);
n = n / 10;
}
if(sum == 1){
return true;
}
if(!set.add(sum)){
return false;
}
n = sum;
sum = 0;
}
}
}
两数之和
1
class Solution {
public int[] twoSum(int[] nums, int target) {
// 方法一：暴力解法
// int[] arr = new int[2];
// for(int i = 0; i < nums.length - 1; i++){
// for(int j = i + 1 ; j < nums.length; j++){
// if(target == (nums[i] + nums[j])){
// return new int[]{i,j};
// }
// }
// }
// return new int[0];
// 方法二：HashMap
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int find = target - nums[i];
if(map.containsKey(find)){
return new int[]{i, map.get(find)};
}else{
map.put(nums[i],i);
}
}
return null;
}
}
四数相加 II
454
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
// 四个数，用哈希表，参考代码随想录
HashMap<Integer,Integer> map = new HashMap<>();
int count = 0;
for(int i : nums1){
for(int j : nums2){
int temp = i + j;
if(map.containsKey(temp)){
map.put(temp, map.get(temp) + 1);
}else{
map.put(temp, 1);
}
}
}
for(int i : nums3){
for(int j : nums4){
int temp = 0- (i + j);
if(map.containsKey(temp)){
count += map.get(temp);
}
}
}
return count;
}
}
赎金信
383
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
// 方法一；hashmap
// HashMap<Character,Integer> map = new HashMap<>();
// char temp;
// for(int i = 0; i < ransomNote.length(); i++){
// temp = ransomNote.charAt(i);
// if(map.containsKey(temp)){
// map.put(temp, map.get(temp) + 1);
// }else{
// map.put(temp, 1);
// }
// }
// for(int i = 0; i < magazine.length(); i++){
// temp = magazine.charAt(i);
// if(map.containsKey(temp)){
// if(map.get(temp) == 1){
// map.remove(temp);
// }else{
// map.put(temp, map.get(temp) - 1);
// }
// }
// }
// if(map.isEmpty()){
// return true;
// }else{
// return false;
// }
// 方法二：数组在哈希法的应用，比起方法一更加节省空间，因为字符串只有小写的英文字母组成
int[] arr = new int[26];
int temp;
for(int i = 0; i < ransomNote.length(); i++){
temp = ransomNote.charAt(i) - 'a';
arr[temp] = arr[temp] + 1;
}
for(int i = 0; i < magazine.length(); i++){
temp = magazine.charAt(i) - 'a';
if(arr[temp] != 0){
arr[temp] = arr[temp] - 1;
}
}
for(int i = 0; i < arr.length; i++){
if(arr[i] != 0){
return false;
}
}
return true;
}
}
三数之和
15
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 如果考虑使用跟四数之和类似的求解方式，由于三元组是在同一个数组中寻找的，且要求不重复的三元组，因此求解会比较复杂
// 题目要求返回的是三元组的具体数值，而不是索引值，因此可以考虑使用双指针
List<List<Integer>> result = new ArrayList<>();
List<Integer> temp = new ArrayList<Integer>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
if(nums[i] > 0){
return result;
}
if(i > 0 && nums[i] == nums[i - 1]){
continue;
}
int left = i + 1;
int right = nums.length - 1;
while(left < right){
if((nums[i] + nums[left] + nums[right]) > 0){
right--;
}else if((nums[i] + nums[left] + nums[right]) < 0){
left++;
}else{
temp.add(nums[i]);
temp.add(nums[left]);
temp.add(nums[right]);
result.add(temp);
temp = new ArrayList<Integer>();
while(left < right && nums[right] == nums[right-1]){
right--;
}
while(left < right && nums[left] == nums[left+1]){
left++;
}
left++;
right--;
}
}
}
return result;
}
}
四数之和
18
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
for(int i=0;i<nums.length-1;i++){
for(int j=0;j<nums.length-1-i;j++){
if(nums[j]>nums[j+1]){
int temp = nums[j+1];
nums[j+1] = nums[j];
nums[j] = temp;
}
}
}
for(int i = 0; i < nums.length; i++){
if (nums[i] > 0 && nums[i] > target) {
return list;
}
if(i > 0 && nums[i] == nums[i - 1]){
continue;
}
for(int j = i + 1; j < nums.length; j++){
if(j > i + 1 && nums[j] == nums[j - 1]){
continue;
}
int left = j + 1;
int right = nums.length - 1;
while(left < right){
long sum = (long)(nums[i] + nums[j] + nums[left] + nums[right]);
if(sum > target){
right--;
}else if(sum < target){
left++;
}else{
list.add(Arrays.asList(nums[i] , nums[j] , nums[left] , nums[right]));
while(left < right && nums[left] == nums[left + 1]){
left++;
}
while(left < right && nums[right] == nums[right - 1]){
right--;
}
left++;
right--;
}
}
}
}
return list;
}
}
字符串：
反转字符串
344
class Solution {
public void reverseString(char[] s) {
// 左右指针
int leftNode = 0;
int rifhtNode = s.length - 1;
char temp;
while(leftNode <= rifhtNode){
temp = s[rifhtNode];
s[rifhtNode] = s[leftNode];
s[leftNode] = temp;
leftNode++;
rifhtNode--;
}
}
}
反转字符串 II
541
class Solution {
public String reverseStr(String s, int k) {
char[] arr = s.toCharArray();
for(int i = 0; i < arr.length; i=i+2*k){
if((i+k)<=arr.length){
reverse(arr,i,i+k-1);
}else{
reverse(arr,i,arr.length-1);
}
}
return new String(arr);
}
public void reverse(char[] arr, int left, int right){
while(left < right){
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}
替换空格
offer 05
class Solution {
public String replaceSpace(String s) {
StringBuffer target = new StringBuffer();
char temp;
for(int i = 0; i < s.length(); i++){
temp = s.charAt(i);
if(temp == ' '){
target.append("%20");
}else{
target.append(temp);
}
}
return new String(target);
}
}
反转字符串中的单词
151
class Solution {
public String reverseWords(String s) {
StringBuffer buffer = new StringBuffer();
int index = 0;
while(s.charAt(index)==' '){
index++;
}
for(;index < s.length();index++){
if(s.charAt(index)!=' '){
buffer.append(s.charAt(index));
}else{
while(index < s.length() && s.charAt(index)==' '){
index++;
}
if(index < s.length()){
buffer.append(' ');
buffer.append(s.charAt(index));
}
}
}
String arr = new String(buffer);
String[] result = arr.split(" ");
int left = 0;
int right = result.length - 1;
while(left < right){
String temp = result[left];
result[left] = result[right];
result[right] = temp;
left++;
right--;
}
StringBuffer buffer1 = new StringBuffer();
for(int a = 0; a < result.length; a++){
buffer1.append(result[a]);
if(a < result.length - 1){
buffer1.append(" ");
}
}
return new String(buffer1);
}
}
左旋转字符串
Offer 58 - II
class Solution {
public String reverseLeftWords(String s, int n) {
// 先整体反转，在根据k进行部分反转
char[] str = s.toCharArray();
reverse(str, 0, str.length - 1);
reverse(str, 0, str.length - 1 - n);
reverse(str, str.length - n, str.length - 1);
return new String(str);
}
public void reverse(char[] str, int start, int end){
while(start < end){
str[start] ^= str[end];
str[end] ^= str[start];
str[start] ^= str[end];
start++;
end--;
}
}
}
找出字符串中第一个匹配项的下标
KMP字符串匹配：在主串中寻找子串的过程，称为模式匹配
KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。
28
class Solution {
public int strStr(String haystack, String needle) {
int[] arr = kmp(needle);
for(int i = 0, j = 0; i < haystack.length(); i++){
while(j > 0 && haystack.charAt(i) != needle.charAt(j)){
j = arr[j - 1];
}
if(haystack.charAt(i) == needle.charAt(j)){
j++;
}
if(j == needle.length()){
return i - j + 1;
}
}
return -1;
}
public int[] kmp(String needle){
int[] next = new int[needle.length()];
for(int i = 1, j = 0; i < next.length; i++){
while(j > 0 && needle.charAt(i) != needle.charAt(j)){
j = next[j - 1];
}
if(needle.charAt(i) == needle.charAt(j)){
j++;
}
next[i] = j;
}
return next;
}
}
重复的子字符串
459
class Solution {
public boolean repeatedSubstringPattern(String s) {
int[] next = new int[s.length()];
next[0] = 0;
for(int i = 1, j = 0; i < s.length(); i++){
while(j > 0 && s.charAt(i) != s.charAt(j)){
j = next[j - 1];
}
if(s.charAt(i) == s.charAt(j)){
j++;
}
next[i] = j;
}
if(next[next.length - 1] != 0 && next.length%(next.length - next[next.length - 1]) == 0){
return true;
}
return false;
}
}
栈和队列：容器适配器，不提供迭代器
232、用栈实现队列
class MyQueue {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public MyQueue() {
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int peek() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
public boolean empty() {
if(stack1.isEmpty() && stack2.isEmpty()){
return true;
}
return false;
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
225、用队列实现栈
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;//用来备份栈的数据（除栈顶）
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
// 方法一：较为繁琐
// public void push(int x) {
// while(queue1.size() > 0){
// queue2.offer(queue1.poll());
// }
// while(queue2.size() > 0){
// queue1.offer(queue2.poll());
// }
// queue1.offer(x);
// }
// public int pop() {
// while(queue1.size() > 1){
// queue2.offer(queue1.poll());
// }
// int temp = queue1.poll();
// while(queue2.size() > 0){
// queue1.offer(queue2.poll());
// }
// return temp;
// }
// public int top() {
// while(queue1.size() > 1){
// queue2.offer(queue1.poll());
// }
// int temp = queue1.peek();
// while(queue1.size() > 0){
// queue2.offer(queue1.poll());
// }
// while(queue2.size() > 0){
// queue1.offer(queue2.poll());
// }
// return temp;
// }
// public boolean empty() {
// return queue1.isEmpty() && queue2.isEmpty();
// }
// 方法二：参考代码随想录
// public void push(int x) {
// queue2.offer(x);
// while(!queue1.isEmpty()){
// queue2.offer(queue1.poll());
// }
// Queue<Integer> temp = new LinkedList<>();
// queue1 = queue2;
// queue2 = temp;
// }
// public int pop() {
// return queue1.poll();
// }
// public int top() {
// return queue1.peek();
// }
// public boolean empty() {
// return queue1.isEmpty() && queue2.isEmpty();
// }
// 方法三：用单队列实现
public void push(int x) {
if(queue1.isEmpty()){
queue1.offer(x);
}else{
int count = queue1.size();
queue1.offer(x);
while(count > 0){
queue1.offer(queue1.poll());
count--;
}
}
}
public int pop() {
return queue1.poll();
}
public int top() {
return queue1.peek();
}
public boolean empty() {
return queue1.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
20、有效的括号
class Solution {
public boolean isValid(String s) {
// 方法一：用字符串
// String s1 = "";
// if(s.length()%2 == 1){
// return false;
// }
// for(int i = 0; i < s.length(); i++){
// if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){
// s1 = s1 + s.charAt(i);
// }else if(s1.length() == 0){
// return false;
// }else if((s.charAt(i) == ']') && (s1.charAt(s1.length()-1) == '[')){
// s1 = s1.substring(0,s1.length() - 1);
// }else if((s.charAt(i) == '}') && (s1.charAt(s1.length()-1) == '{')){
// s1 = s1.substring(0,s1.length() - 1);
// }else if((s.charAt(i) == ')') && (s1.charAt(s1.length()-1) == '(')){
// s1 = s1.substring(0,s1.length() - 1);
// }else{
// return false;
// }
// }
// if(s1.length() == 0){
// return true;
// }else{
// return false;
// }
// 方法二：用栈
Stack<Character> stack = new Stack<>();
char[] arr = s.toCharArray();
for(int i = 0; i < arr.length; i++){
if(arr[i] == '(' || arr[i] == '[' || arr[i] == '{'){
stack.push(arr[i]);
}else if(arr[i] == ')'){
if(stack.isEmpty() || stack.pop() != '('){
return false;
}
}else if(arr[i] == ']'){
if(stack.isEmpty() ||stack.pop() != '['){
return false;
}
}else if(arr[i] == '}'){
if(stack.isEmpty() ||stack.pop() != '{'){
return false;
}
}
}
return stack.isEmpty();
}
}
1047、删除字符串中的所有相邻重复项
class Solution {
public String removeDuplicates(String s) {
// 方法一：用栈
char[] arr = s.toCharArray();
Stack<Character> stack = new Stack<>();
for(int i = 0; i < arr.length; i++){
if(stack.isEmpty()){
stack.push(arr[i]);
}else if(stack.peek() == arr[i]){
stack.pop();
}else{
stack.push(arr[i]);
}
}
String str = "";
while(!stack.isEmpty()){
str = stack.pop() + str;
}
return str;
// // 方法二：双线队列
// char[] arr = s.toCharArray();
// ArrayDeque<Character> arraydeque = new ArrayDeque<>();
// for(int i = 0; i < arr.length; i++){
// if(arraydeque.isEmpty()){
// arraydeque.push(arr[i]);
// }else if(arraydeque.peek() == arr[i]){
// arraydeque.pop();
// }else{
// arraydeque.push(arr[i]);
// }
// }
// String str = "";
// while(!arraydeque.isEmpty()){
// str = arraydeque.pop() + str;
// }
// return str;
}
}
150、逆波兰表达式求值
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < tokens.length; i++){
if(tokens[i].equals("+")){
stack.push(stack.pop() + stack.pop());
}else if(tokens[i].equals("-")){
stack.push(-stack.pop() + stack.pop());
}else if(tokens[i].equals("*")){
stack.push(stack.pop() * stack.pop());
}else if(tokens[i].equals("/")){
int divisor = stack.pop();
int dividend = stack.pop();
int temp = dividend/divisor;
stack.push(temp);
}else{
stack.push(Integer.valueOf(tokens[i]));
}
}
return stack.pop();
}
}
239、滑动窗口最大值
单调队列
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new LinkedList<>();//单调双向队列
int[] result = new int[nums.length - k + 1];
for(int i = 0; i < nums.length; i++){
while(deque.peekFirst() != null && deque.peekFirst() < i - k + 1){
deque.pollFirst();
}
while(deque.peekLast() != null && nums[i] > nums[deque.peekLast()]){
deque.pollLast();
}
deque.offerLast(i);
if(i - k + 1 >= 0 ){
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
}
347、前 K 个高频元素
优先级队列，大顶堆，小顶堆
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int i: nums){
map.put(i, map.getOrDefault(i, 0) + 1);
}
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] m, int[] n){
return m[1] - n[1];
}
});
for(Map.Entry<Integer, Integer> entry: map.entrySet()){
if(pq.size() < k){
pq.add(new int[]{entry.getKey(), entry.getValue()});
}else{
if(pq.peek()[1] < entry.getValue()){
pq.poll();
pq.add(new int[]{entry.getKey(), entry.getValue()});
}
}
}
int[] arr = new int[k];
for(int i = 0; i < arr.length; i++){
arr[i] = pq.poll()[0];
}
return arr;
}
}
二叉树：
种类：满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树
存储方式：链式存储、线式存储（顺序存储）
二叉数遍历：深度优先搜索（前序、中序、后序）：使用递归实现（实际用栈来实现）、迭代法（非递归的方式、栈），广度优先搜索（层序遍历）：用队列
递归三步走写法：1、确定递归函数的参数和返回值。2、确定终止条件。3、确定单层递归的逻辑。
144、二叉树的前序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 方法一：递归法
// public List<Integer> preorderTraversal(TreeNode root) {
// List<Integer> result = new ArrayList<>();
// preorder(root, result);
// return result;
// }
// public void preorder(TreeNode root, List<Integer> result){
// if(root == null){
// return;
// }
// result.add(root.val);
// preorder(root.left, result);
// preorder(root.right, result);
// }
// 方法二：非递归的方法
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
if(cur != null){
result.add(cur.val);
stack.push(cur.right);
stack.push(cur.left);
}else{
continue;
}
}
return result;
}
// 方法三：统一风格的非递归
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
if(stack.peek() != null){
TreeNode cur = stack.pop();
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
stack.push(cur);
stack.push(null);
}else{
stack.pop();
TreeNode cur = stack.pop();
result.add(cur.val);
}
}
return result;
}
}
145、二叉树的后序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 方法一：递归法
// public List<Integer> postorderTraversal(TreeNode root) {
// List<Integer> result = new ArrayList<>();
// postOrder(root, result);
// return result;
// }
// public void postOrder(TreeNode root, List<Integer> result){
// if(root == null){
// return;
// }
// postOrder(root.left, result);
// postOrder(root.right, result);
// result.add(root.val);
// }
// 方法二：非递归
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
result.add(cur.val);
if(cur.left != null){
stack.push(cur.left);
}
if(cur.right != null){
stack.push(cur.right);
}
}
Collections.reverse(result);
return result;
}
// 方法三：统一风格的非递归
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
if(stack.peek() != null){
TreeNode cur = stack.pop();
stack.push(cur);
stack.push(null);
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}else{
stack.pop();
TreeNode cur = stack.pop();
result.add(cur.val);
}
}
return result;
}
}
94、二叉树的中序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 方法一：递归法
// public List<Integer> inorderTraversal(TreeNode root) {
// List<Integer> result = new ArrayList<>();
// infixOrder(root, result);
// return result;
// }
// public void infixOrder(TreeNode root, List<Integer> result){
// if(root == null){
// return;
// }
// infixOrder(root.left, result);
// result.add(root.val);
// infixOrder(root.right, result);
// }
// 方法二：非递归
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
}
return result;
}
// 方法三：统一风格的非递归
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
if(stack.peek() != null){
TreeNode cur = stack.pop();
if(cur.right != null){
stack.push(cur.right);
}
stack.push(cur);
stack.push(null);
if(cur.left != null){
stack.push(cur.left);
}
}else{
stack.pop();
TreeNode cur = stack.pop();
result.add(cur.val);
}
}
return result;
}
}
广度优先搜索：层序遍历
102、二叉树的层序遍历
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<>();
int size = 0;
if(root != null){
queue.offer(root);
size = 1;
}
while(!queue.isEmpty()){
List<Integer> list1 = new ArrayList<>();
while(size > 0){
TreeNode cur = queue.poll();
list1.add(cur.val);
if(cur.left != null){
queue.offer(cur.left);
}
if(cur.right != null){
queue.offer(cur.right);
}
size--;
}
size = queue.size();
list.add(list1);
}
return list;
}
}
107、二叉树的层序遍历 II
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
int size = queue.size();
if(root != null){
queue.offer(root);
size = queue.size();
}
while(!queue.isEmpty()){
List<Integer> list1 = new ArrayList<>();
while(size > 0){
TreeNode cur = queue.poll();
list1.add(cur.val);
if(cur.left != null){
queue.offer(cur.left);
}
if(cur.right != null){
queue.offer(cur.right);
}
size--;
}
size = queue.size();
list.add(list1);
}
Collections.reverse(list);
return list;
}
226、翻转二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 方法一：层次遍历，广度优先算法
// public TreeNode invertTree(TreeNode root) {
// Queue<TreeNode> queue = new LinkedList<>();
// int size = queue.size();
// if(root != null){
// queue.offer(root);
// size = queue.size();
// }
// while(!queue.isEmpty()){
// while(size > 0){
// TreeNode cur = queue.poll();
// if(cur.left != null){
// queue.offer(cur.left);
// }
// if(cur.right != null){
// queue.offer(cur.right);
// }
// swapChildren(cur);
// size--;
// }
// size = queue.size();
// }
// return root;
// }
// public void swapChildren(TreeNode cur){
// TreeNode temp = cur.left;
// cur.left = cur.right;
// cur.right = temp;
// }
// 方法二：递归法，后序
// public TreeNode invertTree(TreeNode root) {
// if(root == null){
// return root;
// }
// invertTree(root.left);
// invertTree(root.right);
// swapChildren(root);
// return root;
// }
// public void swapChildren(TreeNode cur){
// TreeNode temp = cur.left;
// cur.left = cur.right;
// cur.right = temp;
// }
// 方法三：迭代法：中序，统一风格
public TreeNode invertTree(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
if(stack.peek() != null){
TreeNode cur = stack.pop();
if(cur.right != null)
stack.push(cur.right);
if(cur.left != null)
stack.push(cur.left);
stack.push(cur);
stack.push(null);
swapChildren(cur);
}else{
stack.pop();
stack.pop();
}
}
return root;
}
public void swapChildren(TreeNode cur){
TreeNode temp = cur.left;
cur.left = cur.right;
cur.right = temp;
}
}
590、N 叉树的后序遍历
101、对称二叉树
class Solution {
// 方法一：递归，后序遍历
// public boolean isSymmetric(TreeNode root) {
// return compare(root.left, root.right);
// }
// public boolean compare(TreeNode left, TreeNode right){
// if(left == null && right != null){
// return false;
// }
// if(right == null && left != null){
// return false;
// }
// if(right == null && left == null){
// return true;
// }
// if(left.val != right.val){
// return false;
// }
// boolean resultLeft = compare(left.left, right.right);
// boolean resultRight = compare(left.right, right.left);
// return resultLeft && resultRight;
// }
// 方法二：迭代
public boolean isSymmetric(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
deque.offerFirst(root.left);
deque.offerLast(root.right);
while(!deque.isEmpty()){
TreeNode left = deque.pollFirst();
TreeNode right = deque.pollLast();
if(left == null && right == null){
continue;
}
if(left == null && right != null){
return false;
}
if(left != null && right == null){
return false;
}
if(left.val != right.val){
return false;
}
deque.offerFirst(left.left);
deque.offerFirst(left.right);
deque.offerLast(right.right);
deque.offerLast(right.left);
}
return true;
}
}
589、N 叉树的前序遍历
class Solution {
// 方法一：递归
// public List<Integer> resultList = new ArrayList<>();
// public List<Integer> preorder(Node root) {
// if(root == null){
// return resultList;
// }
// resultList.add(root.val);
// for(Node node : root.children){
// preorder(node);
// }
// return resultList;
// }
// 方法二：迭代，统一风格
public List<Integer> preorder(Node root) {
List<Integer> resultList = new ArrayList<>();
Stack<Node> stack = new Stack<>();
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
if(stack.peek() != null){
Node cur = stack.pop();
List<Node> list = new ArrayList<>();
list = cur.children;
for(int i = list.size() - 1; i >= 0; i--){
if(list.get(i) != null){
stack.push(list.get(i));
}
}
stack.push(cur);
stack.push(null);
}else{
stack.pop();
Node cur = stack.pop();
resultList.add(cur.val);
}
}
return resultList;
}
}
559、N 叉树的最大深度
class Solution {
public int maxDepth(Node root) {
// 非递归
// if(root == null){
// return 0;
// }
// Queue<Node> queue = new LinkedList<>();
// queue.offer(root);
// int size = 1;
// int count = 0;
// while(!queue.isEmpty()){
// count++;
// while(size > 0 ){
// Node temp = queue.poll();
// for(Node k : temp.children){
// if(k != null){
// queue.offer(k);
// }
// }
// size--;
// }
// size = queue.size();
// }
// return count;
// 递归法：后序遍历
return find(root);
}
public int find(Node root){
if(root == null){
return 0;
}
int depth = 0;
if(root.children != null){
for(Node k : root.children){
depth = Math.max(find(k),depth);
}
}
return depth + 1;
}
}
117、填充每个节点的下一个右侧节点指针 II
同上！
104、二叉树的最大深度
![]
(https://img2022.cnblogs.com/blog/3018498/202211/3018498-20221121204402960-1570599807.png)
class Solution {
public int maxDepth(TreeNode root) {
// 非递归
// if(root == null){
// return 0;
// }
// Queue<TreeNode> queue = new LinkedList<>();
// queue.offer(root);
// int count = 0;
// int size = 1;
// while(!queue.isEmpty()){
// count++;
// while(size > 0){
// TreeNode temp = queue.poll();
// if(temp.left != null){queue.offer(temp.left);}
// if(temp.right != null){queue.offer(temp.right);}
// size--;
// }
// size = queue.size();
// }
// return count;
// 递归
return find(root, 0);
}
public int find(TreeNode root, int depth){
if(root == null){
return depth;
}
int left = find(root.left, depth);
int right = find(root.right, depth);
depth = Math.max(left,right) + 1;
return depth;
}
}
111、二叉树的最小深度
class Solution {
public int minDepth(TreeNode root) {
// 非递归，层序遍历
// if(root == null){
// return 0;
// }
// Queue<TreeNode> queue = new LinkedList<>();
// queue.offer(root);
// int size = 1;
// int count = 0;
// while(!queue.isEmpty()){
// count++;
// while(size > 0){
// TreeNode temp = queue.poll();
// if(temp.left != null){
// queue.offer(temp.left);
// }
// if(temp.right != null){
// queue.offer(temp.right);
// }
// if(temp.left == null && temp.right == null){
// return count;
// }
// size--;
// }
// size = queue.size();
// }
// return count;
// 递归
if(root == null){
return 0;
}
int left = minDepth(root.left);
int right = minDepth(root.right);
if(root.left == null && root.right != null){
return 1 + right;
}
if(root.right == null && root.left != null){
return 1 + left;
}
return Math.min(left, right) + 1;
}
}
222、完全二叉树的节点个数
class Solution {
public int count = 0;
public int countNodes(TreeNode root) {
if(root == null){
return count;
}
count++;
countNodes(root.left);
countNodes(root.right);
return count;
}
}
110、平衡二叉树
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
return check(root) != -1;
}
public int check(TreeNode root){
if(root == null){
return 0;
}
int left = check(root.left);
if(left == -1){return -1;}
int right = check(root.right);
if(right == -1){return -1;}
int result;
if(Math.abs(left - right) > 1){
return -1;
}else{
result = 1 + Math.max(left, right);
}
return result;
}
}
257、二叉树的所有路径
class Solution {
public List<String> result = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
if(root == null){
return result;
}
List<Integer> list = new ArrayList<>();
TreePaths(root, list);
return result;
}
public void TreePaths(TreeNode root, List<Integer> list){
list.add(root.val);
if(root.left == null && root.right == null){
StringBuffer buf = new StringBuffer();
for(int i = 0; i < list.size() - 1; i++){
buf.append(list.get(i)).append("->");
}
buf.append(list.get(list.size() - 1));
result.add(new String(buf));
return;
}
if(root.left != null){
TreePaths(root.left,list);
list.remove(list.size() - 1);
}
if(root.right != null){
TreePaths(root.right,list);
list.remove(list.size() - 1);
}
}
}
404、左叶子之和
class Solution {
public int result = 0;
public int sumOfLeftLeaves(TreeNode root) {
// 层序遍历
// int result = 0;
// if(root == null){
// return result;
// }
// Queue<TreeNode> queue = new LinkedList<>();
// queue.offer(root);
// int size = 1;
// while(!queue.isEmpty()){
// while(size > 0){
// TreeNode temp = queue.poll();
// if(temp.left != null){
// queue.offer(temp.left);
// if(temp.left.left == null && temp.left.right == null){
// result += temp.left.val;
// }
// }
// if(temp.right != null){
// queue.offer(temp.right);
// }
// size--;
// }
// size = queue.size();
// }
// return result;
// 前序遍历
if(root == null){
return result;
}
sumOfLeftLeaves(root.left);
if(root.left != null && root.left.left == null && root.left.right == null){
result += root.left.val;
}
sumOfLeftLeaves(root.right);
return result;
}
}
513找树左下角的值
class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
int size = queue.size();
if(root != null){
queue.offer(root);
size = queue.size();
}
int find = 0;
while(!queue.isEmpty()){
Queue<TreeNode> result = new LinkedList<>();
while(size > 0){
TreeNode cur = queue.poll();
result.offer(cur);
if(cur.left != null){
queue.offer(cur.left);
}
if(cur.right != null){
queue.offer(cur.right);
}
size--;
}
size = queue.size();
find = result.peek().val;
}
return find;
}
}
112、路径总和
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null){
return false;
}
List<Integer> result = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
pathSum(root, result, temp);
return result.contains(targetSum);
}
public void pathSum(TreeNode root, List<Integer> result, List<Integer> temp){
temp.add(root.val);
if(root.left == null && root.right == null){
int sum = 0;
for(int i = 0; i < temp.size(); i++){
sum += temp.get(i);
}
result.add(sum);
}
if(root.left != null){
pathSum(root.left, result, temp);
temp.remove(temp.size() - 1);
}
if(root.right != null){
pathSum(root.right, result, temp);
temp.remove(temp.size() - 1);
}
}
}
113、路径总和 II
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
if(root == null){
return result;
}
find(root, result, temp, targetSum);
return result;
}
public void find(TreeNode root, List<List<Integer>> result, List<Integer> temp, int targetSum){
temp.add(root.val);
if(root.left == null && root.right == null){
int sum = 0;
for(int i = 0; i < temp.size(); i++){
sum += temp.get(i);
}
if(sum == targetSum){
result.add(new ArrayList<Integer>(temp));
}
}
if(root.left != null){
find(root.left, result, temp, targetSum);
temp.remove(temp.size() - 1);
}
if(root.right != null){
find(root.right, result, temp, targetSum);
temp.remove(temp.size() - 1);
}
}
}
106、从中序与后序遍历序列构造二叉树
class Solution {
public Map<Integer, Integer> map;
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
for(int i = 0; i < inorder.length; i++){
map.put(inorder[i], i);
}
return find(inorder, 0, inorder.length, postorder, 0, postorder.length);
}
public TreeNode find(int[] inorder, int inbegin, int inend, int[] postorder, int pobegin, int poend){
if(inbegin >= inend || pobegin >= poend){
return null;
}
int temp = map.get(postorder[poend - 1]);
int len = temp - inbegin;
TreeNode root = new TreeNode(inorder[temp]);
root.left = find(inorder, inbegin, temp, postorder, pobegin, pobegin + len);
root.right = find(inorder, temp + 1, inend, postorder, pobegin + len, poend - 1);
return root;
}
}
105、从前序与中序遍历序列构造二叉树
class Solution {
public Map<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>();
for(int i = 0; i < inorder.length; i++){
map.put(inorder[i], i);
}
return find(inorder, 0, inorder.length, preorder, 0, preorder.length);
}
public TreeNode find(int[] inorder, int inbegin, int inend, int[] preorder, int prbegin, int prend){
if(inbegin >= inend || prbegin >= prend){
return null;
}
int temp = map.get(preorder[prbegin]);
int len = temp - inbegin;
TreeNode root = new TreeNode(inorder[temp]);
root.left = find(inorder, inbegin, temp, preorder, prbegin + 1, prbegin + len + 1);
root.right = find(inorder, temp + 1, inend, preorder, prbegin + len + 1, prend);
return root;
}
}
654、最大二叉树
class Solution {
public Map<Integer, Integer> map;
public TreeNode constructMaximumBinaryTree(int[] nums) {
map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
map.put(nums[i], i);
}
return binaryTree(nums, 0, nums.length - 1);
}
public TreeNode binaryTree(int[] nums, int left, int right){
int max = -1;
for(int i = left; i <= right; i++){
max = max > nums[i] ? max : nums[i];
}
if(max == -1){
return null;
}else{
int index = map.get(max);
TreeNode root = new TreeNode(max);
root.left = binaryTree(nums, left, index - 1);
root.right = binaryTree(nums, index + 1, right);
return root;
}
}
}
617、合并二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode result = new TreeNode();
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
// 前序遍历，递归
// if(root1 == null){
// return root2;
// }
// if(root2 == null){
// return root1;
// }
// root1.val += root2.val;
// root1.left = mergeTrees(root1.left,root2.left);
// root1.right = mergeTrees(root1.right,root2.right);
// return root1;
// 使用栈迭代
// if(root1 == null){
// return root2;
// }
// if(root2 == null){
// return root1;
// }
// Stack<TreeNode> stack = new Stack<>();
// stack.push(root1);
// stack.push(root2);
// while(!stack.isEmpty()){
// TreeNode cur2 = stack.pop();
// TreeNode cur1 = stack.pop();
// cur1.val += cur2.val;
// if(cur1.left != null && cur2.left != null){
// stack.push(cur1.left);
// stack.push(cur2.left);
// }else{
// if(cur1.left == null){
// cur1.left = cur2.left;
// }
// }
// if(cur1.right != null && cur2.right != null){
// stack.push(cur1.right);
// stack.push(cur2.right);
// }else{
// if(cur1.right == null){
// cur1.right = cur2.right;
// }
// }
// }
// return root1;
// 使用队列迭代
if(root1 == null){
return root2;
}
if(root2 == null){
return root1;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root1);
queue.offer(root2);
while(!queue.isEmpty()){
TreeNode cur1 = queue.poll();
TreeNode cur2 = queue.poll();
cur1.val += cur2.val;
if(cur1.left != null && cur2.left != null){
queue.offer(cur1.left);
queue.offer(cur2.left);
}else{
if(cur1.left == null){
cur1.left = cur2.left;
}
}
if(cur1.right != null && cur2.right != null){
queue.offer(cur1.right);
queue.offer(cur2.right);
}else{
if(cur1.right == null){
cur1.right = cur2.right;
}
}
}
return root1;
}
}
700、二叉搜索树中的搜索
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
// 递归
// if(root == null){
// return null;
// }
// TreeNode result = new TreeNode();
// if(root.val == val){
// result = root;
// }else if(root.val < val){
// result = searchBST(root.right,val);
// }else{
// result = searchBST(root.left,val);
// }
// return result;
// 迭代
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
if(cur.val == val){
return cur;
}else if(cur.val < val){
if(cur.right == null){
return null;
}
stack.push(cur.right);
}else{
if(cur.left == null){
return null;
}
stack.push(cur.left);
}
}
return null;
}
}
98、验证二叉搜索树
class Solution {
public boolean isValidBST(TreeNode root) {
// 需要从底层往上传递判断结果，所以采用后序遍历
if(root == null){
return true;
}
return isValidBST1(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
public boolean isValidBST1(TreeNode root,long left, long right){
if(root == null){
return true;
}
if(root != null && (root.val <= left || root.val >= right)){
return false;
}
boolean leftFlag = isValidBST1(root.left,left,root.val);
boolean rightFlag = isValidBST1(root.right,root.val,right);
if(leftFlag == false || rightFlag == false){
return false;
}
return leftFlag && rightFlag;
}
}
530、二叉搜索树的最小绝对差
class Solution {
public int result = Integer.MAX_VALUE;
TreeNode pre;
public int getMinimumDifference(TreeNode root) {
if(root == null){
return result;
}
traversal(root);
return result;
}
public void traversal(TreeNode cur){
if(cur == null){
return;
}
traversal(cur.left);
if(pre != null){
result = Math.min(result, cur.val - pre.val);
}
pre = cur;
traversal(cur.right);
}
}
501、二叉搜索树中的众数
class Solution {
public int Maxcount;
public int count;
public List<Integer> result;
public TreeNode pre;
public int[] findMode(TreeNode root) {
Maxcount = 0;
count = 0;
result = new ArrayList<>();
pre = null;
traversal(root);
int[] find = new int[result.size()];
for(int i = 0; i < result.size(); i++){
find[i] = result.get(i);
}
return find;
}
public void traversal(TreeNode root){
if(root == null){
return;
}
traversal(root.left);
if(pre == null || root.val != pre.val){
count = 1;
}else{
count++;
}
pre = root;
if(count > Maxcount){
result.clear();
result.add(root.val);
Maxcount = count;
}else if(count == Maxcount){
result.add(root.val);
}
traversal(root.right);
}
}
236、二叉树的最近公共祖先
class Solution {
public TreeNode result = null;
// public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// // 1、后序遍历，从下往上传递，从遇到p或q开始，往上传递true,当某个节点也叶子节点都为true时，找到最近工祖先
// // 递归
// postOrder(root,p.val,q.val);
// return result;
// }
// public boolean postOrder(TreeNode root, int p, int q){
// if(root == null){
// return false;
// }
// boolean leftFlag = postOrder(root.left,p,q);
// boolean rightFlag = postOrder(root.right,p,q);
// if(leftFlag && rightFlag){
// result = root;
// return true;
// }
// if((root.val == q || root.val == p) && (leftFlag || rightFlag)){
// result = root;
// return true;
// }
// if(root.val == q || root.val == p){
// return true;
// }
// if(leftFlag || rightFlag){
// return true;
// }
// return false;
// }
}
235、二叉搜索树的最近公共祖先
class Solution {
public TreeNode result = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int min = p.val < q.val ? p.val : q.val;
int max = p.val > q.val ? p.val : q.val;
find(root,min,max);
return result;
}
public void find(TreeNode root, int pval, int qval){
if(root == null){
return;
}
if(root.val >= pval && root.val <= qval){
result = root;
return;
}
find(root.left,pval,qval);
find(root.right,pval,qval);
}
}
701、二叉搜索树中的插入操作
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null){
return new TreeNode(val);
}
TreeNode result = root;
travesal(root,val);
return result;
}
public void travesal(TreeNode root, int val){
if(root == null){
return;
}
if(root.val < val){
if(root.right == null){
root.right = new TreeNode(val);
return;
}else{
travesal(root.right,val);
}
}else{
if(root.val > val && root.left == null){
root.left = new TreeNode(val);
return;
}else{
travesal(root.left,val);
}
}
}
}
450、删除二叉搜索树中的节点
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
root = delete(root,key);
return root;
}
public TreeNode delete(TreeNode root,int key){
if(root == null){
return null;
}
if(root.val < key){
root.right = delete(root.right,key);
}else if(root.val > key){
root.left = delete(root.left,key);
}else{
if(root.left == null)
return root.right;
if(root.right == null)
return root.left;
TreeNode cur = root.right;
TreeNode temp = root.right;
while(temp.left != null){
temp = temp.left;
}
temp.left = root.left;
return cur;
}
return root;
}
}
669、修剪二叉搜索树
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root == null){
return null;
}
if(root.val < low){
return trimBST(root.right,low,high);
}
if(root.val > high){
return trimBST(root.left,low,high);
}
root.left = trimBST(root.left,low,high);
root.right = trimBST(root.right,low,high);
return root;
}
}
108、将有序数组转换为二叉搜索树
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return travesal(nums,0,nums.length - 1);
}
public TreeNode travesal(int[] nums, int left, int right){
if(left > right){
return null;
}
int mid = left + (right - left)/2;
TreeNode result = new TreeNode(nums[mid]);
result.left = travesal(nums,left,mid - 1);
result.right = travesal(nums,mid + 1, right);
return result;
}
}
538、把二叉搜索树转换为累加树
class Solution {
public int sum = 0;
public TreeNode convertBST(TreeNode root) {
if(root == null){
return null;
}
convertBST(root.right);
root.val += sum;
sum = root.val;
convertBST(root.left);
return root;
}
}
回溯算法
回溯的本质是穷举，所以不是高效的算法
回溯法，一般可以解决如下几种问题：
组合问题：N个数里面按一定规则找出k个数的集合
注意区分一个集合取组合和多个集合取组合的细节。
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等
需要注意问题是有一个解还是多个解，一个解的需要返回值，一旦找到解就逐级返回，多个解的不需要返回值
因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历
77、组合
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
int index = 1;
travesal(n,k,index);
return result;
}
public void travesal(int n, int k, int index){
// 终止条件，得到k个数的组合
if(temp.size() == k){
result.add(new ArrayList<>(temp));
return;
}
for (int i = index; i <= n - (k - temp.size()) + 1; i++) {
temp.add(i);
travesal(n,k,i+1);//递归
temp.remove(temp.size() - 1);//回溯
}
}
}
216、组合总和 III
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<>();
public int sum;
public List<List<Integer>> combinationSum3(int k, int n) {
sum = 0;
find(k,1,n);
return result;
}
public void find(int k, int left, int right){
if(temp.size() == k){
if(sum == right){
result.add(new ArrayList<>(temp));
}
return;
}
for(int i = left; i <= 9 - (k - temp.size()) + 1; i++){
if(sum > right){
continue;
}
temp.add(i);
sum += i;
find(k,i+1,right);
sum -= temp.get(temp.size() - 1);
temp.remove(temp.size() - 1);
}
}
}
17、电话号码的字母组合
class Solution {
public List<String> result = new ArrayList<String>();
public StringBuffer str = new StringBuffer();
public List<String> letterCombinations(String digits) {
// 边界条件
if(digits == null || digits.length() == 0){
return result;
}
char[] digitsArr = digits.toCharArray();
// 映射关系
String[] find = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
int index = 0;
letterCombinationsHelper(digitsArr, find, index);
return result;
}
public void letterCombinationsHelper(char[] digitsArr, String[] find, int index){
if(index == digitsArr.length){
result.add(new String(str));
return;
}
// 第index个数字对应的字母
String strTemp = find[digitsArr[index] - '0'];
for(int i = 0; i < strTemp.length(); i++){
str.append(strTemp.charAt(i));//加入第Index个数字对应的字母的第i个
letterCombinationsHelper(digitsArr,find,index+1);
str.deleteCharAt(str.length() - 1);
}
}
}
39、组合总和
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int sum = 0;
int index = 0;
Arrays.sort(candidates);
combinationSumHelper(candidates,index,sum,target);
return result;
}
public void combinationSumHelper(int[] candidates, int index, int sum,int target){
if(sum >= target){
if(sum == target){
result.add(new ArrayList<Integer>(temp));
}
return;
}
for(int i = index; i < candidates.length; i++){
sum += candidates[i];
temp.add(candidates[i]);
combinationSumHelper(candidates,i,sum,target);
temp.remove(temp.size() - 1);
sum -= candidates[i];
}
}
}
40、 组合总和 II
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
int sum = 0;
int index = 0;
Arrays.sort(candidates);
combinationSumHelper(candidates, target, index, sum);
return result;
}
public void combinationSumHelper(int[] candidates, int target, int index, int sum){
if(sum >= target){
if(sum == target){
result.add(new ArrayList<>(temp));
}
return;
}
// 每个数字在每个组合中只能使用一次
for(int i = index; i < candidates.length; i++){
// 去重逻辑，同层剪枝，同枝可取
if(i > 0 &&i > index && candidates[i] == candidates[i - 1]){
continue;
}
temp.add(candidates[i]);
sum += candidates[i];
combinationSumHelper(candidates, target, i + 1, sum);
temp.remove(temp.size() - 1);
sum -= candidates[i];
}
}
}
131、分割回文串
class Solution {
public List<List<String>> result = new ArrayList<List<String>>();
public List<String> temp = new ArrayList<String>();
public List<List<String>> partition(String s) {
int index = 0;
partitionHelper(s, index);
return result;
}
public void partitionHelper(String s, int index){
if(index == s.length()){
result.add(new ArrayList<>(temp));
return;
}
for(int i = index; i < s.length(); i++){
String s1 = s.substring(index, i + 1);
if(!check(s1,0,s1.length() - 1)){
continue;//字符子串不回文的话直接跳过该次分割方案
}
temp.add(s1);
partitionHelper(s,i+1);
temp.remove(temp.size() - 1);
}
}
// 判断是否回文
public boolean check(String s1, int left, int right){
while(left < right){
if(s1.charAt(left) == s1.charAt(right)){
left++;
right--;
}else{
return false;
}
}
return true;
}
}
93、复原 IP 地址
class Solution {
public List<String> result = new ArrayList<>();
public List<String> temp = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
find(0,s,s.length());
return result;
}
public void find(int index, String s, int length){
if(index == length){
if(temp.size() == 4){
StringBuffer buf = new StringBuffer();
for(int i = 0; i < 3; i++){
buf.append(temp.get(i)).append(".");
}
buf.append(temp.get(3));
result.add(new String(buf));
}
return;
}
for(int i = index; i < length; i++){
int num = Integer.parseInt(s.substring(index,i+1));
if(num > 255){
break;
}
if(s.charAt(index) == '0'){
temp.add(s.substring(index,i+1));
find(i+1,s,length);
temp.remove(temp.size() - 1);
break;
}
temp.add(s.substring(index,i+1));
find(i+1,s,length);
temp.remove(temp.size() - 1);
}
}
}
78、子集
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> subsets(int[] nums) {
subsetsHandler(nums, 0);
return result;
}
public void subsetsHandler(int[] nums, int index){
if(index == nums.length){
result.add(new ArrayList<>(temp));
return;
}
result.add(new ArrayList<>(temp));
for(int i = index; i < nums.length; i++){
temp.add(nums[i]);
subsetsHandler(nums,i+1);
temp.remove(temp.size() - 1);
}
}
}
90、子集 II
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
subsetsWithDupHandler(nums, 0);
return result;
}
public void subsetsWithDupHandler(int[] nums, int index){
if(index == nums.length){
result.add(new ArrayList<>(temp));
return;
}
result.add(new ArrayList<>(temp));
for(int i = index; i < nums.length; i++){
// 不能 包含重复的子集
if(i > 0 &&i > index && nums[i] == nums[i - 1]){
continue;
}
temp.add(nums[i]);
subsetsWithDupHandler(nums, i + 1);
temp.remove(temp.size() - 1);
}
}
}
491、递增子序列
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> findSubsequences(int[] nums) {
// 递增子序列中 至少有两个元素
findSubsequencesHandler(nums, 0);
return result;
}
public void findSubsequencesHandler(int[] nums, int index){
if(temp.size() > 1){
result.add(new ArrayList<>(temp));
}
int[] used = new int[201];
for(int i = index; i < nums.length; i++){
if(temp.size() != 0 && nums[i] < temp.get(temp.size() - 1) || (used[nums[i] + 100] == 1)){
continue;
}
used[nums[i] + 100] = 1;
temp.add(nums[i]);
findSubsequencesHandler(nums, i + 1);
temp.remove(temp.size() - 1);
}
}
}
46、全排列
class Solution {
public List<List<Integer>> result = new ArrayList<>();
public List<Integer> temp = new ArrayList<>();
public int[] used;
public List<List<Integer>> permute(int[] nums) {
used = new int[nums.length];
find(nums);
return result;
}
public void find(int[] nums){
if(temp.size() == nums.length){
result.add(new ArrayList<Integer>(temp));
return;
}
for(int i = 0; i < nums.length; i++){
if(used[i] == 1){
continue;
}
temp.add(nums[i]);
used[i] = 1;
find(nums);
temp.remove(temp.size()-1);
used[i] = 0;
}
}
}
47、全排列 II
class Solution {
public List<List<Integer>> result = new ArrayList<>();
public List<Integer> temp = new ArrayList<>();
public int[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
used = new int[nums.length];
Arrays.sort(nums);
find(nums);
return result;
}
public void find(int[] nums){
if(temp.size() == nums.length){
result.add(new ArrayList<Integer>(temp));
return;
}
for(int i = 0; i < nums.length; i++){
if(used[i] == 1){
continue;
}
if(i > 0 && nums[i] == nums[i - 1] && used[i-1] != 1){
continue;
}
temp.add(nums[i]);
used[i] = 1;
find(nums);
temp.remove(temp.size()-1);
used[i] = 0;
}
}
}
332、重新安排行程
//基本参考代码随想录
class Solution {
public LinkedList<String> result;
public LinkedList<String> path = new LinkedList<String>();
public List<String> findItinerary(List<List<String>> tickets) {
Collections.sort(tickets,(a,b)->a.get(1).compareTo(b.get(1)));//字典排序
path.add("JFK");
int[] used = new int[tickets.size()];
findItineraryHanlder(tickets, used);
return result;
}
public boolean findItineraryHanlder(List<List<String>> tickets, int[] used){
if(path.size() == tickets.size() + 1){
result = new LinkedList<String>(path);
return true;
}
for(int i = 0; i < tickets.size(); i++){
if(used[i] != 1 && tickets.get(i).get(0).equals(path.getLast())){
path.add(tickets.get(i).get(1));
used[i] = 1;
if(findItineraryHanlder(tickets,used)){
return true;
}
path.removeLast();
used[i] = 0;
}
}
return false;
}
}
51、N 皇后
class Solution {
public List<List<String>> result = new ArrayList<List<String>>();
public int[][] arr;
public List<List<String>> solveNQueens(int n) {
arr = new int[n][n];
find(n,0);
return result;
}
public void find(int n, int count){
if(count == n){
List<String> temp = new ArrayList<>();
for(int i = 0; i < n; i++){
String str = "";
for(int j= 0; j < n; j++){
if(arr[i][j] == 1){
str = str + "Q";
}else{
str = str + ".";
}
}
temp.add(str);
}
result.add(new ArrayList<>(temp));
return;
}
for(int i = 0; i < n; i++){
if(check(i,n,count)){
arr[count][i] = 1;
find(n,count+1);
arr[count][i] = 0;
}
}
}
public boolean check(int index,int n,int count){
for(int j = count - 1; j >= 0; j--){
if(arr[j][index] == 1){
return false;
}
}
for(int j = count - 1, index1 = index - 1; j >= 0 &&index1 >= 0; j-- , index1--){
if(arr[j][index1]==1){
return false;
}
}
for(int j = count - 1, index2 = index + 1; j >= 0 && index2<n; j-- ,index2++){
if(arr[j][index2]==1){
return false;
}
}
return true;
}
}
37、解数独
class Solution {
public void solveSudoku(char[][] board) {
solveSudokuHander(board);
}
public boolean solveSudokuHander(char[][] board){
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
if(board[i][j] != '.'){
continue;
}
for(char k = '1'; k <= '9'; k++){
if(judge(board,i,j,k)){
board[i][j] = k;
if(solveSudokuHander(board)){
return true;
}
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
public boolean judge(char[][] board, int i, int j, char k){
for(int m = 0; m < 9; m++){
if(board[i][m]==k){
return false;
}
}
for(int n = 0; n < 9; n++){
if(board[n][j]==k){
return false;
}
}
int startRow = (i/3)*3;
int startCol = (j/3)*3;
for(int m = startRow; m < startRow+3; m++){
for(int n = startCol; n < startCol+3; n++){
if(board[m][n]==k){
return false;
}
}
}
return true;
}
}
相关文章
- 暂无相关文章
用户点评