forked from algorithm020/algorithm020
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathWeek8.java
More file actions
123 lines (112 loc) · 4.86 KB
/
Week8.java
File metadata and controls
123 lines (112 loc) · 4.86 KB
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
package algorithm;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @ClassName Week8
* @Description
* @Author Administrator
* @Date 2021/1/11 9:38
* @Version 1.0
**/
public class Week8 {
/**
* 191. 位1的个数
* 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
*******************************************************************************************************************
* 提示：
* 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
* 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
* 进阶：
* 如果多次调用这个函数，你将如何优化你的算法？
*/
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int bits = 0;
int mask = 1;
for (int i = 0; i < 32; i++) {
if ((n & mask) != 0) {
bits++;
}
mask <<= 1;
}
return bits;
}
public int hammingWeight2(int n) {
int sum = 0;
while (n != 0) {
sum++;
n &= (n - 1);
}
return sum;
}
/**
* 231. 2的幂
* 给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
*/
public boolean isPowerOfTwo(int n) {
if (n == 0)
return false;
while (n % 2 == 0)
n /= 2;
return n == 1;
}
public boolean isPowerOfTwo2(int n) {
if (n == 0) return false;
long x = (long) n;
return (x & (-x)) == x;
}
/**
* 146. LRU 缓存机制
* 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
* 实现 LRUCache 类：
*
* LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
* int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
* void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
* 进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
*/
/**
* 51. N 皇后
* n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
* 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
* 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
* *****************************************************************************************************************
* 输入：n = 4
* 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
* 解释：如上图所示，4 皇后问题存在两个不同的解法。
*/
public List<List<String>> solveNQueens(int n) {
int[] queens = new int[n];
Arrays.fill(queens, -1);
List<List<String>> solutions = new ArrayList<List<String>>();
solve(solutions, queens, n, 0, 0, 0, 0);
return solutions;
}
public void solve(List<List<String>> solutions, int[] queens, int n, int row, int columns, int diagonals1, int diagonals2) {
if (row == n) {
List<String> board = generateBoard(queens, n);
solutions.add(board);
} else {
int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
while (availablePositions != 0) {
int position = availablePositions & (-availablePositions);
availablePositions = availablePositions & (availablePositions - 1);
int column = Integer.bitCount(position - 1);
queens[row] = column;
solve(solutions, queens, n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
queens[row] = -1;
}
}
}
public List<String> generateBoard(int[] queens, int n) {
List<String> board = new ArrayList<String>();
for (int i = 0; i < n; i++) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[queens[i]] = 'Q';
board.add(new String(row));
}
return board;
}
}