算法题总结

发表于 | 分类于 |
字数统计: 27.8k | 阅读时长 ≈ 132

[TOC]

mid

3.无重复字符的最长子串

1
set+双指针i，j 当j不包含时候，添加并计算max，否则，左边界右移动

15.三数之和

排序，for里面套一个双指针while，注意去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while()
{		if(cur==0)
           {
             ...
              while(start<end && nums[start]==nums[start+1])
              {
                  start++;
              }
               while(start<end && nums[end]==nums[end-1])
              {
                  end--;
              }
              start++;
              end--;
           }
    }

146.LRU缓存

1
2
3
4
5
6
7
8
9
10
11
一个HashMap<Integer,Node> map    
Node<key,value>  
removeNode(Node n) 
insertToHead(Node n)
put()
{
 if(map.size()==capacity){
  map.remove();
  removeNode();
 }
}

103.二叉树的锯齿形层序遍历

1
list.add(0,node.val)

215. 数组中的第K个最大元素

1
2
3
4
5
快排
while(true)
{
 int index=partition(arr,l,r)
}

105.从前序与中序遍历序列构造二叉树

1
while(preorder[ps]!=inorder[is+index]) index++;

199. 二叉树的右视图

1
if(i==size-1) res.add(node.val);

54. 螺旋矩阵

1
2
3
4
5
6
7
while (l <= r && u <= d){
            for (int i = l; i <= r; i++) {
                list.add(matrix[u][i]);
            }
            u++;
            ......
            }

33. 搜索旋转排序数组

1
2
3
4
5
6
7
8
9
if(nums[mid]<nums[right])
      {
         if(target<=nums[right] && target>nums[mid])
         {
            left=mid+1; 
         }
         else 
            right=mid-1; 
      }

236. 二叉树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
if(left!=null && right==null)
    {
        return left;
    }
    else if(left==null && right!=null)
    {
        return right;
    }
    else if(left!=null && right!=null)
      return root;

31. 下一个排列

从后往前找

1
2
3
[1,1,5]

[1,5,1]
1
2
3
4
5
6
7
8
9
while(i>=0 && nums[i]>=nums[i+1])
  {
      i--;
  }
  if(i>=0)
  {
      int j=nums.length-1;
      while(j>i && nums[j] <= nums[i])
   }

排序奇升偶降链表

  1. 按奇偶位置拆分链表，得1->3->5->7->NULL和8->6->4->2->NULL

  2. 反转偶链表，得1->3->5->7->NULL和2->4->6->8->NULL

  3. 合并两个有序链表，得1->2->3->4->5->6->7->8->NULL

24. 两两交换链表中的节点

1
2
3
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;

98. 验证二叉搜索树

1
2
3
4
5
6
7
8
9
10
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
public boolean validate(TreeNode node, long min, long max) {
        if (node == null) {
            return true;
        }
        if (node.val <= min || node.val >= max) {
            return false;
        }
        return  validate(node.left, min, node.val) && validate(node.right, node.val, max);
    }

958. 二叉树的完全性检验

广度进行遍历，设一个前驱指针prev，判断prev==null && node！=null

1
2
3
4
5
6
7
if (prev == null && node != null)
                return false;
            if (node != null) {
                queue.add(node.left);
                queue.add(node.right);
            }
            prev = node;

79. 单词搜索

回溯

1
2
3
(char[][] board,int n,int m,int i,int j,char[] cs,int index)

boolean flag=helper(board,n,m,i+1,j,cs,index+1)||helper(board,n,m,i-1,j,cs,index+1)||helper(board,n,m,i,j+1,cs,index+1)||helper(board,n,m,i,j-1,cs,index+1);

143. 重排链表

给定一个单链表 L：L0→L1→…→L**n-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→L**n-2→…

快慢指针找中点，反转，链表合并

1
2
3
ListNode slow=head,fast=head.next;
reverse()
merge

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

1
for (int start = i; start < candidates.length; start++)

518. 零钱兑换 II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

1
2
3
4
5
int dp[][] = new int[n+1][amount+1];
       dp[0][0] = 1;//                   前n个，凑成值为amount
       ...
dp[i][j] = dp[i-1][j];
if(j >= coins[i-1]) dp[i][j] += dp[i][j-coins[i-1]];

162. 寻找峰值

峰值元素是指其值大于左右相邻值的元素。

1
2
3
4
if(nums[mid]>=nums[mid+1])
{
	right=mid; 
}

56. 合并区间

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

1
2
3
4
5
6
7
8
9
 int left=intervals[i][0];
    right=intervals[i][1];
    while(i<intervals.length-1 && right>=intervals[i+1][0])
    {
    right=Math.max(right,intervals[i+1][1]);
    i++;
}
...
return arr.toArray(new int[arr.size()][2]);

148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

  • 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

快慢指针找中心点

归并排序

1
2
3
ListNode l1=mergeSort(head);
   ListNode l2=mergeSort(slow);
   return mergeSort(l1,l2);

135. 分发糖果

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int candy(int[] ratings) {
     int n = ratings.length;
     int[] arr = new int[n];
     Arrays.fill(arr,1);
     for(int i = 1; i < n; i++)
     {
         if(ratings[i] > ratings[i - 1]) {
             arr[i] = arr[i - 1] + 1;
         }
     }
     for(int i = n - 1; i > 0; i--)
     {
         if(ratings[i - 1] > ratings[i])
         {
             arr[i - 1] = Math.max(arr[i - 1], arr[i] + 1);
         }
     }
     int sum = 0;
     for(int i = 0; i < arr.length; i++)
     {
         sum += arr[i];
     }
     return sum;
    }

470. 用 Rand7() 实现 Rand10()

(rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数

即实现了 rand_XY()

1
2
3
4
while(true) {
            int num = (rand7() - 1) * 7 + rand7(); // 等概率生成[1,49]范围的随机数
            if(num <= 40) return num % 10 + 1; // 拒绝采样，并返回[1,10]范围的随机数
        }

662. 二叉树最大宽度

image-20210305092007327

1
2
3
4
5
6
7
8
9
10
11
HashMap<Node,Integer>
while(!q.isEmpty())
{
  max=Math.max(max,map.get(queue.peekLast())-map.get(queue.peekFirst())+1);
  ..
  if(temp.left!=null)
  {
  queue.add(temp.left);
  map.put(temp.left,map.get(temp)*2);  
  }
}

木头切割问题

给定长度为n的数组，每个元素代表一个木头的长度，木头可以任意截断，从这堆木头中截出至少k个相同长度为m的木块。已知k，求max(m)。

输入两行，第一行n, k，第二行为数组序列。输出最大值。

image-20210305093152907

暴力

1
2
3
4
5
6
7
8
9
while (1 <= maxV)
{
    int cnt = 0;
    for (int i = 0; i < n; i ++ ) cnt += a[i] / m;
    if (cnt >= k) res = max(res, cnt);  // 如果当前可以截出来超过k段，就更新结果
    m ++;
}

cout << res << endl;

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;

const int N = 100010;
int a[N];
int n, k;

int check(int mid)
{
    int res = 0;
    for (int i = 0; i < n; i ++ ) res += a[i] / mid;
    return res;
}

int main()
{
    cin >> n >> k;
    int l = 1, r = -1;
    
    for (int i = 0; i < n; i ++ )
    {
        cin >> a[i];
        r = max(r, a[i]);
    }
    
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid) >= k) l = mid;
        else r = mid - 1;
    }
    
    cout << l << endl;
    return 0;
}

圆环回原点问题

image-20210305093719625

走n步到0的方案数=走n-1步到1的方案数+走n-1步到9的方案数。

因此，若设dp[i][j]为从0点出发走i步到j点的方案数，则递推式为：

图片

ps:公式之所以取余是因为j-1或j+1可能会超过圆环0~9的范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void main(String[] args) {
      // dp[i][j]     走i步 到点 j 的走法    dp[n][0]
        // 0~9         k=10
       //   (-1+10)
        // dp[i][j]= dp[i-1][((j-1)+k)%k]+dp[i-1][(j+1)%k]
        // dp[0][0]= 1;
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt(); // 0~9 10
        int[][] dp=new int[n+1][k];
        dp[0][0]=1;
        for(int i=1;i<dp.length;i++)
        {
            for(int j=0;j<dp[0].length;j++)
            {
                dp[i][j]= dp[i-1][((j-1)+k)%k]+dp[i-1][(j+1)%k];
            }
        }
        System.out.println(dp[n][0]);
        //      dp[1][1] = dp[1][0] +
        //      dp[2][0] = dp[1][9] + dp[1][1];

    }

322. 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1：

1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=1;i<amount+1;i++)
    {
        f[0][i]=0x3f3f3f3f;
    }
for(int i=1;i<=coins.length;i++)
    {
        for(int j=1;j<amount+1;j++)
        {
            if(j>=coins[i-1]) f[i][j]=Math.min(f[i-1][j],f[i][j-coins[i-1]]+1);
            else{
                f[i][j]=f[i-1][j];
            }
        }
    }

739. 每日温度

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

先全部压入栈里面，不行就弹出来

1
2
3
4
5
6
while(!stack.isEmpty() && T[stack.peek()]<T[i])
      {
        int temp=stack.pop();
        res[temp]= i-temp;
      }
      stack.push(i);

151. 翻转字符串里的单词

双指针整体反转+局部反转+去除空格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while(r<=cs.length)
    {
        if(r==cs.length || cs[r]==' ')
        {
            reverse(cs,l,r-1);
            l=r+1;
        }
        r++;         
    }
    ...
    while(j<n){
           while(j<n&&ch[j]==' ')j++;//找到第一个不为空格的首字母的位置；
           while(j<n&&ch[j]!=' ')ch[i++]=ch[j++];//将不为空格的字母前移，消除空格；
           while(j<n&&ch[j]==' ')j++;//之后又遇到一个空格;
           if(j<n) ch[i++] = ' ';//保留一个空格
       }

670. 最大交换

先排序，然后设置diff，从后向前找到第一个不相等

1
2
3
4
5
if (oldNum[i] != orderNum[orderNum.length - 1 - i])         
 for (int i = oldNum.length - 1; i >= diff; i--) {
 ...
            if (oldNum[i] == orderNum[orderNum.length - 1 - diff])
            }

91. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，”111” 可以将 “1” 中的每个 “1” 映射为 “A” ，从而得到 “AAA” ，或者可以将 “11” 和 “1”（分别为 “K” 和 “A” ）映射为 “KA” 。注意，”06” 不能映射为 “F” ，因为 “6” 和 “06” 不同。

示例 1：

1
2
3
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
1
2
3
4
5
6
7
8
9
int[] dp=new int[length+1];
dp[0]=1;
for(int i=0;i<length;i++)
{
    dp[i+1]=s.charAt(i)=='0'?0:dp[i];
    if(i>0 && (s.charAt(i-1)=='1'||(s.charAt(i-1)=='2' && s.charAt(i)<='6' 
    )))
    dp[i+1]+=dp[i-1];
 }

134. 加油站

输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

如果剩余量小于0，比如要前面的都失败

1
2
3
4
5
6
7
run+=(gas[i]-cost[i]);
   rest+=(gas[i]-cost[i]);
   if(run<0)
   {
   start=i+1;
   run=0;
   }

138. 复制带随机指针的链表

三次O(n)

第一次新增节点

第二次随即指针

第三次拆分

注意拆分最后一步 cur.next=null;

36进制加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
char getChar(int n)
{
    if (n <= 9)
        return n + '0';
    else
        return n - 10 + 'a';
}
int getInt(char ch)
{
    if ('0' <= ch && ch <= '9')
        return ch - '0';
    else
        return ch - 'a' + 10;
}
string add36Strings(string num1, string num2)
{
    int carry = 0;
    int i = num1.size() - 1, j = num2.size() - 1;
    int x, y;
    string res;
    while (i >= 0 || j >= 0 || carry)
    {
        x = i >= 0 ? getInt(num1[i]) : 0;
        y = j >= 0 ? getInt(num2[j]) : 0;
        int temp = x + y + carry;
        res += getChar(temp % 36);
        carry = temp / 36;
        i--, j--;
    }
    reverse(res.begin(), res.end());
    return res;
}

221. 最大正方形

1
dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));

93. 复原 IP 地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for(int a=1;a<4;a++)
      for(int b=1;b<4;b++)
       for(int c=1;c<4;c++)
        for(int d=1;d<4;d++)
         {
          if(a+b+c+d==s.length())
          {
          int n1=Integer.parseInt(s.substring(0,a));
          int n2=Integer.parseInt(s.substring(a,a+b));
          int n3=Integer.parseInt(s.substring(a+b,a+b+c));
          int n4=Integer.parseInt(s.substring(a+b+c));
          if(n1<=255&&n3<=255&&n2<=255&&n4<=255)
          {
               ip.append(n1).append('.').append(n2)
                                      .append('.').append(n3).append('.').append(n4);
               if(ip.length()==s.length()+3)
                  ret.add(ip.toString());
                
                   ip.delete(0,ip.length());                
          }
         }
         }

1143. 最长公共子序列

1
2
3
4
5
6
7
8
if(text1.charAt(i-1)==text2.charAt(j-1))
 {
              dp[i][j]=dp[i-1][j-1]+1;
  }
   else
   {
        dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
    }

560.和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

1
2
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
1
2
3
4
5
6
7
sum += nums[i];
if(map.containsKey(sum-k))
{
    ret += map.get(sum-k); 
    System.out.println(" sum  : "+String.valueOf(sum)+" ret: "+ret+" "+map.get(sum-k)); 
}               
map.put(sum, map.getOrDefault(sum, 0)+1);

209. 长度最小的子数组

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

1
2
3
4
5
sum += nums[j];
while (sum >= s) {
    len = len == 0 ? j - i + 1 : Math.min(len, j - i + 1);
    sum -= nums[i++];
}

974. 和可被 K 整除的子数组

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

示例：

输入：A = [4,5,0,-2,-3,1], K = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

为了可以处理数组一开始就能被k整除，需要设置 modK[0]=1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int subarraysDivByK(int[] A, int K) {
        int N = A.length, sum = 0, ans = 0;
        HashMap<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        for (int i = 1; i <= N; i++) {
            sum = sum + A[i-1]; 
            int key = (sum % K + K) % K;
            if(map.containsKey(key))
            {
                ans+= map.get(key);
            }
            map.put(key,map.getOrDefault(key,0)+1);
        }
        return ans;
    }
}

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

示例 1：

输入：nums = [1,3,4,2,2]
输出：2

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while(true)
    {
        fast=nums[nums[fast]];
        slow=nums[slow];
        if(fast==slow)
        {
            break;
        }
    }
    fast=0;
    while(fast!=slow)
    {
        fast=nums[fast];
        slow=nums[slow];
    }
    return fast;

210. 课程表 II

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

示例 1:

输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

先构造一个图

1
List<Integer>[] lists = new ArrayList[numCourses];

//记录某个节点的入度

1
int[] points = new int[numCourses];

初始化

1
2
3
4
5
points[p[0]]++;
if(lists[p[1]] == null){
lists[p[1]] = new ArrayList<>();
}
lists[p[1]].add(p[0]);

所以入度为0加入到队列

1
2
3
4
5
6
for(int i = 0; i < numCourses; i++){
           //入度为 0，添加到队列中
           if(points[i] == 0){
               queue.add(i);
           }
       }

依次对指向的结点度减一

1
List<Integer> list = lists[p];

528. 按权重随机选择

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

也就是说，选取下标 i 的概率为 w[i] / sum(w) 。

先构造前缀，再二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//产生随机数
        Random random = new Random();
        int randomNum = random.nextInt(arr[arr.length - 1]) + 1;
        //二分查找随机数所在的区间
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] == randomNum) {
                return mid;
            } else if (arr[mid] > randomNum) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

82. 删除排序链表中的重复元素 II

示例 1:

1
2
输入: 1->2->3->3->4->4->5
输出: 1->2->5
1
2
3
4
5
6
7
8
9
10
11
12
13
while(head!=null && head.next!=null)
  {
      if(head.val==head.next.val)
      {
          while(head.next!=null && head.next!=null && head.val==head.next.val)
          {
           . .. . .. . .
          }
       }
       else{
       
       }
   }

8. 字符串转换整数 (atoi)

1
2
3
4
5
6
7
8
9
10
11
12
13
if(s.length()==0 || s==null) return 0;
s=s.trim();
if(s.length()==0 || s==null) return 0;
...
long a=0;
for{
if(!(c>='0' && c<='9'))
{
return flag?(int)a:(int)-a;
}
a=a*10+c-'0';
if(a>Integer.MAX_VALUE)
}

50. Pow(x, n)

1
2
3
4
5
if(n==0) return 1; 
    if(n<0 && n%2==-1) return 1/myPow(x,-(n+1))*1/x;
    double half=myPow(x,n/2);
    if(n%2==1) return half*half*x;
    return half*half;

147. 对链表进行插入排序

1
2
3
4
5
6
7
while(head!=null && head.next!=null)
    {
        if(head.val==head.next.val)
        {
            head=head.next;
            continue;
        }

264. 丑数 II

编写一个程序，找出第 n 个丑数。

丑数就是质因数只包含 2, 3, 5 的正整数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

三指针+三因子

1
2
3
4
5
6
7
for(int i=1;i<n;i++)
{
   int temp=Math.min(fac2*ugly[idx2],Math.min(fac3*ugly[idx3],fac5*ugly[idx5]));
   if(temp==fac2*ugly[idx2])
   ...
   ugly[i]=temp;
 }

402. 移掉K位数字

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:

num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
示例 1 :

输入: num = “1432219”, k = 3
输出: “1219”
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

从左到右，找第一个比后面大的字符，删除，清零，k次扫描。

1
2
3
4
5
6
7
for (int i = 0; i < k; i++) {
           int idx = 0;
           for (int j = 1; j < s.length() && s.charAt(j) >= s.charAt(j - 1); j++) idx = j;
           System.out.println(idx+" "+s.charAt(idx));
           s.deleteCharAt(idx);
           while (s.length() > 1 && s.charAt(0) == '0') s.deleteCharAt(0);
       }

86. 分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

1
ListNode newTemp=partition(head.next,x);

71. 简化路径

1
2
3
4
5
6
if (item.isEmpty() || item.equals(".")) continue;
       if (item.equals("..")) {
           if (!stack.empty()) stack.pop();
       } else {
           stack.push(item);
       }

22. 括号生成

回溯

1
2
3
4
5
6
7
8
private void backtrack(List<String> res,int left,int right,String ans,int n)

if(left>=right)
        {
            String str=new String(ans);
            backtrack(res,left+1,right,str+"(",n);
            backtrack(res,left,right+1,str+")",n);
        }

279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

1
2
3
4
if(i>=j*j)
        {
            dp[i]=Math.min(dp[i],dp[i-j*j]+1);
        }

139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict*，判定 *s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

  • 拆分时可以重复使用字典中的单词。
  • 你可以假设字典中没有重复的单词。

示例 1：

1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

双指针+memo数组记录前n个是否匹配上

1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<=n;i++) // 注意这一句是为了避免a ["a"]的情况
    {
        for(int j=0;j<i;j++)
        {
            if(memo[j] && wordDict.contains(s.substring(j,i)))
            {
                memo[i]=true;
                break;
            }
        }
    }

647. 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

1
2
3
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

动态规划，从数组尾部向前遍历，两个for

1
2
3
4
5
if(s.charAt(i)==s.charAt(j)&& (j-i<=2 || dp[i+1][j-1]==true) )
            {
                dp[i][j]=true;
                res++;
            }

75. 颜色分类

难度中等805

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

三指针，current,left,right进行遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
if(nums[current]==0)
{
  swap(nums,left,current);
  current++;
  left++;  
}
else if(nums[current]==1)
{
   current++; 
}
else{
 ...
}

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

示例 1：

1
2
输入：s = "3[a]2[bc]"
输出："aaabcbc"

