二分查找
搜索插入位置
class Solution {
/**
在nums里面进行搜索
二分查找,返回第一个不小于targer的nums[i],插入i的位置
返回left
*/
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length;
while(left < right) {
int mid = (left + right)/2;
if(target > nums[mid]) {
left = mid + 1;
}
else if(target < nums[mid]) {
right = mid;
}
else {
right = mid;
}
}
return left;
}
}
搜索二维矩阵
class Solution {
/**
除了朴素的拉成一维矩阵,再二分查找
没想到如何处理二维矩阵
*/
public boolean searchMatrix(int[][] matrix, int target) {
int row = matrix.length;
int col = matrix[0].length;
List<Integer> list = new ArrayList();
int[] mt = new int[(row + 1) * (col + 1)];
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
list.add(matrix[i][j]);
}
}
int left = 0;
int right = list.size();
while(left < right) {
int mid = (left + right) / 2;
if(target == list.get(mid)) {
// System.out.print(mid + " " + mt[mid]);
return true;
}
else if(target > list.get(mid)) {
left = mid + 1;
}
else {
right = mid;
}
}
return false;
}
}
排序数字中开始和结束的位置
class Solution {
/**
二分查找?
分别用二分查找拿到左边界left_bound和右边姐right_bound
这里是左开右开进行区间缩减,while判断的条件是left <= right
*/
public int[] searchRange(int[] nums, int target) {
int[] res = new int[]{searchLeftBound(nums, target), searchRightBound(nums, target)};
return res;
}
public int searchLeftBound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = (left + right) / 2;
if(target > nums[mid]) {
left = mid + 1;
}
else if(target < nums[mid]) {
right = mid - 1;
}
else {
right = mid - 1;
}
}
if(left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
public int searchRightBound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = (left + right) / 2;
if(target > nums[mid]) {
left = mid + 1;
}
else if(target < nums[mid]) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
if(right < 0 || nums[right] != target) {
return -1;
}
return right;
}
}
搜索旋转排序数组
class Solution {
/**
记录下第一次nums[i] > nums[i + 1]的位置的index
寻找时,从0 ~ index、index + 1 ~ nums.len两处范围内找
*/
public int search(int[] nums, int target) {
int idx = 0;
for(int i = 0; i < nums.length - 1; i++) {
if(nums[i] > nums[i + 1]) {
idx = i;
break;
}
}
int res = findTarget(0, idx, target, nums);
if(res != -1) {
return res;
}
if(idx + 1 < nums.length) { // 要这么找,首先肯定要满足条件
res = findTarget(idx + 1, nums.length - 1, target, nums);
}
return res;
}
public int findTarget(int left, int right, int target, int[] nums) {
while(left < right) {
int mid = (left + right) / 2;
if(target > nums[mid]) {
left = mid + 1;
}
else {
right = mid;
}
}
return nums[left] == target ? left : -1;
}
}
寻找旋转排序数组中的最小值
class Solution {
/**
二分直接上左右指针
如果mid比nums.len位置的值大,说明最小值在右边,left = mid + 1
否则,由于可能mid就是最小值,right = mid
*/
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while(left < right) {
int mid = (left + right) / 2;
if(nums[mid] > nums[nums.length - 1]) {
left = mid + 1;
}
else {
right = mid;
}
}
return nums[left];
}
}
有效的括号
class Solution {
/**
利用栈的特性
每次判断为( [ {,入栈的时候对应入栈) ] }
当有同样的) ] } 时,出栈
一旦栈不为空或者不对应,则直接返回false
*/
public boolean isValid(String s) {
Stack<Character> stack = new Stack();
char[] ch = s.toCharArray();
for(int i = 0; i < ch.length; i++) {
if(ch[i] == '(' || ch[i] == '[' || ch[i] == '{') {
if(ch[i] == '(') {
stack.push(')');
}
if(ch[i] == '[') {
stack.push(']');
}
if(ch[i] == '{') {
stack.push('}');
}
}
else {
if(stack.isEmpty() || stack.peek() != ch[i]) {
return false;
}
else {
stack.pop();
}
}
}
if(!stack.isEmpty()) {
return false;
}
return true;
}
}
最小栈
class MinStack {
/**
两个栈,一个最小栈记录最小值
一个正常入
*/
Stack<Integer> stack = new Stack();
Stack<Integer> minstack = new Stack();
public MinStack() {
stack = new Stack();
minstack = new Stack();
}
public void push(int val) {
stack.push(val);
if(minstack.isEmpty() || val <= minstack.peek()) {
minstack.push(val);
}
}
public void pop() {
if(stack.pop().equals(minstack.peek())) {
minstack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minstack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
字符串解码
class Solution {
/**
遇到数字,进行count--
循环打印字符()
数字,存入numstack(当连续时如123)用count计数 num = num*10 + ch - '0'
str拼接存入strstack
*/
public String decodeString(String s) {
Stack<Integer> numstack = new Stack();
Stack<StringBuffer> strstack = new Stack();
StringBuffer sb = new StringBuffer();
char[] ch = s.toCharArray();
int num = 0;
for(int i = 0; i < ch.length; i++) {
// 尚未遇到[]时
if(ch[i] >= '0' && ch[i] <= '9') { // 有数字计算数字
num = num * 10 + ch[i] - '0';
}
else if(ch[i] >= 'a' && ch[i] <= 'z') { // 有字符放字符
sb.append(ch[i]);
}
else if(ch[i] == '[') { // 遇到 "[" 开始更新存放的数字和字符
numstack.push(num);
strstack.push(sb);
num = 0;
sb = new StringBuffer();
}
else if(ch[i] == ']') { // 开始拼接
int count = numstack.pop();
StringBuffer temp = strstack.pop();
while(count > 0) {
temp.append(sb.toString());
count--;
}
sb = temp;
}
}
return sb.toString();
}
}
每日温度
class Solution {
/**
用栈实现
i = 1
temp 74
res 1
stack 73 弹73,入74(1) res = 1
*/
public int[] dailyTemperatures(int[] temperatures) {
Stack<Integer> stack = new Stack();
int[] res = new int[temperatures.length];
for(int i = 0; i < res.length; i++) {
while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()] ) {
int j = stack.pop();
res[j] = i - j;
}
stack.push(i);
}
return res;
}
}
堆(没太接触过)
前K个高频元素
class Solution {
/**
用堆进行筛选
priority<int[]>,存放nums - 次数的数组
这个数组由遍历nums,hashmap得到key - value(key: num, val: num出现次数
pq > k,弹出小的元素
剩余的直接全部拿出
*/
public int[] topKFrequent(int[] nums, int k) {
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
int[] res = new int[k];
HashMap<Integer, Integer> map = new HashMap();
for(int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
for(var node : map.entrySet()) {
int[] tmp = new int[2];
tmp[0] = node.getKey();
tmp[1] = node.getValue();
pq.offer(tmp);
if(pq.size() > k) {
pq.poll();
}
}
int i = 0;
while(!pq.isEmpty()) {
res[i] = pq.poll()[0];
i++;
}
return res