计算机编程充满乐趣。有时候，它是一门优雅的科学，有时候，它要去开发和使用新的软件工具。编程与人息息相关：客户实际想解决什么问题？
解题模板
双指针解题模板
我们通过迭代数组来解决一些问题。通常，我们只需要一个指针进行迭代，即从数组中的第一个元素开始，最后一个元素结束。然而，有时我们会使用两个指针进行迭代。
示例
让我们从一个经典问题开始：
反转数组中的元素。比如数组为 [‘l’, ‘e’, ‘e’, ‘t’, ‘c’, ‘o’, ‘d’, ‘e’]，反转之后变为 [‘e’, ‘d’, ‘o’, ‘c’, ‘t’, ‘e’, ‘e’, ‘l’]。
使用双指针技巧，其思想是分别将两个指针分别指向数组的开头及末尾，然后将其指向的元素进行交换，再将指针向中间移动一步，继续交换，直到这两个指针相遇。
原地哈希(哈希表)
滑动窗口
KMP算法
马拉车算法
回溯算法
二分法
数据结构与算法总结
通用方法代码
485. 最大连续 1 的个数
反转字符串
public static char[] reverse(char[] nums,int begin,int end){
int x = begin;
int y = end;
while(x<y){
char temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
x++;
y--;
}
return nums;
}
//反转链表
public ListNode reverseList(ListNode head) {
ListNode temp = null;
ListNode prev = null;
ListNode cur = head;
while(cur !=null){
temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
//数组实现栈
public class ArrayStack {
/**
* 数组
*/
private String[] nums;
/**
* 栈元素个数
*/
private int count;
/**
* 栈大小
*/
private int size;
public ArrayStack(int size) {
this.nums = new String[size];
this.count = 0;
this.size = size;
}
//入栈操作
public boolean push(String item){
if(count == size){
return false;
}
nums[count] = item;
count++;
return true;
}
public String pop(){
if(count == 0){
return null;
}
String res = nums[count-1];
count--;
return res;
}
public boolean isEmpty(){
return count == 0;
}
public boolean isFull(){
return count == size;
}
}
//链表基本操作
public class ListNodeDemo {
public static class ListNode {
/**
* 节点数据
*/
private Object data;
/**
* 指针
*/
private ListNode next;
/**
* 构造函数
* @param data
*/
public ListNode(Object data) {
this.data = data;
}
public ListNode() {
}
}
/**
* 头结点
*/
private ListNode head;
/**
* 临时变量
*/
private ListNode temp;
/**
*初始化链表
*/
public ListNodeDemo() {
head = new ListNode();
}
/**
* 获取链表长度
* @return
*/
public int getLength(){
temp = head;
int length = 0;
while (temp.next != null){
temp = temp.next;
length++;
}
return length;
}
/**
* 添加链表节点
* @param data
*/
public void addNode(Object data){
ListNode node = new ListNode(data);
temp = head;
while(temp.next !=null){
temp = temp.next;
}
temp.next = node;
}
/**
* 指定位置新增节点
* @param index
* @param data
*/
public void addNodeByIndex(int index ,Object data){
if(index < 1 || index > getLength()+1){
return;
}
ListNode node = new ListNode(data);
int count = 1;
temp = head;
while (temp.next != null){
if(count == index){
node.next = temp.next;
temp.next = node;
return;
}
count++;
temp = temp.next;
}
}
/**
* 删除指定位置节点
* @param index
*/
public void deleteNodeByIndex(int index){
if(index < 1 || index>getLength()+1){
return;
}
int count = 1;
temp = head;
while(temp.next != null){
if(count == index){
temp.next = temp.next.next;
return;
}
count++;
temp = temp.next;
}
}
/**
* 从头到尾打印链表
*/
public void printNodeFromHead(){
ListNode cur = head;
while(cur.next != null){
System.out.println("{"+cur.next.data+"}");
cur = cur.next;
}
}
/**
* 从尾到头打印链表
*/
public void printNodeFromTail(){
//先反转链表再打印
ListNode prev = null;
ListNode cur = head;
while (cur != null){
temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
while(prev.next != null){
System.out.println("{"+prev.data+"}");
prev = prev.next;
}
}
public static void main(String[] args)
{
ListNodeDemo list = new ListNodeDemo();
list.addNode(1);
list.addNode(2);
list.addNode(3);
list.addNode(4);
list.addNode(5);
list.printNodeFromHead();
list.printNodeFromTail();
list.addNodeByIndex(3,2.8);
list.printNodeFromHead();
list.deleteNodeByIndex(3);
list.printNodeFromHead();
System.out.println(list.getLength());
}
}
每日一题
561. 数组拆分 I
//给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得
//从 1 到 n 的 min(ai, bi) 总和最大。
// 返回该 最大总和 。
//
// 示例 1：
//输入：nums = [1,4,3,2]
//输出：4
//解释：所有可能的分法（忽略元素顺序）为：
//1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
//2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
//3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
//所以最大总和为 4
//
// 示例 2：
//输入：nums = [6,2,6,5,1,2]
//输出：9
//解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 +
//6 = 9
//
// 提示：
// 1 <= n <= 104
// nums.length == 2 * n
// -104 <= nums[i] <= 104
// Related Topics 数组
// 👍 240 👎 0
class Solution {
public int arrayPairSum(int[] nums) {
int res = 0;
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
if(i%2 == 0){
res = res + nums[i];
}
}
return res;
}
}
解题思路分析：
我们先对数组进行排序。
由于每两个数，我们只能选择当前小的一个进行累加。
因此我们猜想应该从第一个位置进行选择，然后隔一步选择下一个数。这样形成的序列的求和值最大
566. 重塑矩阵
//在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。
// 给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。
// 重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
// 如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
// 示例 1:
//输入:
//nums =
//[[1,2],
// [3,4]]
//r = 1, c = 4
//输出:
//[[1,2,3,4]]
//解释:
//行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
// 示例 2:
//输入:
//nums =
//[[1,2],
// [3,4]]
//r = 2, c = 4
//输出:
//[[1,2],
// [3,4]]
//解释:
//没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
// 注意：
// 给定矩阵的宽和高范围在 [1, 100]。
// 给定的 r 和 c 都是正数。
//
// Related Topics 数组
// 👍 183 👎 0
class Solution {
public int[][] matrixReshape(int[][] nums, int r, int c) {
int m = nums.length;
int n = nums[0].length;
if(m*n != r*c){
return nums;
}
int[][] ans = new int[r][c];
for(int x=0;x<m*n;x++){
ans[x / c][x % c] = nums[x / n][x % n];
}
return ans;
}
}
1004. 最大连续1的个数 III
//给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
// 返回仅包含 1 的最长（连续）子数组的长度。
// 示例 1：
//
// 输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
//输出：6
//解释：
//[1,1,1,0,0,1,1,1,1,1,1]
//粗体数字从 0 翻转到 1，最长的子数组长度为 6。
//
// 示例 2：
// 输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
//输出：10
//解释：
//[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
//粗体数字从 0 翻转到 1，最长的子数组长度为 10。
// 提示：
// 1 <= A.length <= 20000
// 0 <= K <= A.length
// A[i] 为 0 或 1
//
// Related Topics 双指针 Sliding Window
// 👍 218 👎 0
class Solution {
public int longestOnes(int[] A, int K) {
}
}
解题思路:滑动窗口法，//TODO
数组的遍历
485. 最大连续1的个数
//给定一个二进制数组， 计算其中最大连续1的个数。
//示例 1:
//输入: [1,1,0,1,1,1]
//输出: 3
//解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
//
// 注意：
// 输入的数组只包含 0 和1。
// 输入数组的长度是正整数，且不超过 10,000。
//
// Related Topics 数组
// 👍 165 👎 0
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int count = 0;
int maxCount = 0;
for(int i=0;i<nums.length;i++){
if(nums[i] == 1){
count++;
}
if(nums[i] == 0){
if(count>maxCount){
maxCount = count;
}
count = 0;
}
}
return count>maxCount?count:maxCount;
}
}
思路：遍历数组，用一个计数器(count)记录1的数量，用另一个计数器记录当前1的最大出行次数，如果遇到0 ，比较count与maxCount ,maxCount 记录较大值，同时将count置为0；
495. 提莫攻击
//在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄，他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。现在，给出提莫对艾希的攻击时间序列和提莫攻击
//的中毒持续时间，你需要输出艾希的中毒状态总时长。
//
// 你可以认为提莫在给定的时间点进行攻击，并立即使艾希处于中毒状态。
// 示例1:
//
// 输入: [1,4], 2
//输出: 4
//原因: 第 1 秒初，提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟，直到第 2 秒末结束。
//第 4 秒初，提莫再次攻击艾希，使得艾希获得另外 2 秒中毒时间。
//所以最终输出 4 秒。
//
// 示例2:
//
// 输入: [1,2], 2
//输出: 3
//原因: 第 1 秒初，提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟，直到第 2 秒末结束。
//但是第 2 秒初，提莫再次攻击了已经处于中毒状态的艾希。
//由于中毒状态不可叠加，提莫在第 2 秒初的这次攻击会在第 3 秒末结束。
//所以最终输出 3 。
//
// 提示：
// 你可以假定时间序列数组的总长度不超过 10000。
// 你可以假定提莫攻击时间序列中的数字和提莫攻击的中毒持续时间都是非负整数，并且不超过 10,000,000。
class Solution {
public int findPoisonedDuration(int[] timeSeries, int duration) {
int res = 0;
if(timeSeries.length == 0){
return 0;
}
if(timeSeries.length == 1){
return duration;
}
for(int i=1;i<timeSeries.length;i++){
if(timeSeries[i]-timeSeries[i-1]<duration){
res = res + timeSeries[i] - timeSeries[i-1];
}
else{
res= res + duration;
}
}
return res+duration;
}
}
思路：按照时间序列的话，数组一定是递增的如果第二个时间点和前一个时间之差大于了中毒时间，明显总中毒时间加duration
否则，则有重叠，总中毒时间加上第二个时间点和前一个时间之差。
414. 第三大的数
//给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
// 示例 1：
//输入：[3, 2, 1]
//输出：1
//解释：第三大的数是 1 。
//
// 示例 2：
//输入：[1, 2]
//输出：2
//解释：第三大的数不存在, 所以返回最大的数 2 。
//
// 示例 3：
//输入：[2, 2, 3, 1]
//输出：1
//解释：注意，要求返回第三大的数，是指第三大且唯一出现的数。
//存在两个值为2的数，它们都排第二。
//
// 提示：
// 1 <= nums.length <= 104
// -231 <= nums[i] <= 231 - 1
//
// 进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？
// Related Topics 数组
// 👍 201 👎 0
class Solution {
public int thirdMax(int[] nums) {
TreeSet<Integer> set = new TreeSet<>();
for(int i=0;i<nums.length;i++){
set.add(nums[i]);
if(set.size() > 3){
set.remove(set.first());
}
}
return set.size() <3?set.last():set.first();
}
}
思路：维护一个只有3个元素的TreeSet，如果大于三个元素就就把Set中的最小最小值remove掉。
最后如果Set中元素小于3就返回Set最大值，否则返回最小值。
628. 三个数的最大乘积
//给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
//
// 示例 1：
//输入：nums = [1,2,3]
//输出：6
//
// 示例 2：
//
//输入：nums = [1,2,3,4]
//输出：24
//
// 示例 3：
//
//输入：nums = [-1,-2,-3]
//输出：-6
// 提示：
//
// 3 <= nums.length <= 104
// -1000 <= nums[i] <= 1000
//
// Related Topics 数组 数学
// 👍 278 👎 0
class Solution {
public int maximumProduct(int[] nums) {
Arrays.sort(nums);
int max1 = nums[nums.length-1]*nums[nums.length-2]*nums[nums.length-3];
int max2 = nums[0]*nums[1]*nums[nums.length-1];
return Math.max(max1,max2);
}
}
思路：首先将数组排序。
如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；如果全是非正数，则最大的三个数相乘同样也为最大乘积。
如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积。
综上，我们在给数组排序后，分别求出三个最大正数的乘积，以及两个最小负数与最大正数的乘积，二者之间的最大值即为所求答案。
统计数组中的元素
645. 错误的集合
//集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有
//一个数字重复 。
// 给定一个数组 nums 代表了集合 S 发生错误后的结果。
// 请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
//
// 示例 1：
//输入：nums = [1,2,2,4]
//输出：[2,3]
//
// 示例 2：
//输入：nums = [1,1]
//输出：[1,2]
//
// 提示：
// 2 <= nums.length <= 104
// 1 <= nums[i] <= 104
// Related Topics 哈希表 数学
// 👍 150 👎 0
class Solution {
public int[] findErrorNums(int[] nums) {
}
}
448. 找到所有数组中消失的数字
//给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
// 找到所有在 [1, n] 范围之间没有出现在数组中的数字。
//
// 您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
//
// 示例:
//输入:
//[4,3,2,7,8,2,3,1]
//
//输出:
//[5,6]
// Related Topics 数组
// 👍 641 👎 0
//暴力解法，超出时间限制
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> resp = new ArrayList<>();
List<Integer> map = new ArrayList<>();
for(int i=0;i<nums.length;i++){
map.add(nums[i]);
}
for(int j=1;j<nums.length+1;j++){
if(!list.contains(j)){
resp.add(j);
}
}
return resp;
}
}
//思路二 通过
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> resp = new ArrayList<>();
for(int i=1;i<nums.length+1;i++){
int index = Math.abs(nums[i-1]);
if(nums[index-1] > 0){
nums[index-1] = - nums[index-1];
}
}
for(int i=0;i<nums.length;i++){
if(nums[i] > 0){
resp.add(i+1);
}
}
return resp;
}
}
解题思路：
使用数组的下标来标记数字的出现于否，通过一遍遍历即可标记出全部已经出现的数组
[4,3,2,7,8,2,3,1] 初始数据
[4,3,2,-7,8,2,3,1] 第一个数据 4 出现，将数组的第四个也就是下标 3 的数据修改为负数。-7 计算时，通过绝对值处理一下即可不影响数据的计算
[4,3,-2,-7,8,2,3,1]
[4,-3,-2,-7,8,2,3,1]
[4,-3,-2,-7,8,2,-3,1]
[4,-3,-2,-7,8,2,-3,-1]
[4,-3,-2,-7,8,2,-3,-1]
[4,-3,-2,-7,8,2,-3,-1]
[-4,-3,-2,-7,8,2,-3,-1]
442. 数组中重复的数据
//给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
// 找到所有出现两次的元素。
// 你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
// 示例：
//输入:
//[4,3,2,7,8,2,3,1]
//输出:
//[2,3]
// Related Topics 数组
// 👍 337 👎 0
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> res = new ArrayList<>();
Arrays.sort(nums);
for(int i=1;i<nums.length;i++){
if(nums[i] == nums[i-1]){
res.add(nums[i]);
}
}
return res;
}
}
//解法二
解题思路：
对数组进行排序，如果相邻两数相等，则为重复元素。
41. 缺失的第一个正数
//给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
// 进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？
// 示例 1：
//输入：nums = [1,2,0]
//输出：3
// 示例 2：
//输入：nums = [3,4,-1,1]
//输出：2
// 示例 3：
//输入：nums = [7,8,9,11,12]
//输出：1
// 提示：
// 0 <= nums.length <= 300
// -231 <= nums[i] <= 231 - 1
//
// Related Topics 数组
// 👍 954 👎 0
//哈希表解法
class Solution {
public int firstMissingPositive(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int i=0;i<nums.length;i++){
set.add(nums[i]);
}
for(int i=1;i<nums.length+1;i++){
if(!set.contains(i)){
return i;
}
}
return nums.length +1;
}
}
//暴力破解
class Solution {
public int firstMissingPositive(int[] nums) {
int min = 1;
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
if(nums[i] == min){
min++;
}
}
return min;
}
}
//原地哈希法
解题思路：
1、哈希表 我们可以将数组所有的数放入哈希表，随后从 11 开始依次枚举正整数，并判断其是否在哈希表中。
2、原地哈希：我们对数组进行遍历，对于遍历到的数 x，如果它在 [1, N][1,N] 的范围内，那么就将数组中的第 x-1 个位置（注意：数组下标从 0 开始）打上「标记」。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N+1，否则答案是最小的没有打上标记的位置加 1。
485274. H 指数
//给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。
// h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引
//用了至少 h 次。且其余的 N - h 篇论文每篇被引用次数 不超过 h 次。
// 例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。
// 示例：
//输入：citations = [3,0,6,1,5]
//输出：3
//解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
// 由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
// 提示：如果 h 有多种可能的值，h 指数是其中最大的那个。
// Related Topics 排序 哈希表
// 👍 129 👎 0
class Solution {
public int hIndex(int[] citations) {
}
}
453. 最小操作次数使数组元素相等
//给定一个长度为 n 的 非空 整数数组，每次操作将会使 n - 1 个元素增加 1。找出让数组所有元素相等的最小操作次数。
// 示例：
//输入：
//[1,2,3]
//输出：
//3
//解释：
//只需要3次操作（注意每次操作会增加两个元素的值）：
//[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
//
// Related Topics 数学
// 👍 190 👎 0
//排序解法
class Solution {
public int minMoves(int[] nums) {
Arrays.sort(nums);
int res = 0;
for(int i=0;i<nums.length;i++){
res = res + nums[i] - nums[0];
}
return res;
}
}
//数学解法：
解题思路：先找出数组中的最小值，然后让数组中的每一个值减去最小值,代表着这个数要移动的次数。然后把所有次数累加求和即是结果。
665. 非递减数列
//给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
// 我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
// 示例 1:
//输入: nums = [4,2,3]
//输出: true
//解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
// 示例 2:
//输入: nums = [4,2,1]
//输出: false
//解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
// 提示：
// 1 <= n <= 10 ^ 4
// - 10 ^ 5 <= nums[i] <= 10 ^ 5
//
// Related Topics 数组
// 👍 532 👎 0
class Solution {
public boolean checkPossibility(int[] nums) {
int count = 0;
for(int i=1;i<nums.length;i++){
//出现递减
if(nums[i] <nums[i-1]){
if(i==1 || nums[i] >= nums[i-2]){
nums[i-1] = nums[i];
count++;
}
else{
nums[i] = nums[i-1];
count++;
}
if(count >1){
return false;
}
}
}
return count<=1;
}
}
解题思路:贪心算法，遍历数组，查看是哪个数遍历数组，如果遇到递减：
- 还能修改：
- 修改方案1：将nums[i]缩小至nums[i 1 1]；
- 修改方案2：将nums[i - 1]放大至nums[i]；
283. 移动零
//给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
// 示例:
// 输入: [0,1,0,3,12]
//输出: [1,3,12,0,0]
// 说明:
// 必须在原数组上操作，不能拷贝额外的数组。
// 尽量减少操作次数。
//
// Related Topics 数组 双指针
// 👍 955 👎 0
//暴力解法 使用了额外数组,定义一个新数组，不等于0的放前面，后面的都是0了
class Solution {
public void moveZeroes(int[] nums) {
if(nums == null || nums.length == 0){
return;
}
int[] temp = new int[nums.length];
int j=0;
for(int i=0;i<nums.length;i++){
if(nums[i]!=0){
temp[j] = nums[i];
j++;
}
}
for(int i=0;i<nums.length;i++){
nums[i] = temp[i];
}
}
}
//双指针交换
class Solution {
public void moveZeroes(int[] nums) {
int start = 0;
for(int i=0;i<nums.length;i++){
if(nums[i] != 0){
int temp = nums[i];
nums[i] = nums[start];
nums[start] = temp;
start++;
}
}
}
}
//双指针解法(快慢指针) 优化上面交换方法，减少操作次数
class Solution {
public void moveZeroes(int[] nums) {
if(nums == null || nums.length == 0){
return;
}
int start = 0;
for(int i=0;i<nums.length;i++){
if(nums[i] != 0){
nums[start] = nums[i];
start++;
}
}
for(int i=start;i<nums.length;i++){
nums[i] = 0;
}
}
}
解题思路：
11. 盛最多水的容器
//给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i,
//ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
// 说明：你不能倾斜容器。
// 示例 1：
//输出：49
//解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
// 示例 2：
//输入：height = [1,1]
//输出：1
// 示例 3：
//输入：height = [4,3,2,1,4]
//输出：16
// 示例 4：
//输入：height = [1,2,1]
//输出：2
// 提示：
// n = height.length
// 2 <= n <= 3 * 104
// 0 <= height[i] <= 3 * 104
//
// Related Topics 数组 双指针
// 👍 2215 👎 0
//暴力破解，双层循环找出最大值
class Solution {
public int maxArea(int[] height) {
int maxCount = 0;
for(int i=0;i<height.length;i++){
for(int j=i+1;j<height.length;j++){
maxCount = Math.max(Math.min(height[i], height[j]) * (j - i), maxCount);
}
}
return maxCount;
}
}
//双指针解法
class Solution {
public int maxArea(int[] height) {
int maxCount = 0;
int left = 0;
int right = height.length - 1;
while (left < right) {
maxCount = Math.max(Math.min(height[left], height[right]) * (right - left), maxCount);
if (height[left] <= height[right]) {
++left;
}
else {
--right;
}
}
return maxCount;
}
}
70. 爬楼梯
二维数组及滚动数组
118. 杨辉三角
//给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
// 在杨辉三角中，每个数是它左上方和右上方的数的和。
// 示例:
// 输入: 5
//输出:
//[
// [1],
// [1,1],
// [1,2,1],
// [1,3,3,1],
// [1,4,6,4,1]
//]
// Related Topics 数组
// 👍 454 👎 0
//数学解法
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
for(int i=0;i<numRows;i++){
List<Integer> list = new ArrayList<>();
for(int j=0;j<=i;j++){
if(j==0 || j==i){
list.add(1);
}
else{
list.add(res.get(i-1).get(j-1)+res.get(i-1).get(j));
}
}
res.add(list);
}
return res;
}
}
119. 杨辉三角 II
//给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
// 在杨辉三角中，每个数是它左上方和右上方的数的和。
// 示例:
// 输入: 3
//输出: [1,3,3,1]
// 进阶：
// 你可以优化你的算法到 O(k) 空间复杂度吗？
// Related Topics 数组
// 👍 263 👎 0
class Solution {
public List<Integer> getRow(int rowIndex) {
List<List<Integer>> res = new ArrayList<>();
for(int i=0;i<=rowIndex;i++){
List<Integer> list = new ArrayList<>();
for(int j=0;j<=i;j++){
if(j==0 || j==i){
list.add(1);
}
else{
list.add(res.get(i-1).get(j-1)+res.get(i-1).get(j));
}
}
res.add(list);
}
return res.get(rowIndex);
}
}
数组的旋转
189. 旋转数组
//给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
// 进阶：
// 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
// 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
// 示例 1:
//输入: nums = [1,2,3,4,5,6,7], k = 3
//输出: [5,6,7,1,2,3,4]
//解释:
//向右旋转 1 步: [7,1,2,3,4,5,6]
//向右旋转 2 步: [6,7,1,2,3,4,5]
//向右旋转 3 步: [5,6,7,1,2,3,4]
// 示例 2:
//输入：nums = [-1,-100,3,99], k = 2
//输出：[3,99,-1,-100]
//解释:
//向右旋转 1 步: [99,-1,-100,3]
//向右旋转 2 步: [3,99,-1,-100]
// 提示：
// 1 <= nums.length <= 2 * 104
// -231 <= nums[i] <= 231 - 1
// 0 <= k <= 105
// Related Topics 数组
// 👍 880 👎 0
class Solution {
public void rotate(int[] nums, int k) {
}
}
字符串
520. 检测大写字母
//给定一个单词，你需要判断单词的大写使用是否正确。
// 我们定义，在以下情况时，单词的大写用法是正确的：
// 全部字母都是大写，比如"USA"。
// 单词中所有字母都不是大写，比如"leetcode"。
// 如果单词不只含有一个字母，只有首字母大写， 比如 "Google"。
// 否则，我们定义这个单词没有正确使用大写字母。
// 示例 1:
//输入: "USA"
//输出: True
// 示例 2:
//输入: "FlaG"
//输出: False
// 注意: 输入是由大写和小写拉丁字母组成的非空单词。
// Related Topics 字符串
// 👍 123 👎 0
//解题思路：字符串转字符串数组，判断大写个数，全大写，全小写校验通过，第一个字符大写，校验通过
class Solution {
public boolean detectCapitalUse(String word) {
int count = 0;
char[] chars = word.toCharArray();
for(int i=0;i<chars.length;i++){
if(chars[i]>='A' && chars[i] <= 'Z'){
count++;
}
}
return count==0 || count==chars.length || (count==1 && chars[0]>='A' && chars[0]<='Z');
}
}
125. 验证回文串
//给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
// 说明：本题中，我们将空字符串定义为有效的回文串。
// 示例 1:
// 输入: "A man, a plan, a canal: Panama"
//输出: true
// 示例 2:
// 输入: "race a car"
//输出: false
// Related Topics 双指针 字符串
// 👍 330 👎 0
//双指针解法
class Solution {
public boolean isPalindrome(String s) {
String s1 = s.toLowerCase().trim();
char[] chars = s1.toCharArray();
StringBuilder sb = new StringBuilder();
for(int i=0;i<chars.length;i++){
if((chars[i] >='a' && chars[i] <='z') || (chars[i]>='0' && chars[i]<='9')){
sb.append(chars[i]);
}
}
int j = sb.length()-1;
for(int i=0;i<sb.length();i++){
if(sb.charAt(i) != sb.charAt(j)){
return false;
}
j--;
}
return true;
}
}
14. 最长公共前缀
//编写一个函数来查找字符串数组中的最长公共前缀。
// 如果不存在公共前缀，返回空字符串 ""。
// 示例 1：
//输入：strs = ["flower","flow","flight"]
//输出："fl"
// 示例 2：
//输入：strs = ["dog","racecar","car"]
//输出：""
//解释：输入不存在公共前缀。
// 提示：
// 0 <= strs.length <= 200
// 0 <= strs[i].length <= 200
// strs[i] 仅由小写英文字母组成
// Related Topics 字符串
// 👍 1466 👎 0
//解题思路：纵向比较字符串的位置值是否相等
//flower
//flow
//flight
class Solution {
public String longestCommonPrefix(String[] strs) {
if(null == strs || strs.length==0){
return "";
}
for(int i=0;i<strs[0].length();i++){
char c = strs[0].charAt(i);
for(int j=1;j<strs.length;j++){
if(i== strs[j].length() || strs[j].charAt(i) != c){
return strs[0].substring(0,i);
}
}
}
return strs[0];
}
}
434. 字符串中的单词数
//统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。
// 请注意，你可以假定字符串里不包括任何不可打印的字符。
// 示例:
// 输入: "Hello, my name is John"
//输出: 5
//解释: 这里的单词是指连续的不是空格的字符，所以 "Hello," 算作 1 个单词。
// Related Topics 字符串
// 👍 77 👎 0
class Solution {
public int countSegments(String s) {
int count = 0;
if(s.length()==0 || s.equals("")){
return 0;
}
for (int i = 0; i < s.length(); i++) {
if ((i == 0 || s.charAt(i - 1) == ' ') && s.charAt(i) != '') {
count++;
}
}
return count;
}
}
解题思路：计算单词的数量，就等同于计数单词开始的下标个数。因此，只需要定义好下标的条件，就可以遍历整个字符串，检测每个下标。定义如下：若该下标前为空格（或者为初始下标），且自身不为空格，则其为单词开始的下标。该条件可以以常数时间检测。最后，返回满足条件的下标个数。
58. 最后一个单词的长度
//给你一个字符串 s，由若干单词组成，单词之间用空格隔开。返回字符串中最后一个单词的长度。如果不存在最后一个单词，请返回 0 。
// 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
// 示例 1：
//输入：s = "Hello World"
//输出：5
// 示例 2：
//输入：s = " "
//输出：0
// 提示：
// 1 <= s.length <= 104
// s 仅有英文字母和空格 ' ' 组成
//
// Related Topics 字符串
// 👍 280 👎 0
//字符串分割法
class Solution {
public int lengthOfLastWord(String s) {
if(s==null || s=="" || s.length()==0){
return 0;
}
String[] s1 = s.split(" ");
if(s1.length ==0){
return 0;
}
return s1[s1.length-1].length();
}
}
//从尾部开始遍历字符串
class Solution {
public int lengthOfLastWord(String s) {
int count = 0;
if(s==null || s=="" || s.length()==0){
return 0;
}
for(int i=0;i<s.length();i++){
char k = s.charAt(s.length()-1-i);
if(k != ' '){
count++;
}
if(count>0 && k == ' '){
break;
}
}
return count;
}
}
344. 反转字符串
//编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
// 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
// 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
// 示例 1：
// 输入：["h","e","l","l","o"]
//输出：["o","l","l","e","h"]
// 示例 2：
// 输入：["H","a","n","n","a","h"]
//输出：["h","a","n","n","a","H"]
// Related Topics 双指针 字符串
// 👍 358 👎 0
//暴力破解，双层循环交换
class Solution {
public void reverseString(char[] s) {
if(s==null || s.length==0){
return;
}
for (int i = 0; i < s.length; i++) {
for (int j = i + 1;j<s.length; j++) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
}
}
//双指针解法
class Solution {
public void reverseString(char[] s) {
if(s==null || s.length==0){
return;
}
int left = 0;
int right = s.length-1;
while (left<right){
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
}
541. 反转字符串 II
//给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。
// 如果剩余字符少于 k 个，则将剩余字符全部反转。
// 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
// 示例:
// 输入: s = "abcdefg", k = 2
//输出: "bacdfeg"
// 提示：
// 该字符串只包含小写英文字母。
// 给定字符串的长度和 k 在 [1, 10000] 范围内。
// Related Topics 字符串
// 👍 116 👎 0
class Solution {
public String reverseStr(String s, int k) {
char[] chars = s.toCharArray();
for(int start = 0;start<chars.length;start = start+(2*k)){
int i= start;
int j= Math.min(start+k-1,chars.length-1);
while (i<j){
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
i++;
j--;
}
}
return new String(chars);
}
}
557. 反转字符串中的单词 III
//给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
// 示例：
// 输入："Let's take LeetCode contest"
//输出："s'teL ekat edoCteeL tsetnoc"
// 提示：
// 在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
// Related Topics 字符串
// 👍 274 👎 0
//暴力破解
class Solution {
public String reverseWords(String s) {
if(s==null || s.length()==0 || s==""){
return "";
}
String[] ans = s.split(" ");
StringBuilder result = new StringBuilder();
for(int i=0;i<ans.length;i++){
String s1 = ans[i];
for(int j=0;j<s1.length();j++){
result.append(s1.charAt(s1.length()-1-j));
}
if(i !=ans.length-1){
result.append(" ");
}
}
return result.toString();
}
}
151. 翻转字符串里的单词
//给定一个字符串，逐个翻转字符串中的每个单词。
// 说明：
// 无空格字符构成一个 单词 。
// 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
// 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
// 示例 1：
// 输入："the sky is blue"
//输出："blue is sky the"
// 示例 2：
// 输入：" hello world! "
//输出："world! hello"
//解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
// 示例 3：
// 输入："a good example"
//输出："example good a"
//解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
// 示例 4：
// 输入：s = " Bob Loves Alice "
//输出："Alice Loves Bob"
// 示例 5：
// 输入：s = "Alice does not even like bob"
//输出："bob like even not does Alice"
// 提示：
// 1 <= s.length <= 104
// s 包含英文大小写字母、数字和空格 ' '
// s 中 至少存在一个 单词
// 进阶：
// 请尝试使用 O(1) 额外空间复杂度的原地解法。
// Related Topics 字符串
// 👍 281 👎 0
class Solution {
public String reverseWords(String s) {
if(s == null || s.length() == 0){
return null;
}
StringBuilder result = new StringBuilder();
String[] s1 = s.split(" ");
for(int i=s1.length-1;i>=0;i--){
if(s1[i] == null || s1[i].length() == 0){
continue;
}
result.append(s1[i]).append(" ");
}
return result.toString().trim();
}
}
387. 字符串中的第一个唯一字符
//给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
// 示例：
// s = "leetcode"
//返回 0
//s = "loveleetcode"
//返回 2
// 提示：你可以假定该字符串只包含小写字母。
// Related Topics 哈希表 字符串
// 👍 351 👎 0
//暴露解法 超时
class Solution {
public int firstUniqChar(String s) {
for(int i=0;i<s.length();i++){
int count = 0;
char ans = s.charAt(i);
for(int j=0;j<s.length();j++){
if(s.charAt(j) == ans){
count++;
}
}
if(count == 1){
return i;
}
}
return -1;
}
}
//HashMap 计数
class Solution {
public int firstUniqChar(String s) {
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
Integer integer = map.get(s.charAt(i));
if (null == integer || integer == 0) {
map.put(s.charAt(i), 1);
} else {
map.put(s.charAt(i), integer + 1);
}
}
for (int i = 0; i < s.length(); i++) {
if (map.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
}
389. 找不同
//给定两个字符串 s 和 t，它们只包含小写字母。
// 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
// 请找出在 t 中被添加的字母。
// 示例 1：
// 输入：s = "abcd", t = "abcde"
//输出："e"
//解释：'e' 是那个被添加的字母。
// 示例 2：
// 输入：s = "", t = "y"
//输出："y"
// 示例 3：
// 输入：s = "a", t = "aa"
//输出："a"
// 示例 4：
// 输入：s = "ae", t = "aea"
//输出："a"
// 提示：
// 0 <= s.length <= 1000
// t.length == s.length + 1
// s 和 t 只包含小写字母
// Related Topics 位运算 哈希表
// 👍 235 👎 0
//解题思路1：HashMap 分别统计s、t字母个数，遍历t,如果字母个数不相等，则返回字母。
class Solution {
public char findTheDifference(String s, String t) {
Map<Character,Integer> map = new HashMap<>();
for(int i=0;i<s.length();i++){
Integer integer = map.get(s.charAt(i));
if (null == integer || integer == 0) {
map.put(s.charAt(i), 1);
} else {
map.put(s.charAt(i), integer + 1);
}
}
Map<Character,Integer> map1 = new HashMap<>();
for(int i=0;i<t.length();i++){
Integer integer = map1.get(t.charAt(i));
if (null == integer || integer == 0) {
map1.put(t.charAt(i), 1);
} else {
map1.put(t.charAt(i), integer + 1);
}
}
for(int i=0;i<t.length();i++){
if(map.get(t.charAt(i)) != map1.get(t.charAt(i))){
return t.charAt(i);
}
}
return ' ';
}
}
//解法2：将字符串 *s* 中每个字符的 ASCII 码的值求和，得到 *A_s*；对字符串 *t* 同样的方法得到 *A_t*。两者的差值 *A_t-A_s* 即代表了被添加的字符。
class Solution {
public char findTheDifference(String s, String t) {
int anst = 0; int anss = 0;
for(int i=0;i<s.length();i++){
anss = anss + s.charAt(i);
}
for(int i=0;i<t.length();i++){
anst = anst+t.charAt(i);
}
return (char)(anst - anss);
}
}
//把字符串s和t合并，然后遍历合并的每个字符，判断集合set中是否有这个字符，如果有就移除，否则就加入到集合set中。最后集合set中只有一个字符，这个字符就是我们要求的。
class Solution {
public char findTheDifference(String s, String t) {
Set<Character> set = new HashSet<>();
char[] charArr = s.concat(t).toCharArray();
for (int i = 0; i < charArr.length; i++) {
if (set.contains(charArr[i]))
set.remove(charArr[i]);
else
set.add(charArr[i]);
}
return (char) set.toArray()[0];
}
}
383. 赎金信
//给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面
//的字符构成。如果可以构成，返回 true ；否则返回 false。
// (题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
// 注意：
// 你可以假设两个字符串均只含有小写字母。
// canConstruct("a", "b") -> false
//canConstruct("aa", "ab") -> false
//canConstruct("aa", "aab") -> true
// Related Topics 字符串
// 👍 135 👎 0
//HashMap 分别统计赎金与杂志里的字符个数，如果杂志里没有赎金里的字符或者赎金里的字符个数大于杂志里的字符个数，返回false,不然返回true
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
HashMap<Character, Integer> mMap = new HashMap<>();
HashMap<Character, Integer> rMap = new HashMap<>();
for (int i = 0; i < magazine.length(); i++) {
Integer count = mMap.get(magazine.charAt(i));
if (count == null || count == 0) {
mMap.put(magazine.charAt(i), 1);
} else {
mMap.put(magazine.charAt(i), count + 1);
}
}
for (int i = 0; i < ransomNote.length(); i++) {
Integer count = rMap.get(ransomNote.charAt(i));
if (count == null || count == 0) {
rMap.put(ransomNote.charAt(i), 1);
} else {
rMap.put(ransomNote.charAt(i), count + 1);
}
}
for (int i = 0; i < ransomNote.length(); i++) {
char ans = ransomNote.charAt(i);
if (mMap.get(ans) == null) {
return false;
}
if (mMap.get(ans) != null && rMap.get(ans) != null) {
if (rMap.get(ans) > mMap.get(ans)) {
return false;
}
}
}
return true;
}
}
242. 有效的字母异位词
//给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
// 示例 1:
// 输入: s = "anagram", t = "nagaram"
//输出: true
// 示例 2:
// 输入: s = "rat", t = "car"
//输出: false
// 说明:
//你可以假设字符串只包含小写字母。
// 进阶:
//如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
// Related Topics 排序 哈希表
// 👍 345 👎 0
//HashMap 统计单次个数
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()){
return false;
}
Map<Character,Integer> sMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0) + 1);
}
for(int i=0;i<t.length();i++){
Integer nums = sMap.get(t.charAt(i));
if(nums != null){
sMap.put(t.charAt(i),nums-1);
}
for(int i=0;i<s.length();i++){
if(sMap.get(s.charAt(i)) != 0){
return false;
}
}
return true;
}
}
//解法2 使用数组保存字母个数，由于内存是连续的，-'a' 表示对应字母索引个数
class Solution {
public boolean isAnagram(String s, String t) {
int[] ans = new int[26];
if (s.length() != t.length()) {
return false;
}
for(int i=0;i<s.length();i++){
ans[s.charAt(i)-'a'] = ans[s.charAt(i)-'a'] +1;
}
for(int i=0;i<t.length();i++){
ans[t.charAt(i)-'a'] = ans[t.charAt(i)-'a'] -1;
if(ans[t.charAt(i)-'a'] <0){
return false;
}
}
return true;
}
}
49. 字母异位词分组
//给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
// 示例:
// 输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
//输出:
//[
// ["ate","eat","tea"],
// ["nat","tan"],
// ["bat"]
//]
// 说明：
// 所有输入均为小写字母。
// 不考虑答案输出的顺序。
// Related Topics 哈希表 字符串
// 👍 668 👎 0
//HashMap 解法
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<>();
for(int i=0;i<strs.length;i++){
char[] chars = strs[i].toCharArray();
Arrays.sort(chars);
String key = new String(chars);
List<String> list = map.get(key);
if(list == null || list.size() == 0){
list = new ArrayList<>();
}
list.add(strs[i]);
map.put(key,list);
}
return new ArrayList<>(map.values());
}
}
//Java8写法
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
return new ArrayList<>(Arrays.stream(strs)
.collect(Collectors.groupingBy(str -> {
// 返回 str 排序后的结果。
// 按排序后的结果来grouping by，算子类似于 sql 里的 group by。
char[] array = str.toCharArray();
Arrays.sort(array);
return new String(array);
})).values());
}
}
//一行代码
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(str -> str.chars().sorted().collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString())).values());
}
}
451. 根据字符出现频率排序
//给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
// 示例 1:
//输入:
//"tree"
//输出:
//"eert"
//解释:
//'e'出现两次，'r'和't'都只出现一次。
//因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
// 示例 2:
//输入:
//"cccaaa"
//输出:
//"cccaaa"
//解释:
//'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
//注意"cacaca"是不正确的，因为相同的字母必须放在一起。
// 示例 3:
//输入:
//"Aabb"
//输出:
//"bbAa"
//解释:
//此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
//注意'A'和'a'被认为是两种不同的字符。
// Related Topics 堆 哈希表
// 👍 220 👎 0
class Solution {
public String frequencySort(String s) {
Map<Character,Integer> map = new HashMap<>();
int[] ans = new int[s.length()];
StringBuilder sb = new StringBuilder();
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<s.length();i++){
Integer num = map.get(s.charAt(i));
ans[i] = num;
}
Arrays.sort(ans);
for(int i=ans.length;i>0;i--){
for(int j=0;j<s.length();j++){
if(map.get(s.charAt(j)) == i){
sb.append(s.charAt(j));
}
}
}
return sb.toString();
}
}
423. 从英文中重建数字
//给定一个非空字符串，其中包含字母顺序打乱的英文单词表示的数字0-9。按升序输出原始的数字。
// 注意:
// 输入只包含小写英文字母。
// 输入保证合法并可以转换为原始的数字，这意味着像 "abc" 或 "zerone" 的输入是不允许的。
// 输入字符串的长度小于 50,000。
// 示例 1:
//输入: "owoztneoer"
//输出: "012" (zeroonetwo)
// 示例 2:
//输入: "fviefuro"
//输出: "45" (fourfive)
// Related Topics 数学
// 👍 56 👎 0
class Solution {
public String originalDigits(String s) {
}
}
657. 机器人能否返回原点
//在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。
// 移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。如果机器人在完成所有动作后
//返回原点，则返回 true。否则，返回 false。
// 注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。
// 示例 1:
// 输入: "UD"
//输出: true
//解释：机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。
// 示例 2:
// 输入: "LL"
//输出: false
//解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。
// Related Topics 字符串
// 👍 189 👎 0
class Solution {
public boolean judgeCircle(String moves) {
int x =0;
int y=0;
for(int i=0;i<moves.length();i++){
if(moves.charAt(i) == 'L'){
x--;
}
if(moves.charAt(i) == 'R'){
x++;
}
if(moves.charAt(i) == 'U'){
y--;
}
if(moves.charAt(i) == 'D'){
y++;
}
}
return x==0 && y==0;
}
}
551. 学生出勤记录 I
//给定一个字符串来代表一个学生的出勤记录，这个记录仅包含以下三个字符：
// 'A' : Absent，缺勤
// 'L' : Late，迟到
// 'P' : Present，到场
// 如果一个学生的出勤记录中不超过一个'A'(缺勤)并且不超过两个连续的'L'(迟到),那么这个学生会被奖赏。
// 你需要根据这个学生的出勤记录判断他是否会被奖赏。
// 示例 1:
// 输入: "PPALLP"
//输出: True
// 示例 2:
// 输入: "PPALLL"
//输出: False
// Related Topics 字符串
// 👍 69 👎 0
class Solution {
public boolean checkRecord(String s) {
Map<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);
}
if(map.get('A') == null || map.get('A')<=1){
if(map.get('L') ==null || map.get('L') <=2){
return true;
}
for(int i=2;i<s.length();i++){
if(s.charAt(i) == 'L' && s.charAt(i-1) == 'L' && s.charAt(i-2) == 'L'){
return false;
}
}
return true;
}
return false;
}
}
//优化时间复杂度
class Solution {
public boolean checkRecord(String s) {
int aCount = 0;
int lCount = 0;
for(int i=0;i<s.length();i++){
if(s.charAt(i) == 'A'){
lCount = 0;
aCount++;
if(aCount>1){
return false;
}
}
else if(s.charAt(i) == 'L'){
lCount++;
if(lCount>2){
return false;
}
}
else{
lCount = 0;
}
}
return true;
}
}
//一行代码解决
class Solution {
public boolean checkRecord(String s) {
return s.indexOf("A") == s.lastIndexOf("A") && !s.contains("LLL");
}
}
696. 计数二进制子串
//给定一个字符串 s，计算具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是连续的。
// 重复出现的子串要计算它们出现的次数。
// 示例 1 :
//输入: "00110011"
//输出: 6
//解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
//请注意，一些重复出现的子串要计算它们出现的次数。
//另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
// 示例 2 :
//输入: "10101"
//输出: 4
//解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
// 提示：
// s.length 在1到50,000之间。
// s 只包含“0”或“1”字符。
// Related Topics 字符串
// 👍 336 👎 0
class Solution {
public int countBinarySubstrings(String s) {
}
}
535. TinyURL 的加密与解密
//TinyURL是一种URL简化服务， 比如：当你输入一个URL https://leetcode.com/problems/design-tinyurl 时
//，它将返回一个简化的URL http://tinyurl.com/4e9iAk.
// 要求：设计一个 TinyURL 的加密 encode 和解密 decode 的方法。你的加密和解密算法如何设计和运作是没有限制的，你只需要保证一个URL可
//以被加密成一个TinyURL，并且这个TinyURL可以用解密方法恢复成原本的URL。
// Related Topics 哈希表 数学
// 👍 113 👎 0
public class Codec {
Map<String,String> map = new HashMap<>();
// Encodes a URL to a shortened URL.
public String encode(String longUrl) {
map.put(Integer.toHexString(longUrl.hashCode()),longUrl);
return Integer.toHexString(longUrl.hashCode());
}
// Decodes a shortened URL to its original URL.
public String decode(String shortUrl) {
return map.get(shortUrl);
}
}
299. 猜数字游戏
//你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：
// 你写出一个秘密数字，并请朋友猜这个数字是多少。
// 朋友每猜测一次，你就会给他一个提示，告诉他的猜测数字中有多少位属于数字和确切位置都猜对了（称为“Bulls”, 公牛），有多少位属于数字猜对了但是位置不对
//（称为“Cows”, 奶牛）。
// 朋友根据提示继续猜，直到猜出秘密数字。
// 请写出一个根据秘密数字和朋友的猜测数返回提示的函数，返回字符串的格式为 xAyB ，x 和 y 都是数字，A 表示公牛，用 B 表示奶牛。
// xA 表示有 x 位数字出现在秘密数字中，且位置都与秘密数字一致。
// yB 表示有 y 位数字出现在秘密数字中，但位置与秘密数字不一致。
// 请注意秘密数字和朋友的猜测数都可能含有重复数字，每位数字只能统计一次。
// 示例 1:
// 输入: secret = "1807", guess = "7810"
//输出: "1A3B"
//解释: 1 公牛和 3 奶牛。公牛是 8，奶牛是 0, 1 和 7。
// 示例 2:
// 输入: secret = "1123", guess = "0111"
//输出: "1A1B"
//解释: 朋友猜测数中的第一个 1 是公牛，第二个或第三个 1 可被视为奶牛。
// 说明: 你可以假设秘密数字和朋友的猜测数都只包含数字，并且它们的长度永远相等。
// Related Topics 哈希表
// 👍 119 👎 0
class Solution {
public String getHint(String secret, String guess) {
int[] nums = new int[10];
int countA = 0, countB = 0;
for (int i = 0; i < secret.length(); i++) {
if(secret.charAt(i) == guess.charAt(i)) countA++;
else{
if (nums[guess.charAt(i) - '0']-- > 0) countB++;
if(nums[secret.charAt(i) - '0']++ < 0) countB++;
}
}
return countA + "A" + countB + "B";
}
}
412. Fizz Buzz
//写一个程序，输出从 1 到 n 数字的字符串表示。
// 1. 如果 n 是3的倍数，输出“Fizz”；
// 2. 如果 n 是5的倍数，输出“Buzz”；
// 3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。
// 示例：
// n = 15,
//返回:
//[
// "1",
// "2",
// "Fizz",
// "4",
// "Buzz",
// "Fizz",
// "7",
// "8",
// "Fizz",
// "Buzz",
// "11",
// "Fizz",
// "13",
// "14",
// "FizzBuzz"
//]
//
// 👍 85 👎 0
class Solution {
public List<String> fizzBuzz(int n) {
String[] res = new String[n];
for (int i = 1; i < n; i++) {
if (i % 3 == 0 && i % 5 != 0) {
res[i] = "Fizz";
} else if (i % 5 == 0 && !i % 3 != 0) {
res[i] = "Buzz";
} else if (i % 5 == 0 && i % 3 == 0) {
res[i] = "FizzBuzz";
} else {
res[i] = String.valueOf(i);
}
}
return res;
}
}
506. 相对名次
//给出 N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”（"Gold Medal",
// "Silver Medal", "Bronze Medal"）。
// (注：分数越高的选手，排名越靠前。)
// 示例 1:
//输入: [5, 4, 3, 2, 1]
//输出: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
//解释: 前三名运动员的成绩为前三高的，因此将会分别被授予 “金牌”，“银牌”和“铜牌” ("Gold Medal", "Silver Medal" and
//"Bronze Medal").
//余下的两名运动员，我们只需要通过他们的成绩计算将其相对名次即可。
// 提示:
// N 是一个正整数并且不会超过 10000。
// 所有运动员的成绩都不相同。
//
// 👍 70 👎 0
//先拷贝原数组，再排序后使用HashMap记录对应的名次
import java.util.Arrays;
import java.util.HashMap;
class Solution {
public String[] findRelativeRanks(int[] score) {
int[] newScore = new int[score.length];
String[] res = new String[score.length];
for(int i=0;i<score.length;i++){
newScore[i] = score[i];
}
Map<String,Integer> map = new HashMap<>();
Arrays.sort(score);
for(int i=0;i<score.length;i++){
map.put(String.valueOf(score[i]),score.length-i);
}
for(int i=0;i<newScore.length;i++){
Integer count = map.get(String.valueOf(newScore[i]));
if(count == 1){
res[i] = "Gold Medal";
}
else if(count == 2){
res[i] = "Silver Medal";
}
else if(count == 3){
res[i] = "Bronze Medal";
}
else{
res[i] = String.valueOf(count);
}
}
return res;
}
}
539. 最小时间差
//给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
// 示例 1：
//输入：timePoints = ["23:59","00:00"]
//输出：1
// 示例 2：
//输入：timePoints = ["00:00","23:59","00:00"]
//输出：0
// 提示：
// 2 <= timePoints <= 2 * 104
// timePoints[i] 格式为 "HH:MM"
// Related Topics 字符串
// 👍 82 👎 0
class Solution {
public int findMinDifference(List<String> timePoints) {
if (timePoints.size() > 1440) {
return 0;
}
int[] timeCount = new int[timePoints.size()];
int min = Integer.MAX_VALUE;;
for(int i=0;i<timePoints.size();i++){
String[] timeStr = timePoints.get(i).split(":");
timeCount[i] = Integer.valueOf(timeStr[0])*60+Integer.valueOf(timeStr[1]);
}
Arrays.sort(timeCount);
//排序后相邻相减有最小值
for(int i=1;i<timeCount.length;i++){
min = Math.min(min, timeCount[i] - timeCount[i - 1]);
}
return Math.min(min,timeCount[0]+1440-timeCount[timeCount.length-1]);
}
}
553. 最优除法
//给定一组正整数，相邻的整数之间将会进行浮点除法操作。例如， [2,3,4] -> 2 / 3 / 4 。
// 但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，才能得到最大的结果，并且返回相应的字符串格式的表达式。你的表达式不应
//该含有冗余的括号。
// 示例：
//输入: [1000,100,10,2]
//输出: "1000/(100/10/2)"
//解释:
//1000/(100/10/2) = 1000/((100/10)/2) = 200
//但是，以下加粗的括号 "1000/((100/10)/2)" 是冗余的，
//因为他们并不影响操作的优先级，所以你需要返回 "1000/(100/10/2)"。
//其他用例:
//1000/(100/10)/2 = 50
//1000/(100/(10/2)) = 50
//1000/100/10/2 = 0.5
//1000/100/(10/2) = 2
// 说明:
// 输入数组的长度在 [1, 10] 之间。
// 数组中每个元素的大小都在 [2, 1000] 之间。
// 每个测试用例只有一个最优除法解。
// Related Topics 数学 字符串
// 👍 63 👎 0
//除数最大，被除数最小得最大
class Solution {
public String optimalDivision(int[] nums) {
StringBuilder sb = new StringBuilder();
if(nums.length == 1){
return nums[0]+"";
}
if(nums.length == 2){
return nums[0]+"/"+nums[1];
}
sb.append(nums[0]).append("/(").append(nums[1]);
for(int i=2;i<nums.length;i++){
sb.append("/").append(nums[i]);
}
sb.append(")");
return sb.toString();
}
}
//特殊处理
class Solution {
public String optimalDivision(int[] nums) {
StringBuilder sb = new StringBuilder();
if(nums.length==1){
return nums[0]+"";
}
if(nums.length==2){
return nums[0]+"/"+nums[1];
}
for(int i=0;i<nums.length;i++){
sb.append(nums[i]);
if(i<nums.length-1){
sb.append("/");
}
if(i==0){
sb.append("(");
}
}
sb.append(")");
return sb.toString();
}
}
537. 复数乘法
//给定两个表示复数的字符串。
// 返回表示它们乘积的字符串。注意，根据定义 i2 = -1 。
// 示例 1:
//输入: "1+1i", "1+1i"
//输出: "0+2i"
//解释: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i ，你需要将它转换为 0+2i 的形式。
// 示例 2:
//输入: "1+-1i", "1+-1i"
//输出: "0+-2i"
//解释: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i ，你需要将它转换为 0+-2i 的形式。
// 注意:
// 输入字符串不包含额外的空格。
// 输入字符串将以 a+bi 的形式给出，其中整数 a 和 b 的范围均在 [-100, 100] 之间。输出也应当符合这种形式。
// Related Topics 数学 字符串
// 👍 52 👎 0
//复数乘法公式 (a+b*i)*(c+d*i) = (a*c-b*d)+(b*c+a*d)*i
class Solution {
public String complexNumberMultiply(String a, String b) {
StringBuilder sb = new StringBuilder();
String[] aStr = a.split("\\+");
String[] bStr = b.split("\\+");
Integer ans = (Integer.valueOf(aStr[0])*Integer.valueOf(bStr[0]))- (Integer.valueOf(aStr[1].split("i")[0])*Integer.valueOf(bStr[1].split("i")[0]));
Integer ans1 = (Integer.valueOf(aStr[1].split("i")[0])*Integer.valueOf(bStr[0])) + (Integer.valueOf(Integer.valueOf(aStr[0]) * (Integer.valueOf(bStr[1].split("i")[0]))));
return sb.append(ans).append("+").append(ans1).append("i").toString();
}
}
592. 分数加减运算
//给定一个表示分数加减运算表达式的字符串，你需要返回一个字符串形式的计算结果。 这个结果应该是不可约分的分数，即最简分数。 如果最终结果是一个整数，例如 2，
//你需要将它转换成分数形式，其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。
// 示例 1:
//输入:"-1/2+1/2"
//输出: "0/1"
// 示例 2:
//输入:"-1/2+1/2+1/3"
//输出: "1/3"
// 示例 3:
//输入:"1/3-1/2"
//输出: "-1/6"
// 示例 4:
//输入:"5/3+1/3"
//输出: "2/1"
// 说明:
// 输入和输出字符串只包含 '0' 到 '9' 的数字，以及 '/', '+' 和 '-'。
// 输入和输出分数格式均为 ±分子/分母。如果输入的第一个分数或者输出的分数是正数，则 '+' 会被省略掉。
// 输入只包含合法的最简分数，每个分数的分子与分母的范围是 [1,10]。 如果分母是1，意味着这个分数实际上是一个整数。
// 输入的分数个数范围是 [1,10]。
// 最终结果的分子与分母保证是 32 位整数范围内的有效整数。
// Related Topics 数学
// 👍 40 👎 0
class Solution {
public String fractionAddition(String expression) {
}
}
38. 外观数列
//给定一个正整数 n ，输出外观数列的第 n 项。
// 「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
// 你可以将其视作是由递归公式定义的数字字符串序列：
// countAndSay(1) = "1"
// countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
// 前五项如下：
//1. 1
//2. 11
//3. 21
//4. 1211
//5. 111221
//第一项是数字 1
//描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
//描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
//描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
//描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
// 要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成
//一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。
// 例如，数字字符串 "3322251" 的描述如下图：
// 示例 1：
//输入：n = 1
//输出："1"
//解释：这是一个基本样例。
// 示例 2：
//输入：n = 4
//输出："1211"
//解释：
//countAndSay(1) = "1"
//countAndSay(2) = 读 "1" = 一 个 1 = "11"
//countAndSay(3) = 读 "11" = 二 个 1 = "21"
//countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
// 提示：
// 1 <= n <= 30
// Related Topics 字符串
// 👍 644 👎 0
class Solution {
public String countAndSay(int n) {
}
}
443. 压缩字符串
//给定一组字符，使用原地算法将其压缩。
// 压缩后的长度必须始终小于或等于原数组长度。
// 数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。
// 在完成原地修改输入数组后，返回数组的新长度。
// 进阶：
//你能否仅使用O(1) 空间解决问题？
// 示例 1：
// 输入：
//["a","a","b","b","c","c","c"]
//输出：
//返回 6 ，输入数组的前 6 个字符应该是：["a","2","b","2","c","3"]
//说明：
//"aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。
// 示例 2：
// 输入：
//["a"]
//输出：
//返回 1 ，输入数组的前 1 个字符应该是：["a"]
//解释：
//没有任何字符串被替代。
// 示例 3：
// 输入：
//["a","b","b","b","b","b","b","b","b","b","b","b","b"]
//输出：
//返回 4 ，输入数组的前4个字符应该是：["a","b","1","2"]。
//解释：
//由于字符 "a" 不重复，所以不会被压缩。"bbbbbbbbbbbb" 被 “b12” 替代。
//注意每个数字在数组中都有它自己的位置。
// 提示：
// 所有字符都有一个ASCII值在[35, 126]区间内。
// 1 <= len(chars) <= 1000。
// Related Topics 字符串
// 👍 165 👎 0
class Solution {
public int compress(char[] chars) {
}
}
8. 字符串转换整数 (atoi)
//请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
// 函数 myAtoi(string s) 的算法如下：
// 读入字符串并丢弃无用的前导空格
// 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
// 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
// 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤
//2 开始）。
// 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固
//定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
// 返回整数作为最终结果。
// 注意：
//输入：s = "42"
//输出：42
//解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
//第 1 步："42"（当前没有读入字符，因为没有前导空格）
// ^
//第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
// ^
//第 3 步："42"（读入 "42"）
// ^
//解析得到整数 42 。
//由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。
//
// 示例 2：
//输入：s = " -42"
//输出：-42
//解释：
//第 1 步：" -42"（读入前导空格，但忽视掉）
// ^
//第 2 步：" -42"（读入 '-' 字符，所以结果应该是负数）
// ^
//第 3 步：" -42"（读入 "42"）
// ^
//解析得到整数 -42 。
//由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。
// 示例 3：
//输入：s = "4193 with words"
//输出：4193
//解释：
//第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
// ^
//第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
// ^
//第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
// ^
//解析得到整数 4193 。
//由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。
// 示例 4：
//输入：s = "words and 987"
//输出：0
//解释：
//第 1 步："words and 987"（当前没有读入字符，因为没有前导空格）
// ^
//第 2 步："words and 987"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
// ^
//第 3 步："words and 987"（由于当前字符 'w' 不是一个数字，所以读入停止）
// ^
//解析得到整数 0 ，因为没有读入任何数字。
//由于 0 在范围 [-231, 231 - 1] 内，最终结果为 0 。
// 示例 5：
//输入：s = "-91283472332"
//输出：-2147483648
//解释：
//第 1 步："-91283472332"（当前没有读入字符，因为没有前导空格）
// ^
//第 2 步："-91283472332"（读入 '-' 字符，所以结果应该是负数）
// ^
//第 3 步："-91283472332"（读入 "91283472332"）
// ^
//解析得到整数 -91283472332 。
//由于 -91283472332 小于范围 [-231, 231 - 1] 的下界，最终结果被截断为 -231 = -2147483648 。
// 提示：
// 0 <= s.length <= 200
// s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成
// Related Topics 数学 字符串
// 👍 1006 👎 0
class Solution {
public int myAtoi(String s) {
StringBuilder sb = new StringBuilder();
try{
String sStr = s.trim();
for (int i = 0; i < sStr.length(); i++) {
if (i==0 &&(sStr.charAt(0) == '-' || sStr.charAt(0) == '+')) {
sb.append(sStr.charAt(0));
continue;
}
if (Character.isDigit(sStr.charAt(i))) {
sb.append(sStr.charAt(i));
} else {
break;
}
}
if (sb.length() == 0 || (sb.length()==1 && (sb.toString().contains("+") || sb.toString().contains("-")))) {
return 0;
}
return Integer.valueOf(sb.toString());
}
catch (Exception e){
if(sb.toString().contains("+") || !sb.toString().contains("-")){
return 2147483647;
}
if(sb.toString().contains("-") || !sb.toString().contains("+")){
return -2147483648;
}
return 0;
}
}
}
13. 罗马数字转整数
//罗马数字包含以下七种字符: 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 + I
//I 。
// 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 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 的范围内。
// 示例 1:
//输入: "III"
//输出: 3
// 示例 2:
//输入: "IV"
//输出: 4
// 示例 3:
//输入: "IX"
//输出: 9
// 示例 4:
//输入: "LVIII"
//输出: 58
//解释: L = 50, V= 5, III = 3.
// 示例 5:
//输入: "MCMXCIV"
//输出: 1994
//解释: M = 1000, CM = 900, XC = 90, IV = 4.
// 提示：
// 1 <= s.length <= 15
// s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
// 题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
// 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
// IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
// 关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。
//
// Related Topics 数学 字符串
// 👍 1215 👎 0
class Solution {
public int romanToInt(String s) {
Map<Character, Integer> map = new HashMap<>();
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (i < s.length() - 1 && (map.get(s.charAt(i)) < map.get(s.charAt(i + 1)))) {
count = count + (map.get(s.charAt(i + 1)) - map.get(s.charAt(i)));
i++;
} else {
count = count + map.get(s.charAt(i));
}
}
return count;
}
}
12. 整数转罗马数字
//罗马数字包含以下七种字符： 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 + I
//I 。
// 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 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 的范围内。
// 示例 1:
//输入: 3
//输出: "III"
// 示例 2:
//输入: 4
//输出: "IV"
// 示例 3:
//输入: 9
//输出: "IX"
// 示例 4:
//输入: 58
//输出: "LVIII"
//解释: L = 50, V = 5, III = 3.
// 示例 5:
//输入: 1994
//输出: "MCMXCIV"
//解释: M = 1000, CM = 900, XC = 90, IV = 4.
// 提示：
// 1 <= num <= 3999
// Related Topics 数学 字符串
// 👍 502 👎 0
//穷举
class Solution {
public String intToRoman(int num) {
StringBuilder sb = new StringBuilder();
int mNum = num/1000;
num = num - (mNum*1000);
for(int i=0;i<mNum;i++){
sb.append("M");
}
int cmNum = num/900;
num = num - (cmNum*900);
for(int i=0;i<cmNum;i++){
sb.append("CM");
}
int dNum = num/500;
num = num - (dNum*500);
for(int i=0;i<dNum;i++){
sb.append("D");
}
int cdNum = num/400;
num = num - (cdNum*400);
for(int i=0;i<cdNum;i++){
sb.append("CD");
}
int cNum = num/100;
num = num - (cNum*100);
for(int i=0;i<cNum;i++){
sb.append("C");
}
int xcNum = num/90;
num = num - (xcNum*90);
for(int i=0;i<xcNum;i++){
sb.append("XC");
}
int lNum = num/50;
num = num - (lNum*50);
for(int i=0;i<lNum;i++){
sb.append("L");
}
int xlNum = num/40;
num = num - (xlNum*40);
for(int i=0;i<xlNum;i++){
sb.append("XL");
}
int xNum = num/10;
num = num-(xNum*10);
for(int i=0;i<xNum;i++){
sb.append("X");
}
int ixNum = num/9;
num = num - (ixNum*9);
for(int i=0;i<ixNum;i++){
sb.append("IX");
}
int vNum = num/5;
num = num - (vNum*5);
for(int i=0;i<vNum;i++){
sb.append("V");
}
int ivNum = num/4;
num = num - (ivNum*4);
for(int i=0;i<ivNum;i++){
sb.append("IV");
}
int iNum = num/1;
num = num - (ivNum*1);
for(int i=0;i<iNum;i++){
sb.append("I");
}
return sb.toString();
}
}
//优化
class Solution {
public String intToRoman(int num) {
int[] nums = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
String[] ans = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
StringBuilder sb = new StringBuilder();
for(int i=0;i<nums.length;i++){
while(num>=nums[i]){
num = num - nums[i];
sb.append(ans[i]);
}
}
return sb.toString();
}
}
273. 整数转换英文表示
//将非负整数 num 转换为其对应的英文表示。
// 示例 1：
//输入：num = 123
//输出："One Hundred Twenty Three"
// 示例 2：
//输入：num = 12345
//输出："Twelve Thousand Three Hundred Forty Five"
// 示例 3：
//输入：num = 1234567
//输出："One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
// 示例 4：
//输入：num = 1234567891
//输出："One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thous
//and Eight Hundred Ninety One"
// 提示：
// 0 <= num <= 231 - 1
// Related Topics 数学 字符串
// 👍 134 👎 0
class Solution {
public String numberToWords(int num) {
}
}
165. 比较版本号
//给你两个版本号 version1 和 version2 ，请你比较它们。
// 版本号由一个或多个修订号组成，各修订号由一个 '.' 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编
//号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。
// 比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。
//如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别
//为 0 和 1 ，0 < 1 。
// 返回规则如下：
// 如果 version1 > version2 返回 1，
// 如果 version1 < version2 返回 -1，
// 除此之外返回 0。
// 示例 1：
//输入：version1 = "1.01", version2 = "1.001"
//输出：0
//解释：忽略前导零，"01" 和 "001" 都表示相同的整数 "1"
// 示例 2：
//输入：version1 = "1.0", version2 = "1.0.0"
//输出：0
//解释：version1 没有指定下标为 2 的修订号，即视为 "0"
// 示例 3：
//输入：version1 = "0.1", version2 = "1.1"
//输出：-1
//解释：version1 中下标为 0 的修订号是 "0"，version2 中下标为 0 的修订号是 "1" 。0 < 1，所以 version1 < ve
//rsion2
// 示例 4：
//输入：version1 = "1.0.1", version2 = "1"
//输出：1
// 示例 5：
//输入：version1 = "7.5.2.4", version2 = "7.5.3"
//输出：-1
// 提示：
// 1 <= version1.length, version2.length <= 500
// version1 和 version2 仅包含数字和 '.'
// version1 和 version2 都是 有效版本号
// version1 和 version2 的所有修订号都可以存储在 32 位整数 中
// Related Topics 字符串
// 👍 139 👎 0
class Solution {
public int compareVersion(String version1, String version2) {
String[] ans = version1.split("\\.");
String[] ans1= version2.split("\\.");
int size = Math.max(ans.length,ans1.length);
int[] ans5 = new int[ans.length];
for(int i=0;i<ans.length;i++){
ans5[i] = Integer.valueOf(ans[i]);
}
int[] ans6 = new int[ans1.length];
for(int i=0;i<ans1.length;i++){
ans6[i] = Integer.valueOf(ans1[i]);
}
int[] ans3 = Arrays.copyOf(ans5, size);
int[] ans4 = Arrays.copyOf(ans6, size);
for(int i=0;i<size;i++){
if(Integer.valueOf(ans3[i])>Integer.valueOf(ans4[i])){
return 1;
}
if(Integer.valueOf(ans3[i])<Integer.valueOf(ans4[i])){
return -1;
}
if(Integer.valueOf(ans3[i]) == Integer.valueOf(ans4[i])){
continue;
}
}
return 0;
}
}
//精简版
class Solution {
public int compareVersion(String version1, String version2) {
String[] ans = version1.split("\\.");
String[] ans1= version2.split("\\.");
int size = Math.max(ans.length,ans1.length);
for(int i=0;i<size;i++){
int j = i<ans.length? Integer.valueOf(ans[i]):0;
int k = i<ans1.length?Integer.valueOf(ans1[i]):0;
if(j!=k){
return j>k?1:-1;
}
}
return 0;
}
}
481. 神奇字符串
//神奇的字符串 S 只包含 '1' 和 '2'，并遵守以下规则：
// 字符串 S 是神奇的，因为串联字符 '1' 和 '2' 的连续出现次数会生成字符串 S 本身。
// 字符串 S 的前几个元素如下：S = “1221121221221121122 ......”
// 如果我们将 S 中连续的 1 和 2 进行分组，它将变成：
// 1 22 11 2 1 22 1 22 11 2 11 22 ......
// 并且每个组中 '1' 或 '2' 的出现次数分别是：
// 1 2 2 1 1 2 1 2 2 1 2 2 ......
// 你可以看到上面的出现次数就是 S 本身。
// 给定一个整数 N 作为输入，返回神奇字符串 S 中前 N 个数字中的 '1' 的数目。
// 注意：N 不会超过 100,000。
// 示例：
// 输入：6
//输出：3
//解释：神奇字符串 S 的前 6 个元素是 “12211”，它包含三个 1，因此返回 3。
// 👍 43 👎 0
class Solution {
public int magicalString(int n) {
}
}
子序列
392. 判断子序列
//给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
// 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"ae
//c"不是）。
// 进阶：
// 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代
//码？
// 致谢：
// 特别感谢 @pbrother 添加此问题并且创建所有测试用例。
// 示例 1：
//输入：s = "abc", t = "ahbgdc"
//输出：true
// 示例 2：
//输入：s = "axc", t = "ahbgdc"
//输出：false
// 提示：
// 0 <= s.length <= 100
// 0 <= t.length <= 10^4
// 两个字符串都只由小写字符组成。
// Related Topics 贪心算法 二分查找 动态规划
// 👍 397 👎 0
//直接查找拼接
class Solution {
public boolean isSubsequence(String s, String t) {
int j=0;
StringBuilder sb = new StringBuilder();
for(int i=0;i<t.length();i++){
if(j<s.length() && t.charAt(i) == s.charAt(j)){
sb.append(t.charAt(i));
j++;
}
}
return sb.toString().equals(s);
}
}
//解法二
524. 通过删除字母匹配到字典里最长单词
//给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符
//串。如果答案不存在，则返回空字符串。
// 示例 1:
//输入:
//s = "abpcplea", d = ["ale","apple","monkey","plea"]
//输出:
//"apple"
// 示例 2:
//输入:
//s = "abpcplea", d = ["a","b","c"]
//输出:
//"a"
// 说明:
// 所有输入的字符串只包含小写字母。
// 字典的大小不会超过 1000。
// 所有输入的字符串长度不会超过 1000。
// Related Topics 排序 双指针
// 👍 132 👎 0
class Solution {
public String findLongestWord(String s, List<String> dictionary) {
List<String> res = new ArrayList<>();
int maxSize = 0;
String result = "";
for (int i = 0; i < dictionary.size(); i++) {
String ans = dictionary.get(i);
StringBuilder sb = new StringBuilder();
int k = 0;
for (int j = 0; j < s.length(); j++) {
if (k < ans.length() && s.charAt(j) == ans.charAt(k)) {
sb.append(s.charAt(j));
k++;
}
}
if (sb.toString().equals(ans)) {
res.add(sb.toString());
}
}
//子串排序按字典顺序最小排序
res.sort(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.compareTo(o2);
}
});
//找出长度最长的子串
for (int l = 0; l < res.size(); l++) {
if (res.get(l).length() > maxSize) {
maxSize = res.get(l).length();
result = res.get(l);
}
}
//如果答案不止一个，且长度都相等，返回第一个字典顺序最小的
if (res != null && res.size() > 0) {
if (maxSize == res.get(0).length()) {
return res.get(0);
}
}
return result;
}
}
521. 最长特殊序列 Ⅰ
//给你两个字符串，请你从这两个字符串中找出最长的特殊序列。
// 「最长特殊序列」定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。
// 子序列 可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。
// 输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。
// 示例 1：
// 输入: "aba", "cdc"
//输出: 3
//解释: 最长特殊序列可为 "aba" (或 "cdc")，两者均为自身的子序列且不是对方的子序列。
// 示例 2：
// 输入：a = "aaa", b = "bbb"
//输出：3
// 示例 3：
// 输入：a = "aaa", b = "aaa"
//输出：-1
// 提示：
// 两个字符串长度均处于区间 [1 - 100] 。
// 字符串中的字符仅含有 'a'~'z' 。
// Related Topics 脑筋急转弯 字符串
// 👍 91 👎 0
class Solution {
public int findLUSlength(String a, String b) {
boolean res = isSubsequence(a.length()>=b.length()?a:b,a.length()< b.length()?a:b);
return (res||a.equals(b))?-1:Math.max(a.length(),b.length());
}
boolean isSubsequence(String s, String t) {
int j=0;
StringBuilder sb = new StringBuilder();
for(int i=0;i<t.length();i++){
if(j<s.length() && t.charAt(i) == s.charAt(j)){
sb.append(t.charAt(i));
j++;
}
}
return sb.toString().equals(s);
}
}
//神™脑筋急转弯
class Solution {
public int findLUSlength(String a, String b) {
if(a.equals(b)){
return -1;
}
return Math.max(a.length(),b.length());
}
}
522. 最长特殊序列 II
//给定字符串列表，你需要从它们中找出最长的特殊序列。最长特殊序列定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。
// 子序列可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。
// 输入将是一个字符串列表，输出是最长特殊序列的长度。如果最长特殊序列不存在，返回 -1 。
// 示例：
// 输入: "aba", "cdc", "eae"
//输出: 3
// 提示：
// 所有给定的字符串长度不会超过 10 。
// 给定字符串列表的长度将在 [2, 50 ] 之间。
// Related Topics 字符串
// 👍 58 👎 0
class Solution {
public int findLUSlength(String[] strs) {
}
}
66. 加一
//给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
// 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
// 你可以假设除了整数 0 之外，这个整数不会以零开头。
// 示例 1：
//输入：digits = [1,2,3]
//输出：[1,2,4]
//解释：输入数组表示数字 123。
// 示例 2：
//输入：digits = [4,3,2,1]
//输出：[4,3,2,2]
//解释：输入数组表示数字 4321。
// 示例 3：
//输入：digits = [0]
//输出：[1]
// 提示：
// 1 <= digits.length <= 100
// 0 <= digits[i] <= 9
// Related Topics 数组
// 👍 637 👎 0
class Solution {
public int[] plusOne(int[] digits) {
for(int i=digits.length-1;i>=0;i--){
digits[i]++;
digits[i] = digits[i] % 10;
if(digits[i] != 0){
return digits;
}
}
digits = new int[digits.length+1];
digits[0] = 1;
return digits;
}
}
67. 二进制求和
//给你两个二进制字符串，返回它们的和（用二进制表示）。
// 输入为 非空 字符串且只包含数字 1 和 0。
// 示例 1:
// 输入: a = "11", b = "1"
//输出: "100"
// 示例 2:
// 输入: a = "1010", b = "1011"
//输出: "10101"
// 提示：
// 每个字符串仅由字符 '0' 或 '1' 组成。
// 1 <= a.length, b.length <= 10^4
// 字符串如果不是 "0" ，就都不含前导零。
// Related Topics 数学 字符串
// 👍 568 👎 0
class Solution {
public String addBinary(String a, String b) {
}
}
415. 字符串相加
//给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
// 提示：
// num1 和num2 的长度都小于 5100
// num1 和num2 都只包含数字 0-9
// num1 和num2 都不包含任何前导零
// 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式
//
// Related Topics 字符串
// 👍 320 👎 0
class Solution {
public String addStrings(String num1, String num2) {
int i = num1.length()-1;
int j = num2.length()-1;
int add = 0;
StringBuilder ans = new StringBuilder();
while(i>=0 || j>=0 || add !=0){
int x = i>=0?num1.charAt(i)-'0':0;
int y = j>=0?num2.charAt(j)-'0':0;
int result = x+y+add;
ans.append(result%10);
add = result/10;
i--;
j--;
}
ans.reverse();
return ans.toString();
}
}
482. 密钥格式化
//有一个密钥字符串 S ，只包含字母，数字以及 '-'（破折号）。其中， N 个 '-' 将字符串分成了 N+1 组。
// 给你一个数字 K，请你重新格式化字符串，使每个分组恰好包含 K 个字符。特别地，第一个分组包含的字符个数必须小于等于 K，但至少要包含 1 个字符。两个分
//组之间需要用 '-'（破折号）隔开，并且将所有的小写字母转换为大写字母。
//
// 给定非空字符串 S 和数字 K，按照上面描述的规则进行格式化。
// 示例 1：
//
// 输入：S = "5F3Z-2e-9-w", K = 4
//输出："5F3Z-2E9W"
//解释：字符串 S 被分成了两个部分，每部分 4 个字符；
// 注意，两个额外的破折号需要删掉。
// 示例 2：
//
// 输入：S = "2-5g-3-J", K = 2
//输出："2-5G-3J"
//解释：字符串 S 被分成了 3 个部分，按照前面的规则描述，第一部分的字符可以少于给定的数量，其余部分皆为 2 个字符。
// 提示:
// S 的长度可能很长，请按需分配大小。K 为正整数。
// S 只包含字母数字（a-z，A-Z，0-9）以及破折号'-'
// S 非空
// 👍 61 👎 0
class Solution {
public String licenseKeyFormatting(String S, int K) {
StringBuilder sb = new StringBuilder();
StringBuilder resp = new StringBuilder();
for(int i=0;i<S.length();i++){
if(S.charAt(i) !='-'){
sb.append(S.charAt(i));
}
}
String ans = sb.toString().toUpperCase();
int j=0;
for(int i=ans.length()-1;i>=0;i--){
if(j!=0 && j%K ==0){
resp.append("-");
j=0;
}
resp.append(ans.charAt(i));
j++;
}
return resp.reverse().toString();
}
}
6. Z 字形变换
//将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
// 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
//P A H N
//A P L S I I G
//Y I R
// 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
// 请你实现这个将字符串进行指定行数变换的函数：
//string convert(string s, int numRows);
// 示例 1：
//输入：s = "PAYPALISHIRING", numRows = 3
//输出："PAHNAPLSIIGYIR"
//示例 2：
//输入：s = "PAYPALISHIRING", numRows = 4
//输出："PINALSIGYAHRPI"
//解释：
//P I N
//A L S I G
//Y A H R
//P I
// 示例 3：
//输入：s = "A", numRows = 1
//输出："A"
// 提示：
// 1 <= s.length <= 1000
// s 由英文字母（小写和大写）、',' 和 '.' 组成
// 1 <= numRows <= 1000
// Related Topics 字符串
// 👍 1035 👎 0
class Solution {
public String convert(String s, int numRows) {
if(numRows == 1){
return s;
}
List<StringBuilder> res = new ArrayList<>();
for(int i=0;i<numRows;i++){
res.add(new StringBuilder());
}
char[] chars =s.toCharArray();
int rows = 0;
boolean goingDown = false;
for(int j=0;j<chars.length;j++){
res.get(rows).append(chars[j]);
if(rows == 0 || rows == numRows-1){
goingDown = !goingDown;
}
if(goingDown){
rows = rows+1;
}
if(!goingDown){
rows = rows-1;
}
}
StringBuilder result = new StringBuilder();
for(int i=0;i<res.size();i++){
result.append(res.get(i));
}
return result.toString();
}
}
解题思路：
通过从左向右迭代字符串，我们可以轻松地确定字符位于 Z 字形图案中的哪一行。
我们可以使用 min(numRows,len(s)) 个列表来表示 Z 字形图案中的非空行。
从左到右迭代 ss，将每个字符添加到合适的行。可以使用当前行和当前方向这两个变量对合适的行进行跟踪。
只有当我们向上移动到最上面的行或向下移动到最下面的行时，当前方向才会发生改变。
68. 文本左右对齐
//给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
// 你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
// 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
// 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
// 说明:
// 单词是指由非空格字符组成的字符序列。
// 每个单词的长度大于 0，小于等于 maxWidth。
// 输入单词数组 words 至少包含一个单词。
// 示例:
// 输入:
//words = ["This", "is", "an", "example", "of", "text", "justification."]
//maxWidth = 16
//输出:
[4 2 2 6 2 4 14]
//[
// "This is an",
// "example of text",
// "justification. "
//]
// 示例 2:
// 输入:
//words = ["What","must","be","acknowledgment","shall","be"]
//maxWidth = 16
//输出:
//[
// "What must be",
// "acknowledgment ",
// "shall be "
//]
//解释: 注意最后一行的格式应为 "shall be " 而不是 "shall be",
// 因为最后一行应为左对齐，而不是左右两端对齐。
// 第二行同样为左对齐，这是因为这行只包含一个单词。
// 示例 3:
// 输入:
//words = ["Science","is","what","we","understand","well","enough","to","explain
//",
// "to","a","computer.","Art","is","everything","else","we","do"]
//maxWidth = 20
//输出:
//[
// "Science is what we",
// "understand well",
// "enough to explain to",
// "a computer. Art is",
// "everything else we",
// "do "
//]
//
// Related Topics 字符串
// 👍 126 👎 0
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
}
}
28. 实现 strStr()
//实现 strStr() 函数。
// 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如
//果不存在，则返回 -1。
// 示例 1:
// 输入: haystack = "hello", needle = "ll"
//输出: 2
// 示例 2:
// 输入: haystack = "aaaaa", needle = "bba"
//输出: -1
// 说明:
// 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
// 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
// Related Topics 双指针 字符串
// 👍 726 👎 0
class Solution {
public int strStr(String haystack, String needle) {
if(needle.length()==0 || haystack.equals(needle)){
return 0;
}
String[] split = haystack.split(needle);
if(split.length==0){
return 0;
}
if(split[0].equals(haystack)){
return -1;
}
return split[0].length();
}
}
686. 重复叠加字符串匹配
//给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。
// 注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。
// 示例 1：
// 输入：a = "abcd", b = "cdabcdab"
//输出：3
//解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。
// 示例 2：
// 输入：a = "a", b = "aa"
//输出：2
// 示例 3：
// 输入：a = "a", b = "a"
//输出：1
// 示例 4：
// 输入：a = "abc", b = "wxyz"
//输出：-1
// 提示：
// 1 <= a.length <= 104
// 1 <= b.length <= 104
// a 和 b 由小写英文字母组成
// Related Topics 字符串
// 👍 129 👎 0
class Solution {
public int repeatedStringMatch(String a, String b) {
StringBuilder sb = new StringBuilder();
if(a.contains(b)){
return 1;
}
int ans = 1;
for(int i=0;i<ans;i++){
sb.append(a);
if(sb.toString().contains(b)){
return ans;
}
else{
ans= ans+1;
}
if(sb.toString().length() > (a.length())+b.length()){
break;
}
}
return -1;
}
}
//解法二
class Solution {
public int repeatedStringMatch(String a, String b) {
StringBuilder sb = new StringBuilder(a);
int count =1;
while(sb.toString().length()<b.length()){
sb.append(a);
count++;
}
if(sb.toString().indexOf(b)>=0){
return count;
}
sb.append(a);
if(sb.toString().indexOf(b) >=0){
return count+1;
}
return -1;
}
}
459. 重复的子字符串
//给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
// 示例 1:
//输入: "abab"
//输出: True
//解释: 可由子字符串 "ab" 重复两次构成。
// 示例 2:
//输入: "aba"
//输出: False
// 示例 3:
//输入: "abcabcabcabc"
//输出: True
//解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
// Related Topics 字符串
// 👍 463 👎 0
//如果字符串 S 包含一个重复的子字符串，那么这意味着您可以多次 “移位和换行”`您的字符串，并使其与原始字符串匹配。
//超时
class Solution {
public boolean repeatedSubstringPattern(String s) {
String s1 = s;
String[] ans = new String[s.length()-1];
for(int i=0;i<s.length()-1;i++){
StringBuilder sb = new StringBuilder();
char temp = s.charAt(0);
ans[i] = sb.append(s.substring(1)).append(temp).toString();
s = ans[i];
}
for(int i=0;i<ans.length;i++){
if(ans[i].equals(s1)){
return true;
}
}
return false;
}
}
//取巧
class Solution {
public boolean repeatedSubstringPattern(String s) {
String str = s+s;
if(str.substring(1,str.length()-1).contains(s)){
return true;
}
return false;
}
}
214. 最短回文串
//给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
// 示例 1：
//输入：s = "aacecaaa"
//输出："aaacecaaa"
// 示例 2：
//输入：s = "abcd"
//输出："dcbabcd"
// 提示：
// 0 <= s.length <= 5 * 104
// s 仅由小写英文字母组成
// Related Topics 字符串
// 👍 321 👎 0
//暴力超时 abcd , 每次添加一个字符，判断是否回文，循环判断
class Solution {
public String shortestPalindrome(String s) {
if(isPalid(s)){
return s;
}
String s1 = s;
for(int i=1;i<s.length();i++){
StringBuilder sb = new StringBuilder();
StringBuilder str = new StringBuilder();
str.append(s.substring(s.length()-i));
String param = sb.append(str.reverse()).append(s1).toString();
boolean res = isPalid(param);
if(res){
return param;
}
}
return "";
}
public boolean isPalid(String s){
int j=s.length()-1;
for(int i=0;i<s.length();i++){
if(s.charAt(i) != s.charAt(j)){
return false;
}
j--;
}
return true;
}
}
5. 最长回文子串
//给你一个字符串 s，找到 s 中最长的回文子串。
// 示例 1：
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 示例 2：
//输入：s = "cbbd"
//输出："bb"
// 示例 3：
//输入：s = "a"
//输出："a"
// 示例 4：
//输入：s = "ac"
//输出："a"
// 提示：
// 1 <= s.length <= 1000
// s 仅由数字和英文字母（大写和/或小写）组成
// Related Topics 字符串 动态规划
// 👍 3300 👎 0
//暴力超时
class Solution {
public String longestPalindrome(String s) {
if(s.length()==1){
return s;
}
List<String> str = new ArrayList<>();
String resp = "";
int maxLength = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
String ans = s.substring(i, j);
if(j-i<maxLength){
continue;
}
if(isPalind(ans)){
str.add(ans);
maxLength = Math.max(ans.length(),maxLength);
}
}
}
for(int j=0;j<str.size();j++){
if(str.get(j).length()>resp.length()){
resp = str.get(j);
}
}
return resp;
}
public boolean isPalind(String s){
int j = s.length()-1;
for(int i=0;i<s.length();i++){
if(s.charAt(i) != s.charAt(j)){
return false;
}
j--;
}
return true;
}
}
//中心扩散法
class Solution {
public String longestPalindrome(String s) {
String res = "";
for(int i=0;i<s.length();i++){
String s1 = palindrome(s,i,i);
String s2 = palindrome(s,i,i+1);
res = res.length()>s1.length()? res:s1;
res = res.length()>s2.length()? res:s2;
}
return res;
}
private String palindrome(String s,int left,int right){
while(left>=0 && right<s.length()){
if(s.charAt(left) == s.charAt(right)){
left--;
right++;
}
else{
break;
}
}
return s.substring(left+1,right);
}
}
647. 回文子串
//给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
// 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
// 示例 1：
// 输入："abc"
//输出：3
//解释：三个回文子串: "a", "b", "c"
// 示例 2：
// 输入："aaa"
//输出：6
//解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
// 提示：
// 输入的字符串长度不会超过 1000 。
// Related Topics 字符串 动态规划
// 👍 504 👎 0
//暴力通过
class Solution {
public int countSubstrings(String s) {
int count = 0;
for(int i=0;i<s.length();i++){
for(int j=i+1;j<=s.length();j++){
String ans = s.substring(i,j);
if(isPalind(ans)){
count++;
}
}
}
return count;
}
public boolean isPalind(String s){
int left = 0;
int right = s.length()-1;
while(left<right){
if(s.charAt(left) != s.charAt(right)){
return false;
}
left++;
right--;
}
return true;
}
}
//中心扩散法
数与位
9. 回文数
//给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
// 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
// 示例 1：
//输入：x = 121
//输出：true
// 示例 2：
//输入：x = -121
//输出：false
//解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
// 示例 3：
//输入：x = 10
//输出：false
//解释：从右向左读, 为 01 。因此它不是一个回文数。
// 示例 4：
//输入：x = -101
//输出：false
// 提示：
// -231 <= x <= 231 - 1
// 进阶：你能不将整数转为字符串来解决这个问题吗？
// Related Topics 数学
// 👍 1413 👎 0
//反转后比较
class Solution {
public boolean isPalindrome(int x) {
String ans = String.valueOf(x);
char[] chars = ans.toCharArray();
int k = 0;
int y = chars.length-1;
while(k<y){
char temp = chars[k];
chars[k] = chars[y];
chars[y] = temp;
k++;
y--;
}
String res = String.valueOf(chars);
return ans.equals(res);
}
}
//一一比较
class Solution {
public boolean isPalindrome(int x) {
String ans = String.valueOf(x);
int j = ans.length()-1;
for(int i=0;i<ans.length();i++){
if(ans.charAt(i) != ans.charAt(j)){
return false;
}
j--;
}
return true;
}
}
231. 2的幂
//给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
// 示例 1:
// 输入: 1
//输出: true
//解释: 20 = 1
// 示例 2:
// 输入: 16
//输出: true
//解释: 24 = 16
// 示例 3:
// 输入: 218
//输出: false
// Related Topics 位运算 数学
// 👍 290 👎 0
//递归解法
class Solution {
public boolean isPowerOfTwo(int n) {
if(n == 1){
return true;
}
if(n==0){
return false;
}
if(n%2!=0){
return false;
}
return isPowerOfTwo(n/2);
}
}
//位运算处理
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}
342. 4的幂
//给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
// 整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x
// 示例 1：
//输入：n = 16
//输出：true
// 示例 2：
//输入：n = 5
//输出：false
// 示例 3：
//输入：n = 1
//输出：true
// 提示：
// -231 <= n <= 231 - 1
// 进阶：
// 你能不使用循环或者递归来完成本题吗？
// Related Topics 位运算
// 👍 168 👎 0
//递归解法
class Solution {
public boolean isPowerOfFour(int n) {
if(n == 0){
return false;
}
if(n==1){
return true;
}
if(n % 4 !=0){
return false;
}
return isPowerOfFour(n/4);
}
}
263. 丑数
//编写一个程序判断给定的数是否为丑数。
// 丑数就是只包含质因数 2, 3, 5 的正整数。
// 示例 1:
// 输入: 6
//输出: true
//解释: 6 = 2 × 3
// 示例 2:
// 输入: 8
//输出: true
//解释: 8 = 2 × 2 × 2
// 示例 3:
// 输入: 14
//输出: false
//解释: 14 不是丑数，因为它包含了另外一个质因数 7。
// 说明：
// 1 是丑数。
// 输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]。
// Related Topics 数学
// 👍 176 👎 0
class Solution {
public boolean isUgly(int n) {
if(n==0){
return false;
}
while(n%2==0){
n = n/2;
}
while(n%3 == 0){
n = n/3;
}
while(n%5 == 0){
n = n/5;
}
return n==1;
}
}
190. 颠倒二进制位
//颠倒给定的 32 位无符号整数的二进制位。
// 示例 1：
// 输入: 00000010100101000001111010011100
//输出: 00111001011110000010100101000000
//解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
// 因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
//
// 示例 2：
// 输入：11111111111111111111111111111101
//输出：10111111111111111111111111111111
//解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
// 因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
// 提示：
// 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的
//还是无符号的，其内部的二进制表示形式都是相同的。
// 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -10737418
//25。
// 进阶:
//如果多次调用这个函数，你将如何优化你的算法？
// Related Topics 位运算
// 👍 273 👎 0
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
}
}
492. 构造矩形
//作为一位web开发者， 懂得怎样去规划一个页面的尺寸是很重要的。 现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的
//矩形的页面。要求：
//1. 你设计的矩形页面必须等于给定的目标面积。
//2. 宽度 W 不应大于长度 L，换言之，要求 L >= W 。
//3. 长度 L 和宽度 W 之间的差距应当尽可能小。
// 你需要按顺序输出你设计的页面的长度 L 和宽度 W。
// 示例：
//输入: 4
//输出: [2, 2]
//解释: 目标面积是 4， 所有可能的构造方案有 [1,4], [2,2], [4,1]。
//但是根据要求2，[1,4] 不符合要求; 根据要求3，[2,2] 比 [4,1] 更能符合要求. 所以输出长度 L 为 2， 宽度 W 为 2。
// 说明:
// 给定的面积不大于 10,000,000 且为正整数。
// 你设计的页面的长度和宽度必须都是正整数。
// Related Topics 数学
// 👍 51 👎 0
class Solution {
public int[] constructRectangle(int area) {
int[] res = new int[2];
int i = new Double(Math.sqrt(area)).intValue();
while (i>=0){
if(area%i==0){
res[0] = area/i;
res[1] = i;
break;
}
i--;
}
return res;
}
}
29. 两数相除
//给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
// 返回被除数 dividend 除以除数 divisor 得到的商。
// 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
// 示例 1:
// 输入: dividend = 10, divisor = 3
//输出: 3
//解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
// 示例 2:
// 输入: dividend = 7, divisor = -3
//输出: -2
//解释: 7/-3 = truncate(-2.33333..) = -2
// 提示：
// 被除数和除数均为 32 位有符号整数。
// 除数不为 0。
// 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
// Related Topics 数学 二分查找
// 👍 518 👎 0
class Solution {
public int divide(int dividend, int divisor) {
}
}
507. 完美数
//对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。
// 给定一个 整数 n， 如果是完美数，返回 true，否则返回 false
// 示例 1：
// 输入：28
//输出：True
//解释：28 = 1 + 2 + 4 + 7 + 14
//1, 2, 4, 7, 和 14 是 28 的所有正因子。
// 示例 2：
// 输入：num = 6
//输出：true
// 示例 3：
// 输入：num = 496
//输出：true
// 示例 4：
// 输入：num = 8128
//输出：true
// 示例 5：
// 输入：num = 2
//输出：false
// 提示：
// 1 <= num <= 108
// Related Topics 数学
// 👍 82 👎 0
class Solution {
public boolean checkPerfectNumber(int num) {
}
}
栈与递归
682. 棒球比赛
//你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。
// 比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：
// 整数 x - 表示本回合新获得分数 x
// "+" - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
// "D" - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
// "C" - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。
// 请你返回记录中所有得分的总和。
// 示例 1：
//输入：ops = ["5","2","C","D","+"]
//输出：30
//解释：
//"5" - 记录加 5 ，记录现在是 [5]
//"2" - 记录加 2 ，记录现在是 [5, 2]
//"C" - 使前一次得分的记录无效并将其移除，记录现在是 [5].
//"D" - 记录加 2 * 5 = 10 ，记录现在是 [5, 10].
//"+" - 记录加 5 + 10 = 15 ，记录现在是 [5, 10, 15].
//所有得分的总和 5 + 10 + 15 = 30
// 示例 2：
//输入：ops = ["5","-2","4","C","D","9","+","+"]
//输出：27
//解释：
//"5" - 记录加 5 ，记录现在是 [5]
//"-2" - 记录加 -2 ，记录现在是 [5, -2]
//"4" - 记录加 4 ，记录现在是 [5, -2, 4]
//"C" - 使前一次得分的记录无效并将其移除，记录现在是 [5, -2]
//"D" - 记录加 2 * -2 = -4 ，记录现在是 [5, -2, -4]
//"9" - 记录加 9 ，记录现在是 [5, -2, -4, 9]
//"+" - 记录加 -4 + 9 = 5 ，记录现在是 [5, -2, -4, 9, 5]
//"+" - 记录加 9 + 5 = 14 ，记录现在是 [5, -2, -4, 9, 5, 14]
//所有得分的总和 5 + -2 + -4 + 9 + 5 + 14 = 27
// 示例 3：
//输入：ops = ["1"]
//输出：1
// 提示：
// 1 <= ops.length <= 1000
// ops[i] 为 "C"、"D"、"+"，或者一个表示整数的字符串。整数范围是 [-3 * 104, 3 * 104]
// 对于 "+" 操作，题目数据保证记录此操作时前面总是存在两个有效的分数
// 对于 "C" 和 "D" 操作，题目数据保证记录此操作时前面总是存在一个有效的分数
//
// Related Topics 栈
// 👍 168 👎 0
class Solution {
public int calPoints(String[] ops) {
int[] res = new int[ops.length];
int index = 0;
int sum = 0;
for(int i=0;i<ops.length;i++){
if(ops[i].equals("C")){
res[index-1] = 0;
index--;
continue;
}
else if(ops[i].equals("D")){
res[index] = res[index-1] * 2;
}
else if(ops[i].equals("+")){
res[index] = res[index-1] + res[index-2];
}
else{
res[index] = Integer.valueOf(ops[i]);
}
index++;
}
for(int i=0;i<res.length;i++){
sum = sum + res[i];
}
return sum;
}
}
//栈的方式解决
class Solution {
public int calPoints(String[] ops) {
Deque<Integer> deque = new ArrayDeque<>();
for(int i=0;i<ops.length;i++){
if(ops[i].equals("C")){
deque.pollLast();
}
else if(ops[i].equals("D")){
deque.offerLast(2*deque.peekLast());
}
//先弹出栈顶元素，再记录最后一个，最后把弹出的元素加回去
else if(ops[i].equals("+")){
int top = deque.pollLast();
int top1 = deque.peekLast();
int addNum = top + top1;
deque.offerLast(top);
deque.offerLast(addNum);
}
else{
deque.offerLast(Integer.valueOf(ops[i]));
}
}
int res = 0;
for (Integer i:deque) {
res =res + i;
}
return res;
}
}
150. 逆波兰表达式求值
//根据 逆波兰表示法，求表达式的值。
// 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
// 说明：
// 整数除法只保留整数部分。
// 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
// 示例 1：
// 示例 2：
// 输入: ["4", "13", "5", "/", "+"]
//输出: 6
//解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
// 示例 3：
// 输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
//输出: 22
//解释:
//该算式转化为常见的中缀算术表达式为：
// ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
//= ((10 * (6 / (12 * -11))) + 17) + 5
//= ((10 * (6 / -132)) + 17) + 5
//= ((10 * 0) + 17) + 5
//= (0 + 17) + 5
//= 17 + 5
//= 22
// 逆波兰表达式：
// 逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
// 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
// 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
// 逆波兰表达式主要有以下两个优点：
// 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
// 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
// Related Topics 栈
// 👍 263 👎 0
import java.util.ArrayDeque;
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> deque = new ArrayDeque<>();
for(int i=0;i<tokens.length;i++){
if (tokens[i].equals("+")) {
deque.offerLast(deque.pollLast() + deque.pollLast());
} else if (tokens[i].equals("-")) {
deque.offerLast(-deque.pollLast() + deque.pollLast());
} else if (tokens[i].equals("/")) {
int top = deque.pollLast();
int top1 = deque.pollLast();
deque.offerLast(top1 / top);
} else if (tokens[i].equals("*")) {
deque.offerLast(deque.pollLast() * deque.pollLast());
}
else{
deque.offerLast(Integer.valueOf(tokens[i]));
}
}
return deque.peekFirst();
}
}
227. 基本计算器 II
//实现一个基本的计算器来计算一个简单的字符串表达式的值。
// 字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。
// 示例 1:
// 输入: "3+2*2"
//输出: 7
// 示例 2:
// 输入: " 3/2 "
//输出: 1
// 示例 3:
// 输入: " 3+5 / 2 "
//输出: 5
// 说明：
// 你可以假设所给定的表达式都是有效的。
// 请不要使用内置的库函数 eval。
// Related Topics 栈 字符串
// 👍 269 👎 0
class Solution {
public int calculate(String s) {
List<String> res = new ArrayList<>();
//中缀转后缀
//优先级高 入栈 来的元素优先级<= 栈内元素优先级，弹出
Deque<Character> chars = new ArrayDeque<>();
Deque<Integer> deque = new ArrayDeque<>();
for(int i=0;i<s.length();i++){
if(s.charAt(i) == ' '){
continue;
}
//如果是符号类型，栈为空，入栈
else if(!Character.isDigit(s.charAt(i)) && chars.isEmpty()){
chars.offerLast(s.charAt(i));
}
//如果当前符号优先级<= 栈顶符号 ，将栈内元素弹出直到栈为空，将当前符号入栈
else if(s.charAt(i) == '+' || s.charAt(i) == '-'){
while (!chars.isEmpty()){
res.add(String.valueOf(chars.pollLast()));
}
chars.offerLast(s.charAt(i));
}
///如果当前符号优先级<= 栈顶符号 ，将栈内元素弹出直到栈为空，将当前符号入栈,
else if(s.charAt(i) == '*' || s.charAt(i) == '/'){
Character k = chars.peekLast();
//当前符号优先级大于栈顶元素，符号入栈
if(k =='+' || k=='-'){
chars.offerLast(s.charAt(i));
}
else{
while (true){
if(chars.isEmpty() || chars.peekLast()=='+' || chars.peekLast() == '-'){
break;
}
if(chars.peekLast() == '*' || chars.peekLast() == '/'){
res.add(String.valueOf(chars.pollLast()));
}
}
chars.offerLast(s.charAt(i));
}
}
else{
//数字，多位数截取
int k = i+1;
while(k<=s.length()-1 && Character.isDigit(s.charAt(k))){
k++;
}
res.add(s.substring(i,k));
i = k-1;
}
}
while(!chars.isEmpty()){
res.add(String.valueOf(chars.pollLast()));
}
//逆波兰表达式求值，后缀表达式转中缀表达式
for(int i=0;i<res.size();i++){
if (res.get(i).equals("+")) {
deque.offerLast(deque.pollLast() + deque.pollLast());
} else if (res.get(i).equals("-")) {
deque.offerLast(-deque.pollLast() + deque.pollLast());
} else if (res.get(i).equals("/")) {
int top = deque.pollLast();
int top1 = deque.pollLast();
deque.offerLast(top1 / top);
} else if (res.get(i).equals("*")) {
deque.offerLast(deque.pollLast() * deque.pollLast());
}
else{
deque.offerLast(Integer.valueOf(res.get(i)));
}
}
return deque.peekFirst();
}
}
224. 基本计算器
//给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
// 示例 1：
//输入：s = "1 + 1"
//输出：2
// 示例 2：
//输入：s = " 2-1 + 2 "
//输出：3
// 示例 3：
//输入：s = "(1+(4+5+2)-3)+(6+8)"
//输出：23
// 提示：
// 1 <= s.length <= 3 * 105
// s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
// s 表示一个有效的表达式
// Related Topics 栈 数学
// 👍 494 👎 0
class Solution {
public int calculate(String s) {
}
}
20. 有效的括号
//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
// 有效字符串需满足：
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
// 示例 1：
//输入：s = "()"
//输出：true
// 示例 2：
//输入：s = "()[]{}"
//输出：true
// 示例 3：
//输入：s = "(]"
//输出：false
// 示例 4：
//输入：s = "([)]"
//输出：false
// 示例 5：
//输入：s = "{[]}"
//输出：true
// 提示：
// 1 <= s.length <= 104
// s 仅由括号 '()[]{}' 组成
// Related Topics 栈 字符串
// 👍 2225 👎 0
class Solution {
public boolean isValid(String s) {
Deque<Character> deque = new ArrayDeque<>();
for(int i=0;i<s.length();i++){
if(s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) =='}'){
if(deque.isEmpty()){
return false;
}
if(s.charAt(i) == ']' && deque.pollLast() !='[' ){
return false;
}
if(s.charAt(i) == ')' && deque.pollLast() !='(' ){
return false;
}
if(s.charAt(i) == '}' && deque.pollLast() !='{' ){
return false;
}
}
else{
deque.offerLast(s.charAt(i));
}
}
if(!deque.isEmpty()){
return false;
}
return true;
}
}
链表
24. 两两交换链表中的节点
//给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
// 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
// 示例 1：
//输入：head = [1,2,3,4]
//输出：[2,1,4,3]
// 示例 2：
//输入：head = []
//输出：[]
// 示例 3：
//输入：head = [1]
//输出：[1]
// 提示：
// 链表中节点的数目在范围 [0, 100] 内
// 0 <= Node.val <= 100
// 进阶：你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）
// Related Topics 递归 链表
// 👍 869 👎 0
/**迭代法
* 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) {
ListNode dummy = new ListNode(-1,head);
ListNode temp = dummy;
while(temp.next != null && temp.next.next != null){
ListNode node1 = temp.next;
ListNode node2 = temp.next.next;
temp.next = node2;
node1.next = node2.next;
node2.next = node1;
temp = node1;
}
return dummy.next;
}
}
206. 反转链表
//反转一个单链表。
//
// 示例:
//
// 输入: 1->2->3->4->5->NULL
//输出: 5->4->3->2->1->NULL
//
// 进阶:
//你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
// Related Topics 链表
// 👍 1637 👎 0
/**
* 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) {
ListNode prev = null;
ListNode curr = head;
ListNode temp = null;
while(curr != null){
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
}
92. 反转链表 II
//给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链
//表节点，返回 反转后的链表 。
// 示例 1：
//输入：head = [1,2,3,4,5], left = 2, right = 4
//输出：[1,4,3,2,5]
// 示例 2：
//输入：head = [5], left = 1, right = 1
//输出：[5]
// 提示：
// 链表中节点数目为 n
// 1 <= n <= 500
// -500 <= Node.val <= 500
// 1 <= left <= right <= n
// 进阶： 你可以使用一趟扫描完成反转吗？
// Related Topics 链表
// 👍 839 👎 0
/**穿针引线
* 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 reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
for(int i=0;i<left-1;i++){
prev = prev.next;
}
ListNode rightNode = prev;
for(int i=0;i<right-left+1;i++){
rightNode = rightNode.next;
}
ListNode curr = rightNode.next;
ListNode leftNode = prev.next;
//切断链表
prev.next = null;
rightNode.next = null;
reverseNode(leftNode);
//接链表
prev.next = rightNode;
leftNode.next = curr;
return dummy.next;
}
public void reverseNode(ListNode head){
ListNode prev = null;
ListNode curr = head;
ListNode temp = null;
while(curr != null){
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
}
}
2. 两数相加
//给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
// 请你将两个数相加，并以相同形式返回一个表示和的链表。
// 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
// 示例 1：
//输入：l1 = [2,4,3], l2 = [5,6,4]
//输出：[7,0,8]
//解释：342 + 465 = 807.
// 示例 2：
//输入：l1 = [0], l2 = [0]
//输出：[0]
// 示例 3：
//输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
//输出：[8,9,9,9,0,0,0,1]
// 提示：
// 每个链表中的节点数在范围 [1, 100] 内
// 0 <= Node.val <= 9
// 题目数据保证列表表示的数字不含前导零
//
// Related Topics 递归 链表 数学
// 👍 5910 👎 0
/**
* 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 addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(-1);
int carry = 0;
while(l1 != null || l2 != null || carry !=0){
int l1Val = l1 !=null ? l1.val : 0;
int l2Val = l2 !=null ? l2.val : 0;
int sumVal = l1Val+l2Val+carry;
carry = sumVal/10;
addNode(result,sumVal%10);
if(l1 !=null){
l1 = l1.next;
}
if(l2 != null){
l2 = l2.next;
}
}
return result.next;
}
public void addNode(ListNode head,int val){
ListNode curr = head;
while(curr.next != null){
curr = curr.next;
}
ListNode node = new ListNode(val);
curr.next = node;
}
}
445. 两数相加 II
//给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
// 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
// 进阶：
// 如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
// 示例：
// 输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
//输出：7 -> 8 -> 0 -> 7
//
// Related Topics 链表
// 👍 359 👎 0
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
l1 = reverseNode(l1);
l2 = reverseNode(l2);
int carry = 0;
ListNode result = new ListNode(-1);
while (l1 != null || l2 != null || carry != 0) {
int l1Val = l1 != null ? l1.val : 0;
int l2Val = l2 != null ? l2.val : 0;
int sumVal = l1Val + l2Val + carry;
carry = sumVal / 10;
addNode(result, sumVal % 10);
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
return reverseNode(result.next);
}
public ListNode reverseNode(ListNode head) {
ListNode prev = null;
ListNode curr = head;
ListNode temp = null;
while (curr != null) {
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
public void addNode(ListNode head, int val) {
ListNode curr = head;
while (curr.next != null) {
curr = curr.next;
}
ListNode node = new ListNode(val);
curr.next = node;
}
}
21. 合并两个有序链表
//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
// 示例 1：
//输入：l1 = [1,2,4], l2 = [1,3,4]
//输出：[1,1,2,3,4,4]
// 示例 2：
//输入：l1 = [], l2 = []
//输出：[]
// 示例 3：
//输入：l1 = [], l2 = [0]
//输出：[0]
// 提示：
// 两个链表的节点数目范围是 [0, 50]
// -100 <= Node.val <= 100
// l1 和 l2 均按 非递减顺序 排列
//
// Related Topics 递归 链表
// 👍 1632 👎 0
/**
* 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 mergeTwoLists(ListNode l1, ListNode l2) {
ListNode result = new ListNode(-1);
while (l1 != null || l2 != null) {
if (l1 != null && l2 != null) {
if (l1.val >= l2.val) {
addNode(result, l2.val);
l2 = l2.next;
} else {
addNode(result, l1.val);
l1 = l1.next;
}
}
if (l1 == null && l2 != null) {
addNode(result, l2.val);
l2 = l2.next;
}
if (l1 != null && l2 == null) {
addNode(result, l1.val);
l1 = l1.next;
}
}
return result.next;
}
public void addNode(ListNode head,int val){
ListNode curr = head;
while(curr.next != null){
curr = curr.next;
}
ListNode node =new ListNode(val);
curr.next = node;
}
}
/**迭代优化
* 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 mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode prev = dummy;
while(l1 !=null && l2!=null){
if(l1.val>=l2.val){
prev.next = l2;
l2 = l2.next;
}
else{
prev.next = l1;
l1 = l1.next;
}
prev = prev.next;
}
prev.next = l1==null?l2:l1;
return dummy.next;
}
}
哈希表
217. 存在重复元素
//给定一个整数数组，判断是否存在重复元素。
// 如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
// 示例 1:
//输入: [1,2,3,1]
//输出: true
// 示例 2:
//输入: [1,2,3,4]
//输出: false
// 示例 3:
//输入: [1,1,1,3,3,4,3,2,4,2]
//输出: true
// Related Topics 数组 哈希表
// 👍 376 👎 0
//数组排序
class Solution {
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
int length = nums.length;
for(int i=0;i<length-1;i++){
if(nums[i] == nums[i+1]){
return true;
}
}
return false;
}
}
//哈希表
class Solution {
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for(int i=0;i<nums.length;i++){
set.add(nums[i]);
}
return set.size() != nums.length;
}
}
633. 平方数之和
//给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
// 示例 1：
// 输入：c = 5
//输出：true
//解释：1 * 1 + 2 * 2 = 5
// 示例 2：
// 输入：c = 3
//输出：false
// 示例 3：
// 输入：c = 4
//输出：true
// 示例 4：
// 输入：c = 2
//输出：true
// 示例 5：
// 输入：c = 1
//输出：true
// 提示：
// 0 <= c <= 231 - 1
// Related Topics 数学
// 👍 170 👎 0
//双指针法
class Solution {
public boolean judgeSquareSum(int c) {
int i=0;
int j = new Double(Math.sqrt(c)).intValue() + 1;
while(i<=j){
if(i*i+j*j>c){
j--;
}
else if(i*i+j*j<c){
i++;
}
else{
return true;
}
}
return false;
}
}
349. 两个数组的交集
//给定两个数组，编写一个函数来计算它们的交集。
// 示例 1：
// 输入：nums1 = [1,2,2,1], nums2 = [2,2]
//输出：[2]
// 示例 2：
// 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
//输出：[9,4]
// 说明：
// 输出结果中的每个元素一定是唯一的。
// 我们可以不考虑输出结果的顺序。
//
// Related Topics 排序 哈希表 双指针 二分查找
// 👍 345 👎 0
//HashSet处理
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> nums1Set = new HashSet<>();
HashSet<Integer> nums2Set = new HashSet<>();
for (int i = 0; i < nums1.length; i++) {
nums1Set.add(nums1[i]);
}
for(int i=0;i<nums2.length;i++){
if(nums1Set.contains(nums2[i])){
nums2Set.add(nums2[i]);
}
}
int[] res = new int[nums2Set.size()];
int i=0;
for(Integer item: nums2Set){
res[i] = item;
i++;
}
return res;
}
}
128. 最长连续序列
//给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
// 进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？
// 示例 1：
//输入：nums = [100,4,200,1,3,2]
//输出：4
//解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
// 示例 2：
//输入：nums = [0,3,7,2,5,8,4,6,0,1]
//输出：9
// 提示：
// 0 <= nums.length <= 104
// -109 <= nums[i] <= 109
//
// Related Topics 并查集 数组
// 👍 728 👎 0
//去重->排序处理
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length == 0){
return 0;
}
if(nums.length==1){
return 1;
}
Set<Integer> sets = new HashSet<>();
for(int i=0;i<nums.length;i++){
sets.add(nums[i]);
}
int[] ans = new int[sets.size()];
int i=0;
for(Integer item:sets){
ans[i] = item;
i++;
}
Arrays.sort(ans);
int max = Integer.MIN_VALUE;
int count = 0;
for(int j=0;j<ans.length-1;j++){
if(ans[j+1] == ans[j]+1){
count++;
}
else{
count = 0;
}
max = Math.max(count,max);
}
return Math.max(count,max)+1;
}
}
500. 键盘行
//给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。
// 美式键盘 中：
// 第一行由字符 "qwertyuiop" 组成。
// 第二行由字符 "asdfghjkl" 组成。
// 第三行由字符 "zxcvbnm" 组成。
// 示例 1：
//输入：words = ["Hello","Alaska","Dad","Peace"]
//输出：["Alaska","Dad"]
// 示例 2：
//输入：words = ["omk"]
//输出：[]
// 示例 3：
//输入：words = ["adsdf","sfd"]
//输出：["adsdf","sfd"]
// 提示：
// 1 <= words.length <= 20
// 1 <= words[i].length <= 100
// words[i] 由英文字母（小写和大写字母）组成
// Related Topics 哈希表
// 👍 127 👎 0
class Solution {
public String[] findWords(String[] words) {
Set<String> first = new HashSet<>();
Set<String> second = new HashSet<>();
Set<String> third = new HashSet<>();
String firstKey = "qwertyuiop";
String secondKey = "asdfghjkl";
String thirdKey = "zxcvbnm";
List<String> res = new ArrayList<>();
for(int i=0;i<firstKey.length();i++){
first.add(String.valueOf(firstKey.charAt(i)));
}
for(int i=0;i<secondKey.length();i++){
second.add(String.valueOf(secondKey.charAt(i)));
}
for(int i=0;i<thirdKey.length();i++){
third.add(String.valueOf(thirdKey.charAt(i)));
}
for (int i = 0; i < words.length; i++) {
String message = words[i];
boolean flagA = true;
for (int j = 0; j < message.length(); j++) {
if (!first.contains(String.valueOf(message.charAt(j)).toLowerCase())) {
flagA = false;
break;
}
}
if (flagA) {
res.add(message);
}
boolean flagB = true;
for (int k = 0; k < message.length(); k++) {
if (!second.contains(String.valueOf(message.charAt(k)).toLowerCase())) {
flagB = false;
break;
}
}
if (flagB) {
res.add(message);
}
boolean flagC = true;
for (int l = 0; l < message.length(); l++) {
if (!third.contains(String.valueOf(message.charAt(l)).toLowerCase())) {
flagC = false;
break;
}
}
if (flagC) {
res.add(message);
}
}
String[] resp = new String[res.size()];
int m = 0;
for (String item: res) {
resp[m] = item;
m++;
}
return resp;
}
}
290. 单词规律
//给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
//
// 这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
//
// 示例1:
//
// 输入: pattern = "abba", str = "dog cat cat dog"
//输出: true
//
// 示例 2:
//
// 输入:pattern = "abba", str = "dog cat cat fish"
//输出: false
//
// 示例 3:
//
// 输入: pattern = "aaaa", str = "dog cat cat dog"
//输出: false
//
// 示例 4:
//
// 输入: pattern = "abba", str = "dog dog dog dog"
//输出: false
//
// 说明:
//你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。
// Related Topics 哈希表
// 👍 319 👎 0
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public boolean wordPattern(String pattern, String s) {
}
}
//leetcode submit region end(Prohibit modification and deletion)
205. 同构字符串
//给定两个字符串 s 和 t，判断它们是否是同构的。
// 如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
// 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
// 示例 1:
//输入：s = "egg", t = "add"
//输出：true
// 示例 2：
//输入：s = "foo", t = "bar"
//输出：false
// 示例 3：
//输入：s = "paper", t = "title"
//输出：true
// 提示：
// 可以假设 s 和 t 长度相同。
// Related Topics 哈希表
// 👍 345 👎 0
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character,Character> sMap = new HashMap<>();
Map<Character,Character> tMap = new HashMap<>();
for(int i=0;i<s.length();i++){
char x = s.charAt(i), y = t.charAt(i);
if((sMap.containsKey(x) && sMap.get(x) !=y) || (tMap.containsKey(y) && tMap.get(y) != x)){
return false;
}
sMap.put(x,y);
tMap.put(y,x);
}
return true;
}
}
167. 两数之和 II - 输入有序数组
//给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
// 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0]
// < answer[1] <= numbers.length 。
// 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
// 示例 1：
//输入：numbers = [2,7,11,15], target = 9
//输出：[1,2]
//解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
// 示例 2：
//输入：numbers = [2,3,4], target = 6
//输出：[1,3]
// 示例 3：
//输入：numbers = [-1,0], target = -1
//输出：[1,2]
// 提示：
// 2 <= numbers.length <= 3 * 104
// -1000 <= numbers[i] <= 1000
// numbers 按 递增顺序 排列
// -1000 <= target <= 1000
// 仅存在一个有效答案
//
// Related Topics 数组 双指针 二分查找
// 👍 491 👎 0
class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] res = new int[2];
int i=0;
int j = nums.length - 1;
while (i < j) {
if (nums[i] + nums[j] == target) {
res[0] = i+1;
res[1] = j+1;
break;
}
if (nums[i] + nums[j] > target) {
j--;
} else {
i++;
}
}
return res;
}
}
599. 两个列表的最小索引总和
//假设Andy和Doris想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
//
// 你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设总是存在一个答案。
// 示例 1:
// 输入:
//["Shogun", "Tapioca Express", "Burger King", "KFC"]
//["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
//输出: ["Shogun"]
//解释: 他们唯一共同喜爱的餐厅是“Shogun”。
// 示例 2:
// 输入:
//["Shogun", "Tapioca Express", "Burger King", "KFC"]
//["KFC", "Shogun", "Burger King"]
//输出: ["Shogun"]
//解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。
// 提示:
// 两个列表的长度范围都在 [1, 1000]内。
// 两个列表中的字符串的长度将在[1，30]的范围内。
// 下标从0开始，到列表的长度减1。
// 两个列表都没有重复的元素。
// Related Topics 哈希表
// 👍 102 👎 0
class Solution {
public static String[] findRestaurant(String[] list1, String[] list2) {
Map<String, Integer> sMap = new HashMap<>();
Map<String, Integer> tMap = new HashMap<>();
List<String> ans = new ArrayList<>();
for (int i = 0; i < list1.length; i++) {
sMap.put(list1[i], i);
}
int minIndex = Integer.MAX_VALUE;
for(int i=0;i<list2.length;i++){
if(sMap.containsKey(list2[i])){
minIndex = Math.min(minIndex,sMap.get(list2[i])+i);
tMap.put(list2[i],sMap.get(list2[i])+i);
}
}
for (Map.Entry<String, Integer> entry : tMap.entrySet()) {
if(entry.getValue().equals(minIndex)){
ans.add(entry.getKey().toString());
}
}
String[] resp = new String[ans.size()];
for(int i=0;i<ans.size();i++){
resp[i] = ans.get(i);
}
return resp
}
}
219. 存在重复元素 II
//给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值
// 至多为 k。
// 示例 1:
// 输入: nums = [1,2,3,1], k = 3
//输出: true
// 示例 2:
// 输入: nums = [1,0,1,1], k = 1
//输出: true
// 示例 3:
// 输入: nums = [1,2,3,1,2,3], k = 2
//输出: false
// Related Topics 数组 哈希表
// 👍 252 👎 0
//给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值
// 至多为 k。
//
//
//
// 示例 1:
//
// 输入: nums = [1,2,3,1], k = 3
//输出: true
//
// 示例 2:
//
// 输入: nums = [1,0,1,1], k = 1
//输出: true
//
// 示例 3:
//
// 输入: nums = [1,2,3,1,2,3], k = 2
//输出: false
// Related Topics 数组 哈希表
// 👍 252 👎 0
//暴力
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i] == nums[j] && Math.abs(i-j)<=k){
return true;
}
}
}
return false;
}
}
//hashMap解决
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
if(map.containsKey(nums[i]) && Math.abs(i-map.get(nums[i])) <=k){
return true;
}
map.put(nums[i],i);
}
return false;
}
}
220. 存在重复元素 III
//在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的
//绝对值也小于等于 ķ 。
// 如果存在则返回 true，不存在返回 false。
// 示例 1:
// 输入: nums = [1,2,3,1], k = 3, t = 0
//输出: true
// 示例 2:
// 输入: nums = [1,0,1,1], k = 1, t = 2
//输出: true
// 示例 3:
// 输入: nums = [1,5,9,1,5,9], k = 2, t = 3
//输出: false
// Related Topics 排序 Ordered Map
// 👍 308 👎 0
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(k==10000) return false;
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
if(Math.abs(new Double(nums[i])-new Double(nums[j])) <=t && Math.abs(new Double(i-j))<=k){
return true;
}
}
}
return false;
}
}
594. 最长和谐子序列
350. 两个数组的交集 II
//给定两个数组，编写一个函数来计算它们的交集。
// 示例 1：
// 输入：nums1 = [1,2,2,1], nums2 = [2,2]
//输出：[2,2]
// 示例 2:
// 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
//输出：[4,9]
// 说明：
// 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
// 我们可以不考虑输出结果的顺序。
// 进阶：
// 如果给定的数组已经排好序呢？你将如何优化你的算法？
// 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
// 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
// Related Topics 排序 哈希表 双指针 二分查找
// 👍 469 👎 0
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer,Integer> map = new HashMap<>();
List<Integer> ans = new ArrayList<>();
for(int i=0;i<nums1.length;i++){
map.put(nums1[i],map.getOrDefault(nums1[i],0)+1);
}
for(int i=0;i<nums2.length;i++){
if(map.containsKey(nums2[i]) && map.get(nums2[i]) !=0){
ans.add(nums2[i]);
map.put(nums2[i],map.get(nums2[i])-1);
}
}
int[] res = new int[ans.size()];
for(int i=0;i<ans.size();i++){
res[i] = ans.get(i);
}
return res;
}
}
//排序+双指针
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int nums1Length = nums1.length;
int nums2Length = nums2.length;
int i=0;
int j=0;
List<Integer> ans = new ArrayList<>();
while(i<nums1Length && j<nums2Length){
if(nums1[i] == nums2[j]){
ans.add(nums1[i]);
i++;
j++;
}
else if(nums1[i]<nums2[j]){
i++;
}
else{
j++;
}
}
int[] res = new int[ans.size()];
for(int k=0;k<ans.size();k++){
res[k] = ans.get(k);
}
return res;
}
}
609. 在系统中查找重复文件
//给定一个目录信息列表，包括目录路径，以及该目录中的所有包含内容的文件，您需要找到文件系统中的所有重复文件组的路径。一组重复的文件至少包括二个具有完全相同内容
//的文件。
// 输入列表中的单个目录信息字符串的格式如下：
// "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_conten
//t)"
// 这意味着有 n 个文件（f1.txt, f2.txt ... fn.txt 的内容分别是 f1_content, f2_content ... fn_co
//ntent）在目录 root/d1/d2/.../dm 下。注意：n>=1 且 m>=0。如果 m=0，则表示该目录是根目录。
// 该输出是重复文件路径组的列表。对于每个组，它包含具有相同内容的文件的所有文件路径。文件路径是具有下列格式的字符串：
// "directory_path/file_name.txt"
// 示例 1：
// 输入：
//["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)
//", "root 4.txt(efgh)"]
//输出：
//[["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"
//]]
// 注：
// 最终输出不需要顺序。
// 您可以假设目录名、文件名和文件内容只有字母和数字，并且文件内容的长度在 [1，50] 的范围内。
// 给定的文件数量在 [1，20000] 个范围内。
// 您可以假设在同一目录中没有任何文件或目录共享相同的名称。
// 您可以假设每个给定的目录信息代表一个唯一的目录。目录路径和文件信息用一个空格分隔。
//
// 超越竞赛的后续行动：
// 假设您有一个真正的文件系统，您将如何搜索文件？广度搜索还是宽度搜索？
// 如果文件内容非常大（GB级别），您将如何修改您的解决方案？
// 如果每次只能读取 1 kb 的文件，您将如何修改解决方案？
// 修改后的解决方案的时间复杂度是多少？其中最耗时的部分和消耗内存的部分是什么？如何优化？
// 如何确保您发现的重复文件不是误报？
//
// Related Topics 哈希表 字符串
// 👍 62 👎 0
class Solution {
public List<List<String>> findDuplicate(String[] paths) {
List<List<String>> resp = new ArrayList<>();
Map<String,List<String>> map = new HashMap<>();
for(int i=0;i<paths.length;i++){
String path = paths[i];
String[] ans= path.split(" ");
for(int j=1;j<ans.length;j++){
String root = ans[0];
String file = ans[j].split("\\(")[0];
String content = ans[j].split("\\(")[1].split("\\)")[0];
String rootFile = new StringBuilder(root).append("/").append(file).toString();
List<String> mapValue = map.getOrDefault(content, new ArrayList<>());
mapValue.add(rootFile);
map.put(content,mapValue);
}
}
for(Map.Entry<String,List<String>> entry : map.entrySet()){
if(entry.getValue().size()>1){
resp.add(entry.getValue());
}
}
return resp;
}
}
454. 四数相加 II
//给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[
//l] = 0。
// 为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最
//终结果不会超过 231 - 1 。
// 例如:
//输入:
//A = [ 1, 2]
//B = [-2,-1]
//C = [-1, 2]
//D = [ 0, 2]
//输出:
//2
//解释:
//两个元组如下:
//1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
//2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
// Related Topics 哈希表 二分查找
// 👍 348 👎 0
class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<A.length;i++){
for(int j=0;j<B.length;j++){
map.put(A[i]+B[j],map.getOrDefault(A[i]+B[j],0)+1);
}
}
int res = 0;
for(int i=0;i<C.length;i++){
for(int j=0;j<D.length;j++){
if(map.containsKey(-(C[i]+D[j]))){
res = res+map.get(-(C[i]+D[j]));
}
}
}
return res;
}
}
18. 四数之和
//给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c +
// d 的值与 target 相等？找出所有满足条件且不重复的四元组。
// 注意：答案中不可以包含重复的四元组。
// 示例 1：
//输入：nums = [1,0,-1,0,-2,2], target = 0
//输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
// 示例 2：
//输入：nums = [], target = 0
//输出：[]
// 提示：
// 0 <= nums.length <= 200
// -109 <= nums[i] <= 109
// -109 <= target <= 109
//
// Related Topics 数组 哈希表 双指针
// 👍 800 👎 0
//暴力，离谱
class Solution {
public static List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> resp = new ArrayList<>();
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
for(int k=j+1;k<nums.length;k++){
for(int l=k+1;l<nums.length;l++){
if(nums[i]+nums[j]+nums[k]+nums[l] == target){
List<Integer> ans = new ArrayList<>();
ans.add(nums[i]);
ans.add(nums[j]);
ans.add(nums[k]);
ans.add(nums[l]);
Collections.sort(ans);
if(!resp.contains(ans)){
resp.add(ans);
}
}
}
}
}
}
return resp;
}
}
贪心算法
605. 种花问题
//假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
//
// 给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则
//的情况下种入 n 朵花？能则返回 true ，不能则返回 false。
//
//
//
// 示例 1：
//
//
//输入：flowerbed = [1,0,0,0,1], n = 1
//输出：true
//
//
// 示例 2：
//
//
//输入：flowerbed = [1,0,0,0,1], n = 2
//输出：false
//
//
//
//
// 提示：
//
//
// 1 <= flowerbed.length <= 2 * 104
// flowerbed[i] 为 0 或 1
// flowerbed 中不存在相邻的两朵花
// 0 <= n <= flowerbed.length
//
// Related Topics 贪心算法 数组
// 👍 334 👎 0
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < flowerbed.length; i++) {
map.put(i, flowerbed[i]);
}
map.put(-1, 0);
map.put(flowerbed.length, 0);
for (int i = 0; i < flowerbed.length; i++) {
if (flowerbed[i] == 0 && map.get(i - 1) == 0 && map.get(i + 1) == 0) {
n--;
map.put(i, 1);
if(n==0){
return true;
}
}
}
return n<=0;
}
}
//贪心算法
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int sum = 0;
for(int i=0;i<flowerbed.length;i++){
if((flowerbed[i] == 0) && (i-1<0 || flowerbed[i-1]==0) && (i+1>=flowerbed.length || flowerbed[i+1]==0)){
sum++;
if(sum >=n){
return true;
}
flowerbed[i] = 1;
}
}
return sum>=n;
}
}
121. 买卖股票的最佳时机
//给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
// 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
// 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
// 示例 1：
//输入：[7,1,5,3,6,4]
//输出：5
//解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
// 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
// 示例 2：
//输入：prices = [7,6,4,3,1]
//输出：0
//解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
// 提示：
// 1 <= prices.length <= 105
// 0 <= prices[i] <= 104
// Related Topics 数组 动态规划
// 👍 1548 👎 0
class Solution {
public int maxProfit(int[] prices) {
Integer minPrice = Integer.MAX_VALUE;
int res = 0;
for(int i=0;i<prices.length;i++){
minPrice = Math.min(minPrice,prices[i]);
res = Math.max(res,prices[i]-minPrice);
}
return res;
}
}
122. 买卖股票的最佳时机 II
//给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
// 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
// 示例 1:
// 输入: [7,1,5,3,6,4]
//输出: 7
//解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
// 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
// 示例 2:
// 输入: [1,2,3,4,5]
//输出: 4
//解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
// 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
// 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
// 示例 3:
//
// 输入: [7,6,4,3,1]
//输出: 0
//解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
// 提示：
// 1 <= prices.length <= 3 * 10 ^ 4
// 0 <= prices[i] <= 10 ^ 4
//
// Related Topics 贪心算法 数组
// 👍 1176 👎 0
class Solution {
public int maxProfit(int[] prices) {
int ans = 0;
for(int i=0;i<prices.length-1;i++){
if(prices[i+1]>prices[i]){
ans = ans + prices[i+1] - prices[i];
}
}
return ans;
}
}
455. 分发饼干
//假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
// 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i
//]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
// 示例 1:
//输入: g = [1,2,3], s = [1,1]
//输出: 1
//解释:
//你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
//虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
//所以你应该输出1。
// 示例 2:
//输入: g = [1,2], s = [1,2,3]
//输出: 2
//解释:
//你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
//你拥有的饼干数量和尺寸都足以让所有孩子满足。
//所以你应该输出2.
// 提示：
// 1 <= g.length <= 3 * 104
// 0 <= s.length <= 3 * 104
// 1 <= g[i], s[j] <= 231 - 1
//
// Related Topics 贪心算法
// 👍 316 👎 0
//双指针 贪心算法
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int i=0;
int j=0;
int res = 0;
while(i<g.length && j<s.length){
if(s[j]>=g[i]){
res++;
i++;
j++;
}
else{
j++;
}
}
return res;
}
}
409. 最长回文串
//给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
// 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
// 注意:
//假设字符串的长度不会超过 1010。
// 示例 1:
//输入:
//"abccccdd"
//输出:
//7
//解释:
//我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
// Related Topics 哈希表
// 👍 283 👎 0
class Solution {
public int longestPalindrome(String s) {
int count = 0;
Map<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(Map.Entry<Character,Integer> entry : map.entrySet()){
if(entry.getValue() %2 == 0){
count = count+ entry.getValue();
}
else{
count = count + entry.getValue()-1;
}
}
if(count<s.length()){
count = count+1;
}
return count;
}
}
双指针
15. 三数之和
//给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重
//复的三元组。
// 注意：答案中不可以包含重复的三元组。
// 示例 1：
//输入：nums = [-1,0,1,2,-1,-4]
//输出：[[-1,-1,2],[-1,0,1]]
// 示例 2：
//输入：nums = []
//输出：[]
// 示例 3：
//输入：nums = [0]
//输出：[]
// 提示：
// 0 <= nums.length <= 3000
// -105 <= nums[i] <= 105
//
// Related Topics 数组 双指针
// 👍 3239 👎 0
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> resp = new ArrayList<>();
Arrays.sort(nums);
for(int k=0;k<nums.length;k++){
if(nums[k] > 0) break;
if(k > 0 && nums[k] == nums[k - 1]) continue;
int i = k+1;
int j = nums.length-1;
while(i<j){
List<Integer> ans = new ArrayList<>();
if(nums[k]+nums[i]+nums[j] == 0){
ans.add(nums[k]);
ans.add(nums[i]);
ans.add(nums[j]);
ans = ans.stream().sorted(Integer::compareTo).collect(Collectors.toList());
if(!resp.contains(ans)){
resp.add(ans);
}
i++;
j--;
continue;
}
if(nums[i]+nums[j] > -nums[k]){
j--;
}
if(nums[i]+nums[j] < -nums[k]){
i++;
}
}
}
return resp;
}
}
16. 最接近的三数之和
//给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和
//。假定每组输入只存在唯一答案。
// 示例：
// 输入：nums = [-1,2,1,-4], target = 1
//输出：2
//解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
// 提示：
// 3 <= nums.length <= 10^3
// -10^3 <= nums[i] <= 10^3
// -10^4 <= target <= 10^4
// Related Topics 数组 双指针
// 👍 752 👎 0
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int closestNum = nums[0]+nums[1]+nums[2];
for(int i=0;i<nums.length;i++){
int l=i+1;
int r=nums.length-1;
while(l<r){
int threeNum = nums[i]+nums[l]+nums[r];
if(Math.abs(threeNum-target)<Math.abs(closestNum-target)){
closestNum = threeNum;
}
if(threeNum>target){
r--;
}
else if(threeNum < target){
l++;
}
else{
return threeNum;
}
}
}
return closestNum;
}
}
18. 四数之和
//给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c +
// d 的值与 target 相等？找出所有满足条件且不重复的四元组。
// 注意：答案中不可以包含重复的四元组。
// 示例 1：
//输入：nums = [1,0,-1,0,-2,2], target = 0
//输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
// 示例 2：
//输入：nums = [], target = 0
//输出：[]
// 提示：
// 0 <= nums.length <= 200
// -109 <= nums[i] <= 109
// -109 <= target <= 109
// Related Topics 数组 哈希表 双指针
// 👍 821 👎 0
//暴力
class Solution {
public static List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> resp = new ArrayList<>();
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
for(int k=j+1;k<nums.length;k++){
for(int l=k+1;l<nums.length;l++){
if(nums[i]+nums[j]+nums[k]+nums[l] == target){
List<Integer> ans = new ArrayList<>();
ans.add(nums[i]);
ans.add(nums[j]);
ans.add(nums[k]);
ans.add(nums[l]);
Collections.sort(ans);
if(!resp.contains(ans)){
resp.add(ans);
}
}
}
}
}
}
return resp;
}
}
//双指针
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> resp = new ArrayList<>();
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
int l = j+1;
int r = nums.length-1;
while(l<r){
List<Integer> ans = new ArrayList<>();
if(nums[i]+nums[j]+nums[l]+nums[r] == target){
ans.add(nums[i]);
ans.add(nums[j]);
ans.add(nums[r]);
ans.add(nums[l]);
Collections.sort(ans);
if(!resp.contains(ans)){
resp.add(ans);
}
l++;
r--;
continue;
}
if(nums[i]+nums[j]+nums[l]+nums[r] > target){
r--;
continue;
}
if(nums[i]+nums[j]+nums[l]+nums[r] < target){
l++;
continue;
}
}
}
}
return resp;
}
}
187. 重复的DNA序列
//所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复
//序列有时会对研究非常有帮助。
// 编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
// 示例 1：
//输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
//输出：["AAAAACCCCC","CCCCCAAAAA"]
// 示例 2：
//输入：s = "AAAAAAAAAAAAA"
//输出：["AAAAAAAAAA"]
// 提示：
// 0 <= s.length <= 105
// s[i] 为 'A'、'C'、'G' 或 'T'
// Related Topics 位运算 哈希表
// 👍 158 👎 0
import java.util.ArrayList;
import java.util.HashSet;
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
Set<String> set = new HashSet<>();
List<String> res = new ArrayList<>();
for(int i=0;i<s.length();i++){
if(i+10<=s.length()){
String ans = s.substring(i,i+10);
if(set.contains(ans) && !res.contains(ans)){
res.add(ans);
}
set.add(ans);
}
}
return res;
}
}
643. 子数组最大平均数 I
//给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
// 示例：
//输入：[1,12,-5,-6,50,3], k = 4
//输出：12.75
//解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
// 提示：
// 1 <= k <= n <= 30,000。
// 所给数据范围 [-10,000，10,000]。
//
// Related Topics 数组
// 👍 182 👎 0
class Solution {
public double findMaxAverage(int[] nums, int k) {
int sum = 0;
for (int i = 0; i < k; i++) {
sum = sum + nums[i];
}
int maxValue = sum;
for (int i = k; i < nums.length; i++) {
sum = sum + nums[i] - nums[i - k];
maxValue = Math.max(maxValue, sum);
}
return maxValue / (1.0 * k);
}
}
674. 最长连续递增序列
//给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
// 连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那
//么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
// 示例 1：
//输入：nums = [1,3,5,4,7]
//输出：3
//解释：最长连续递增序列是 [1,3,5], 长度为3。
//尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
// 示例 2：
//输入：nums = [2,2,2,2,2]
//输出：1
//解释：最长连续递增序列是 [2], 长度为1。
// 提示：
// 0 <= nums.length <= 104
// -109 <= nums[i] <= 109
//
// Related Topics 数组
// 👍 178 👎 0
class Solution {
public int findLengthOfLCIS(int[] nums) {
if(null == nums || nums.length == 0){
return 0;
}
if(nums.length == 1){
return 1;
}
int ans = 1;
int max = Integer.MIN_VALUE;
for(int i=1;i<nums.length;i++){
if(nums[i]>nums[i-1]){
ans++;
}
else{
ans = 1;
}
max = Math.max(max,ans);
}
return max;
}
}
//优化
class Solution {
public int findLengthOfLCIS(int[] nums) {
int ans = 0;
int start = 0;
for(int i=0;i<nums.length;i++){
if(i>0 && nums[i] <= nums[i-1]){
start = i;
}
ans = Math.max(ans,i-start+1);
}
return ans;
}
}
142. 环形链表 II
//给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
// 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，po
//s 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
// 说明：不允许修改给定的链表。
// 进阶：
// 你是否可以使用 O(1) 空间解决此题？
// 示例 1：
//输入：head = [3,2,0,-4], pos = 1
//输出：返回索引为 1 的链表节点
//解释：链表中有一个环，其尾部连接到第二个节点。
// 示例 2：
//输入：head = [1,2], pos = 0
//输出：返回索引为 0 的链表节点
//解释：链表中有一个环，其尾部连接到第一个节点。
// 示例 3：
//输入：head = [1], pos = -1
//输出：返回 null
//解释：链表中没有环。
// 提示：
// 链表中节点的数目范围在范围 [0, 104] 内
// -105 <= Node.val <= 105
// pos 的值为 -1 或者链表中的一个有效索引
// Related Topics 链表 双指针
// 👍 976 👎 0
/**
* 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 curr = head;
Set<ListNode> set = new HashSet<>();
while(curr != null && curr.next !=null){
if(set.contains(curr)){
return curr;
}
set.add(curr);
curr = curr.next;
}
return null;
}
}
143. 重排链表
//给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
//将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
// 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
// 示例 1:
// 给定链表 1->2->3->4, 重新排列为 1->4->2->3.
// 示例 2:
// 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
// Related Topics 链表
// 👍 572 👎 0
/**
* 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 void reorderList(ListNode head) {
if(head == null){
return;
}
List<ListNode> list = new ArrayList<>();
ListNode curr = head;
while(curr != null){
list.add(curr);
curr = curr.next;
}
int i=0;
int j=list.size()-1;
while(i<j){
list.get(i).next = list.get(j);
i++;
list.get(j).next = list.get(i);
j--;
if(i==j){
break;
}
}
list.get(i).next = null;
}
}
234. 回文链表
//请判断一个链表是否为回文链表。
// 示例 1:
// 输入: 1->2
//输出: false
// 示例 2:
// 输入: 1->2->2->1
//输出: true
// 进阶：
//你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
// Related Topics 链表 双指针
// 👍 956 👎 0
/**
* 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 boolean isPalindrome(ListNode head) {
List<ListNode> list = new ArrayList<>();
ListNode curr = head;
while(curr != null){
list.add(curr);
curr = curr.next;
}
int i = 0;
int j = list.size()-1;
while(i<j){
if(list.get(i).val != list.get(j).val){
return false;
}
i++;
j--;
}
return true;
}
}