用一个StringBuilder sb记录先前的字符串，两个栈一个数字栈，一个字符串栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for(char c : s.toCharArray()){
            if('0' <= c && '9' >= c){
                mul = mul * 10 + (c - '0');
            }else if(c == '['){
                //遇到左括号，保存前面的值。
                strStack.push(sb);
                numStack.push(mul);
                sb = new StringBuilder();
                mul = 0;
            }else if(c == ']'){
                //出栈
                int cnt = numStack.pop();
                StringBuilder tmp = sb;
                sb = strStack.pop();
                for(int i = 0; i < cnt; i++){
                    sb.append(tmp);
                }
            }else{
                sb.append(c);
            }

1438. 绝对差不超过限制的最长连续子数组

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

1
2
3
PriorityQueue<Integer> minQueue = new PriorityQueue<>(Comparator.naturalOrder());
...
 maxQueue.remove((Integer) nums[left]);

807. 保持城市天际线

最后，从新数组的所有四个方向（即顶部，底部，左侧和右侧）观看的“天际线”必须与原始数组的天际线相同。 城市的天际线是从远处观看时，由所有建筑物形成的矩形的外部轮廓。 请看下面的例子。

两次两个for，取行和列最大值

43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

两个for，数组长度为num1.length+num2.length,低位为 num[i+j+1]高位 num[i+j]

1
2
3
4
5
6
7
8
9
for(int i = n1; i >= 0; --i) {
            for(int j = n2; j >= 0; --j) {
                int bitmul = (num1.charAt(i)-'0') * (num2.charAt(j)-'0');      
                bitmul += mul[i+j+1]; // 先加低位判断是否有新的进位
                
                mul[i+j] += bitmul / 10;
                mul[i+j+1] = bitmul % 10;
            }
        }

496. 下一个更大元素 I

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

先用HashMap，遍历nums2.

503. 下一个更大元素 II

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

扩容数组，进行循环判断

1
2
3
4
5
6
7
for (int i = 0; i < n*2; i++){
            int num = nums[i % n];
            while(!stack.isEmpty() && num > nums[stack.peek()]){
                res[stack.pop()] = num;
            }
            if(i < n) stack.add(i);
        }

951. 翻转等价二叉树

我们可以为二叉树 T 定义一个翻转操作，如下所示：选择任意节点，然后交换它的左子树和右子树。

1
2
3
4
5
if (root1 == null || root2 == null || root1.val != root2.val) {
            return false;
        }
        return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||
                (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));

701. 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

用一个parent记录父结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if(root == null){
            return new TreeNode(val);
        }
        TreeNode parent = root,p = root;
        while(p != null){
            parent = p;
            p = p.val < val ? p.right : p.left;
        }
        if(parent.val < val){
            parent.right = new TreeNode(val);
        } else {
            parent.left = new TreeNode(val);
        }
        return root;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
   * 递归版
   */
  public TreeNode insertIntoBST(TreeNode root, int val) {
      if(root == null){
          return new TreeNode(val);
      }
      if(root.val < val){
          root.right = insertIntoBST(root.right,val);
      } else {
          root.left = insertIntoBST(root.left,val);
      }
      return root;
  }

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

1
2
3
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

小于0就进行交换

1
2
3
4
5
6
7
8
if(nums[i] < 0){          // 3 2 -1 -1
                                   //   3 6 -2  6
             int tmp = imax;      //    3 2 -6  2
             imax = imin;
             imin = tmp;
           }
           imax = Math.max(imax*nums[i], nums[i]);
           imin = Math.min(imin*nums[i], nums[i]);

525. 连续数组

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。

把0变为-1，前缀和+Map进行存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int findMaxLength(int[] nums) {
    for (int i = 0; i < nums.length; i++) if (nums[i] == 0) nums[i] = -1;
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    int sum = 0, res = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (map.containsKey(sum)) res = Math.max(res, i - map.get(sum));
        else map.put(sum, i);
    }
    return res;
}
}

468. 验证IP地址

编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址。

  • 如果是有效的 IPv4 地址，返回 "IPv4" ；
  • 如果是有效的 IPv6 地址，返回 "IPv6" ；
  • 如果不是上述类型的 IP 地址，返回 "Neither" 。

对.进行split，要用IP.split(“\.”); split完后判断String[]的长度，是否为4或8

IPV4: 对每个数字字符串，判断是否为数字，然后累加，判断是否大于255

IPV6 : if (!((c >= ‘a’ && c <= ‘f’) || (c >= ‘A’ && c <= ‘F’) || (c >= ‘0’ && c <= ‘9’)))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (String string : strings) {
           if (string.length() == 0 || (string.charAt(0) == '0' && string.length() != 1)) {
               return false;
           }
           int num = 0;
           for (int i = 0; i < string.length(); i++) {
               char c = string.charAt(i);
               if (!(c >= '0' && c <= '9')) {
                   return false;
               }
               num = num * 10 + c - '0';
               if (num > 255) {
                   return false;
               }
           }
       }

260. 只出现一次的数字 III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

全部异或取结果为K，开一个res数组,res[2] if(num&k)==0 res[1]^=num

1
2
3
4
5
6
7
8
9
10
11
12
13
nt k=s & (-s);
    int[] res=new int[2];
    for(int num:nums)
    {
        if((num &k)==0)
        {
            res[1]^=num;
        }
        else
         {
             res[0]^=num;
         }
    }

347. 前 K 个高频元素

示例 1:

1
2
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
1
2
3
4
5
6
7
8
9
10
11
12
for(Integer key:map.keySet())
    {
      if(pq.size()<k)
      {
        pq.add(key);  
      }
      else if (map.get(key)>map.get(pq.peek()))
     {
       pq.remove();
       pq.add(key); 
     } 
    }

842. 将数组拆分成斐波那契序列

给定一个数字字符串 S，比如 S = "123456579"，我们可以将它分成斐波那契式的序列 [123, 456, 579]。

采用dfs，首先考虑一个idx和一个存储先前字符串的idx

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public boolean dfs(String s,int idx,LinkedList<Integer> res)
    {
       if(idx==s.length())
       {
           return res.size()>2;
       }
       for(int i=idx+1;i<=s.length();i++)
       {
          String temp=s.substring(idx,i);
          if(s.charAt(idx)=='0' && i>idx+1 || Long.valueOf(temp)>Integer.MAX_VALUE)
          {
              break;
          } 
          int str=Integer.valueOf(temp);
          int one=res.size()>=2?res.get(res.size()-2):-1;
          int two=res.size()>=2?res.get(res.size()-1):-1;
          res.add(str);
          if((one==-1 || two==-1 || one+two==str) && dfs(s,i,res))
          {
              return true;
          }
          res.remove(res.size()-1);
       }
       return false; 
    }

179. 最大数

给定一组非负整数 nums，重新排列它们每个数字的顺序（每个数字不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10,2]
输出：”210”

1
2
3
4
5
6
7
8
9
Comparator<String> cmp=new Comparator<String>()
    {
        public int compare(String str1,String str2)
        {
           String s1=str1+str2;
           String s2=str2+str1;
           return s2.compareTo(s1);  
        }
    };

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

动态规划

1
2
3
 dp[0]=nums[0];
   dp[1]=Math.max(nums[0],nums[1]);
dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);

213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

1
2
3
4
5
6
7
8
9
10
11
if (len <= 2) return len == 0 ? 0 : len == 1 ? nums[0] : Math.max(nums[0], nums[1]);
       int[] dp1 = new int[len - 1];
       int[] dp2 = new int[len - 1];
       dp1[0] = nums[0];
       dp1[1] = Math.max(nums[0], nums[1]);
       dp2[0] = nums[1];
       dp2[1] = Math.max(nums[2], nums[1]);
       for (int i = 2; i < len - 1; i++) {
           dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
           dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i + 1]);
       }

609. 在系统中查找重复文件

给定一个目录信息列表，包括目录路径，以及该目录中的所有包含内容的文件，您需要找到文件系统中的所有重复文件组的路径。一组重复的文件至少包括二个具有完全相同内容的文件。

516. 最长回文子序列

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

1
2
3
4
5
6
7
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i+1][j-1] + 2;
}
//表明这时dp[i][j]只需取两者之间的最大值即可
else{
dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
}

416. 分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

  1. 每个数组中的元素不会超过 100
  2. 数组的大小不会超过 200

示例 1:

1
2
3
4
5
输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].
1
2
3
4
if(j-nums[i-1]<0) dp[i][j]=dp[i-1][j];
else{
 dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]];
}
1
2
3
4
5
6
7
8
9
10
boolean[] dp=new boolean[target+1];
     dp[0]=true;
     for(int i=0;i<n;i++)
     {
         int num=nums[i];
         for(int j=target;j>=num;j--)
         {
             dp[j]=dp[j] || dp[j-num];
         }
     }

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

img

示例 1：

1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

设置一个idx往后遍历，对每一个idx取出Map的数据

1
2
3
4
5
6
7
8
9
String value = map.get(digits.charAt(index));
 for (int j = 0; j < value.length(); j++) {

     // drill down
     backTrack(list, digits, map, index + 1, sb.append(value.charAt(j)));

     // reverse states
     sb.deleteCharAt(sb.length() - 1);
 }

49. 字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

1
2
3
4
5
6
7
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
1
2
Map<String, List<String>> map = new HashMap<String, List<String>>();
遍历数组，然后Sort一下，存入map

334. 递增的三元子序列

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
if (nums[i] <= first) {
    first = nums[i];
    } else if (nums[i] <= second) {
    second = nums[i];
    } else {
    return true;
}

208. 实现 Trie (前缀树)

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

1
2
3
4
5
6
7
8
Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

说明:

  • 你可以假设所有的输入都是由小写字母 a-z 构成的。
  • 保证所有输入均为非空字符串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
private class TrieNode{
        private boolean isEnd;
        private TrieNode[] next;
        public TrieNode()
        {
           this.isEnd=false;
           this.next=new TrieNode[26]; 
        }
    }
 /** Inserts a word into the trie. */
    public void insert(String word) {
     TrieNode cur=root;
     for(int i=0;i<word.length();i++)
     {
         int c=word.charAt(i)-'a';
         if(cur.next[c]==null)
         {
             cur.next[c]=new TrieNode();
         }
         cur=cur.next[c];
     }
     cur.isEnd=true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode cur = root;
		for (int i = 0; i < word.length(); i++) {
			int ch =  word.charAt(i) - 'a';
			if (cur.next[ch] == null)
				return false;
			cur = cur.next[ch];
		}
		return cur.isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
		for (int i = 0; i < prefix.length(); i++) {
			int ch = prefix.charAt(i) - 'a';
			if (cur.next[ch] == null)
				return false;
			cur = cur.next[ch];
		}
		return true;
    }

