231. 2的幂
暴力法，时间复杂度O(logn):
class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0) {
return false;
}
while (n % 2 == 0) {
n /= 2;
}
return n == 1;
}
}
2的幂一共只可能有31个数，逐个判断即可，时间复杂度O1:
class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0) {
return false;
}
int x = 1;
for (int i = 1; i <= 31; i++) {
if (x == n) {
return true;
}
x <<= 1;
}
return false;
}
}
位运算，n 二进制最高位为 1，其余所有位为 0。n - 1二进制最高位为 0，其余所有位为 1，只要n & (n-1) ==0 就是2的幂。
时间复杂度O1:
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}
232. 用栈实现队列
class MyQueue {
Deque<Integer> stack1, stack2;
/**
* Initialize your data structure here.
*/
public MyQueue() {
stack1 = new ArrayDeque<>();
stack2 = new ArrayDeque<>();
}
/**
* Push element x to the back of queue.
*/
public void push(int x) {
while (!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
stack1.push(x);
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
/**
* Removes the element from in front of queue and returns that element.
*/
public int pop() {
return stack2.pop();
}
/**
* Get the front element.
*/
public int peek() {
return stack2.peek();
}
/**
* Returns whether the queue is empty.
*/
public boolean empty() {
return stack2.isEmpty();
}
}
233. 数字 1 的个数
234. 回文链表
借助数组很容易判断，时间复杂度On,空间复杂度On:
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> list = new ArrayList<>();
while (head != null) {
list.add(head.val);
head = head.next;
}
int i = 0, j = list.size() - 1;
while (i < j) {
if (list.get(i).equals(list.get(j))) {
i++;
j--;
} else {
return false;
}
}
return true;
}
}
使用快慢指针，时间复杂度On,空间复杂度O1：
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode head2 = slow.next;
slow.next = null;
ListNode dummyHead2 = new ListNode(0);
while (head2 != null) {
ListNode temp = head2.next;
head2.next = dummyHead2.next;
dummyHead2.next = head2;
head2 = temp;
}
head2 = dummyHead2.next;
while (head != null && head2 != null) {
if (head.val != head2.val) {
return false;
}
head = head.next;
head2 = head2.next;
}
return true;
}
}
235. 二叉搜索树的最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (true) {
if (p.val < root.val && q.val < root.val) {
root = root.left;
} else if (p.val > root.val && q.val > root.val) {
root = root.right;
} else {
break;
}
}
return root;
}
}
236. 二叉树的最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null) {
return right;
} else if (right == null) {
return left;
} else {
return root;
}
}
}
237. 删除链表中的节点
class Solution {
public void deleteNode(ListNode node) {
ListNode pre = node;
while (node.next != null) {
node.val = node.next.val;
pre = node;
node = node.next;
}
pre.next = null;
}
}
238. 除自身以外数组的乘积
先计算前缀积和后缀积，再遍历每个数的时候直接调用结果。
时间复杂度On,空间复杂度On。
class Solution {
public int[] productExceptSelf(int[] nums) {
int len = nums.length;
int[] pre = new int[len], post = new int[len];
pre[0] = nums[0];
for (int i = 1; i < len; i++) {
pre[i] = pre[i - 1] * nums[i];
}
post[len - 1] = nums[len - 1];
for (int i = len - 2; i >= 0; i--) {
post[i] = post[i + 1] * nums[i];
}
int[] res = new int[len];
for (int i = 0; i < len; i++) {
res[i] = (i - 1 >= 0 ? pre[i - 1] : 1) * (i + 1 <= len - 1 ? post[i + 1] : 1);
}
return res;
}
}
239. 滑动窗口最大值
dp，比暴力稍微快一点，时间复杂度On^2 ：
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] dp = new int[nums.length - k + 1];
dp[0] = nums[0];
for (int i = 1; i < k; i++) {
dp[0] = Math.max(dp[0], nums[i]);
}
for (int i = 1; i < dp.length; i++) {
if (nums[i - 1] == dp[i - 1]) {
dp[i] = nums[i];
for (int j = i + 1; j < i + k; j++) {
dp[i] = Math.max(dp[i], nums[j]);
}
} else {
dp[i] = Math.max(dp[i - 1], nums[i + k - 1]);
}
}
return dp;
}
}
240. 搜索二维矩阵 II
每一行使用二分搜索，时间复杂度Onlogn：
class Solution {
public boolean search(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] > target) {
hi--;
} else if (arr[mid] == target) {
return true;
} else if (arr[mid] < target) {
lo++;
}
}
return false;
}
public boolean searchMatrix(int[][] matrix, int target) {
for (int i = 0; i < matrix.length; i++) {
if (search(matrix[i], target)) {
return true;
}
}
return false;
}
}
优化：
从左下角出发，上面的数一定小于它，右边的数一定大于它，不断的往右上角走，如果遇到了target则返回true，如果走到边界了则返回false。
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int row = matrix.length - 1, col = 0;
while (row >= 0 && col < matrix[0].length) {
if (matrix[row][col] > target) {
row--;
} else if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] < target) {
col++;
}
}
return false;
}
}
