66. 加一(简单)

题目描述：
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位，数组中每个元素只存储单个数字。你可以假设除了整数00之外，这个整数不会以零开头。
在这里插入图片描述
题解：从最后一位开始+1+1，如果+1+1之后结果等于1010，则需要进位，前一位继续+1+1，如果没有等于1010则退出。

如果第一位为0，说明溢出了，则需要新开一个n+1n+1的数组，第n+1n+1位为1，其他为digitsdigits中结果。

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        int [] result = new int[n+1];
        for(int i = n-1 ; i>= 0 ; i--)
        {
            digits[i] +=1;
            if(digits[i] == 10)
                digits[i]=0;
                
            else
                break;
            result[i+1] = digits[i];
        }   
        if(digits[0] == 0)
        {
             result[0] = 1;
             return result;
        }
        return digits;
    }
}

211. 添加与搜索单词 - 数据结构设计(中)

题目描述：
在这里插入图片描述
看了题解发现这道题需要一种叫 Trie (前缀树)的数据结构。前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
以下内容来自「宫水三叶」，地址为：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247488490&idx=1&sn=db2998cb0e5f08684ee1b6009b974089&chksm=fd9cb8f5caeb31e3f7f67dba981d8d01a24e26c93ead5491edb521c988adc0798d8acb6f9e9d&token=1006889101&lang=zh_CN#rd

  • Trie 类：
    • Trie()Trie() 初始化前缀树对象。
    • voidinsert(Stringword)void insert(String word) 向前缀树中插入字符串 wordword。
    • booleansearch(Stringword)boolean search(String word) 如果字符串 wordword 在前缀树中，返回 truetrue（即，在检索之前已经插入）；否则，返回 falsefalse 。
    • booleanstartsWith(Stringprefix)boolean startsWith(String prefix) 如果之前已经插入的字符串 wordword 的前缀之一为 prefixprefix ，返回 truetrue ；否则，返回 falsefalse 。
      TrieTrie树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。其核心是使用「边」来代表有无字符，使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」。
      在这里插入图片描述
      Trie(二维数组实现)
  • 一个朴素的想法是直接使用「二维数组」来实现TrieTrie树
    • 使用二维数组trie[]trie[]来存储我们所有的单词字符。
    • 使用二维数组 indexindex来存储我们所有的单词字符。
    • 使用count[]count[]数组记录某个格子被「被标记为结尾的次数」（当 [idx][idx]编号的格子被标记了 nn次，则有cnt[idx]=ncnt[idx] = n
class Trie {
    int N = 100009; // 直接设置为十万级
    int[][] trie;
    int[] count;
    int index;

    public Trie() {
        trie = new int[N][26];
        count = new int[N];
        index = 0;
    }
    
    public void insert(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (trie[p][u] == 0) trie[p][u] = ++index;
            p = trie[p][u];
        }
        count[p]++;
    }
    
    public boolean search(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (trie[p][u] == 0) return false;
            p = trie[p][u];
        }
        return count[p] != 0;
    }
    
    public boolean startsWith(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (trie[p][u] == 0) return false;
            p = trie[p][u];
        }
        return true;
    }
}
  • 时间复杂度： TrieTrie树的每次调用时间复杂度取决于入参字符串的长度。复杂度为O(Len)O(Len)
  • 空间复杂度：二维数组的高度为nn，字符集大小为kk。复杂度为O(nk)O(nk).
    Trie(TreeNode)
    相比二维数组，更加常规的做法是建立TreeNodeTreeNode结构节点。
    随着数据的不断插入，根据需要不断创建TreeNodeTreeNode节点。
class Trie {
    class TrieNode {
        boolean end;
        TrieNode[] tns = new TrieNode[26];
    }

    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }

    public void insert(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) p.tns[u] = new TrieNode();
            p = p.tns[u]; 
        }
        p.end = true;
    }

    public boolean search(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) return false;
            p = p.tns[u]; 
        }
        return p.end;
    }

    public boolean startsWith(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) return false;
            p = p.tns[u]; 
        }
        return true;
    }
}
  • 时间复杂度： TrieTrie树的每次调用时间复杂度取决于入参字符串的长度。复杂度为O(Len)O(Len)
  • 空间复杂度：二维数组的高度为nn，字符集大小为kk。复杂度为O(nk)O(nk).
    本题题解
    在 searchsearch 操作中会有 .. 符号，我们需要枚举某个 .. 所代指的字母是什么，这需要结合 DFS 来做.
class WordDictionary {
    class TreeNode{
        boolean isWord = false;
        TreeNode [] child = new TreeNode[26];//每个节点后面可能都有26个字母
    }


    TreeNode root  = new TreeNode();
    //添加节点
    public void addWord(String word) {
            TreeNode p = root;
            for(int i = 0 ; i <word.length(); i++)
            {
                int c = word.charAt(i) - 'a';
                if(p.child[c] == null) 
                {
                    p.child[c] = new TreeNode();
                }
                p = p.child[c];
            }
            p.isWord = true;
    }
    