498. 对角线遍历

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

image-20210307115017107

定义r和c，初始为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if ((r + c) % 2 == 0) {
            if (c == col - 1) {
                // 往下移动一格准备向下遍历
                r++;
            } else if (r == 0) {
                // 往右移动一格准备向下遍历
                c++;
            } else {
                // 往上移动
                r--;
                c++;
            }
        }
        else{
        ...
        }

238. 除自身以外数组的乘积

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

1
2
输入: [1,2,3,4]
输出: [24,12,8,6]

双指针，两次遍历

1
2
3
4
5
for(int i=nums.length-1;i>=0;i--)
   {
       output[i]*=right;
       right*=nums[i];
   }

55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
1
2
3
4
5
6
7
8
9
for(int i=0;i<nums.length;i++)
    {
        if(i>right) return false;
        right=Math.max(right,nums[i]+i);
        if(right>=nums.length-1)
        {
            return true;
        }
    }

45. 跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

1
2
3
4
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

80. 删除排序数组中的重复项 II

难度中等373

给定一个增序排列数组 nums ，你需要在 原地 删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

  • len表示的是删除重复元素后新序列的长度，同时也表示新元素进入新序列的索引；
  • i就是循环变量，用于遍历整个旧序列；
  • if (len < 2) nums[len++] = nums[i];的意思就是如果新序列的长度小于2（即新序列中不会存在两个相同的元素，这时候i位置所在元素不会和新序列中的元素相同），直接将新元素加入到新序列中，并更新新序列的长度；
  • if (nums[i] != nums[len-2]) nums[len++] = nums[i];的意思就是如果新元素加入后不会和前两个元素构成3个相同的元素（nums[len-2]就是直接取新序列中倒数第二个元素，如果该元素和新元素相同，说明加入后会构成3个相同的元素，显然是不符合题意的），就将新元素加入到新序列中，并更新新序列的长度；
  • 题意只要求将新序列紧挨在一起就行，多出的长度将不参与评测；
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int removeDuplicates(int[] nums) {
      int len = 0;
        for (int i = 0; i < nums.length; i++) {
            if (len < 2 || nums[i] != nums[len-2])
                nums[len++] = nums[i];
        }
        return len;
    }
}

26. 删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

1
2
3
4
5
6
7
8
9
for (int j = 1; j < nums.length; j++) {
        while(j<nums.length && nums[j]==nums[i])
        {
            j++;
        }
        //1 1 2 3
        // 
        if(j<nums.length)  nums[++i]=nums[j];        
    }

767. 重构字符串

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

1
2
输入: S = "aab"
输出: "aba"

构造优先队列PriorityQueue pq=new PriorityQueue<>((a,b)->cnt[b-‘a’]-cnt[a-‘a’]);

1
2
3
4
5
if(cnt[i]!=0)
{
	pq.add((char)(i+'a'));
}
 while(pq.size()>=2)

523. 连续的子数组和

给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 nk，其中 n 也是一个*整数**。

示例 1：

1
2
3
输入：[23,2,4,6,7], k = 6
输出：True
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。

map.put(0,-1)是为了避免数组前几位mod为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
if(nums.length < 2) return false;
       for(int i = 0; i < nums.length-1; ++i) 
           if(nums[i] == 0 && nums[i+1] == 0) return true;
       if(k == 0) return false;
       if(k < 0) k = -k;
       
       Map<Integer, Integer> map = new HashMap<>();
       //  map.put(0, -1);
       int sum = 0;
       for(int i = 0; i < nums.length; ++i) {
           sum += nums[i];
           int mod = sum % k;
           System.out.println(sum+" "+mod+" ");
           if(map.containsKey(mod)) {
               if(i-map.get(mod) > 1)
                   return true;
           }
           else // 不存在再更新
               map.put(mod, i); // 0 0 
                                // 0 1
       //    System.out.println(mod+" "+map.get(mod));    
       }
       return false;

96. 不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

1
2
3
4
5
6
7
8
9
10
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
1
2
3
4
5
6
//dp[n]=dp[0]*dp[n-1-0]+dp[1]*dp[n-1-1]
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=i-1;j++)
        dp[i]+=dp[j]*dp[i-1-j];
    }

376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

示例 1:

1
2
3
输入: [1,7,4,9,2,5]
输出: 6 
解释: 整个序列均为摆动序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        int up = 1;
        int down = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            }
            if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }
}

1498. 满足条件的子序列数目

给你一个整数数组 nums 和一个整数 target 。

请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。

由于答案可能很大，请将结果对 10^9 + 7 取余后返回。

排序+双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=1;i<n;i++){
           pow[i]=pow[i-1]*2%mod;
       }
       int left=0,right=n-1;
       while(left<=right){
           if(nums[left]+nums[right]<=target){
               res+=pow[right-left];
               res%=mod;
               left++;
           }
           else
               right--;
       }

863. 二叉树中所有距离为 K 的结点

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。

返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
输出：[7,4,1]
解释：
所求结点为与目标结点（值为 5）距离为 2 的结点，
值分别为 7，4，以及 1



注意，输入的 "root" 和 "target" 实际上是树上的结点。
上面的输入仅仅是对这些对象进行了序列化描述。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        List<Integer>[] graph = new ArrayList[1000];
        for(int i = 0; i < 1000; i++){
            graph[i] = new ArrayList<Integer>();
        }
        buildGraph(graph, root);
        Queue<Integer[]> queue = new LinkedList<Integer[]>();
        boolean[] vis = new boolean[1000];
        List<Integer> res = new ArrayList<Integer>();
        queue.add(new Integer[]{target.val,0});
        vis[target.val] = true;
        while(queue.peek() != null){
            Integer[] arr = queue.poll();
            if(arr[1] == K){
                res.add(arr[0]);
                continue;
            }
            for(int child : graph[arr[0]]){
                if(!vis[child]){
                    queue.add(new Integer[]{child, arr[1] + 1});
                    vis[child] = true;
                }
            }
        }
        return res;
    }
    
    void buildGraph(List<Integer>[] graph, TreeNode node){
        if(node == null) return;
        if(node.left != null){
            graph[node.val].add(node.left.val);
            graph[node.left.val].add(node.val);
            buildGraph(graph, node.left);
        }
        if(node.right != null){
            graph[node.val].add(node.right.val);
            graph[node.right.val].add(node.val);
            buildGraph(graph, node.right);
        }
    }

45. 跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

1
2
3
4
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

我来大概解释一下吧，献丑了，鉴于题目已经给了前提，那就是肯定能到达最后一个元素，那么只要考虑每一跳所能达到的最远位置就行了，也就是每次都选择最远可达的点，reach是当前需要进行跳跃的右界限，nextReach是下一次跳跃的右界限，nextReach的值一直动态更新，以保证每次跳跃都是最远的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int jump(int[] nums) {
        if(nums.length == 1) return 0;
        int reach = 0;
        int nextreach = nums[0];
        int step = 0;
        for(int i = 0;i<nums.length;i++){
            nextreach = Math.max(i+nums[i],nextreach);
            if(nextreach >= nums.length-1) return (step+1);
            if(i == reach){
                step++;
                reach = nextreach;
            }
        }
        return step;
    }
}

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

1
2
3
4
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
1
2
3
4
5
6
7
8
9
10
11
12
while(l<=r)
   {
       if(nums[l]*nums[l]<nums[r]*nums[r])
       {
          arr[idx--]=nums[r]*nums[r];
          r--;
       }
       else{
           arr[idx--]=nums[l]*nums[l];
           l++;
       }
   }

680. 验证回文字符串 Ⅱ

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

1
2
输入: "aba"
输出: True
1
2
3
4
5
6
7
8
9
while(i<j)
    {
        if(s.charAt(i)!=s.charAt(j))
        {
            return isValid(s,i+1,j) || isValid(s,i,j-1);
        }
        i++;
        j--;
    }

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

1
2
输入：strs = ["flower","flow","flight"]
输出："fl"
1
2
3
4
5
6
7
8
9
10
11
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() || c!=strs[j].charAt(i))
          {
            return strs[0].substring(0,i);
          }  
        }
    }

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

1
2
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
1
2
3
4
5
6
7
for(int i=0;i<nums.length;i++)
     {
         if(nums[i]!=0)
         {
             nums[index++]=nums[i];
         }
     }

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

开一个new int[26]的数组 ，接下来一个+，一个-

1
2
3
4
for(int i = 0; i< s.length(); i++) {
            alpha[s.charAt(i) - 'a'] ++;
            alpha[t.charAt(i) - 'a'] --;
        }

572. 另一个树的子树

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

1
2
3
4
5
6
7
8
9
10
public boolean isSame(TreeNode s,TreeNode t)
   {
    if(s==null && t==null) return true;
    if(s==null || t==null) return false;
    if(s.val==t.val)
    {
       return isSame(s.left,t.left) && isSame(s.right,t.right); 
    }
    return false;   
   }

190. 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

1
2
3
4
5
6
for(int i=0;i<32;i++)
    {
        int bit=n&1;
        n=n>>>1;
        res=(res<<1)^bit;
    }

459. 重复的子字符串

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:

1
2
3
4
5
输入: "abab"

输出: True

解释: 可由子字符串 "ab" 重复两次构成。
1
return (s+s).substring(1,s.length()*2-1).indexOf(s)!=-1;

7. 整数反转

给你一个 32 位的有符号整数 x ，返回 x 中每位上的数字反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

1
2
3
4
5
6
7
8
9
10
while(x!=0)
    {
        int pop=x%10;
        if(res>Integer.MAX_VALUE/10 || (res==Integer.MAX_VALUE/10 && pop>7))
        return 0;
        if(res<Integer.MIN_VALUE/10 || (res==Integer.MIN_VALUE/10 && pop<-8))
        return 0;
        res=res*10+pop;
        x/=10;
    }

