Java练习算法代码(排序,数据结构,小算法,LeetCode练习题)
八大排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 基数排序(桶排序)
- 希尔排序
- 堆排序
Java简单的算法题,目前有20道
递归知识~
2018年9月25日更新,_old文件夹的是之前的(..
一些LeetCode的题目.
- No1:找出数组中能够组成sum的两个数的数组下标
- 解法:使用Map来存储,如果发现
target-arr[i]
如果在Map中有数据,那返回下标即可
- 解法:使用Map来存储,如果发现
- No3:求出数组能组成最大不重复元素的间隔
- 解法:使用滑动窗口的**,不停往前移动,每次移动一次时计算max值,最终返回的一定是符合条件的最大值
- No7:反转整数
- 解法:其实就是运用数学方法:
int pop = x % 10;x /= 10;rev = rev * 10 + pop;
。同时因为res*10
可能会发生溢出,可以使用Math方法来判断一下:if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
- 解法:其实就是运用数学方法:
- No17: 9宫格,例如:输入123能够组合成哪些字母
- 解法:将123..使用数组的方式来装载(类似于查表),将输入的字符串123(digits),从index开始,使用String s来记录每次可能得到的组合值。如果
index==digits.length
,说明已经是一种情况了。
- 解法:将123..使用数组的方式来装载(类似于查表),将输入的字符串123(digits),从index开始,使用String s来记录每次可能得到的组合值。如果
- No19:删除链表第n个元素,tips:删除链表元素最好使用一个dummyHead,这样就不用担心删除的是链表头了。使用方式:
dummyHead.next = head
- 解法1:计算出链表的长度,
int k = length-n
,k的坐标就是要删除的位置了 - 解法2:使用两个指针fast和slow,先让fast先走
n-1
个位置,然后两个指针同时走(直到fast==null),最后,slow的下一个节点就是要删除的节点。
- 解法1:计算出链表的长度,
- No20:检验字符串
[]{]}{]{}(
这样的字符串是否有效(对齐)- 解法:使用Stack来存储
[{(
这些字符,如果是不是这些字符的话,则出栈,判断是否与[{(
相匹配。- 可能遇到的边界问题:一、出栈时需要判断Stack是否有元素。二、所有元素进出栈完毕后,需要判断Stack是否为null
- 解法:使用Stack来存储
- No24:两两交换链表的节点
- 解法:使用
p=dummyHead
,while(p.next != null && p.next.next != null )
,找出接下来的三个节点,分别为node1,node2,next。做法很简单:node2指向node1,node1指向next,p指向node2,node1的位置由p取代
- 解法:使用
- No47:数字全排列(回溯法)
- 解法:使用一个数组记录已经"走过"的数字,从
index=0
开始,当index==nums.length
说明已经出现一个结果了。每次遍历一个数字时,判断是否已经"走过",如果没有"走过"则设置为"走过",并add到我们的结果中。回溯完了之后需要清除状态!
- 解法:使用一个数组记录已经"走过"的数字,从
- No51:八皇后问题(回溯法)
- 解决:其实与全排列的问题是一样的,解法也是一样的。只不过八皇后问题需要针对具体的条件来判断而已。规律就是这三个条件:
col[i] && !dia1[index + i] && !dia2[index - i + n - 1]
- 解决:其实与全排列的问题是一样的,解法也是一样的。只不过八皇后问题需要针对具体的条件来判断而已。规律就是这三个条件:
- No75:给出只有
[0,1,2]
的数组,这个数组是乱序的,想要将其结果变成是[0,1,2]
有序- 解决1:可能首先想到的是排序算法,排序算法的话时间复杂度最低控制在O(nlogn)
- 解决2:因为只有3个元素,其实我们可以创建出一个三个元素的数组,记录每个数字出现的频率,然后根据
0,1,2
的频率放回到数组里边去,这样就是有序的了。这个时间复杂度和空间复杂度都为O(n) - 解决3:使用三路快排的**,可以不用开辟多于的空间。具体实现就是0放在最左侧,1在中间,2在最右侧。
- No77:求解C(n,k)的组合(回溯法)
- 解法:从1开始,只要
result.size()==k
则是一种组合,递归完记得要清除状态
- 解法:从1开始,只要
- No79:在n*m的“地图”中,是否存在有对应的路径找到对应的答案(回溯)
- 解法:使用一个二维数组来代表上下移动(遍历这个数组,即可实现)
int d[][] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
使用一个visited数组来代表这个“位置”是否已经被走过了。如果没有被走过,并且是当前的结果路径之一,则继续上下左右移动。直到当前的结果长度与index相等(递归出口) 。回溯完需要清除状态值
- 解法:使用一个二维数组来代表上下移动(遍历这个数组,即可实现)
- No96-144-145:遍历树
- 解法1:使用递归的话就很容易前中后遍历数了。
- 解法2:使用Stack来实现无递归的方式来遍历,要注意使用Stack时,什么时候push进去!因为跟递归的时候是相反的
- No102:层序遍历树
- 解法:使用队列的方式(linkedList)就很容易实现了
- No104:树的最大深度
- 解法:使用递归的方式,其实就一行代码
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
- 解法:使用递归的方式,其实就一行代码
- No112:树根节点到叶节点的"和"路径是否存在
- 解法:递归的出口就是-->叶子节点的值是否等于sum,递归调用
return hasPathSum(root.left, sum - root.val)|| hasPathSum(root.right, sum - root.val);
- 解法:递归的出口就是-->叶子节点的值是否等于sum,递归调用
- No113:求出树根节点到叶节点的"和"路径
- 解法:相对于leetcode 112,它只是要求出对应的路径。我们可以使用一个list来记录路径,每次进入之前就add进去,递归完了之后就remove掉。其实就相当于回溯法
- No167:找出数组中能够组成sum的两个数的数组下标,此时这个数组是有序的。
- 跟第一题不同的是,此时的数组是有序的。
- 解法1:使用二分的方式来搜索,找出对应的下标(此时的时间复杂度是O(nlogn)
- 解法2:使用滑动窗口的方式来搜索,因为l值是小的,r值是大的。如果l+r < target,l这边++即可!
- No200:寻找"陆地"的个数,在n*m的数组中寻找出"陆地"(深度遍历)
- 解法:使用一个二维数组来实现移动
d[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
,使用visited[][]
来记录已经走过的位置。
- 解法:使用一个二维数组来实现移动
- No203:在链表删除重复的节点
- 解法1:使用dummyHead就不用再做其余的处理了
- 解法2:使用递归的方式:
head.next = removeElements4(head.next, val);
,最后head.val == val ? head.next : head;
- No206:反转链表
- 解法1:循环的方式;使用一个pre节点,找到next节点。
cur.next= pre; pre = cur; cur = next
- 解法2:递归的方式;
ListNode rhead = reverseList2(head.next); head.next.next = head; head.next = null; return rhead;
- 解法1:循环的方式;使用一个pre节点,找到next节点。
- No209:给出一个数组,给出一个target,求出数组的元素+起来的和>target的最短间隔
- 解法:跟No3不同的是,No3着重于不重复元素的间隔,而这里着重于比较target的值。使用一个sum来维护,每次
- No219:给出一个数组,在k的范围内,判断有没有重复的元素
- 解法:使用HashSet来维护,如果在add之前发现已经重复了,返回true。当map的大小大于k+1,那就减去最左边的元素
if(record.size() == k + 1) record.remove(nums[i-k]);
- 解法:使用HashSet来维护,如果在add之前发现已经重复了,返回true。当map的大小大于k+1,那就减去最左边的元素
- No220:在距离当前位置为k的范围内,是否存在一个点的值与当前位置值的差的绝对值小于等于t。
- 解法:在上一题中,主要是判断是否有重复值,而此道的条件是有无绝对值小于的等于t(在k范围内)。其实就是判断条件变化了,绝对值问题我们可以使用treeSet的ceiling方法:
if (record.ceiling((long) nums[i] - (long) t) != null &&record.ceiling((long) nums[i] - (long) t) <= (long) nums[i] + (long) t)
- 解法:在上一题中,主要是判断是否有重复值,而此道的条件是有无绝对值小于的等于t(在k范围内)。其实就是判断条件变化了,绝对值问题我们可以使用treeSet的ceiling方法:
- No226:反转树
- 解法:使用递归,得到左边,得到右边。左右两边交换
- No237:在链表删除元素为value的节点
- 解法:找到给定值的节点,将找到的节点的下一个节点的值赋值给当前节点,删除掉下一个节点
- No253:在二叉树找出p和q节点的最小公共祖先
- 解法:p q 都在root左边
if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
...右边也是差不多的,如果在同一侧,直接返回root
- 解法:p q 都在root左边
- No257:求出二叉树的路径
- 解法:当遍历到叶子节点时,此时加入根节点。否则递归求出左子树和右子树的路径
- No260:给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素
- 解法:其实如果是恰好有一个元素只出现一次的话,我们可以直接异或就搞掂了。现在是两个元素只出现一次,解决其实也一样:对这些数据进行异或,得出一个sum-->
sum ^= nums[i];
,使用sum &= -sum;
得出两个数异或结果的最右边的一个1,其他的为零,这样进行&操作就可以将两个不同的数分到不同的两组去。于是使用int[] res = new int[2];
根据==0来区分两个组来异或,最后得出的结果就是res的值了!
- 解法:其实如果是恰好有一个元素只出现一次的话,我们可以直接异或就搞掂了。现在是两个元素只出现一次,解决其实也一样:对这些数据进行异或,得出一个sum-->
- No283:将数组的0移到最后,其余的元素顺序不发生改变
- 解法1:使用一个新数组装载非0元素,将nums剩余的位置放置为0:
for(int i = nonZeroElements.size() ; i < nums.length ; i ++) nums[i] = 0;
- 解法2:nums中, [0...k)的元素均为非0元素,只要遍历到的元素不为0,k++。
- 解法3:使用交换的方式
for(int i = 0 ; i < nums.length ; i ++) if(nums[i] != 0) if(k != i)swap(nums, k++, i); else k ++;
- 解法1:使用一个新数组装载非0元素,将nums剩余的位置放置为0:
- No347:求Top K 频率出现最高的元素
- 解法:使用HashMap来记录每个元素出现的频率,然后使用小顶堆将其比较,如果当前pop出来的堆顶比当前遍历到的元素频率要小,则出队,换当前元素进去(注意,要维护当前堆只有k个元素的)
- No349:求两个数组的交集,只出现一次
- 解法:将其中一个数组遍历,使用hashSet来存储。再将第二个数组遍历,判断当前元素是否存在HashSet中,如果存在则是其中一个结果
- No350:求两个数组的交集,这次要求有多少个相同的,交集的结果也得有多少个
- 解法:使用HashMap来计算频率,在遍历第二个数组的时候,根据频率来add到结果集中
- No437:树根节点到其余树节点的"和"路径有多少条?
- 解法:这跟之前那个有点区别,这不是规定到叶子节点上了,而是每个节点上都行!
return findPath(root, sum)+ pathSum(root.left, sum) + pathSum(root.right, sum);
- 解法:这跟之前那个有点区别,这不是规定到叶子节点上了,而是每个节点上都行!
- No447:求出三个点距离的组合
- 解法使用hashMap来存储起来合适的距离。求和的时候使用
res += record.get(dis) * (record.get(dis) - 1);
即可!
- 解法使用hashMap来存储起来合适的距离。求和的时候使用
- No454:求出四个数组的元素能够组成0的组合
- 解法:计算C和D的sum,放入Map,如果sum重复的话,value加1(开辟空间来减少时间复杂度)。遍历AB的时候,算出具体的个数就可以了:
if(map.containsKey(-A[i]-B[j])) res += map.get(-A[i]-B[j]);
- 解法:计算C和D的sum,放入Map,如果sum重复的话,value加1(开辟空间来减少时间复杂度)。遍历AB的时候,算出具体的个数就可以了:
- No804:唯一摩尔斯密码词
- 解法:查表(将密码定义成表,查出对应的摩斯密码),放入set集合即可