以往刷题的很多题并没有做系统性记录，逻辑不够清晰。本页将已经刷过的每题进行二次总结，强化算法实现、逻辑思维能力。同时每天也会坚持刷题，坚持总结一篇以往AC的题目。
罗马数字包含以下七种字符:
I，V，X，L，C，D和M。字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000例如， 罗马数字 2 写做
II，即为两个并列的 1。12 写做XII，即为X+II。 27 写做XXVII, 即为XX+V+II。通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做
IIII，而是IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为IX。这个特殊的规则只适用于以下六种情况：
I可以放在V(5) 和X(10) 的左边，来表示 4 和 9。X可以放在L(50) 和C(100) 的左边，来表示 40 和 90。C可以放在D(500) 和M(1000) 的左边，来表示 400 和 900。给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
import java.util.HashMap;
import java.util.Map;
/*
* @lc app=leetcode.cn id=13 lang=java
*
* [13] 罗马数字转整数
*/
// @lc code=start
class Solution {
public int romanToInt(String s) {
/**
* Accepted //时间有点慢
* 3999/3999 cases passed (10 ms)
* Your runtime beats 24.88 % of java submissions
* Your memory usage beats 5.56 % of java submissions (40.2 MB)
*/
if(s == null || s.length() == 0){
return 0;
}
Map<String, Integer> lib = new HashMap<>();
lib.put("I", 1);
lib.put("V", 5);
lib.put("X", 10);
lib.put("L", 50);
lib.put("C", 100);
lib.put("D", 500);
lib.put("M", 1000);
int sum = 0;
String preSIString ="";
for (int i = 0; i < s.length(); ++i) {
String sI = s.substring(i, i + 1);
sum+=lib.get(sI);
if((sI.equals("V") || sI.equals("X")) && preSIString.equals("I") ){
sum -=2;
}
else if((sI.equals( "L") || sI.equals("C")) && preSIString.equals("X")){
sum -=20;
}
else if((sI.equals( "D") || sI.equals( "M")) && preSIString.equals("C")){
sum -=200;
}
preSIString = sI;
}
return sum;
}
public static void main(String[] args) {
String rom = "LVIII";
Solution solution = new Solution();
int ret = solution.romanToInt(rom);
System.out.println(ret);
}
}
// @lc code=end
解：
我们定义一个Map存储每个字符对应的数值。
根据如下信息，可以得到，在遇上I、V、X 或者 X、L、C 或者C、D、M同时出现时需要特殊处理。
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。因此，我们在遇到每个字符的时候在总数上加上一个该字符对应的数值，通过判断当前字符是否是”V、X 或者L、C 或者D、M”来进行处理特殊情况。在上述条件下，且上一个字符是对应的I、X、C，则需要减去2 * I、2 * X、2 * C，来纠正最新的数据。
最终数据的总和就是我们要的答案。
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串
""。输入: ["flower","flow","flight"] 输出: "fl"输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。
package leetcode_14_longestCommonPrefix;
/*
* @lc app=leetcode.cn id=14 lang=java
*
* [14] 最长公共前缀
*/
// @lc code=start
class Solution {
/**
* Accepted
* 118/118 cases passed (1 ms)
* Your runtime beats 79.38 % of java submissions
* Your memory usage beats 42.5 % of java submissions (37.6 MB)
*/
public String longestCommonPrefix(String[] strs) {
// 输入校验
StringBuffer strPrefix = new StringBuffer();
if(strs == null || strs.length == 0){
return "";
}
if(strs.length ==1){
return strs[0];
}
for (int i = 0; i < strs[0].length(); ++i) {
char tmp = strs[0].charAt(i);
// 遍历有几个字符串
for (int j = 0; j < strs.length; ++j) {
if (strs[j].length() == i || strs[j].charAt(i) != tmp) {
return strs[0].substring(0, i);
}
}
strPrefix.append(tmp);
}
return strPrefix.toString();
}
public static void main(String[] args) {
String[] strs = {"cc","c",};
Solution solution = new Solution();
String prefix = solution.longestCommonPrefix(strs);
System.out.println(prefix);
}
}
// @lc code=end
解：
时间复杂度：log(n*m)，n代表数组长度，m代表共同前缀个数
思路:
获取第一个字符串的长度n，从0-n进行遍历，在某个下标位置记录当前字符，比较数组中剩下元素的当前位置字符是否相同。如果相同，则输出字符串附加一个字符。
给定一个包括 n 个整数的数组
nums和 一个目标值target。找出nums中的三个整数，使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。
import java.util.*;
class Solution {
/*异常类*/
class mException extends Exception {
public String getCode() {
return "new Exception";
}
public mException(String message) {
super(message);
}
}
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int len = nums.length;
try {
if (3 > len) {
throw new mException("Invalid Input! Length of array < 3");
}
// int [] nums= {-1,2,1,-4};-4 -1 1 2
int i = 0, startIndex = i + 1, endIndex = len - 1;
int closestNum = nums[i] + nums[startIndex] + nums[endIndex];
int tempNum = 0;
for (; i < nums.length; ++i) {
startIndex = i + 1;
endIndex = len - 1;
while (i != startIndex && startIndex != endIndex && i != endIndex) {
tempNum = nums[i] + nums[startIndex] + nums[endIndex];
// 计算两个数值的距离
if (Math.abs(target - tempNum) < Math.abs(target - closestNum)) {
closestNum = tempNum;
}
if (tempNum < target) {
startIndex++;
} else {
endIndex--;
}
}
}
return closestNum;
} catch (mException e) {
// TODO: handle exception
e.printStackTrace();
}
return 0;
}
public static void main(String[] args) {
int[] nums = { -1, 2, 1, -4 };
Solution so = new Solution();
int target = 1;
System.out.println(so.threeSumClosest(nums, target));
}
}
解：
我们可以通过双指针的方式降低时间复杂度（前提是该数组是有序的）。
i指向当前下标，start = i+1，end = length - 1;
每次遍历，将三个下标对应的数组相加求和（temp）。记录和target距离最小的temp。
如果target < temp，end小标减一。如果target > temp，start下标加一，该过程用于找到每个i小标对应的与target相差最小的那三组数之和。
遍历完i，就得到了最接近target的三数之和。
给定一个包含 n 个整数的数组
nums和一个目标值target，判断nums中是否存在四个元素 a，**b，c 和 d ，使得 a + b + c + d 的值与target相等？找出所有满足条件且不重复的四元组。注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
package leetcode_18_fourSum;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// @lc code=start
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<Integer> item;
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
for (int a = 0; a < nums.length - Number.LastTwoIndex; ++a) {
for (int b = a + 1; b < nums.length - 1; ++b) {
int startIndex = b + 1;
int endIndex = nums.length - 1;
while (startIndex < endIndex) {
int tempSum = nums[a] + nums[b] + nums[startIndex] + nums[endIndex];
if ((tempSum - target) == 0) {
item = new ArrayList<>();
/**
* 需要考虑提出重复元组
*/
item.add(nums[a]);
item.add(nums[b]);
item.add(nums[startIndex]);
item.add(nums[endIndex]);
if (nums[a] == 333) {
int breakPoint = 1;
}
if (!isExist(ans, item)) {
ans.add(item);
}
}
if (tempSum > target) {
endIndex--;
} else {
startIndex++;
}
}
}
}
return ans;
}
private boolean isExist(List<List<Integer>> ans, List<Integer> item) {
boolean is = false;
for (List<Integer> itemInList : ans) {
boolean lastSame = false;
for (int i = 0; i < item.size(); ++i) {
// Java中要进行比较的，最好还是用equals。
// 从java核心技术讲义中，如果两个Integer变量的值在区间-128到127之间，则比较结果为true
if (item.get(i).equals(itemInList.get(i))) {
lastSame = true;
} else {
lastSame = false;
break;
}
}
if (lastSame) {
return true;
}
}
return is;
}
public static void main(String[] args) {
/*测试*/
int[] nums = { -497, -494, -484, -477, -453, -453, -444, -442, -428, -420, -401, -393, -392, -381, -357, -357,
-327, -323, -306, -285, -284, -263, -262, -254, -243, -234, -208, -170, -166, -162, -158, -136, -133,
-130, -119, -114, -101, -100, -86, -66, -65, -6, 1, 3, 4, 11, 69, 77, 78, 107, 108, 108, 121, 123, 136,
137, 151, 153, 155, 166, 170, 175, 179, 211, 230, 251, 255, 266, 288, 306, 308, 310, 314, 321, 322, 331,
333, 334, 347, 349, 356, 357, 360, 361, 361, 367, 375, 378, 387, 387, 408, 414, 421, 435, 439, 440, 441,
470, 492 };
int target = 1682;
new Solution().fourSum(nums, target);
}
public static class Number {
public static Integer LastTwoIndex = 2;
}
}
// @lc code=end
解：
该题“最接近的四数之和”，可以通过三数之和一样的思路进行解题。三数之和把0(n^3) => 0(n^2)，在这里可以为四数之和降到 0(n^3)的时间复杂度。
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true示例 2:
输入: "()[]{}" 输出: true示例 3:
输入: "(]" 输出: false示例 4:
输入: "([)]" 输出: false示例 5:
输入: "{[]}" 输出: true
package leetcode_20_isValid;
/*
* @lc app=leetcode.cn id=20 lang=java
* [20] 有效的括号
*/
import java.util.*;
// @lc code=start
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
/**
* 解题思路： 如果是空格则跳过 如果是左括号则放入栈 如果是有括号则找栈顶，如果是一对，则栈顶出栈。 如果不是一对，则返回false
*
* 遍历完之后，如果栈里面只有空格或者为空则返回true。
* Accepted 76/76 cases passed (3 ms) Your runtime beats 40.3 % of java
* submissions Your memory usage beats 5.48 % of java submissions (37.8 MB)
*/
if (s == null) {
return false;
}
if (s.length() == 0) {
return true;
}
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == ' ') {
continue;
} else if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
stack.push(s.charAt(i));
} else if (s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) == '}') {
if (stack.size() <= 0) {
return false; // 如果有有括号的情况，没了左括号，那么就是无效的一组
}
Character top = stack.peek();
if (mEqual(top, s.charAt(i))) {
stack.pop();
} else {
return false;
}
}
}
if (stack.size() == 0) {
return true;
}
return false;
}
private boolean mEqual(Character left, Character right) {
// System.out.println(left.equals(new Character('(')));
// System.out.println(right.equals(new Character(')')));
if (left.equals(new Character('(')) && right.equals(new Character(')')) || left.equals('[') && right.equals(']')
|| left.equals('{') && right.equals('}')) {
return true;
}
return false;
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "]";
boolean out = solution.isValid(s);
System.out.println(out);
return;
}
}
// @lc code=end
解：
通过栈的方式完成任务，把任何左括号的类型一律入栈。
如果遇到了右括号则去栈中弹出一个字符，如果这两个括号是对应的一组则继续遍历，如果不是则返回false
如果字符串遍历完毕之后栈中还有数据，那么括号不对称返回false。
如果字符串遍历完，且栈为空，那么返回true。
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3 输出: 1->2->3->4示例 2:
输入: -1->5->3->4->0 输出: -1->0->3->4->5
package leetcode148;
// @lc code=start
/**
* Definition for singly-linked list. public class ListNode { int val; ListNode
* next; ListNode(int x) { val = x; } }
*/
class Solution {
public ListNode sortList(ListNode head) {
/**
* O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
*/
/**
* 快排是二分，可以达到nlogn的复杂度，需要递归，并且遍历末尾节点比较费时间。 归并排序也是二分，可以达到nlogn的时间复杂度，同时可以达到常数复杂度。
*/
/**
* 输入检验
*/
if (head == null || head.next == null) {
return head;
}
// Accepted
// 16/16 cases passed (3 ms)
// Your runtime beats 99.19 % of java submissions
// Your memory usage beats 10.58 % of java submissions (42.9 MB)
ListNode newList = mergeSortListNode(head);
return newList;
}
public ListNode mergeSortListNode(ListNode firstNode) {
// 找到一个节点的位置
if (firstNode.next == null) {
return firstNode;
}
// 计算中间节点，进行递归
ListNode midNode = findMidNode(firstNode);
ListNode secondNode = midNode.next;
// 把列表切断成两部分！
midNode.next = null;
ListNode head1 = mergeSortListNode(firstNode);
ListNode head2 = mergeSortListNode(secondNode);
ListNode ptr1 = head1;
ListNode ptr2 = head2;
/**
* 咱们在进行合并的时候不是会遇上链表循环连接？那就解决这个问题，在查找中点的时候把他cut断就好啦！！！
*/
ListNode newHead;
ListNode ptrCur;
if (ptr1.val < ptr2.val) {
newHead = ptr1;
ptr1 = ptr1.next;
} else {
newHead = ptr2;
ptr2 = ptr2.next;
}
ptrCur = newHead;
while (ptr1 != null && ptr2 != null) {
if (ptr1.val < ptr2.val) {
ptrCur.next = ptr1;
ptr1 = ptr1.next;
} else {
ptrCur.next = ptr2;
ptr2 = ptr2.next;
}
ptrCur = ptrCur.next;
}
if (ptr1 != null) {
ptrCur.next = ptr1;
ptr1 = ptr1.next;
}
if (ptr2 != null) {
ptrCur.next = ptr2;
ptr2 = ptr2.next;
}
return newHead;
}
public ListNode findMidNode(ListNode firstNode) {
/**
* 找中点，快慢指针！
*/
ListNode ptr = firstNode;
ListNode fastPtr = firstNode;
while (fastPtr != null && fastPtr.next != null && fastPtr.next.next != null) {
ptr = ptr.next;
fastPtr = fastPtr.next.next;
}
return ptr;
}
public static void main(String[] args) {
int[] nums = { 4, 2, 1, 3, 5, 8 };
Solution solution = new Solution();
ListNode head = ListNode.createNodeList(nums);
solution.sortList(head);
System.out.println(head);
}
}
// @lc code=end
解：
归并递归描述
依据归并排序，我们需要对数据进行不断地二分。划分到只有一个节点之后，返回阶段，在返回是对两组数据进行归并，然后进一步递归返回，再将两个数组进行按序归并，如此到递归退出就能获得有序地数据。
上面代码比较长，这里做一个解释。
由于是链表，不能直接类似于数组进行索引访问，因此需要通过快慢指针获得中间元素。findMidNode()
midNode.next = null;给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树
[1,2,2,3,4,4,3]是对称的。1 / \ 2 2 / \ / \ 3 4 4 3
/**
* @description: 对称二叉树 https://leetcode-cn.com/problems/symmetric-tree/description/
* @modifyContent:
* @author: Maple Chan
* @date: 2020-07-18 16:09:36
* @version: 0.0.1
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
// 思路, 广度优先遍历，用栈的方式。
if (null == root) {
return true;
}
// 迭代
return isSymmetricCoreBfs(root.left, root.right);
}
public boolean isSymmetricCore(TreeNode left, TreeNode right) {
// Accepted
// 195/195 cases passed (0 ms)
// Your runtime beats 100 % of java submissions
// Your memory usage beats 28.75 % of java submissions (38 MB)
if (null == left && null == right) {
return true;
}
if (null != left && null == right) {
return false;
}
if (null == left && null != right) {
return false;
}
if (left.val == right.val) {
return isSymmetricCore(left.left, right.right) && isSymmetricCore(left.right, right.left);
}
return false;
}
LinkedList<TreeNode> stack = new LinkedList<>();
/**
* @description 迭代的方法，用队列存数据进行两两比较。
* @author Maple Chan
* @date: 2020-07-18 16:07:16
* @params
* @return
*/
public boolean isSymmetricCoreBfs(TreeNode left, TreeNode right) {
// Accepted
// 195/195 cases passed (1 ms)
// Your runtime beats 30.72 % of java submissions
// Your memory usage beats 5 % of java submissions (39.5 MB)
if (null == left && null == right) {
return true;
}
if (null != left && null == right) {
return false;
}
if (null == left && null != right) {
return false;
}
stack.add(left);
stack.add(right);
while (0 < stack.size()) {
TreeNode node1 = stack.pop();
TreeNode node2 = stack.pop();
if (null == node1 && null == node2) {
continue;
}
if (null == node1 || null == node2 || node1.val != node2.val) {
return false;
}
stack.push(node1.left);
stack.push(node2.right);
stack.push(node1.right);
stack.push(node2.left);
}
return true;
}
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);
Solution solution = new Solution();
boolean ret = solution.isSymmetric(root);
System.out.println(ret);
return;
}
}
解：
递归
如果镜像对称，那么左子树和右子树也一定是镜像对称。
通过递归，将左子树的左节点和右子树的右节点递归传入进行比较。
① 递归结束条件：如果左节点 == 右节点 == null， 返回 ture；如果左节点 != 右节点，返回false；
②如果两个节点都不为空，且值相等，则需要进一步递归。
层序遍历
通过迭代，定义一个栈，将左节点的左子节点和右节点的右子节点，左节点的右子节点和右节点的左子节点并列放入栈中。
每次弹出两个数据：
如果两个数据相等则进一步迭代，直至栈为空返回ture。
如果两个数据不相等直接返回false
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组
[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2] 输出: 1示例 2:
输入: [4,5,6,7,0,1,2] 输出: 0
题解：
/**
*
* 146/146 cases passed (8 ms)
* Your runtime beats 41.73 % of cpp submissions
* Your memory usage beats 17.38 % of cpp submissions (8.8 MB)
*
*/
// @lc code=start
#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
/**
* 用两个指针减少遍历的次数
*/
int findMin(vector<int>& nums) {
size_t leftPtr = 0;
size_t rightPtr = nums.size() -1;
size_t destinyPtr = 0;
//cout << "debug:: in the findMin function!"<<endl;
if(nums.size() < 1)
cerr << "Invalid Input arry" << endl;
if(nums.size()==1)
return nums[0];
while (nums[leftPtr] >= nums[rightPtr])
{
//cout << "debug:: still in the while!"<<endl;
/* code */
if(rightPtr - leftPtr == 1){
//如果两个指针之差为1则说明已经找到了最小值
destinyPtr = rightPtr;
break;
}
size_t mid = (rightPtr + leftPtr) / 2;
if(nums[mid]==nums[leftPtr] && nums[mid] == nums[rightPtr]){
//如果三个相等没法判断的情况
//采用顺序查找的方式
int min = nums[0];
for(size_t i=0;i<nums.size();++i){
if(min > nums[i]){
min = nums[i];
}
}
return min;
}
if(nums[mid] > nums[leftPtr]){
leftPtr = mid;
}
if(nums[mid] < nums[rightPtr]){
rightPtr = mid;
}
}
return nums[destinyPtr];
}
};
// @lc code=end
int main(){
vector<int> nums = {1,2};
Solution so;
int min = so.findMin(nums);
cout << min <<endl;
return 0;
}
解：
本题是二分搜索的变题
对于传入数组，指定两个指针，一个left指针，一个right指针。
如果nums[left] >= nums[right]则说明，left指针在旋转点的左侧，right指针在旋转点的右侧。则不断进行循环，执行二分的过程。
二分的结束条件为， nums[left] > nums[right] && right-left == 1
如果nums[mid] < nums[left]说明，mid在旋转点的右侧，应该将right = mid；
如果nums[mid] > nums[right]说明，mid在旋转点的左侧，应该将left = mid；
上述代码中间还处理一个特殊情况，
nums[left] == nums[mid] == nums[right]。这种情况没法区分下一个mid应该在哪半边区域，因此用遍历的方式进行寻找
nums[left] > nums[right]的位置
您需要在二叉树的每一行中找到最大的值。
示例：
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: [1, 3, 9]
class Solution {
public List<Integer> largestValues(TreeNode root) {
// Accepted
// 78/78 cases passed (2 ms)
// Your runtime beats 81.33 % of java submissions
// Your memory usage beats 7.14 % of java submissions (40.3 MB)
// 输出检查
List<Integer> list = new LinkedList<>();
if (null == root) {
return list;
}
// 核心函数
largestValuesCore(root, list, 0);
return list;
}
private void largestValuesCore(TreeNode root, List<Integer> retList, int level) {
if (null == root) {
return;
}
if (retList.size() - 1 < level) {
retList.add(Integer.MIN_VALUE);
}
Integer iItem = retList.get(level);
if (iItem.intValue() < root.val) {
retList.set(level, root.val);
}
largestValuesCore(root.left, retList, level + 1);
largestValuesCore(root.right, retList, level + 1);
}
/**
* 测试例子
*/
public static void main(String[] args) {
final TreeNode root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
// root.left.left = new TreeNode(3);
// root.left.right = new TreeNode(4);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
final Solution solution = new Solution();
final List<Integer> ret = solution.largestValues(root);
System.out.println(ret);
return;
}
}
解：
通过递归实现。
① 递归结束条件：碰到叶节点。
② 在进行DFS遍历二叉树的同时，传入参数level给定每次递归的层级，通过层级来进行对当前level的最大值进行比较和替换。
（如果list中没有当前层级的数据，则初始化Integer.MIN_VALUE，有则取出来和当前数值进行比较，若当前值更大则将当前值替换成list中的数值。）
时间复杂度：遍历每个节点，0(N)
空间复杂度：递归需要每向下一层就需要入栈，O(h + h + h) 。三个h分别存储root节点、每层max的值，该层对应的level。