204. 计数质数

统计所有小于非负整数 n 的质数的数量。

示例 1：

1
2
3
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
1
2
3
4
5
6
7
8
9
10
11
for(int i=2;i<n;i++)
     {
         if(!isPrime[i])
         {
          count++;
          for(int j=2*i;j<n;j+=i)
          {
              isPrime[j]=true;
          }
         }
     }

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例 1：

1
2
3
4
5
6
7
输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isHappy(int n) {
      int sum, count = 0;
        while (n != 1 && count < 500)
        {
            sum = 0;
            while (n!=0)
            {
                sum += (n % 10) * (n % 10);
                n /= 10;
            }
            n = sum;
            count++;
        }
        return n == 1;  
    }

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

1
2
3
4
5
6
7
8
9
10
public void helper(TreeNode root,int count)
     {
         if(root==null) return;
         if(root.left==null && root.right==null)
         {
             res=Math.min(res,count);
         }
         helper(root.left,count+1);
         helper(root.right,count+1);
     }

922. 按奇偶排序数组 II

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] sortArrayByParityII(int[] A) {
        int j = 1;
        for (int i = 0; i < A.length - 1; i = i + 2) {
            if ((A[i] & 1) != 0) {
                while ((A[j] & 1) != 0) {
                    j = j + 2;
                }
                int tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
            }
        }
        return A;
    }
}

9. 回文数

1
2
3
4
5
6
7
8
9
10
11
while(x>0)
     {
         int left=x/div;
         int right=x%10;
         if(left!=right)
         {
             return false;
         }
         x= (x%div)/10;
         div/=100;
     }

1299. 将每个元素替换为右侧最大元素

给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。

完成所有替换操作后，请你返回这个数组。

1
2
3
4
5
6
7
for (int i = arr.length - 1; i >= 0; i--) {
           int temp = arr[i];
           arr[i] = max;
           if (temp > max) {
               max = temp;
           }
       }

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 。

1
2
3
4
5
6
7
dp[0][0]=0;           // 不持有
     dp[0][1]=-prices[0]; // 持有   
     for(int i=1;i<prices.length;i++)
     {
         dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
         dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
     }

405. 数字转换为十六进制数

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。

注意:

  1. 十六进制中所有字母(a-f)都必须是小写。
  2. 十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
  3. 给定的数确保在32位有符号整数范围内。
  4. 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。

示例 1：

1
2
3
4
5
输入:
26

输出:
"1a"
1
2
3
4
5
6
7
8
char[] hex="0123456789abcdef".toCharArray();
     StringBuilder sb=new StringBuilder();
     while(num!=0)
     {
         int temp=num & 0xf;
         sb.append(hex[temp]);
         num>>>=4;
     }

836. 矩形重叠

矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。矩形的上下边平行于 x 轴，左右边平行于 y 轴。

如果相交的面积为 正 ，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。

给出两个矩形 rec1 和 rec2 。如果它们重叠，返回 true；否则，返回 false 。

示例 1：

1
2
输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true
1
2
3
4
5
6
7
8
if(rec2[1] >= rec1[3] || rec1[1] >= rec2[3]){
        return false;
        }
System.out.println("hello");
if(rec1[0] >= rec2[2] || rec1[2] <= rec2[0]){
      return false;
    }
 return true;

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
while(i<version1.length() || j<version2.length())
    {
        int a=0,b=0;
        while(i<version1.length() && version1.charAt(i)!='.')
        {
            a=a*10+version1.charAt(i)-'0';
            i++;
        }
        while(j<version2.length() && version2.charAt(j)!='.')
        {
            b=b*10+version2.charAt(j)-'0';
            j++;
        }
        if (a > b) return 1;
        else if (a < b) return -1;
        i++;
        j++;
    }

443. 压缩字符串

给定一组字符，使用原地算法将其压缩。

压缩后的长度必须始终小于或等于原数组长度。

数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。

在完成原地修改输入数组后，返回数组的新长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
while(idx<n)
    {
       // ["a","b","b","c","c","c"]
        char c=chars[idx];
        int count=0;
        while(idx<n && chars[idx]==c)
        {
            idx++;
            count++;
        }
        chars[begin++]=c;
        if(count!=1)
        {
            for(char cc:String.valueOf(count).toCharArray())
            {
                chars[begin++]=cc;
            }
        }
    }

316. 去除重复字母

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例 1：

1
2
输入：s = "bcabc"
输出："abc"

思路就是 遇到一个新字符 如果比栈顶小 并且在新字符后面还有和栈顶一样的 就把栈顶的字符抛弃了

1013. 将数组分成和相等的三个部分

给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。

形式上，如果可以找出索引 i+1 < j 且满足 A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1] 就可以将数组三等分。

示例 1：

1
2
3
输入：[0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 值得注意的是最后一句return cnt >= 3, 为什么是大于等于呢? 显然, 如果找到等于 sum / 3的部分和数量cnt < 3, 那么一定不满足题意, cnt = 3也很好理解, 问题就在于, 当找出两个等于 sum / 3的部分和后, 数组剩余的部分其和一定也是 sum / 3, 但是考虑到sum = 0的特殊情况, 最后的sum / 3的数组中, 仍然可能含有部分和为0的子结构, 导致计数变量cnt > 3
class Solution {
    public boolean canThreePartsEqualSum(int[] A) {
        int sum=0;
        for(int i:A){
            sum+=i;
        }
        if(sum%3!=0) return false;
        sum/=3;
        System.out.println(sum);
        int count=0,temp=0;
        for(int i:A){
            temp+=i;
            if(temp==sum){
                count++;
                temp=0;
            }
        }
     //   System.out.println(count+ " " + sum);
        return count ==3 || (count > 3 && sum <= 0);
    }
}

628. 三个数的最大乘积

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

1
2
Arrays.sort(nums);
      return Math.max(nums[nums.length-1]*nums[nums.length-2]*nums[nums.length-3],nums[0]*nums[1]*nums[nums.length-1]);

227. 基本计算器 II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

示例 1：

1
2
输入：s = "3+2*2"
输出：7

示例 2：

1
2
输入：s = " 3/2 "
输出：1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int calculate(String s) {
        // 保存上一个符号，初始为 +
        char sign = '+';
        Stack<Integer> numStack = new Stack<>();
        // 保存当前数字，如：12是两个字符，需要进位累加
        int num = 0;
        int result = 0;
        for(int i = 0; i < s.length(); i++){
            char cur = s.charAt(i);
            if(cur >= '0'){
                // 记录当前数字。先减，防溢出
                num = num*10 - '0' + cur;
            }
            if((cur < '0' && cur !=' ' )|| i == s.length()-1){
                // 判断上一个符号是什么
                switch(sign){
                    // 当前符号前的数字直接压栈
                    case '+': numStack.push(num);break;
                    // 当前符号前的数字取反压栈
                    case '-': numStack.push(-num);break;
                    // 数字栈栈顶数字出栈，与当前符号前的数字相乘，结果值压栈
                    case '*': numStack.push(numStack.pop()*num);break;
                    // 数字栈栈顶数字出栈，除于当前符号前的数字，结果值压栈
                    case '/': numStack.push(numStack.pop()/num);break;
                }
                // 记录当前符号
                sign = cur;
                // 数字清零
                num = 0;
            }
        }
        // 将栈内剩余数字累加，即为结果
        while(!numStack.isEmpty()){
            result += numStack.pop();
        }
        return result;
    }
}

224. 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

示例 1：

1
2
输入：s = "1 + 1"
输出：2

示例 2：

1
2
输入：s = " 2-1 + 2 "
输出：3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//https://leetcode-cn.com/problems/basic-calculator/solution/ji-ben-ji-suan-qi-zhan-dui-yu-gua-hao-yo-a1f0/

class Solution {

    public int calculate(String s) {

        Deque<Character> q = new LinkedList<>();
        for (char c : s.toCharArray()) {

            q.offer(c);
        }
        return helper(q);
    }

    private int helper(Deque<Character> q) {

        Stack<Integer> stack = new Stack<>();
        char preSign = '+';
        int num = 0;
        int res = 0;

        while (!q.isEmpty()) {

            char c = q.poll();
            if (Character.isDigit(c)) num = num * 10 + c -'0';
            if (c == '(') num = helper(q);

            if(!Character.isDigit(c) && c != ' ' || q.isEmpty()) {
                
                if (preSign == '+') stack.push(num);
                else if (preSign == '-') stack.push(-num);
                else if (preSign == '*') {

                    stack.push(stack.pop() * num);
                } else if (preSign == '/') {

                    stack.push(stack.pop() / num);
                }
                num = 0;
                preSign = c;
            }

            if (c == ')') break;
        }
        while (!stack.isEmpty()) {

            res += stack.pop();
        }
        return res;
    }
}

作者：Booooo_
链接：https://leetcode-cn.com/problems/basic-calculator/solution/ji-ben-ji-suan-qi-zhan-dui-yu-gua-hao-yo-a1f0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

N进制相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;

public class N进制加法 {

    static String addByBase(String a, String b, int base) {

        StringBuffer ans = new StringBuffer();

        int n = Math.max(a.length(), b.length()), carry = 0;

        for (int i = 0; i < n; i++) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % base + '0'));
            carry /= base;
        }

        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();

        return ans.toString();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next(); // 数字 a
        String b = sc.next(); // 数字 b
        int base = sc.nextInt(); // 进制
        System.out.println(addByBase(a, b, base));
    }

}

剑指offer

剑指 Offer 05. 替换空格

难度简单80收藏分享切换为英文接收动态反馈

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

示例 1：

1
2
输入：s = "We are happy."
输出："We%20are%20happy."
1
2
3
4
5
6
7
8
9
10
while (P1 >= 0 && P2 > P1) {
        char c = str.charAt(P1--);
        if (c == ' ') {
            str.setCharAt(P2--, '0');
            str.setCharAt(P2--, '2');
            str.setCharAt(P2--, '%');
        } else {
            str.setCharAt(P2--, c);
        }
    }

