48~58

48. 最长不含重复字符的子字符串

难度中等476

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

滑动窗口:

通过map记录下标, 如果遇到了相同字符, 就把左下标换成前面的那个字符+1

需要注意的是, map会存储所有出现的字符, 也就是说前面的那个相同的字符(有可能不在窗口的范围),

这个字符的位置+1有可能是小于pre的, 这样就会导致 pre 偏大

因此需要 pre=Math.max(pre,map.get(chars[i])+1);

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int pre=0,res=0;
        if(s.length()==0)return res;
        Map<Character,Integer> map=new HashMap<>();
        char[]chars=s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            //abcb
            if(map.containsKey(chars[i])){
                pre=Math.max(map.get(chars[i])+1,pre);
            }
            map.put(chars[i],i);
            res=Math.max(res,i+1-pre);
        }
        return res;
    }
}

49. 丑数

难度中等367

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

丑数的递推性质：丑数只包含因子 2, 3, 5，因此有 “丑数 == 某较小丑数× 某因子”

例如：10 = 5 X 2。

我们可以通过 1 , 然后乘以不同的因子(2 3 5) 来得到所有的丑数 ,

" 只包含质因子 2、3 和 5 的数称作丑数 "

根据丑数的递推性质, 丑数 X

n+1

只可能是下面的三种情况之一:
1. Xa *2
2. Xb *2
3. Xc *5
由于是从小到大递推 , 因此 **Xn+1 = min(Xa 2,Xb 3, Xc *5)

我们使用dp数组来记录丑数, 毫无疑问 , dp[0]=1 , 因为第一个丑数是1

定义三个指针 , 分别指向2 ,3 ,5 当前对应的Xn , 初始化索引是 0, 也就是指向dp[0]

第二个是 2, 然后是3 ,然后是5, 然后是6, 然后是8

可以通过 **Xn+1 = min(Xa 2,Xb 3, Xc *5) 来得出,

class Solution {
    public int nthUglyNumber(int n) {
        int []dp=new int[n]; // 使用dp数组记录 丑数
        dp[0]=1;
        int a=0,b=0,c=0;
        for(int i=1;i<dp.length;i++){
            int n2=dp[a]*2,n3=dp[b]*3,n5=5*dp[c];
            dp[i]=Math.min(Math.min(n2,n3),n5);
            if(dp[i]==n2) a++;
            if(dp[i]==n3) b++;
            if(dp[i]==n5) c++;
        }
        return dp[n-1];
    }
}

50. 第一个只出现一次的字符

难度简单253

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

最开始的解法, 蠢且慢

class Solution {
    public char firstUniqChar(String s) {
        Map<Character,Integer> map=new HashMap<>();
        for(char ch:s.toCharArray()){
            if(map.containsKey(ch)){
                map.put(ch,map.get(ch)+1);
                continue;
            }
            map.put(ch,1);
        }
        for (char c : s.toCharArray()) {
            if(map.get(c)==1)
                return c;
        }
        return ' ';
    }
}

稍微快了一点的解法

使用哈希表, 映射类型为Boolean , 利用containsKey( ) 方法, 使得单次出现的一定为true , 多次出现的为false , 最后只需要通过char[] 检索true的key即可

Boolean类型节省空间

class Solution {
    public char firstUniqChar(String s) {
        Map<Character,Boolean> map=new HashMap<>(); // 如果只出现一次那么就是true
        for(char ch:s.toCharArray()){
            map.put(ch,!map.containsKey(ch)); //如果不包含放进去就是true, 如果出现了多次那么就是 false
        }
        for(char ch:s.toCharArray()){
            if(map.get(ch))
                return ch;
        }
        return ' ' ;
    }
}

直接用数组new int[26],更快

class Solution {
    public char firstUniqChar(String s) {
        int []cnt=new int[26];
        for (char c : s.toCharArray()) {
            cnt[c-'a']++;
        }
        for (char c : s.toCharArray()) {
            if(cnt[c-'a']==1)
                return c;
        }
        return ' ';
    }
}

