1. 单链表反转
// 迭代版
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
// 递归版
public ListNode reverseList(ListNode head) {
ListNode newHead;
if(head == null || head.next == null){
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
2. 二进制中1的个数
public int count(int n){
int num = 0;
while(n != 0){
n = n & (n-1);
num++;
}
return num;
}
3. 最长上升子序列(LIS)
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if(len == 0){
return 0;
}
int[] dp = new int[len];
for(int i=0;i<len;i++){
dp[i] = 1;
}
int ret = dp[0];
for(int i=1;i<len;i++){
for(int j=0;j<i;j++){
if(nums[j]<nums[i]){
dp[i] = Math.max(dp[j]+1,dp[i]);
}
}
ret = Math.max(dp[i],ret);
}
return ret;
}
}
4. 最大连续子序和(MSA)
class Solution {
public int maxSubArray(int[] nums) {
/*
int res = nums[0];
int sum = 0;
for (int num : nums) {
if (sum > 0)
sum += num;
else
sum = num;
res = Math.max(res, sum);
}
return res;
*/
int dp[]=new int[nums.length];
dp[0]=nums[0];
int res = nums[0];
for(int i=1;i<nums.length;i++){
dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
if(res < dp[i])
res = dp[i];
}
return res;
}
}
5. 最长回文子串(LPS)
class Solution {
public String longestPalindrome(String s) {
char[] chars = s.toCharArray();
int length = chars.length;
if(length==0||length==1){
return s;
}
boolean[][] lps = new boolean[length][length];
int maxLen = 1;
int start = 0;
for (int i=0; i<length;i++) {
for (int j=i; j>=0;j--) {
if (i-j<2) {
lps[j][i] = chars[i] == chars[j];
} else {
lps[j][i] = lps[j+1][i-1] && (chars[i] == chars[j]);
}
if (lps[j][i] && (i-j+1)>maxLen) {
maxLen = i - j + 1;
start = j;
}
}
}
return s.substring(start,start+maxLen);
}
}
6. 数组前K个最小数
public class Solution {
public ArrayList<Integer> getTopK(int [] input, int k) {
ArrayList<Integer> ret = new ArrayList<>();
int len = input.length;
if (k<=0 || k>len) {
return ret;
}
int low = 0;
int high = len-1;
int index = partion(input,low,high);
while(index != k-1){
if(index > k-1){
high = index-1;
index = partion(input,low,high);
}else{
low = index+1;
index = partion(input,low,high);
}
}
for(int i=0;i<k;i++){
ret.add(input[i]);
}
return ret;
}
public int partion(int[] arr,int low,int high){
int key = arr[low];
while(low < high){
while(low<high && arr[high]>=key){
high--;
}
arr[low] = arr[high];
while(low<high && arr[low]<=key){
low++;
}
arr[high] = arr[low];
}
arr[low] = key;
return low;
}
}