12. 矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[[“a”,”b“,”c”,”e”],
[“s”,”f“,”c“,”s”],
[“a”,”d”,”e“,”e”]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

示例 1：

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
1
2
3
4
5
6
7
8
9
10
vis[i][j]=1;
      
      boolean ans= false;
      ans=
      dfs(i+1,j,board,word,index+1) || 
      dfs(i-1,j,board,word,index+1) ||
      dfs(i,j+1,board,word,index+1) || 
      dfs(i,j-1,board,word,index+1);
      
      vis[i][j]=0;

13. 机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

1
2
输入：m = 2, n = 3, k = 1
输出：3
1
2
3
4
5
6
7
8
9
public int dfs(int m,int n,int k,int x,int y)
    {
      if(!check(m,n,k,x,y) || vis[x][y]==1)
      {
          return 0;
      }
      vis[x][y]=1;
      return 1+dfs(m,n,k,x+1,y)+dfs(m,n,k,x-1,y)+dfs(m,n,k,x,y+1)+dfs(m,n,k,x,y-1);
    }

15. 二进制中1的个数

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：

1
2
3
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
1
2
3
4
5
while(n!=0)
   {
       if((n & 1)==1) cnt++;
       n=n>>>1;
   }

21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例：

1
2
3
输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。
1
2
3
4
5
6
7
8
for(int i=0;i<nums.length;i++)
     {
         if(nums[i]%2==1)
         {
             swap(nums,i,p);
             p++;
         }
     }

24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

1
2
3
4
5
6
7
while(head!=null)
        {
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }

26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

image-20210308095816745

1
2
3
4
5
6
7
public boolean dfs(TreeNode t1,TreeNode t2)
    {
      if(t2==null) return true;
      if(t1==null) return false;
      if(t1.val!=t2.val) return false;
      return dfs(t1.left,t2.left) && dfs(t1.right,t2.right); 
    }

28. 对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

image-20210308100250659

1
2
3
4
5
6
7
8
TreeNode t1=q.poll();
        TreeNode t2=q.poll();
        if(t1==null && t2==null) continue;
        if(t1==null || t2==null || t1.val!=t2.val) return false;
        q.add(t1.left);
        q.add(t2.right);
        q.add(t1.right);
        q.add(t2.left);

31.栈的压入、弹出序列

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

1
2
3
4
5
6
7
8
9
10
for(int i=0;i<pushed.length;i++)
    {
      stack.push(pushed[i]);
      while(!stack.isEmpty() && stack.peek()==popped[idx])
      {
          stack.pop();
          idx++;
      }

    }

30. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void push(int x) {
    if(x<=min)
    {
        stack.push(min);
        min=x;
    }
    stack.push(x);
    }
    
    public void pop() {
    if(stack.pop()==min)
    {
        min=stack.pop();
    }

03. 数组中重复的数字

找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

1
2
3
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=0;i<nums.length;i++)
     {
         while(nums[i]!=i)
         {
             if(nums[i]==nums[nums[i]])
             {
                 return nums[i];
             }
             int tmp=nums[i];
             nums[i]=nums[tmp];
             nums[tmp]=tmp;
         }
     }

剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：

1
2
3
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
1
2
3
4
5
6
7
8
9
int[] dp=new int[n+1];
    dp[1]=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            dp[i]=Math.max(dp[i],Math.max(dp[j],j)*(i-j));
        }
    }
1
2
3
4
5
6
7
while(n>=5)
     {
        n-=3;
        cnt*=3;
        cnt%=1000000007;
     }
     return (int)(cnt*n%1000000007);

33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

1
2
3
4
5
    5
   / \
  2   6
 / \
1   3
1
2
3
4
5
6
7
8
9
10
11
int rootValue=num[right];
int k=left;
while(k<right && num[k]<rootValue)
{
k++;
}
for(int i=k;i<right;i++)
{
if(num[i]<rootValue) return false;
}
return helper(num,left,k-1) && helper(num,k,right-1);

46. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

1
2
3
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
1
2
3
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
1
2
3
4
5
6
7
if(str.charAt(i-2) != '0' &&
    str.substring(i-2,i).compareTo("25") <= 0)            {
    dp[i] = dp[i-1] + dp[i-2];  
    }else{
    //如果不能组成,就单独为1个数字,和前面方法数相等
    dp[i] = dp[i-1];
}

37. 序列化二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public String serialize(TreeNode root) {
     if(root==null) return "";
     StringBuilder sb=new StringBuilder();
     LinkedList<TreeNode> q=new LinkedList<>();
     q.add(root);
     while(!q.isEmpty())
     {
         TreeNode tmp=q.poll();
         if(tmp==null)
         {
             sb.append("n ");
             continue;
         }
         sb.append(tmp.val+" ");
         q.add(tmp.left);
         q.add(tmp.right);        
     }
     return sb.toString(); 
    }

        // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
    if(data=="") return null;
    String[] values=data.split(" ");
    TreeNode root=new TreeNode(Integer.parseInt(values[0]));
    LinkedList<TreeNode> q=new LinkedList<>();
    q.add(root);
    for(int i=1;i<values.length;i++)
    {
       TreeNode node=q.poll();
       if(!values[i].equals("n"))
       {
          TreeNode left=new TreeNode(Integer.parseInt(values[i]));          node.left=left;
          q.add(left);  
       }
       if(!values[++i].equals("n"))
       {
          TreeNode right=new TreeNode(Integer.parseInt(values[i]));          node.right=right;
          q.add(right);  
       }
    }
    return root;    
    }

41. 数据流中的中位数

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构

用大顶堆+小顶堆方法，可以看作大顶堆是普通班，小顶堆是实验班。数量上时刻保持 小顶-大顶<=1（两堆相等或者小顶比大顶多一个）。

新学生先入普通班（大顶堆），此时可能会失去平衡了，于是取大顶堆的第一个（班里最好的学生）加入实验班（小顶堆），判断若数量过多（不是等于或多一个），取第一个（实验班里最差的学生）到普通班（大顶堆）里。 取中位数的时候，若两堆数量相等，则各取堆顶取平均，若小顶比大顶多一，则多的那一个就是中位数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MedianFinder {
    PriorityQueue<Integer> left;//大顶
    PriorityQueue<Integer> right;//小顶
    public MedianFinder() {
        left=new PriorityQueue<>((n1,n2)->n2-n1);
        right=new PriorityQueue<>();
    }
    public void addNum(int num) {
        left.add(num);
        right.add(left.poll());
        if(left.size()+1<right.size())
            left.add(right.poll());
    }
    public double findMedian() {
        if(right.size()>left.size())return right.peek();
        return (double)(left.peek()+right.peek())/2;
    }
}

51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

1
2
输入: [7,5,6,4]
输出: 5
1
2
3
4
5
6
7
public void merge(int[] nums,int l,int r)
 public void merge(int[] nums,int l,int mid,int r)
 if(nums[i]>nums[j])
 {
 sum+=mid-i+1;
 temp[idx++]=nums[j++];
 }

53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

1
2
3
4
5
6
if(nums[mid]>mid)
       {
           right=mid;
       }
       
       return left == nums.length - 1 && nums[left] == left ? left + 1 : left;

68 - I. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

1
2
3
4
if (root.val > p.val && root.val > q.val)
            return lowestCommonAncestor(root.left, p, q);
        if (root.val < p.val && root.val < q.val)
            return lowestCommonAncestor(root.right, p, q);

61. 扑克牌中的顺子

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1:

1
2
输入: [1,2,3,4,5]
输出: True
1
2
3
4
5
6
Set<Integer> repeat = new HashSet<>();
if(num == 0) continue; // 跳过大小王
max = Math.max(max, num); // 最大牌
min = Math.min(min, num); // 最小牌
if(repeat.contains(num)) return false; // 若有重复，提前返回 false
repeat.add(num); // 添加此牌至 Set

88. 合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i=m-1,j=n-1,p=m+n-1;//从后往前，最大的放在num1的最后面
        while(i>=0&&j>=0){
            if(nums1[i]>nums2[j]) nums1[p--]=nums1[i--];
            else nums1[p--]=nums2[j--];
        }
        while(j>=0) nums1[p--]=nums2[j--];
    }
   
}

69. x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

1
2
3
4
5
6
7
8
int mid=left+(right-left+1)/2;
     if(mid>x/mid)
     {
         right=mid-1;
     }
     else{
         left=mid;
     }

56 - II. 数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for(int i=0;i<32;i++)
    {
        int count=0;
        for(int j=0;j<nums.length;j++)
        {
         if(((nums[j]>>>i)&1)==1)
         {
             count++;
         }
        }
        if(count%3!=0)
        {
            ans=ans|(1<<i);
        }
    }

53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
while(left<right)
    {
        // 0 2 3
        // 0 1 3
        int mid=left+(right-left)/2;
        if(nums[mid]>mid)
        {
            right=mid;
        }
        else{
            left=mid+1;
        }
    }

57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

1
2
输入：target = 9
输出：[[2,3,4],[4,5]]

59 - II. 队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

1
2
3
4
5
6
7
8
9
10
11
12
13
public void push_back(int value) {
       queue.add(value);
       while(max.size()!=0&&max.getLast()<value){//注意：这里第二个判断条件不能带等号，即max中对于当前queue中的具有相同值的元素会全部存储，而不是存储最近的那个。
           max.removeLast();
       }
       max.add(value);
   }
   
   public int pop_front() {
       if(max.size()!=0&&queue.peek().equals(max.getFirst()))//Integer类型的值的比较不能直接使用==
           max.removeFirst();
       return queue.size()==0?-1:queue.poll();
   }

65. 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    
    public int add(int a, int b) {// 假如 b是进位  a是非进位和
        if(b==0){
            return a; 
        }

        int c = (a&b)<<1; // 进位赋值给c，准备下一次递归使用
        int d = a^b; // 非进位和赋值给d ，准备下一次递归使用
        return add(d,c);

    }
}

64. 求1+2+…+n

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

1
2
3
4
5
public int sumNums(int n) {
    boolean x=n>1 && sumNums(n-1)==0;
    res+=n;
    return res;
   }

