367. Valid Perfect Square
Given a positive integer num, write a function which returns True if num is a perfect square else False.
Note: Do not use any built-in library function such as sqrt.
Example 1:
Input: 16
Returns: True
Example 2:
Input: 14
Returns: False
题目： 判断一个正整数num能否开方后得到整数。
思路： 1. 平方数本身可以写成1 + 3 +5 + 7……这样奇数之和，这种算法的复杂度为根号n。 2. 二叉搜索，复杂度为logn。
解法一：
1
2
3
4
5
6
7
8
9
10
class Solution {
public boolean isPerfectSquare(int num) {
int i = 1;
while(num > 0){
num -= i;
i += 2;
}
return num == 0;
}
}
解法二：
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public boolean isPerfectSquare(int num) {
int left = 0, right = num;
while(left <= right){
long mid = (left + right) / 2;
if(mid * mid == num) return true;
else if(mid * mid < num) left = (int)mid + 1;
else if(mid * mid > num) right = (int)mid - 1;
}
return false;
}
}
2. Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
题目： 两个链表形如(2 -> 4 -> 3) + (5 -> 6 -> 4)，计算每个节点相加得到(7 -> 0 -> 8)，类似于实现加法运算。
思路：加法运算。
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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int count = 0;
ListNode res = new ListNode(0);
ListNode ptr = res;
while(l1 != null || l2 != null || count != 0){
int sum = (l1 == null? 0: l1.val) + (l2 == null? 0: l2.val) + count;
count = sum / 10;
ptr.next = new ListNode(sum % 10);
l1 = (l1 == null)? l1: l1.next;
l2 = (l2 == null)? l2: l2.next;
ptr = ptr.next;
}
return res.next;
}
}
198. House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
题目： 一个小偷要抢劫一排店铺，但是他不能抢相邻的两家店，如何抢到最多的钱。输入为一个记录店铺价值的数组，例[2,5,1,3]。
思路： 对每家店只能做抢和不抢两种决策。从n家店铺最后一家店开始抢，如果抢了第n家店，则跳过n-1家店；如果不抢，则抢第n-1家店。在这两种决策中选择收益大的一种，递归搜索，就能找出最优解。在此基础上，我们记录已经计算过的字问题，减少计算的时间复杂度。
- 递归版：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public static int[] result;
public int robmax(int idx, int[] nums){
if(idx < 0){
return 0;
}
if(result[idx] >= 0){ # 被计算过就返回该result
return result[idx];
}
result[idx] = Math.max(nums[idx]+robmax(idx - 2, nums),
robmax(idx - 1, nums));
return result[idx];
}
public int rob(int[] nums) {
result = new int[nums.length];
for(int i = 0; i<nums.length;i++){
result[i] = -1;
}
return robmax(nums.length - 1, nums);
}
}
- 递推版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public static int[] result;
public int rob(int[] nums) {
if(nums.length == 0){
return 0;
}
if(nums.length == 1){
return nums[0];
}
result = new int[nums.length];
result[0] = nums[0];
result[1] = Math.max(nums[0], nums[1]);
for(int i = 2; i <= nums.length - 1; i++){
result[i] = Math.max(nums[i] + result[i - 2], result[i - 1]);
}
return result[nums.length - 1];
}
}
322. Coin Change
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
Note: You may assume that you have an infinite number of each kind of coin.
题目： 对于一个总数amount，和一堆coins，例如11和[1, 2, 5]，从coins里取不同种类的coin使得其总和为amount，求取coin的最小次数。其中每种coin可以重复取。
思路：和01背包问题本质是相同的，是一个物品可以重复取，取了之后每次价值加1，当无法填满背包时返回-1的变种背包问题。因为硬币可以无限重复拿取，因此无需考虑取了哪些硬币，只需要一个一维dp数组就可以存放结果。该问题的子问题，是对于更小的amount的最好取法。
例如，硬币种类为[1, 2]，当amount为3时，可以分成amount=1时的最优解再取一个2元硬币，与amount=2时的最优解再取一个1元硬币，比较这两者，取最小，即为amount=3时的最优解。
实际上这个和跳楼梯问题也是一样的，coins[]数组相当于限制了单次跳楼梯能跳的级数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int coinChange(int[] coins, int amount) {
int[] V = new int[amount + 1];
if(amount == 0){
return 0;
}
for(int j = 1; j < amount + 1; j++ ){
V[j] = Integer.MAX_VALUE;
for(int i = 0; i < coins.length; i++){
if((j >= coins[i]) && (V[j - coins[i]] != Integer.MAX_VALUE)){
V[j] = Math.min(V[j - coins[i]] + 1, V[j]);
}
}
}
int result = V[amount];
if(result == Integer.MAX_VALUE){
return -1;
}
else{
return result;
}
}
}