只使用一次s.toCharArray( ) , 快了1 ms

class Solution {
    public char firstUniqChar(String s) {
        int []cnt=new int[26];
        char []chars=s.toCharArray();
        for (char c : chars) {
            cnt[c-'a']++;
        }
        for (char c : chars) {
            if(cnt[c-'a']==1)
                return c;
        }
        return ' ';
    }
}

image-20220805232831149

52. 两个链表的第一个公共节点

使用栈, 从末尾开始找

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // 将两个节点入栈, 然后出栈比较是否公共节点
    if(headA==null||headB==null) return null;
        Stack<ListNode> stack1=new Stack<>();
        Stack<ListNode> stack2=new Stack<>();
        while(headA!=null){
            stack1.push(headA);
            headA=headA.next;
        }
        while(headB!=null){
            stack2.push(headB);
            headB=headB.next;
        }
        ListNode now=stack1.pop();
        ListNode res=null;
        while(now==stack2.pop()){
            res=now;
            if(stack1.size()==0||stack2.size()==0)
                break;
            now=stack1.pop();
        }
        return res;
    }
}

设「第一个公共节点」为 node ，「链表 headA」的节点数量为 a ，「链表 headB」的节点数量为 b ，「两链表的公共尾部」的节点数量为 c ，

则有：

头节点 headA 到 node 前，共有 a - c 个节点；

头节点 headB 到 node 前，共有 b - c 个节点；

image-20220807164155572

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A=headA;
        ListNode B=headB;
        while(A!=B){
            A=A==null?headB:A.next;
            B=B==null?headA:B.next;
        }	
        return A;
    }
}

53 - I. 在排序数组中查找数字 I

难度简单342

统计一个数字在排序数组中出现的次数。

class Solution {
    public int search(int[] nums, int target) {
        int l=0,r=nums.length-1;
        int res=0;
        while(l<=r){
           int m=(r-l)/2+l;
            if(nums[m]<target){ //target在右半部分
                l=m+1;
            }
            else if(nums[m]>target){//target在左半部分
                r=m-1;
            }
            else{ // 相等
                //分别向左右两边 while循环查找相等的个数
                res=1;
                int ptr=m;
                while(ptr-1>=0&&target==nums[--ptr]) res++;// 左边
                ptr=m;
                while(ptr+1<nums.length&&target==nums[++ptr]) res++; // 右边
                break;
            }
        }
        return res;
    }
}

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

难度简单296

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

二分 ,

可以将数组看成两个部分, 左子数组的顺序全部正常, 右子数组的顺序全部混乱, 需要做的就是找到右子数组的首元素

如果当前下标的数字与数字对应的数字相同, 就往右走,

如果不相同 , 往当前范围的左半部分走,

一直走到 l==r, 就是右子数组的首元素 , 这时候的下标也就是缺失的元素

跳出时，变量 l 和 r 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素” 。因此返回 l 即可。

class Solution {
    public int missingNumber(int[] nums) {
        // 0 1 2 3 
        int l=0,r=nums.length-1;
        while(l<=r){
            int m=(r-l)/2+l;
            if(nums[m]==m) l=m+1;
            else r=m-1;
        }
        return l;
    }
}// [0,1,2,3,4,5,6,7,9,10,11,12,13,14,15,16]

54. 二叉搜索树的第k大节点

难度简单328

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

前序遍历：根结点 —> 左子树 —> 右子树

中序遍历：左子树—> 根结点 —> 右子树

后序遍历：左子树 —> 右子树 —> 根结点

层次遍历：只需按层次遍历即可

对于二叉搜索树, 如果想要的到第k 最大值, 可以使用倒序的中序遍历 : 右左根

本题使用倒序的中序遍历+提前返回

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int res=0,cnt=0;
    public int kthLargest(TreeNode root, int k) {
        cnt=k;
        dfs(root);
        return res;
    }
    public void dfs(TreeNode root ){
        if(root==null) return ;
        dfs(root.right);
        if(--cnt==0) res=root.val;
        dfs(root.left);
    }
}

55 - I. 二叉树的深度