59 - I. 滑动窗口的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i=0;i<num.length;i++)
      {
       while(!q.isEmpty() && num[q.peekLast()]<num[i] )
       {
          q.pollLast(); 
       }
          q.addLast(i);
          if(i-q.peekFirst()>=size)
          {
              q.pollFirst();
          }
          if(i>=size-1)
          {
              res.add(num[q.peekFirst()]);
          }
      }

62. 圆圈中最后剩下的数字

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/

1
2
3
4
5
6
7
8
9
int ans=0;
    // 0 1 2 3 4
    // 0 1 3 4
    // 1 4
    for(int i=2;i<=n;i++)
    {
        ans=(ans+m)%i;
    }
    return ans;

57 - II. 和为s的连续正数序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
while(i<=target/2)
   {
       if(sum<target)
       {
           sum+=j;
           j++;
       }
       else if(sum>target)
       {
           sum-=i;
           i++;
       }
       else{
           int[] arr=new int[j-i];
           for(int k=0;k<arr.length;k++)
           {
               arr[k]=i+k;
           }
           res.add(arr);
           sum-=i;
           i++;
       }
       
   }

17. 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private void print1ToMaxOfNDigits(char[] number, int digit) {
        if (digit == number.length) {
            printNumber(number);
            return;
        }
        for (int i = 0; i < 10; i++) {
            number[digit] = (char) (i + '0');
            print1ToMaxOfNDigits(number, digit + 1);
        }
    }

    private void printNumber(char[] number) {
        int index = 0;
        while (index < number.length && number[index] == '0')
            index++;
        int cnt=0;
        while (index < number.length)
        {
            cnt=cnt*10+number[index]-'0';
            index++;
        }
        res.add(cnt);
        System.out.println();
    }

进制转换

给定一个十进制数M，以及需要转换的进制数N。将十进制数M转化为N进制数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public String solve (int M, int N) {
        // write code here
        if(M == 0)  return "0";
        String s = "0123456789ABCDEF";
        StringBuffer sb = new StringBuffer();
        boolean f = false;
        if(M < 0){
            f = true;
            M = -M;
        }
        while(M != 0){
            sb.append(s.charAt(M%N));
            M /= N;
        }
        if(f) sb.append("-");
        return sb.reverse().toString();
    }
}

Hot100

1. 两数之和

1
2
3
4
5
int ret=target-nums[i];
if(map.containsKey(ret) && map.get(ret)!=i)
{
	return new int[]{res,i}
}

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
1
2
3
4
5
6
7
8
9
10
11
12
if(stack.isEmpty())
       {
         stack.push(c);  
       }
       else if(isSym(stack.peek(),c))
       {
          stack.pop(); 
       }
       else
       {
          stack.push(c); 
       }

34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
while(l<r)
      {
          int mid=l+(r-l)/2;
          if(nums[mid]>=target)
          {
              r=mid;
          }
          else{
              l=mid+1;
          }
      }
while(l<r)
      {
      int mid=(l+r+1)/2;
      if(nums[mid]>target)
      {
      r=mid-1;
      }
      else{
       l=mid;
      }
      }
      if(nums[begin]!=target || nums[end]!=target)
      {
      return new int[]{-1,-1};
      }
      return new int[]{begin,end};

136. 只出现一次的数字38

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

1
2
3
4
for(int i=1;i<nums.length;i++)
        {
            ans=ans^nums[i];
        }

226. 翻转二叉树

1
2
3
4
5
6
TreeNode left=invertTree(root.left);
      TreeNode right=invertTree(root.right);
      TreeNode temp=root.right;
      root.right=root.left;
      root.left=temp;
      return root;
1
2
3
4
5
6
7
8
9
10
11
12
while (!queue.isEmpty()){
               TreeNode node = queue.poll();
               TreeNode rightTree = node.right;
               node.right = node.left;
               node.left = rightTree;
               if (node.left != null){
                   queue.offer(node.left);
               }
               if (node.right != null){
                   queue.offer(node.right);
               }
           }

494. 目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

1
2
3
4
5
6
7
8
9
10
11
输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 目标和不可能大于总和
      if (S > sum) {
          return 0;
      }
      sum = (sum + S) >> 1;
      int len = nums.length;
      int[][] dp = new int[len + 1][sum + 1];
      dp[0][0] = 1;
      
      for (int i = 1; i <= len; i++) {
          for (int j = 0; j <= sum; j++) {
              // 装不下（不选当前元素）
              if (j - nums[i - 1] < 0) {
                  dp[i][j] = dp[i - 1][j];
              // 可装可不装（当前元素可选可不选）
              } else {
                  dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
              }
          }
      }

543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

1
2
3
4
5
    1
   / \
  2   3
 / \     
4   5
1
2
3
4
5
6
7
8
private int depth(TreeNode root)
   {
      if(root==null) return 0;
      int left=depth(root.left);
      int right=depth(root.right);
      if(left+right>max) max=left+right;
      return Math.max(left,right)+1;
   }

322. 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
1
2
3
4
5
6
7
8
9
10
for(int i=1;i<=coins.length;i++)
   {
       for(int j=1;j<amount+1;j++)
       {
           if(j>=coins[i-1]) f[i][j]=Math.min(f[i-1][j],f[i][j-coins[i-1]]+1);
           else{
               f[i][j]=f[i-1][j];
           }
       }
   }

518. 零钱兑换 II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 

1
2
3
4
5
6
7
8
9
10
11
for(int i = 1; i < dp.length; i++)
    {
       for(int j = 0; j < amount + 1; j++)
       {
           dp[i][j] = dp[i-1][j];
           if(j >= coins[i-1])
           {
               dp[i][j] += dp[i][j - coins[i - 1]];
           }
       } 
    }

860. 柠檬水找零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int five = 0,ten = 0;
       for(int value : bills){
           if(value == 5){
               five++;
           }else if(value == 10){
               if(five == 0) return false;
               five--;
               ten++;
           }else{
               if(ten >= 1 && five >= 1){
                   ten--;
                   five--;
               }else if(five >= 3){
                   five = five - 3;
               }else{
                   return false;
               }
           }
       }
       return true;

338. 比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

1
2
输入: 2
输出: [0,1,1]

示例 2:

1
2
输入: 5
输出: [0,1,1,2,1,2]
  • 方法一：i & (i - 1)可以去掉i最右边的一个1（如果有），因此 i & (i - 1）是比 i 小的，而且i & (i - 1)的1的个数已经在前面算过了，所以i的1的个数就是 i & (i - 1)的1的个数加上1
1
2
3
4
5
6
7
public int[] countBits(int num) {
    int[] res = new int[num + 1];
    for(int i = 1;i<= num;i++){  //注意要从1开始，0不满足
        res[i] = res[i & (i - 1)] + 1;
    }
    return res;
}

617. 合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

image-20210309125320229

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
while (!queue.isEmpty()) {
            //两棵树的节点同时出队
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
            //把这两个节点的值相加，然后合并到第1棵树的节点上
            node1.val += node2.val;
            if (node1.left == null) {
                //如果node1左子节点为空，我们直接让node2的
                //左子结点成为node1的左子结点，
                node1.left = node2.left;
            } else {
                //执行到这一步，说明node1的左子节点不为空，
                //如果node2的左子节点为空就不需要合并了，
                //只有node2的左子节点不为空的时候才需要合并
                if (node2.left != null) {
                    queue.add(node1.left);
                    queue.add(node2.left);
                }
            }

            //原理同上，上面判断的是左子节点，这里判断的是右子节点
            if (node1.right == null) {
                node1.right = node2.right;
            } else {
                if (node2.right != null) {
                    queue.add(node1.right);
                    queue.add(node2.right);
                }
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public TreeNode mergeTrees_1(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        // 先合并根节点
        t1.val += t2.val;
        // 再递归合并左右子树
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }

    /**
     * 不修改原二叉树的解法
     */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return null;
        }
        // 先合并根节点
        TreeNode root = new TreeNode((t1 == null ? 0 : t1.val) + (t2 == null ? 0 : t2.val));
        // 再递归合并左右子树
        root.left = mergeTrees(t1 == null ? null : t1.left, t2 == null ? null : t2.left);
        root.right = mergeTrees(t1 == null ? null : t1.right, t2 == null ? null : t2.right);
        return root;
    }
}

448. 找到所有数组中消失的数字

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:

1
2
3
4
5
输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]

438. 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

  • 字母异位词指字母相同，但排列不同的字符串。
  • 不考虑答案输出的顺序。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public List<Integer> findAnagrams(String s, String p) {
       int n = s.length(), m = p.length();
       List<Integer> res = new ArrayList<>();
       if(n < m) return res;

       int[] pCnt = new int[26];
       int[] sCnt = new int[26];

       for(int i = 0; i < m; i++){
           pCnt[p.charAt(i) - 'a'] ++;
       }

       int left = 0;
       for(int right = 0; right < n; right++){
           int curRight = s.charAt(right) - 'a';
           sCnt[curRight]++;
           while(sCnt[curRight] > pCnt[curRight]){
               int curLeft = s.charAt(left) - 'a';
               sCnt[curLeft]--;
               left++;
           }
           if(right - left + 1 == m){
               res.add(left);
           }
       }
       return res;
   }

538. 把二叉搜索树转换为累加树

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
   int num = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root != null) {
            //遍历右子树
            convertBST(root.right);
            //遍历顶点
            root.val = root.val + num;
            num = root.val;
            //遍历左子树
            convertBST(root.left);
            return root;
        }
        return null;
    }
}

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = “aab”
输出：[[“a”,”a”,”b”],[“aa”,”b”]]
示例 2：

输入：s = “a”
输出：[[“a”]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        backtrack(res, s,  new ArrayList<String>());
        return res;

    }
    private void backtrack(List<List<String>> res,String s,ArrayList<String> tmp)
    {
        if(s==null||s.length()==0) res.add(new ArrayList<String>(tmp));
        for(int i=1;i<s.length()+1;i++)
        {
            if(isValid(s.substring(0,i)))
            {
             tmp.add(s.substring(0,i));
             backtrack(res,s.substring(i,s.length()),tmp);
             tmp.remove(tmp.size()-1);   
            }
        }
        }
    
    private  boolean isValid(String sb) {
        int left = 0;
        int right = sb.length() - 1;
        while (left < right) {
            if (sb.charAt(left) != sb.charAt(right)) return false;
            left++;
            right--;
        }
        return true;

    }
}

