青蛙跳台阶
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int numWays(int n) {
if(n==0)
return 1;
int[] array=new int[n+1];
array[0]=1;
array[1]=1;
for(int i=2;i<=n;i++)
{
array[i]=array[i-1]+array[i-2];
array[i]%=1000000007;
}
return array[n];
}
}
|
最长上升子序列
很容易想到O(n^2)的解法，可以定义一个数组保存当前位置为止的最长上升子序列
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
| class Solution {
public int lengthOfLIS(int[] nums) {
if(nums.length==0)
return 0;
int[] array=new int[nums.length];
array[0]=1;
for(int i=1;i<nums.length;i++)
{
int max=1;
for(int j=0;j<i;j++)
{
if(nums[i]>nums[j])
{
max=Math.max(max,array[j]+1);
}
}
array[i]=max;
}
int max=0;
for(int i=0;i<array.length;i++)
{
if(max<array[i])
max=array[i];
}
return max;
}
}
|
最长公共子序列
这道题是一道典型的动态规划题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int length1=text1.length();
int length2=text2.length();
int[][] array=new int[length1+1][length2+1];
for(int i=0;i<length1;i++)
{
for(int j=0;j<length2;j++)
{
if(text1.charAt(i)==text2.charAt(j))
{
array[i+1][j+1]=array[i][j]+1;
}
else if(array[i+1][j]>array[i][j+1])
array[i+1][j+1]=array[i+1][j];
else
array[i+1][j+1]=array[i][j+1];
}
}
return array[length1][length2];
}
}
|
编辑距离
看了大佬的解答跪了，还是没有考虑完全，其实跟平常的动态规划题差别
不大，核心就是分析最优情况
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
| class Solution {
public int minDistance(String word1, String word2) {
int m=word1.length();
int n=word2.length();
int[][] cost=new int[m+1][n+1];
for (int i = 0; i <= m; ++i) {
cost[i][0] = i;
}
for (int j = 0; j <= n; ++j) {
cost[0][j] = j;
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (word1.charAt(i-1) == word2.charAt(j-1)) {
cost[i][j] = cost[i-1][j-1];
} else {
cost[i][j] = 1 +
Math.min(cost[i-1][j-1], Math.min(cost[i][j-1],
cost[i-1][j]));
}
}
}
return cost[m][n];
}
}
|
零钱兑换II
这题有点难度，官方题解还没看懂
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int x = coin; x < amount + 1; ++x) {
dp[x] += dp[x - coin];
}
}
return dp[amount];
}
}
|
翻转单词顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public String reverseWords(String s) {
s=s.trim();
String[] array=s.split(" ");
StringBuilder str=new StringBuilder();
for(int i=array.length-1;i>=0;i--)
{
if(array[i].equals(""))
continue;
if(i!=0)
str.append(array[i]+" ");
else
str.append(array[i]);
}
return str.toString();
}
}
|
二进制中1的个数
这个题的n是无符号数，区分正负会有问题，最简明的思路是按位与，还有一种
思路是利用n&(n-1)，n-1的意思是二进制数字n最右边的1变成0，此1右边的0
都变成1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public int hammingWeight(int n) {
int sum=0;
while(n!=0){
sum=sum+(n&1);
n=n>>>1;
}
return sum;
}
public int hammingWeight(int n) {
int sum=0;
while(n!=0){
sum++;
n&=(n-1);
}
return sum;
}
|
颠倒二进制位
这道题的思路不难，我对位运算还是掌握不深，循环32次，每次将右边最后
1位获取保存，同时已经保存的位左移
1
2
3
4
5
6
7
8
9
10
11
| public int reverseBits(int n) {
int res=0;
for(int i=0;i<32;i++)
{
res<<=1;
res=res|(n&1);
n>>>=1;
}
return res;
}
|
复制IP地址
回溯剪枝
两数之和
利用HashMap的特性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> a=new HashMap<>();
for(int i=0;i<nums.length;i++)
{
if(a.containsKey(target-nums[i]))
return new int[]{a.get(target-nums[i]),i};
else
a.put(nums[i],i);
}
return null;
}
}
|
三数之和
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
| class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> a=new ArrayList<>();
if(nums==null)
return a;
if(nums.length<3)
return a;
Arrays.sort(nums);
int start=0;
int end=nums.length-1;
for(int i=0;i<nums.length;i++)
{
if(nums[i]>0)
break;
if(i>0&&nums[i]==nums[i-1])
continue;
start=i+1;
end=nums.length-1;
while(start<end)
{
if(nums[i]+nums[start]+nums[end]==0)
{
ArrayList<Integer> b=new ArrayList<>();
b.add(nums[i]);
b.add(nums[start]);
b.add(nums[end]);
a.add(b);
while(start<end&&nums[start]==nums[start+1])
start++;
while(start<end&&nums[end]==nums[end-1])
end--;
start++;
end--;
}
else if(nums[i]+nums[start]+nums[end]>0)
end--;
else
start++;
}
}
return a;
}
}
|
最接近的三数之和
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
| class Solution {
public int threeSumClosest(int[] nums, int target) {
int ans=nums[0]+nums[1]+nums[2];
Arrays.sort(nums);
boolean flag=false;
for(int i=0;i<nums.length;i++)
{
int start=i+1;
int end=nums.length-1;
if(flag==true)
break;
while(start<end)
{
if(Math.abs(nums[i]+nums[start]+nums[end]-target)<Math.abs(
ans-target))
ans=nums[i]+nums[start]+nums[end];
if(ans==target)
{
flag=true;
break;
}
if(nums[i]+nums[start]+nums[end]>target)
end--;
else
start++;
}
}
return ans;
}
}
|
买卖股票的最佳时机I
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int maxProfit(int[] prices) {
int num=0;
int profit=0;
for(int i=0;i<prices.length-1;i++)
{
num=Math.max(0,num+prices[i+1]-prices[i]);
profit=Math.max(num,profit);
}
return profit;
}
}
|
买股票的最佳时机II
这道题的条件其实很宽松，可以进行多次买卖，所以只关注眼前每次遇到更大
的就买卖，贪心算法
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int maxProfit(int[] prices) {
int sum=0;
for(int i=0;i<prices.length-1;i++)
{
if(prices[i]<prices[i+1])
{
sum=sum+prices[i+1]-prices[i];
}
}
return sum;
}
}
|
买股票的最佳时机III
动态规划
有效的括号
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
| class Solution {
public boolean isValid(String s) {
int length=-1;
ArrayList<Character> list=new ArrayList<>();
for(int i=0;i<s.length();i++)
{
char ch=s.charAt(i);
if(ch=='('||ch=='{'||ch=='[')
{
list.add(ch);
length++;
}
else if(ch==')'||ch=='}'||ch==']')
{
if(length==-1)
return false;
char temp=list.get(length);
if((ch==')'&&temp=='(')||(ch=='}'&&
temp=='{')||(ch==']'&&temp=='['))
{
list.remove(length);
length--;
}
else
return false;
}
}
if(list.size()>0)
return false;
return true;
}
}
|
最长有效括号
动态规划
单词搜索
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
| public class Solution {
private boolean[][] marked;
private int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
private int m;
private int n;
private String word;
private char[][] board;
public boolean exist(char[][] board, String word) {
m = board.length;
if (m == 0) {
return false;
}
n = board[0].length;
marked = new boolean[m][n];
this.word = word;
this.board = board;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(int i, int j, int start) {
if (start == word.length() - 1) {
return board[i][j] == word.charAt(start);
}
if (board[i][j] == word.charAt(start)) {
marked[i][j] = true;
for (int k = 0; k < 4; k++) {
int newX = i + direction[k][0];
int newY = j + direction[k][1];
if (inArea(newX, newY) && !marked[newX][newY]) {
if (dfs(newX, newY, start + 1)) {
return true;
}
}
}
marked[i][j] = false;
}
return false;
}
private boolean inArea(int x, int y) {
return x >= 0 && x < m && y >= 0 && y < n;
}
public static void main(String[] args) {
char[][] board = {{'a', 'b'}};
String word = "ba";
Solution solution = new Solution();
boolean exist = solution.exist(board, word);
System.out.println(exist);
}
}
|
重排链表
快慢指针
验证栈序列
贪心算法
字典序排数
剪绳子I
贪心算法
剪绳子II
贪心算法
最长回文子串
这道题有点难度，容易想到的是中心扩散法，从某个位置向两边进行
扩散，但是要分两种情况，例如aba abba
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
| class Solution {
public String longestPalindrome(String s) {
if(s.length()<2)
return s;
int maxlength=1;
int left=0;
int right=0;
String ss=s.substring(0,1);
for(int i=0;i<s.length()-1;i++)
{
String s1=Stringcut(s,i,i+1);
String s2=Stringcut(s,i,i);
String max=s1.length()>s2.length()?s1:s2;
if(max.length()>maxlength)
{
ss=max;
maxlength=max.length();
}
}
return ss;
}
public String Stringcut(String s,int left,int right)
{
int length=s.length();
int i=left;
int j=right;
while(i>=0&&j<length)
{
if(s.charAt(i)==s.charAt(j))
{
i--;
j++;
}
else
break;
}
return s.substring(i+1,j);
}
}
|
下一个数
位运算
