classSolution{ publicintfindRepeatNumber(int[] nums){ Arrays.sort(nums); for (int i = 1;i < nums.length; i++) { if (nums[i] == nums[i - 1]) { return nums[i]; } } return0; } }
Set去重
可以将该数组丢到Set集合里去重,若是添加失败就代表该数字重复,直接返回就好了。
1 2 3 4 5 6 7 8 9 10 11
classSolution{ publicintfindRepeatNumber(int[] nums){ Set<Integer> set = new HashSet<>(); for (int i : nums) { if (!set.add(i)) { return i; } } return0; } }
哈希表
跟Set差不多,添加到哈希表之前,先判断一下是否有该键,然后要是有就直接返回。
1 2 3 4 5 6 7 8 9 10 11 12
classSolution{ publicintfindRepeatNumber(int[] nums){ HashMap<Integer,Integer> map = new HashMap<>(); for (int i : nums) { if (map.containsKey(i)) { return i; } map.put(i,i); } return0; } }
classMyQueue{ Stack<Integer> stack1 = new Stack(); Stack<Integer> stack2 = new Stack(); /** Initialize your data structure here. */ publicMyQueue(){} /** Push element x to the back of queue. */ publicvoidpush(int x){ stack1.push(x); } /** Removes the element from in front of queue and returns that element. */ publicintpop(){ if (!stack2.isEmpty()) return stack2.pop(); if (!stack1.isEmpty()) { while(!stack1.isEmpty()) { stack2.push(stack1.pop()); } return stack2.pop(); } return -1; } /** Get the front element. */ publicintpeek(){ if (!stack2.isEmpty()) return stack2.peek(); if (!stack1.isEmpty()) { while(!stack1.isEmpty()) { stack2.push(stack1.pop()); } return stack2.peek(); } return -1; } /** Returns whether the queue is empty. */ publicbooleanempty(){ if (stack1.isEmpty() && stack2.isEmpty()) returntrue; elsereturnfalse; } }
/** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */
classSolution{ publicintfib(int n){ if (n <= 0) return0; if (n == 1 || n == 2) return1; int a = 1; int b = 1; for (int i = 3;i <= n; i++) { int c = (a + b) % 1000000007; a = b; b = c; } return b; } }
青蛙跳台阶
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution{ publicintnumWays(int n){ if (n <= 1) return1; if (n == 2) return2; int a = 1; int b = 1; for (int i = 2;i <= n;i++) { int c = (a + b) % 1000000007; a = b; b = c; } return b; } }
classSolution{ publicintminArray(int[] numbers){ for (int i = 0;i < numbers.length - 1; i++) { if (numbers[i] > numbers[i + 1]) return numbers[i + 1]; } return numbers[0]; } }
二分查找
二分查找最主要的就是划分区间,需要先分析一下怎样确定好区间。
中间的数大于最右边的数,代表期间不会单调递增,直接进入右边的区间
中间的数小于最右边的数,代表期间是单调递增的,直接进入左边的区间
要是中间的数与最右边的数相等,那就缩进一下区间
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution{ publicintminArray(int[] numbers){ int l = 0; int r = numbers.length - 1; while (l < r) { int mid = l + r >> 1; if (numbers[mid] > numbers[r]) { l = mid + 1; } elseif (numbers[mid] < numbers[r]) { r = mid; } else { r -= 1; } } return numbers[l]; } }
classSolution{ publicintmovingCount(int m, int n, int k){ if (m == 0 || n == 0) return0; boolean[][] isVisited = newboolean[m][n]; return dfs(0,0,k,isVisited); }
publicintdfs(int i,int j,int k,boolean[][] isVisited){ if (i < 0 || i >= isVisited.length || j < 0 || j >= isVisited[0].length || isVisited[i][j] || !isAllowed(i,j,k)) return0; isVisited[i][j] = true; // 上下左右 return dfs(i-1,j,k,isVisited) + dfs(i+1,j,k,isVisited) + dfs(i,j-1,k,isVisited) + dfs(i,j+1,k,isVisited) + 1; } // 判断是否合法 publicbooleanisAllowed(int m, int n, int k){ int sum = 0; while (m != 0) { sum += m % 10; m = m / 10; } while (n != 0) { sum += n % 10; n = n / 10; } if (sum <= k) returntrue; elsereturnfalse; } }
看看别人的发现判断是否合法不用这么麻烦,还可以优化一下,所以变成下面这样。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution{ publicintmovingCount(int m, int n, int k){ if (m == 0 || n == 0) return0; boolean[][] isVisited = newboolean[m][n]; return dfs(0,0,k,isVisited); }
classSolution{ publicintmovingCount(int m, int n, int k){ if (m == 0 || n == 0) return0; boolean[][] isVisited = newboolean[m][n]; return dfs(0,0,k,isVisited); }
classSolution{ publicdoublemyPow(double x, int n){ if (n == 0) return1; long a = n; double res = 1.0; if (n < 0) { x = 1 / x; a = -a; } while (a > 0) { if ((a & 1) == 1) res *= x; x = x * x; a = a >> 1; } return res; } }
快速幂的递归写法
1 2 3 4 5 6 7 8
classSolution{ publicdoublemyPow(double x, int n){ if (n == 0) return1; if (n == -1) return1 /x; if ((n & 1) == 1) return myPow(x * x,n >> 1) * x; elsereturn myPow(x * x,n >> 1); } }
18.删除链表的节点
这里可以直接查到那个需要删除的节点,然后改变链表的指向就好了。
迭代写法
1 2 3 4 5 6 7 8 9 10 11 12
classSolution{ public ListNode deleteNode(ListNode head, int val){ if (head == null) returnnull; if (head.val == val) return head.next; ListNode node = head; while (head.next.val != val) { head = head.next; } head.next = head.next.next; return node; } }
递归写法
1 2 3 4 5 6 7 8
classSolution{ public ListNode deleteNode(ListNode head, int val){ if (head == null) returnnull; if (head.val == val) return head.next; head.next = deleteNode(head.next,val); return head; } }
21.调整数组顺序使奇数位于偶数前面
这题一看题目就是有点像快排的思想,双指针遍历就好了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution{ publicint[] exchange(int[] nums) { if (nums.length == 0) returnnewint[0]; int pre = 0; int cur = nums.length - 1; while (cur > pre) { while (nums[pre] % 2 != 0 && pre < cur) pre++; while (nums[cur] % 2 == 0 && pre < cur) cur--; int temp = nums[pre]; nums[pre] = nums[cur]; nums[cur] = temp; } return nums; } }