发表更新LeetCode3 分钟读完 (大约450个字)

1838. 最高频元素的频数--题解

1838. 最高频元素的频数

元素的 频数 是该元素在一个数组中出现的次数。

给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。

执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。

示例 1：

1
2
3
4
输入：nums = [1,2,4], k = 5
输出：3
解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。
4 是数组中最高频元素，频数是 3 。

示例 2：

1
2
3
4
5
6
输入：nums = [1,4,8,13], k = 5
输出：2
解释：存在多种最优解决方案：
- 对第一个元素执行 3 次递增操作，此时 nums = [4,4,8,13] 。4 是数组中最高频元素，频数是 2 。
- 对第二个元素执行 4 次递增操作，此时 nums = [1,8,8,13] 。8 是数组中最高频元素，频数是 2 。
- 对第三个元素执行 5 次递增操作，此时 nums = [1,4,13,13] 。13 是数组中最高频元素，频数是 2 。

示例 3：

1
2
输入：nums = [3,9,6], k = 2
输出：1

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k <= 105

题解

总体思路采用滑动窗口的方式：

  1. 计算窗口内的差值，如果转变成最后一个值的变化数量小于 k 时，直接向后移动窗口
  2. 如果窗口的值大于 K 时，移动左侧指针，计算出最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func maxFrequency(nums []int, k int) int {
	sort.Ints(nums)
	start,sum := 0,0
	ans := 1
	for i := 1; i < len(nums); i++ {
         //计算差值
         //1,2,5  (2-1)*1+(5-2)*2=7.
         //此处需要多想一下
		sum += (nums[i] - nums[i-1]) * (i - start)
		for sum > k {
			sum -= nums[i] - nums[start]
			start++

		}
		if i-start+1 > ans {
			ans = i - start + 1
		}

	}
	return ans

}
发表更新LeetCode3 分钟读完 (大约439个字)

36. 有效的数独--题解

36. 有效的数独

请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

注意：

  • 一个有效的数独（部分已被填充）不一定是可解的。
  • 只需要根据以上规则，验证已经填入的数字是否有效即可。

示例 1：

img

1
2
3
4
5
6
7
8
9
10
11
输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

1
2
3
4
5
6
7
8
9
10
11
12
输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 '.'

题解

思路：

  1. 使用一个维度相同的二位数组，把当前数独中的值映射到新数组中
  2. 如果数组的值为 1 ，代表是重复，否则是个新值
  3. index_box 代表是同一个 3*3 的单元内都是一个索引
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func isValidSudoku(board [][]byte) bool {
	var row,col,sbox [9][9]int
	for i := 0 ; i < 9; i++ {
		for j := 0 ; j < 9; j++ {
			if board[i][j] != '.' {
				//代表当前的索引
				num := board[i][j]-'1'
				index_box := (i/3)*3+j/3
				if row[i][num] == 1 {
					return false
				}else{
					row[i][num] = 1
				}
				if col[j][num] == 1 {
					return false
				}else{
					col[j][num] = 1
				}
				if sbox[index_box][num] == 1 {
					return false
				}else {
					sbox[index_box][num] = 1
				}
			}
		}
	}
	return true
}

发表更新LeetCode2 分钟读完 (大约319个字)

34. 在排序数组中查找元素的第一个和最后一个位置--题解

在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

  • 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：

1
2
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

1
2
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

1
2
输入：nums = [], target = 0
输出：[-1,-1]

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
func searchRange(nums []int, target int) []int {
	if len(nums) == 0 {
		return []int{-1, -1}
	}
  //找到头
	start := findFirst(nums, target)
	if start == -1 {
		return []int{-1, -1}
	}
  //找到尾
	end := findLast(nums, target)
	return []int{start, end}
}

func findFirst(nums []int, target int) int {
	start, end := 0, len(nums)-1
	for start < end {
		mid := (start + end) / 2
		if nums[mid] > target {
			end = mid - 1
		} else if nums[mid] == target {
			end = mid
		} else {
			start = mid + 1
		}
	}
  //此处防止数组第一个数是 target ，所以校验下是否相等
	if nums[start] == target {
		return start
	}
	return -1
}

func findLast(nums []int, target int) int {
	start, end := 0, len(nums)-1
	for start < end {
    //此处注意,为了防止 start=mid<end 导致死循环的问题
		mid := (start + end + 1) / 2
		if nums[mid] > target {
			end = mid - 1
		} else if nums[mid] == target {
			start = mid
		} else {
			start = mid + 1
		}
	}
	return end
}

发表更新LeetCode2 分钟读完 (大约343个字)

3. 无重复字符的最长子串--题解

3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

1
2
输入: s = ""
输出: 0

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

题解

