数据结构开篇

h2pl · h2pl · commit 55693bfcda84 · 2018-04-13T18:20:34.000+08:00
diff --git a/src/数据结构/位运算/统计两个数的二进制表示有多少位不同.java b/src/数据结构/位运算/统计两个数的二进制表示有多少位不同.java
@@ -0,0 +1,7 @@
+package 数据结构.位运算;
+
+/**
+ * Created by 周杰伦 on 2018/4/13.
+ */
+public class 统计两个数的二进制表示有多少位不同 {
+}
diff --git a/src/数据结构/哈希表/判断数组是否含有相同元素.java b/src/数据结构/哈希表/判断数组是否含有相同元素.java
@@ -0,0 +1,20 @@
+package 数据结构.哈希表;
+
+import java.util.HashMap;
+
+/**
+ * Created by 周杰伦 on 2018/4/13.
+ */
+public class 判断数组是否含有相同元素 {
+    public boolean containsDuplicate(int[] nums) {
+        HashMap<Integer, Integer> map = new HashMap<>();
+        for (int i = 0;i < nums.length;i ++) {
+            if (map.containsKey(nums[i])) {
+                return true;
+            }else {
+                map.put(nums[i], 1);
+            }
+        }
+        return false;
+    }
+}
diff --git a/src/数据结构/哈希表/数组中的两个数和为给定值.java b/src/数据结构/哈希表/数组中的两个数和为给定值.java
@@ -0,0 +1,32 @@
+package 数据结构.哈希表;
+
+import java.util.Arrays;
+import java.util.HashMap;
+
+/**
+ * Created by 周杰伦 on 2018/4/13.
+ */
+public class 数组中的两个数和为给定值 {
+    public static void main(String[] args) {
+        int []a = {3,2,4};
+        System.out.println(Arrays.toString(twoSum(a, 6)));
+    }
+    public static int[] twoSum(int[] nums, int target) {
+        int []two = new int[2];
+        HashMap<Integer, Integer> map = new HashMap<>();
+        for (int i = 0;i < nums.length;i ++) {
+            map.put(nums[i],i);
+        }
+        for (int i = 0;i < nums.length;i ++) {
+            if (map.containsKey(target - nums[i])) {
+                if (i == map.get(target - nums[i])) {
+                    continue;
+                }
+                two[0] = i;
+                two[1] = map.get(target - nums[i]);
+                return two;
+            }
+        }
+        return two;
+    }
+}
diff --git a/src/数据结构/哈希表/最长和谐序列.java b/src/数据结构/哈希表/最长和谐序列.java
@@ -0,0 +1,30 @@
+package 数据结构.哈希表;
+
+import java.util.Arrays;
+import java.util.HashMap;
+
+/**
+ * Created by 周杰伦 on 2018/4/13.
+ */
+public class 最长和谐序列 {
+    public static void main(String[] args) {
+        int []a = {1,3,2,2,5,2,3,7};
+        System.out.println(findLHS(a));
+    }
+
+    public static int findLHS(int[] nums) {
+        int cnt = 1;
+        HashMap<Integer, Integer> map = new HashMap<>();
+        for (int i = 0;i < nums.length;i ++) {
+            if (map.containsKey(nums[i])) {
+                cnt ++;
+            }else {
+                map.put(nums[i], i);
+                if (map.containsKey(nums[i] - 1) || map.containsKey(nums[i] + 1)) {
+                    cnt ++;
+                }
+            }
+        }
+        return cnt;
+    }
+}
diff --git a/src/数据结构/图/冗余连接.java b/src/数据结构/图/冗余连接.java
@@ -0,0 +1,7 @@
+package 数据结构.图;
+
+/**
+ * Created by 周杰伦 on 2018/4/13.
+ */
+public class 冗余连接 {
+}
diff --git a/src/数据结构/字符串/两个字符串包含的字符是否完全相同.java b/src/数据结构/字符串/两个字符串包含的字符是否完全相同.java
@@ -0,0 +1,20 @@
+package 数据结构.字符串;
+
+/**
+ * Created by 周杰伦 on 2018/4/13.
+ */
+public class 两个字符串包含的字符是否完全相同 {
+    public boolean isAnagram(String s, String t) {
+        int[] map = new int[26];
+        for (int i = 0;i < s.length();i ++) {
+            map[s.charAt(i) - 'a'] += 1;
+        }
+        for (int i = 0;i < t.length();i ++) {
+            map[s.charAt(i) - 'a'] -= 1;
+        }
+        for (int i : map) {
+            if (i != 0)return false;
+        }
+        return true;
+    }
+}
diff --git a/src/数据结构/数组与矩阵/把数组中的0移到末尾.java b/src/数据结构/数组与矩阵/把数组中的0移到末尾.java
@@ -0,0 +1,24 @@
+package 数据结构.数组与矩阵;
+
+import java.util.Arrays;
+
+/**
+ * Created by 周杰伦 on 2018/4/13.
+ */
+public class 把数组中的0移到末尾 {
+    public static void main(String[] args) {
+        int []a = {0, 1, 0, 3, 12};
+        moveZeroes(a);
+        System.out.println(Arrays.toString(a));
+    }
+    public static void moveZeroes(int[] nums){
+        int index = 0;
+        for (int i = 0;i < nums.length;i ++) {
+            if (nums[i] != 0) {
+                nums[index] = nums[i];
+                index ++;
+            }
+        }
+        Arrays.fill(nums,index, nums.length, 0);
+    }
+}
diff --git a/src/数据结构/栈和队列/在另一个数组中比当前元素大的下一个元素.java b/src/数据结构/栈和队列/在另一个数组中比当前元素大的下一个元素.java
@@ -0,0 +1,23 @@
+package 数据结构.栈和队列;
+
+import java.util.Arrays;
+
+/**
+ * Created by 周杰伦 on 2018/4/13.
+ */
+public class 在另一个数组中比当前元素大的下一个元素 {
+    //这题的测试用例有点问题
+    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
+        int []big = new int[nums1.length];
+        Arrays.fill(big, -1);
+        for (int i = 0;i < nums1.length;i ++) {
+            for (int j = i + 1;j < nums2.length;j ++) {
+                if (nums2[j] > nums1[i]) {
+                    big[i] = nums2[j];
+                    break;
+                }
+            }
+        }
+        return big;
+    }
+}
diff --git a/src/数据结构/栈和队列/循环数组中比当前元素大的下一个元素.java b/src/数据结构/栈和队列/循环数组中比当前元素大的下一个元素.java
@@ -0,0 +1,30 @@
+package 数据结构.栈和队列;
+
+import java.util.Arrays;
+
+/**
+ * Created by 周杰伦 on 2018/4/13.
+ */
+public class 循环数组中比当前元素大的下一个元素 {
+    //旋转数组很好的解决方式就是复制一份接在后面
+    public int[] nextGreaterElements(int[] nums) {
+        int []big = new int[nums.length];
+        int []newnum = new int[nums.length * 2];
+        Arrays.fill(big, -1);
+        for (int i = 0;i < nums.length;i ++) {
+            newnum[i] = nums[i];
+        }
+        for (int i = nums.length;i < newnum.length;i ++) {
+            newnum[i] = nums[i - nums.length];
+        }
+        for (int i = 0;i < nums.length;i ++) {
+            for (int j = i + 1;j < newnum.length;j ++) {
+                if (newnum[j] > nums[i]) {
+                    big[i] = newnum[j];
+                    break;
+                }
+            }
+        }
+        return big;
+    }
+}
diff --git a/src/数据结构/栈和队列/括号匹配.java b/src/数据结构/栈和队列/括号匹配.java
@@ -0,0 +1,46 @@
+package 数据结构.栈和队列;
+
+import java.util.Stack;
+
+/**
+ * Created by 周杰伦 on 2018/4/13.
+ */
+public class 括号匹配 {
+    public static void main(String[] args) {
+
+    }
+    public boolean isValid(String s) {
+        Stack<Character> stack = new Stack<>();
+        for (int i = 0;i < s.length();i ++) {
+            char c = s.charAt(i);
+            switch (c) {
+                case '(' : stack.push(c);
+                break;
+                case '[' : stack.push(c);
+                break;
+                case '{' : stack.push(c);
+                break;
+                case ')' : {
+                    if (!stack.isEmpty() && stack.peek() == '(') {
+                        stack.pop();
+                        break;
+                    }else return false;
+                }
+                case ']' : {
+                    if (!stack.isEmpty() && stack.peek() == '[') {
+                        stack.pop();
+                        break;
+                    }else return false;
+                }
+                case '}' : {
+                    if (!stack.isEmpty() && stack.peek() == '{') {
+                        stack.pop();
+                    }else return false;
+                }
+            }
+        }
+        if (stack.isEmpty()) {
+            return true;
+        }else return false;
+    }
+}
diff --git a/src/数据结构/栈和队列/数组中元素与下一个比它大的元素之间的距离.java b/src/数据结构/栈和队列/数组中元素与下一个比它大的元素之间的距离.java
@@ -0,0 +1,47 @@
+package 数据结构.栈和队列;
+
+import java.util.Arrays;
+import java.util.Stack;
+
+/**
+ * Created by 周杰伦 on 2018/4/13.
+ */
+public class 数组中元素与下一个比它大的元素之间的距离 {
+    public static void main(String[] args) {
+        int []a = {73,74,75,71,69,72,76,73};
+        System.out.println(Arrays.toString(dailyTemperatures(a)));
+    }
+    // 不想用栈
+    public static int[] dailyTemperatures(int[] temperatures) {
+        int[]big = new int[temperatures.length];
+        Arrays.fill(big, 0);
+        for (int i = 0;i < temperatures.length - 1;i ++) {
+            for (int j = i + 1;j < temperatures.length;j ++) {
+                if (temperatures[j] > temperatures[i]) {
+                    big[i] = j - i;
+                    break;
+                }
+            }
+        }
+        return big;
+    }
+    //用栈的解法，没看懂
+    public int[] dailyTemperatures2(int[] temperatures) {
+        int n = temperatures.length;
+        int[] ret = new int[n];
+        Stack<Integer> stack = new Stack<>();
+
+        //每次压入一个元素，如果后面的元素大于栈顶元素，则找到。出栈。
+        //如果不满足，则把当前元素也压栈。重复多次后可能有多个元素在栈内。
+        //当找到一个满足的元素时，继续判断之前栈中的元素是否小于它。
+        //若满足则一次可以标记多个元素的距离值。这样的话时间复杂度要低很多。
+        for(int i = 0; i < n; i++) {
+            while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
+                int idx = stack.pop();
+                ret[idx] = i - idx;
+            }
+            stack.add(i);
+        }
+        return ret;
+    }
+}
diff --git a/src/数据结构/栈和队列/最小值栈.java b/src/数据结构/栈和队列/最小值栈.java
@@ -0,0 +1,44 @@
+package 数据结构.栈和队列;
+
+import java.util.Stack;
+
+/**
+ * Created by 周杰伦 on 2018/4/13.
+ */
+public class 最小值栈 {
+    //入栈时压入当前最小值。
+    //出栈时出栈当前最小值。
+    //注意所有入栈出栈操作数据栈和最小值栈要一致，否则当多个元素相同时会出错。
+    class MinStack {
+
+        private Stack<Integer> dataStack;
+        private Stack<Integer> minStack;
+        private int min;
+
+        public MinStack() {
+            dataStack = new Stack<>();
+            minStack = new Stack<>();
+            min = Integer.MAX_VALUE;
+        }
+
+        public void push(int x) {
+            dataStack.add(x);
+            min = Math.min(min, x);
+            minStack.add(min);
+        }
+
+        public void pop() {
+            dataStack.pop();
+            minStack.pop();
+            min = minStack.isEmpty() ? min = Integer.MAX_VALUE : minStack.peek();
+        }
+
+        public int top() {
+            return dataStack.peek();
+        }
+
+        public int getMin() {
+            return min;
+        }
+    }
+}
diff --git a/src/数据结构/栈和队列/用栈实现队列.java b/src/数据结构/栈和队列/用栈实现队列.java
diff --git a/src/数据结构/栈和队列/用队列实现栈.java b/src/数据结构/栈和队列/用队列实现栈.java
diff --git a/src/数据结构/树/树的高度.java b/src/数据结构/树/树的高度.java
diff --git a/src/数据结构/链表/找出两个链表的交点.java b/src/数据结构/链表/找出两个链表的交点.java
