刷题记录
数组问题
最长无重复子数组
给定一个数组arr,返回arr的最长无重复元素子数组的长度,无重复指的是所有数字都不相同。子数组是连续的,比如[1,3,5,7,9]的子数组有[1,3],[3,5,7]等等,但是[1,3,7]不是子数组
输入:
[1,2,3,1,2,3,2,2]
返回值:
3
复制
说明:
最长子数组为[1,2,3]
方法一:
public class Solution {
/**
*
* @param arr int整型一维数组 the array
* @return int整型
*/
public int maxLength (int[] arr) {
if(arr.length <= 1) {
return arr.length;
}
// 无重复的起点
int a = 0;
// 当前无重复的最大长度
int max = 1;
// 1,2,3,1,4
for(int b = 1; b < arr.length;b++) {
// 寻找[a, b-1]是否存在于arr[b]相等的数, 如果存在则要更新a的值
for(int i = b-1; i >= a; i--) {
if(arr[i] == arr[b]) {
a = i + 1;
break;
}
}
max = Math.max(max, b - a + 1);
}
return max;
}
}
方法二:
public class Solution {
/**
*
* @param arr int整型一维数组 the array
* @return int整型
*/
public int maxLength (int[] arr) {
if(arr.length <= 1) {
return arr.length;
}
// 无重复的起点
int a = 0;
// 当前无重复的最大长度
int max = 0;
// 使用一个Map来保存已经遍历过的元素
Map<Integer, Integer> map = new HashMap();
// 1,2,3,1,4
for(int b = 0; b < arr.length;b++) {
if(map.containsKey(arr[b])) {
// 每次的取值都要大于等于a, 防止a往前走
a = Math.max(a, map.get(arr[b]) + 1);
}
map.put(arr[b], b);
max = Math.max(max, b - a + 1);
}
return max;
}
}
方法三:
public class Solution {
/**
*
* @param arr int整型一维数组 the array
* @return int整型
*/
public int maxLength (int[] arr) {
if(arr.length <= 1) {
return arr.length;
}
int max = 0;
// 使用一个队列来保存当前无重复的数据
LinkedList<Integer> queue = new LinkedList();
for(int i = 0; i < arr.length; i++) {
// 遇到重复元素时,从头部一直出栈,知道无重复元素
while(queue.contains(arr[i])) {
queue.removeFirst();
}
queue.addLast(arr[i]);
max = Math.max(max, queue.size());
}
return max;
}
}
子数组的最大累加和问题
给定一个数组arr,返回子数组的最大累加和
例如,arr = [1, -2, 3, 5, -2, 6, -1],所有子数组中,[3, 5, -2, 6]可以累加出最大的和12,所以返回12.
题目保证没有全为负数的数据
[要求]
时间复杂度为O(n),空间复杂度为O(1)
输入:
[1, -2, 3, 5, -2, 6, -1]
返回值:
12
方法一:空间复杂度为O(n)
public class Solution {
/**
*
* 状态转移方程如下
* dp[0] = arr[0];
* dp[i - 1] > 0 ==> dp[i] = dp[i - 1] + arr[i];
* dp[i - 1] <= 0 ==> dp[i] = arr[i];
*/
public int maxsumofSubarray (int[] arr) {
if(arr.length == 0) {
return 0;
}
if(arr.length == 1) {
return arr[0];
}
int[] dp = new int[arr.length];
dp[0] = arr[0];
int max = dp[0];
for(int i = 1; i < arr.length; i++) {
if(dp[i - 1] > 0) {
dp[i] = dp[i - 1] + arr[i];
} else {
dp[i] = arr[i];
}
max = Math.max(max, dp[i]);
}
return max;
}
}
方法二:空间复杂度为O(1)
public class Solution {
/**
* 状态转移方程如下
* dp[0] = arr[0];
* dp[i - 1] > 0 ==> dp[i] = dp[i - 1] + arr[i];
* dp[i - 1] <= 0 ==> dp[i] = arr[i];
*/
public int maxsumofSubarray (int[] arr) {
if(arr.length == 0) {
return 0;
}
if(arr.length == 1) {
return arr[0];
}
int pre = arr[0];
int max = pre;
for(int i = 1; i < arr.length; i++) {
if(pre > 0) {
pre = pre + arr[i];
} else {
pre = arr[i];
}
max = Math.max(max, pre);
}
return max;
}
}
链表问题
删除有序链表中重复的元素-II
给出一个升序排序的链表,删除链表中的所有重复出现的元素,只保留原链表中只出现一次的元素。
例如:
给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
给出的链表为1→1→1→2→3, 返回2→3.
方法一:空间复杂度O(n)
过程:
public class Solution {
/**
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode deleteDuplicates (ListNode head) {
// 设置一个伪节点,主要是为了方便处理
ListNode result = new ListNode(0);
ListNode resultTemp = result;
ListNode h = head;
while(h != null) {
ListNode cur = h;
ListNode node = cur.next;
boolean flag = false;
// 这里是为了找到当前节点是否存在重复元素
while(node != null) {
if(node.val == cur.val) {
flag = true;
// 这里主要是过滤掉重复的
node = node.next;
} else {
break;
}
}
if(!flag) {
// 不存在重复元素,则新建一个元素
resultTemp.next = new ListNode(cur.val);
resultTemp = resultTemp.next;
}
// h指向node: 因为此时的node是指向一个与cur不相等的节点, 如果h直接指向node就行了
h = node;
}
return result.next;
}
}
方法二:空间复杂度O(1),直接在原链表上面操作
public class Solution {
/**
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode deleteDuplicates (ListNode head) {
// 设置一个伪节点,主要是为了方便处理
ListNode result = new ListNode(0);
result.next = head;
// 前指针
ListNode pre = result;
// 当前指针
ListNode cur = head;
// 每次都判断当前指针的下一个指针是否与当前指针的值相同
// 如果相同, 则找到第一个与当前指针不相同的节点node, 然后将前指针的next指针指向node
// 如果不相同, 则前指针和当前指针都指向下一个
// 1 2 3 3 4 4 5
while(cur != null) {
if(cur.next != null && cur.next.val == cur.val) {
// 存在相同值
ListNode node = cur.next;
// 这里主要是让node指向一个不与cur相同的节点
while(node != null && node.val == cur.val) {
node = node.next;
}
// 直接将 pre.next 指向 node, 达到了删除相同元素的目的
pre.next = node;
cur = node;
} else {
// 不存在相同值, 都指向下一个指针
pre = pre.next;
cur = cur.next;
}
}
return result.next;
}
}
字符串问题
最长回文子串
对于一个字符串,请设计一个高效算法,计算其中最长回文子串的长度。
给定字符串A以及它的长度n,请返回最长回文子串的长度。
输入:"abc1234321ab",12
返回:7
方法一: 暴力法
public class Solution {
public int getLongestPalindrome(String A, int n) {
// write code here
if(n <= 1) {
return n;
}
int max = 1;
char[] chars = A.toCharArray();
// 两个for循环遍历所有可能的子串
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
// 如果当前字符串长度大于 max 并且是回文
if(j - i + 1 > max && isHuiwen(chars, i, j)) {
max = j - i + 1;
}
}
}
return max;
}
public boolean isHuiwen(char[] chars, int i, int j) {
while(i < j) {
if(chars[i] != chars[j]) {
return false;
}
i++;
j--;
}
return true;
}
}
方法二: 动态规划
dp[left][right]代表[left, right]之间是否为回文
s.charAt(left) == s.charAt(right)
如果 right - left <= 2, dp[left][right] = true; 则字符长度为2或者3, 类似于这种: "aa"、"aba"
如果 right - left > 2, dp[left][right] = dp[left+1][right-1];
public class Solution {
public int getLongestPalindrome(String A, int n) {
if(n < 2) {
return A.length();
}
boolean[][] dp = new boolean[n][n];
int max = 1;
char[] chars = A.toCharArray();
for(int right = 1; right < n; right++) {
for(int left = 0; left < right; left++) {
// 如果不相同, 说明[left, right]肯定不是回文
if(chars[left] != chars[right]) {
continue;
}
if(right - left <= 2){
// aa 或者 aba
dp[left][right] = true;
} else {
dp[left][right] = dp[left + 1][right - 1];
}
if(dp[left][right]) {
max = Math.max(max, right - left + 1);
}
}
}
return max;
}
}
二叉树
对称二叉树
public class Main {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(2);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(4);
root.right.right = new TreeNode(3);
//
// root.left.left.left = new Node(7);
// root.left.left.right = new Node(8);
// root.left.right.left = new Node(9);
// root.left.right.right = new Node(10);
System.out.println(isSymmetric2(root));;
}
/**
* 递归法
* 判断是否为对称二叉树
* https://leetcode-cn.com/problems/symmetric-tree/
*/
public static boolean isSymmetric(TreeNode root){
if (root == null) {
return true;
}
return compare(root.left, root.right);
}
/**
* 1
* / \
* 2 2
* / \ / \
* 3 4 4 3
*
* 比较左子树跟右子树
* 1. 空判断
* 2.
* left.left == right.right 外侧比较
* left.right == right.left 内测比较
* @param left
* @param right
* @return
*/
public static boolean compare(TreeNode left, TreeNode right){
if (left == null && right == null) {
return true;
} else if (left == null && right != null) {
return false;
} else if (left != null && right == null) {
return false;
} else if (left.value != right.value) {
return false;
}
// 比较外侧
boolean outSide = compare(left.left, right.right);
// 比较内侧
boolean inSide = compare(left.right, right.left);
return outSide && inSide;
}
/**
* 非递归法
* 判断是否为对称二叉树
* https://leetcode-cn.com/problems/symmetric-tree/
*/
public static boolean isSymmetric2(TreeNode root){
if (root == null) {
return true;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root.left);
stack.push(root.right);
while (!stack.isEmpty()) {
// 出栈-拿出右树
TreeNode right = stack.pop();
// 出栈-拿出左树
TreeNode left = stack.pop();
if (right == null && left == null) {
continue;
} else if (right == null && left != null) {
return false;
} else if (right != null && left == null) {
return false;
} else if (right.value != left.value) {
return false;
}
// 外侧
stack.push(left.left);
stack.push(right.right);
// 内侧
stack.push(left.right);
stack.push(right.left);
}
return true;
}
}
二叉树的最大深度
/**
* 二叉树的最大深度
* https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
*/
public static int getMaxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = getMaxDepth(root.left);
int right = getMaxDepth(root.right);
return Math.max(left, right) + 1;
}
二叉树的最小深度
/**
* 111. 二叉树的最小深度
* 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
* https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
*/
public static int getMinDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = getMaxDepth(root.left);
int right = getMaxDepth(root.right);
// 左节点为空
if (root.left == null && root.right != null) {
return 1 + right;
}
// 右节点为空
if (root.left != null && root.right == null) {
return 1 + left;
}
return Math.min(left, right) + 1;
}
计算二叉树的节点个数
/**
* 计算二叉树的节点个数
* 递归
*/
public static int getNodeCount(TreeNode root) {
if (root == null) {
return 0;
}
// 计算左树节点个数
int leftCount = getNodeCount(root.left);
// 计算右树节点个数
int rightCount = getNodeCount(root.right);
// 加1是因为加上当前节点
return leftCount + rightCount + 1;
}
/**
* 计算二叉树的节点个数
* 非递归-使用层次遍历
*/
public static int getNodeCount2(TreeNode root) {
if (root == null) {
return 0;
}
LinkedList<TreeNode> list = new LinkedList();
list.addLast(root);
int count = 0;
while (!list.isEmpty()) {
int size = list.size();
for (int i = 0; i < size; i++) {
TreeNode node = list.removeFirst();
if (node.left != null) {
list.addLast(node.left);
}
if (node.right != null) {
list.addLast(node.right);
}
count++;
}
}
return count;
}
本作品采用《CC 协议》,转载必须注明作者和本文链接