难度简单203

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。]\

使用队列进行层序遍历即可

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
    public int maxDepth(TreeNode root) {
        // 队列 : 层序遍历
        if(root==null) return 0;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        int res=0;
        while(queue.size()!=0){
            int size=queue.size();
            for(int i=0;i< size;i++){
                TreeNode temp=queue.poll();
                if(temp.left!=null)
                    queue.add(temp.left);
                if(temp.right!=null)
                    queue.add(temp.right);
            }
            res++;
        }
        return res;
    }
}

递归(DFS)
树的后序遍历 / 深度优先搜索往往利用递归或栈实现，本文使用递归实现。

关键点：此树的深度和其左（右）子树的深度之间的关系。显然，
- 树的深度等于左子树的深度与右子树的深度中的最大值 +1 。

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
		return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

55 - II. 平衡二叉树

难度简单300

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

image-20220808122527662

递归判断左子树以及右子树是否是平衡二叉树以及左右孩子的深度是否相差超过1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        // 中序遍历, 设定一个返回值
        if(root==null) return true;
        return Math.abs(depth(root.left)-depth(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }

    int depth(TreeNode root){
        if(root==null) return 0;
        return Math.max(depth(root.left)+1,depth(root.right)+1);
    }
}

后序遍历(左右根) + 剪枝

思路是对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。

返回值：

当节点root 左 / 右子树的深度差 ≤1 ：则返回当前子树的深度，即节点 root 的左 / 右子树的深度最大值+1 （ max(left, right) + 1 ）；
当节点root 左 / 右子树的深度差 > 2 ：则返回 −1 ，代表此子树不是平衡树。

深度:

当左 / 右子树的深度为-1 ,代表当前的树不是平衡二叉树, 直接返回 -1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root)==-1?false:true;
    }
    int recur(TreeNode root){
        if(root==null) return 0;
        int left=recur(root.left);
        if(left == -1 ) return -1;
        int right=recur(root.right);
        if(right == -1) return -1;
        return Math.abs(left-right)>=2?-1:Math.max(left,right)+1;
    }
}

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

原书: 面试题40：数组中只出现一次的数字

难度中等684

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

我们试着把原数组分成两个子数组，使得每个子数组包含一个只出现一次的数字，而其他数字都成对出现两次。如果能够这样拆分成两个数组，我们就可以按照前面的办法分别找出两个只出现一次的数字了。

我们还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。

因为其他数字都出现了两次，在异或中全部抵消了。

由于这两个数字肯定不一样，那么异或的结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。

我们在结果数字中找到第一个为1的位的位置，记为第m位。

现在我们以第m位是不是1为标准把原数组中的数字分成两个子数组，

第一个子数组中每个数字的第n位都是1，

而第二个子数组中每个数字的第n位都是0。

由于我们分组的标准是数字中的某一位是1还是0，那么出现了两次的数字肯定被分配到同一个子数组。

因为两个相同的数字的任意一位都是相同的，我们不可能把两个相同的数字分配到两个子数组中去，

于是我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。

class Solution {
    public int[] singleNumbers(int[] nums) {
        int a=nums[0],x = 0,y=0,m=1;
        // 两个相同的数字 异或的结果为 0   x^y==a
        for (int i = 1; i < nums.length; i++) {
            a^=nums[i];
        }
        while((a&m)==0){
            m<<=1;
        }// x^y 的倒数m位是1 ,  并且可以知道 x ,y 的倒数第m 位不相同,
        for (int num : nums) {
            // 通过倒数第 m位 来区分 x,y ,由于两个相同的数字的二进制位也完全相同 , 因此 x^=num 的最终结果就是x本身
            if ((num & m) !=0) x ^= num;
            else y ^= num;
        }
        return new int[]{x,y};
    }
}

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

难度中等370

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

由于数字的存在的次数只有 1 or 3 , 因此可以通过二进制的方式计算所有的数字的每一位的和, 最后mod 3 , 即可得到只出现一次的那个数字的二进制 ,

然后通过循环即可计算出来这个数字