    public boolean search(String word) {
        return dfs(word,root,0);
    }
    //对于"."字符，需要使用DFS来判断不同的情况
    public boolean dfs(String word,TreeNode p,int index)
    {
        int n = word.length();
        if(index == n) 
        {
            return p.isWord;//遍历结束
        }
        if(word.charAt(index) == '.')
        {
            //如果等于. 需要遍历这个字符后的所有字符 看是否符合情况
            for(int j = 0 ; j < 26 ;j ++)
            {
                if(p.child[j] != null)
                {
                    if(dfs(word,p.child[j],index+1) == true)
                    {
                        return true;
                    }
                }
            }
        }
        else
        {
            int c = word.charAt(index) -'a';
            if (p.child[c] == null) 
            {
                return false;
            }
            return dfs(word, p.child[c], index + 1);

        }
        return false;
    }
}

230. 二叉搜索树中第K小的元素

题目描述：
给定一个二叉搜索树的根节点rootroot ，和一个整数 kk ，请你设计一个算法查找其中第 kk 个最小元素（从 11 开始计数）。
在这里插入图片描述
二叉搜索树（BST：Binary Search Tree）：

  • 其左子树（left subtree）下的每个后代节点（descendant node）的值都小于节点nn的值。
  • 其右子树（right subtree）下的每个后代节点的值都大于节点 nn 的值。
    树的遍历 + 优先队列（堆）
    构建一个容量为 kk 的大根堆
    根据大根堆的元素个数和当前节点与堆顶元素的关系来分情况讨论：
  • 大根堆元素不足 kk 个：直接将当前节点值放入大根堆；
  • *大根堆元素为 kk 个，根据堆顶元素和当前节点值的大小关系进一步分情况讨论：
  • 如果当前节点值元素大于堆顶元素，说明当前节点值不可能在第 kk 小的范围内，直接丢弃；
  • 如果当前节点值元素小于堆顶元素，说明当前节点值可能在第 kk 小的范围内，先 pollpoll 一个再 addadd 进去。
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        //根 左 右
        while(!d.isEmpty())
        {
            TreeNode node = d.pollFirst();
            if (q.size() < k) {
                q.add(node.val);
            } else if (q.peek() > node.val) {
                q.poll();
                q.add(node.val);
            }
            if (node.left != null) d.addLast(node.left);
            if (node.right != null) d.addLast(node.right);
        }
        return q.peek();
    }
}

中序遍历
二叉搜索树的中序遍历是有序的，只需要中序遍历，然后返回第k个元素即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> d = new ArrayDeque<>();
        //左根右，先将根结点入队列，遍历最左，再遍历最右侧
        while(root !=null || !d.isEmpty())
        {
            while(root != null)
            {
                d.addLast(root);
                root = root.left;
            }
            root = d.pollLast();
            if (--k == 0) return root.val;
            root = root.right;
        }
        return -1;
    }
}

282. 给表达式添加运算符（难）

回溯算法
题目描述：
给定一个仅包含数字0−90-9的字符串numnum和一个目标值整数targettarget，在numnum的数字之间添加二元运算符（不是一元）+、−+、- 或 ∗*，返回所有能够得到目标值的表达式。
在这里插入图片描述

回溯算法
设字符串numnum的长度为nn,构建表达式时需要向nn个字符的n−1n-1个空间中插入+、−+、- 或 ∗*，或者不添加符号。我们使用回溯来模拟。
定义递归方法dfs(intu,longcur,longpre,Strings)dfs(int u,long cur,long pre,String s)其中：

  • uu为当前枚举到第u个数字
  • curcur为当前表达式的计算结果
  • prepre为最后一个连乘串的计算结果（乘法的优先级高，需要单独考虑）
  • ss为当前构建的字符串
    该递归函数分为两种情况：
  • 如果 u=nu=n，说明表达式已经构造完成，若此时有 cur=targetcur=target，则找到了一个可行解，我们将 ss 放入答案数组中，递归结束；
  • 如果 u<nu<n，需要枚举当前表达式末尾需要添加的符号（+、−+、- 或 ∗*），以及该符号要截取多少位，设当前符号后面的数字为valval
    • 若添加++，则curcur增加valval，且valval为当前表达式的最后一个连乘串。
    • 若添加−-，则curcur减少valval，且−val-val为当前表达式的最后一个连乘串。
    • 若添加∗*，由于乘法优先级高，所以需要和撤销prepre的计算结果，并添加新的连乘结果pre∗valpre*val,即cur−pre+pre∗valcur-pre+pre*val.
      数字可以是单个00，但不能有前导零，需要单独判断，运算过程可能会有超过32位的整数，所以要用64位的整数存储运算结果。
