liuyongt/javaarithmetic

Java练习算法代码(排序，数据结构，小算法练习题)

JavaArithmetic

Java练习算法代码(排序，数据结构，小算法，LeetCode练习题)

一、sort文件夹是排序算法

八大排序算法

• 冒泡排序
• 选择排序
• 插入排序
• 归并排序
• 快速排序
• 基数排序(桶排序)
• 希尔排序
• 堆排序

三、basic文件夹是基础相关

Java简单的算法题，目前有20道

递归知识～

四、datastructure

2018年9月25日更新，_old文件夹的是之前的(..

五、LeetCode

一些LeetCode的题目.

• No1：找出数组中能够组成sum的两个数的数组下标
  • 解法：使用Map来存储，如果发现target-arr[i]如果在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，说明已经是一种情况了。
• No19：删除链表第n个元素，tips：删除链表元素最好使用一个dummyHead，这样就不用担心删除的是链表头了。使用方式：dummyHead.next = head
  • 解法1：计算出链表的长度，int k = length-n，k的坐标就是要删除的位置了
  • 解法2：使用两个指针fast和slow，先让fast先走n-1个位置，然后两个指针同时走(直到fast==null)，最后，slow的下一个节点就是要删除的节点。
• No20：检验字符串[]{]}{]{}(这样的字符串是否有效(对齐)
  • 解法：使用Stack来存储[{(这些字符，如果是不是这些字符的话，则出栈，判断是否与[{(相匹配。
    • 可能遇到的边界问题：一、出栈时需要判断Stack是否有元素。二、所有元素进出栈完毕后，需要判断Stack是否为null
• 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则是一种组合，递归完记得要清除状态
• 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);
• 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;
• 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]);
• 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)
• 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
• No257：求出二叉树的路径
  • 解法：当遍历到叶子节点时，此时加入根节点。否则递归求出左子树和右子树的路径
• No260：给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素
  • 解法：其实如果是恰好有一个元素只出现一次的话，我们可以直接异或就搞掂了。现在是两个元素只出现一次，解决其实也一样：对这些数据进行异或，得出一个sum-->sum ^= nums[i];，使用sum &= -sum;得出两个数异或结果的最右边的一个1，其他的为零，这样进行&操作就可以将两个不同的数分到不同的两组去。于是使用int[] res = new int[2];根据==0来区分两个组来异或，最后得出的结果就是res的值了！
• 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 ++;
• 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);即可！
• No454：求出四个数组的元素能够组成0的组合
  • 解法：计算C和D的sum，放入Map，如果sum重复的话，value加1(开辟空间来减少时间复杂度)。遍历AB的时候，算出具体的个数就可以了：if(map.containsKey(-A[i]-B[j])) res += map.get(-A[i]-B[j]);
• No804：唯一摩尔斯密码词
  • 解法：查表(将密码定义成表，查出对应的摩斯密码)，放入set集合即可