LeetCode 318.最大单词长度乘积
题目描述
给定一个字符串数组 words,找到 length(word[i]) * length(word[j]) 的最大值,并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词,返回 0。
算法描述
这里直接用哈希表,分词的话那么会很麻烦,所以这里使用的是移位的思想。首先用一个数组来存储每一个对应的字符串到底出现了哪个单词(这里并不需要记录出现的次数,因为只要找出两个没有公共字母的单词)。这里如何记录是否出现呢?可以用一个26位的二进制数,1表示对应位置的字母出现了。那么如何记录呢?那就是以下的代码: 1
2
3for (char c : words[i].toCharArray()) {
hash[i] |= 1 << (c - 'a');
}
随后就可以遍历两两组合,相与为零的二进制数就是不重复的单词。
完整代码
1 | package maxProduct; |
LeetCode 43.字符串相乘
题目描述
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
算法描述
- 如果num1和num2之一是0,则直接将0作为结果返回即可
- 如果num1和num2都不是0,则可以通过模拟竖式乘法的方法计算乘积。从右往左遍历乘数,将乘数的每一位与被乘数相乘得到对应的结果,再将每次得到的结果累加。
完整代码
1 | package multiply; |
LeetCode No166.分数到小数
题目描述
给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以 字符串形式返回小数 。
如果小数部分为循环小数,则将循环的部分括在括号内。
如果存在多个答案,只需返回 任意一个 。
算法描述
这里要用到的一个容器就是哈希表,当然哈希表键值对是用来存储除数得到的余数的10倍是否出现过,用的就是长除法的思想。每一次除不下的时候我们要考虑的是补零,若补零之后出现的整数之前出现过在哈希表中,那么可以肯定的是从这一位开始就要产生一个循环。那么这样就可以得到一个循环的结束条件。
完整代码
1 | class Solution { |
LeetCode No29.不使用除法运算符计算除法
题目描述
不使用除法运算符,进行除法的计算,返回的结果是除数取整的结果
算法描述
- 不使用除法运算符,得到整数除法的求余结果
- 考虑的是移位法,可以先把一个被除数除以2^n,n的初始值为31
- 不断减少n去试探,当某个n满足被除数/2^n>=divisor时
- 表示找到了一个足够大的数,这个数*除数是不大于被除数的,所以可以减去2^n个除数
完整代码
1 | package divide; |
LeetCode No24. 两两交换链表中的节点
题目描述
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。你不能只是单纯的改变节点内部的值,而是需要实际的进行节点的交换。
算法描述
这里要用到虚拟头节点,交换相邻的两个元素,进行如下的三步:
完整代码
1 | class Solution { |
LeetCode No. 450 && No.701
这两个题目可以放在一起,分别是删除搜索二叉树的节点以及给搜索二叉树添加节点。
对于插入来说,由于题目说的是可以不考虑改变树的结构的插入方式,所以这里只要按照二叉搜索树的规则去遍历,遇到空节点就插入即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
TreeNode newRoot = root;
TreeNode pre = root;
while (root != null) {
pre = root;
if (root.val > val) {
root = root.left;
} else if (root.val < val) {
root = root.right;
}
}
if (pre.val > val) {
pre.left = new TreeNode(val);
} else {
pre.right = new TreeNode(val);
}
return newRoot;
}
}对于删除节点,要比插入节点要复杂一点,因为要考虑结构的变化更多。首先进行递归的操作,如果递归到空节点,说明没有找到删除的节点那么就直接返回。如果找到了删除的节点:(1) 左右孩子都为空,直接删除,置这个节点为空。(2)删除节点的左孩子为空,右孩子不为空,删除节点,右孩子补位,返回右孩子为根节点。(3)删除节点的右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点。(5)左右孩子都不为空,则将删除节点的左子树头节点(左孩子)放到删除节点的右子树的最左面的左孩子上,返回删除节点的右孩子为新的根节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution1{
public TreeNode deleteNode(TreeNode root, int key){
if (root == null) return root;//没找到节点
if (root.val == key){//找到了节点
if (root.left == null)
return root.right;//如果节点的左子节点是空的,就返回右子树
else if (root.right == null)
return root.left;//如果右子节点为空,就返回左子树
else {//都不为空,首先找到右子树的最左边的孩子节点,将左子树添加到其上,以右子节点为根节点
TreeNode cur = root.right;
while (cur.left != null)
cur = cur.left;
cur.left = root.left;
root = root.right;
return root;
}
}
if (root.val > key) root.left = deleteNode(root.left, key);
if (root.val < key) root.right = deleteNode(root.right, key);
return root;
}
}