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. 给表达式添加运算符(难)

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

回溯算法
设字符串numnum的长度为nn,构建表达式时需要向nn个字符的n1n-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的计算结果,并添加新的连乘结果prevalpre*val,即curpre+prevalcur-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 的整数数组,每次操作将会使 n1n - 1 个元素增加 11 。返回让数组所有元素相等的最小操作次数。
在这里插入图片描述

  • 每次使n1n-1个元素增加11,相当于每次将一个元素减小11,直到所有元素都等于刚开始numsnums最小的那个元素。这个减小次数就是所求的次数,即最终的答案应该是(nummin)(num- min)求和,即每个numnum中每个元素与最小值的差求和。变形得sum(nums)minnsum(nums) - min * n,其中nnnumsnums中元素个数,minminnums$中元素的最小值。
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. 数字的补数

题目描述:
对整数的二进制表示取反(00111100)后,再转换为十进制表示,可以得到这个整数的补数。

  • 例如,整数 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相当于num2num*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 的前 s1s - 1 位进行取反即是答案(第 ss 位的取反结果始终为 00)。
因此我们可以先使用 lowbit 操作来得到 numnum 二进制表示中最高位 11 的位置为 11,其余位为 00 时所代表的数字 xx
然后 x1x - 1 即是二进制表示中前 s1s - 1 位均为 11,其余位为 00 的数字,将其与 numnum 的取反数执行「按位与」操作,即可达到「仅对 numnum 的前 s1s−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);
}
}