12. 整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public String intToRoman(int num) {
int[] values={1000,900,500,400,100,90,50,40,10,9,5,4,1};
String[] str={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
String s="";
for(int i=0;i<str.length;i++)
{
    int time=0;
    if(num<values[i])
    {
        continue;
    }
    if(num>=values[i])
    {
       time=num/values[i];
    }
    for(int j=0;j<time;j++)
    {
        s+=str[i];
    }
      num=num-time*values[i];   
}
return s;

}

自创题

CodeTop easy

258. 各位相加

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

示例:

1
2
3
输入: 38
输出: 2 
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int addDigits(int num) {
     int sum = 0;
     if(num / 10 == 0) return num;
     while(num != 0)
     {
         sum += (num % 10);
         num /= 10;
     }
     return addDigits(sum);
    }
}

728. 自除数

自除数 是指可以被它包含的每一位数除尽的数。

例如，128 是一个自除数，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。

还有，自除数不允许包含 0 。

给定上边界和下边界数字，输出一个列表，列表的元素是边界（含边界）内所有的自除数。

示例 1：

1
2
3
输入： 
上边界left = 1, 下边界right = 22
输出： [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> list = new LinkedList<>();
        for (int i = left; i <= right; i++) {
            if (isDivisionMath(i)) {
                list.add(i);
            }
        }
        return list;
    }
// 12 
    public boolean isDivisionMath(int n) {
       int value = n;
       while(value > 0)
       {
           if(value % 10 != 0 && n % (value % 10) == 0)
           {
               value /= 10;
           }
           else{
               return false;
           }
       }
       return true; 
    }

706. 设计哈希映射

1
2
3
4
5
6
7
8
9
10
class Node{
    private int key;
    private int value;
    public Node(int key,int value){
        this.key = key;
        this.value = value;
    }
}
private List<Node>[] map;
private static final int capacity = 857;

Hard

4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：

1
2
3
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int left=(n+m+1)/2;
int right=(n+m+2)/2;
public int helper(int[] nums1,int s1,int[] nums2,int s2,int total)
    {
      if(s1>=nums1.length)
      {
          return nums2[s2+total-1];
      }
      if(s2>=nums2.length)
      {
          return nums1[s1+total-1];
      }      
      if(total==1)
      {
          return Math.min(nums1[s1],nums2[s2]);
      }
      int mid1=(s1+total/2-1<nums1.length?nums1[s1+total/2-1]:Integer.MAX_VALUE);
      int mid2=(s2+total/2-1<nums2.length?nums2[s2+total/2-1]:Integer.MAX_VALUE);
      if(mid1<mid2)
      {
          return helper(nums1,s1+total/2,nums2,s2,total-total/2);
      }
    else{
          return helper(nums1,s1,nums2,s2+total/2,total-total/2);
        }
    }

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

双指针双max,一个left，一个right，一个left_max，一个right_max

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while (left < right) {
       if (height[left] < height[right]) {
           if (height[left] >= left_max) {
               left_max = height[left];
           } else {
               ans += (left_max - height[left]);
           }
           ++left;
       } else {
           if (height[right] >= right_max) {
               right_max = height[right];
           } else {
               ans += (right_max - height[right]);
           }
           --right;
       }

72. 编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=0;i<n1;i++)
    {
        for(int j=0;j<n2;j++)
        {
            if(word1.charAt(i)==word2.charAt(j))
            {
                dp[i+1][j+1]=dp[i][j];
            }
            else{
                dp[i+1][j+1]=Math.min(Math.min(dp[i+1][j],dp[i][j+1]),dp[i][j])+1;
            }
        }
    }

76. 最小覆盖子串5

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

1
2
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

先开need窗口记录t，当满足

1
2
3
if (needs[ch] > 0 && needs[ch] >= window[ch]) {
                count++;
            }

说明此时还是需要的，接下来移动到不满足为主，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//移动到不满足条件为止
            while (count == t.length()) {
                ch = s.charAt(left);
                if (needs[ch] > 0 && needs[ch] == window[ch]) { 
                   // System.out.println(needs[ch]+" "+ch);
                    count--;
                }
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    res = s.substring(left, right + 1);

                }
                window[ch]--;
                left++;

            }
            right++;

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

示例 1：

1
2
3
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
1
2
3
4
5
6
7
8
9
10
11
if(!set.contains(num-1))
       {
           int cur=num;
           int count=1;
           while(set.contains(cur+1))
           {
               cur++;
               count++;
           }
           max=Math.max(max,count);
       }

124. 二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

1
2
3
4
5
int leftMax = Math.max(0, dfs(root.left));
       //计算右边分支最大值，右边分支如果为负数还不如不选择
       int rightMax = Math.max(0, dfs(root.right));
       //left->root->right 作为路径与已经计算过历史最大值做比较
       max = Math.max(max, root.val + leftMax + rightMax);

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i = 0;i < nums.length;i++){
           // 保证从大到小 如果前面数小则需要依次弹出，直至满足要求
           while(!queue.isEmpty() && nums[queue.peekLast()] < nums[i]){
               queue.pollLast();
           }
           // 添加当前值对应的数组下标
           queue.addLast(i);
           // 判断当前队列中队首的值是否有效
           if(0 < i-k-queue.peek()+1){
               queue.poll();   
           } 
           // 当窗口长度为k时 保存当前窗口中最大值
           if(i+1 >= k){
               result[i+1-k] = nums[queue.peek()];
           }
       }

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

1
2
3
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (int i = 1; i < s.length(); i++) {
            if(s.charAt(i)==')')
            {
                if(s.charAt(i-1)=='(')
                {
                    dp[i]=(i>=2?dp[i-2]:0)+2;
                }
                else
                {
                    if(s.charAt(i-1)==')'&& i-dp[i-1]>0 &&s.charAt(i-dp[i-1]-1)=='(')
                    {
                      dp[i]=dp[i-1]+((i-dp[i-1]-2)>=0?dp[i-dp[i-1]-2]:0)+2;  
                    }
                }
                maxans=Math.max(maxans,dp[i]);
            }
        }

862. 和至少为 K 的最短子数组

1
2
3
4
5
6
7
8
9
for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j < A.length + 1; j++) {
                if ((preSum[j] - preSum[i]) >= K) {
                    if ((j - i) < minLen) {
                        minLen = j - i;
                    }
                }
            }
        }

329. 矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

示例 1：

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int longestIncreasingPath(int[][] matrix) {
    if(matrix.length == 0) return 0;
    int m = matrix.length, n = matrix[0].length;
    int[][] cache = new int[m][n];
    int max = 1;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            int len = dfs(matrix, i, j, m, n, cache);
            max = Math.max(max, len);
        }
    }   
    return max;
}

public int dfs(int[][] matrix, int i, int j, int m, int n, int[][] cache) {
    if(cache[i][j] != 0) return cache[i][j];
    int max = 1;
    for(int[] dir: dirs) {
        int x = i + dir[0], y = j + dir[1];
        if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) continue;
        int len = 1 + dfs(matrix, x, y, m, n, cache);
        max = Math.max(max, len);
    }
    cache[i][j] = max;
    return max;
}

44. 通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

1
2
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 1:

1
2
3
4
5
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
dp[0][0] = true;
        for (int j = 1; j < p.length() + 1; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 1; j < p.length() + 1; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }

99. 恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

示例 1：

img

1
2
3
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void recoverTree(TreeNode root) {

        in_order(root);
        int tmp = firstNode.val;
        firstNode.val = secondNode.val;
        secondNode.val = tmp;
    }
//  3 2 1  ->  1 2 3
    private void in_order(TreeNode root) {
        if (root == null) return;
        in_order(root.left);
        if (firstNode == null && preNode.val > root.val) firstNode = preNode;
        if (firstNode != null && preNode.val > root.val) secondNode = root;
        preNode = root;
        in_order(root.right);
    }

10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

1
2
3
输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
for(int i=0;i<n2;i++)
    {
        if(i>0 && p.charAt(i)=='*'  &&dp[0][i-1]==true)
        {
          dp[0][i+1]=true;  
        }
    }
    for(int i=0;i<n1;i++)
    {
        for(int j=0;j<n2;j++)
        {
         if(p.charAt(j)==s.charAt(i) || p.charAt(j)=='.')
         {
             dp[i+1][j+1]=dp[i][j];
         }
         else{
             if(j>0 && p.charAt(j)=='*')
             {
                 if(p.charAt(j-1)!='.' && p.charAt(j-1)!=s.charAt(i))
                 {
                     dp[i+1][j+1]=dp[i+1][j-1];
                 }
                 else{
                   dp[i+1][j+1]=dp[i+1][j]||dp[i+1][j-1] || dp[i][j+1];
                 }
             }
         }   
        }
    }

440. 字典序的第K小数字

难度困难194

给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。

注意：1 ≤ k ≤ n ≤ 109。

示例 :

1
2
3
4
5
6
7
8
输入:
n: 13   k: 2

输出:
10

解释:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int findKthNumber(int n, int k) {
      int cur=1;
      int prefix=1;
      while(cur<k)
      {
          int tmp=count(prefix,n);
          if(tmp+cur>k)
          {
              prefix*=10;
              cur++;
          }
          else{
              
          }
      }
    }
    private int count(int prefix,int n)
    {
        long cur=prefix;
        long next=prefix+1;
        int count=0;
        // 
        while(cur<=n)
        {
            count+=Math.min(n+1,next)-cur;
            cur*=10;
            next*=10; 
        }
        return count;
    }

124. 二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //计算左边分支最大值，左边分支如果为负数还不如不选择
        int leftMax = Math.max(0, dfs(root.left));
        //计算右边分支最大值，右边分支如果为负数还不如不选择
        int rightMax = Math.max(0, dfs(root.right));
        //left->root->right 作为路径与已经计算过历史最大值做比较
        max = Math.max(max, root.val + leftMax + rightMax);
        // 返回经过root的单边最大分支给当前root的父节点计算使用
        return root.val + Math.max(leftMax, rightMax);
    }

99. 恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

image-20210331100800759