class Solution {
    public  int singleNumber(int[] nums) {
        int []k=new int[32];
        for (int i = 0; i < nums.length; i++) {
            int cnt=0;
            while(nums[i]!=0){
                k[cnt++]+=nums[i]&1;
                nums[i]>>=1;
            }
        }
        for (int i = 0; i < k.length; i++) k[i]%=3;
        int res=0;
        for (int i = 0; i < k.length; i++) {
            res+=Math.pow(2,i)*k[i];
        }
        return res;
    }
}

57. 和为s的两个数字

难度简单204

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

把i<=j 改成i<j 快了1ms

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int i=0,j=nums.length-1;
        while(i<j){
            int temp=nums[i]+nums[j];
            if(temp<target) i++;
            else if(temp>target) j--;
            else return new int[]{nums[i],nums[j]};
        }
        return null;
    }
}

HashMap

很慢

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map=new HashMap<>();
        int cnt=0;
        for (int num : nums) {
            if(map.containsKey(target-num))
            {
                return new int[]{num,target-num};
            }
            map.put(num,cnt++);
        }
        return null;
    }
}

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

难度简单466

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

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

滑动窗口

首先把small初始化为1，bug初始化为2。

如果从small到big的序列的和大于s，我们可以从序列中去掉较小的值，也就是增大small的值。

如果从small到big的序列的和小于s，我们可以增大big，让这个序列包含更多的数字。

因为这个序列至少要有两个数字，我们一直增加small到（1+s）/2为止。

image-20220808165631996

class Solution {
    public int[][] findContinuousSequence(int target) { // 滑动窗口
        int i=1,j=2,sum=3;
        List<int[]> res=new ArrayList<>();
        while(i<j){
            if(sum==target){ //add
                int []ans=new int[j-i+1];
                for (int i1 = 0; i1 < ans.length; i1++) 
                    ans[i1]=i+i1;
                res.add(ans);
            }
            if(sum>=target){
                sum-=i++;
            }else{
                sum+=++j;
            }
        }
        return res.toArray(new int[0][]);
    }
}

注意不要把img写成两个连续的 if ,img这样会导致前面的那个if修改了值, 导致下面的也直接改变了,

例如:

target=15 , i=1 , j=4 ,此时会执行 sum+=++j ,

然后下面的那个if 又会执行 sum-=i++, 导致下一次判断的时候 sum!=target ,

导致list 少添加了一次ans

58 - I. 翻转单词顺序

难度简单232

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。

双指针:

倒序遍历

class Solution {
    public String reverseWords(String s) {
        s=s.trim();
        StringBuilder sb=new StringBuilder("");
        int i=s.length()-1,j=i;
        while(j>=0){
            while(j>=0&&s.charAt(j)!=' ') j--; // 走到空格的位置
            sb.append(s.substring(j+1, i + 1)).append(" ");
            while(j>=0&&s.charAt(j)==' ')j--; // 跳过空格的位置 (如果是空格就走下一步)
            i=j;
        }
        return sb.toString().trim();
    }
}

使用String.split(String regex)

把字符串按照空格分隔成String数组

倒序添加即可

需要注意的是, 如果中间存在多个空格, 会有" " 空格字符串, 因此在添加的时候调用trim() 避免

class Solution {
    public String reverseWords(String s) {
        String []words=s.split(" ");
        StringBuilder res=new StringBuilder("");
        for (int i = words.length-1; i >=0; i--) {
            if(words[i].trim()!="")
                res.append(words[i]).append(" ");
        }
        return res.toString().trim();
    }
}

58 - II. 左旋转字符串

难度简单285

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

StringBuilder 和subString太香了

class Solution {
    public String reverseLeftWords(String s, int n) { // 左旋字符串
        StringBuilder sb=new StringBuilder();
        sb.append(s.substring(n,s.length()));
        sb.append(s.substring(0,n));
        return sb.toString();
    }
}

更懒的做法:

class Solution {
    public String reverseLeftWords(String s, int n) { // 左旋字符串
        return s.substring(n)+s.substring(0,n);
    }
}