class Solution {
    int n;//字符串长度
    List<String> result = new ArrayList<String>();
    int target;
    String num;
    public List<String> addOperators(String num, int target) {
        this.num = num;
        this.target = target;
        n = num.length();
        dfs(0,0,0,"");
        return result;
    }
    //u为当前是第几位
    //cur是当前表示的数字
    //pre是上一次迭代结束 最后一个连乘串的结构
    //s为当前构造好的字符串
    public void dfs(int u,long cur,long pre,String s)
    {
        if(u == n )
        {
            if( cur == target) result.add(s);
            return;
        }
        for(int j = u ; j < n ; j++)
        {
           // 0 单独作为一位是被允许的，但是多位且首部为 00 是不允许的
            if(u != j && num.charAt(u) == '0')
            {
                    break;
            }
            long next = Long.parseLong(num.substring(u, j + 1));
            if(u==0)
            {
                dfs(j+1,next,next,"" + next);
            }
            else
            {
                //添加加号
                dfs(j+1,cur+next,next,s + "+" + next);
                //添加减号
                dfs(j+1,cur-next,-next,s+"-"+next);
                //添加乘号
                long x = pre*next;
                dfs(j+1,cur-pre+x,x,s+"*"+next);
            }
        }
        
    }
}

453. 最小操作次数使数组元素相等（简单）

题目描述
给你一个长度为 nn 的整数数组，每次操作将会使 n−1n - 1 个元素增加 11 。返回让数组所有元素相等的最小操作次数。
在这里插入图片描述

  • 每次使n−1n-1个元素增加11,相当于每次将一个元素减小11，直到所有元素都等于刚开始numsnums最小的那个元素。这个减小次数就是所求的次数，即最终的答案应该是(num−min)(num- min)求和，即每个numnum中每个元素与最小值的差求和。变形得sum(nums)−min∗nsum(nums) - min * n,其中nn为numsnums中元素个数，minmin为为为nums$中元素的最小值。
class Solution {
    public int minMoves(int[] nums) {
        //每次使n-1个元素增加1 相当于每次将一个元素减小1，直到所有元素都等于刚开始nums最小的那个元素。
        //这个次数就是所求的次数，即最终的答案应该是（num- min）求和，即每个num中每个元素与最小值的差求和
        //变形得sum（nums） - min*n
        int n = nums.length;
        int sum = 0,min = nums[0];
        for(int num :nums)
        {
            min = Math.min(min,num);
            sum +=num;
        }
        return (int)sum - n * min;

    }
}

467. 数字的补数

题目描述：
对整数的二进制表示取反（00 变 11 ，11 变 00）后，再转换为十进制表示，可以得到这个整数的补数。

  • 例如，整数 55 的二进制表示是 "101""101" ，取反后得到 "010""010" ，再转回十进制表示得到补数 22 。
    给你一个整数 numnum，输出它的补数。
    在这里插入图片描述
    老实巴交的做法
    看到题就想着循环计算(num(num%2),并求反存到字符串中，然后在转化成十进制，很简单。
class Solution {
    public int findComplement(int num) {
        StringBuffer sb  = new StringBuffer();
        while(num != 0)
        {
            int temp = num%2;
            if(temp == 1)
            {
                sb.append("0");
            }
            else
            {
                sb.append("1");
            }
            num = num/2;
        }
        
    }
}

但是看到题解发现有很多高大上的写法，如
模拟（遍历）
先对 numnum 进行「从高到低」的检查，找到最高位 11 的位置 ss，然后再对$num $进行遍历，将低位到 ss 位的位置执行逐位取反操作。

  • 这里使用了位运算，Java中的为运算有三种
    • <<<<：左移，num<<1num<<1相当于num∗2num*2。
    • >>>>：右移，num>>1num>>1相当于num/2num/2。
    • >>>>>>：无符号右移，忽略符号位，空位都以00补齐
class Solution {
    public int findComplement(int num) {
        int s = -1;
        //从int的最高位开始 不断右移，找到最高位1所在的位置s
        for (int i = 31; i >= 0; i--) {
            if (((num >> i) & 1) != 0) {
                s = i;
                break;
            }
        }
        int ans = 0;
        //然后从最低位开始，如果某位为1则乘2的i次方（1<<i）
        for (int i = 0; i < s; i++) {
            if (((num >> i) & 1) == 0) ans |= (1 << i);
        }
        return ans;
    }
}

模拟（lowbit）
如果numnum的二进制表示中最高位 11 的位置为 ss 的话，那么实际上我们只需要对 numnum 的前 s−1s - 1 位进行取反即是答案（第 ss 位的取反结果始终为 00）。
因此我们可以先使用 lowbit 操作来得到 numnum 二进制表示中最高位 11 的位置为 11，其余位为 00 时所代表的数字 xx。
然后 x−1x - 1 即是二进制表示中前 s−1s - 1 位均为 11，其余位为 00 的数字，将其与 numnum 的取反数执行「按位与」操作，即可达到「仅对 numnum 的前 s−1s−1 位进行取反」的效果。

class Solution {
    public int findComplement(int num) {
        int x = 0;
        //求x 其中i & -i 为二进制与
        for (int i = num; i != 0; i -= i & -i) x = i;
        return ~num & (x - 1);
    }
}