思路：

  1. 把已经过滤的字符放入 map，key 为当前字符，value 是当前索引
  2. 如果当前 map 中存在字符，说明当前是一个重复的字符
    1. 计算当前已经走过的长度和最长长度比
    2. 计算长度方法是 i - start + 1
  3. v>=start+1 说明有重复，但当前索引在 start 后面。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func lengthOfLongestSubstring(s string) int {
    start := 0
	m := make(map[byte]int)
	max := 0
	for i, ch := range []byte(s) {
		if v, hasKey := m[ch]; hasKey && v >= start {
			start = v + 1
		}
		if i-start+1 > max {
			max = i - start + 1
		}
		m[ch] = i
	}
	return max
}
发表更新Java8 分钟读完 (大约1127个字)

 一行代码引发的性能暴跌 10 倍

代码测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import com.google.common.base.Stopwatch;
import java.util.concurrent.TimeUnit;
public class StackTest {
    public static void main(String[] args) {
        Stopwatch started = new Stopwatch();
        started.start();
        User user = null;
        for (long i = 0; i < 1000_000_000; i++) {
            user = new User();
        }
        started.stop();
        System.out.println(started.elapsed(TimeUnit.MILLISECONDS) + "ms");
        //不加打印 300ms
        //加了打印 3000ms
//        System.out.println(user);
    }
}

class User {
    private int age;
    private String userName;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getUserName() {
        return userName;
    }

    public void setUserName(String userName) {
        this.userName = userName;
    }
}
阅读更多
发表更新Java10 分钟读完 (大约1515个字)

ReentrantLock 源码解析

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

public class App {
	public static void main(String[] args) {
		
		test1();
	}
	
	public static void test1() {
		Lock lock = new ReentrantLock();
		Thread t1 = new Thread(() -> {
			lock.lock();
			System.out.println("线程 " + Thread.currentThread().getId() + " 获得锁");
			try {
				Thread.sleep(50000000);
			} catch (InterruptedException e) {
				System.out.println("线程 " + Thread.currentThread().getId() + " 释放锁");
			} finally {
				lock.unlock();
			}
		});
		t1.start();
		
		try {
			Thread.sleep(1000);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		
		
		Thread t2 = new Thread(()->{
			lock.lock();
			System.out.println("线程 " + Thread.currentThread().getId() + " 获得锁");
			lock.unlock();
		});
		t2.start();
		Scanner scanner=new Scanner(System.in);
		scanner.nextLine();
	}
	
	public static void test2(){
	
	}
}
阅读更多
发表更新Java7 分钟读完 (大约1017个字)

Java 对象深入探究

这篇博客是为了深入探究 Java 中对象的知识。

对象的创建

首先我们先看下一个简单创建对象的代码，看一个对象到底是如何在内存中创建的。

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
        Person obj = new Person();
    }


public class Person {
    private int age=8;
    private String name="fu";

}
阅读更多
发表更新Java6 分钟读完 (大约869个字)

synchronized 锁的升级过程

测试代码

为了更清楚的看 synchronized 的锁的升级的过程，我们用代码来打印对象的布局，使用的类库是：

1
2
3
4
5
6
<dependency>
  <groupId>org.openjdk.jol</groupId>
  <artifactId>jol-core</artifactId>
  <version>0.14</version>
  <scope>provided</scope>
</dependency>
阅读更多
发表更新Java16 分钟读完 (大约2417个字)

synchronized 关键字

Synchronized 是 Java 中的一种锁的方式，是在 JVM 层面一种锁。在 jdk 1.6以前是一种重量级锁，在经历过优化后 Synchronized 锁已经没有那么“重”了。

Synchronized 有 3 种使用方式：

  1. 普通同步方法，锁是当前实例对象
  2. 静态同步方法，锁是当前类的Class对象
  3. 同步代码块，锁是Synchonized括号里配置的对象
阅读更多
发表更新JVM2 分钟读完 (大约268个字)

Big-Edian 存储和 Little-Edian 存储

在 JVM 虚拟机规范中有对 class 字节内容的顺序的一句话，多字节数据项总是按照 Big-Endian 的顺序进行存储,刚开始不太明白，只是根据规范解析了一下，具体的java 代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13

public ClassReadCursor(String filePath, ClassParseInfo classParseInfo) {
	try {
		this.classParseInfo = classParseInfo;
		byte[] bytes = Files.readAllBytes(Paths.get(filePath));
		ByteBuffer byteBuffer = ByteBuffer.wrap(bytes).order(ByteOrder.BIG_ENDIAN);
		this.dataInputStream = new DataInputStream(new ByteArrayInputStream(byteBuffer.array()));
	} catch (IOException e) {
		e.printStackTrace();
	}
	
}

阅读更多
关注我

归档

标签

.Net4
DDD2
DOS1
Docker1
GO1
Guava2
IO4
JVM7
Java52
Kafka4
Linux8
MySQL11
Netty2
Redis7
Spring6
SpringMVC1
Vue1
bash1
docker1
elasticsearch7
github2
go1
jekyll4
js4
linux1
python12
sublime2
tensorflow13
win101
原理12
多线程2
插件1
数据结构1
杂货铺8
架构5
比赛错题2
消息中间件4
爬虫2
算法2
算法-回溯法1
算法-数组4
算法-滑动窗口1
设计模式5

最新文章

分类

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×