赞
踩
从第一次进入力扣,和朋友们琢磨着第一题的两数之和,到现在玩力扣有一个多学期了。虽然没有系统的训练,但还是见识到了一些基础的算法。先把做过的题总结了,然后接下来就捡一些重点算法去打。
方法:暴力,快慢指针
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] ans = new int[2];
for (int i = 0;i < nums.length;++i){
for (int j = i + 1;j < nums.length;++j) {
if(nums[j] == target-nums[i]) {
ans[0] = i;
ans[1] = j;
return ans;
}
}
}
return ans;
}
}
方法:一位一位反转(注意:判断溢出)
class Solution { public int reverse(int x) { int ans = 0; while (x != 0) { // 判断当前值是否溢出 if ((ans * 10) / 10 != ans) { ans = 0; break; } // 反转当前位 ans = ans * 10 + x % 10; x = x / 10; } return ans; } }
方法:反转此数,判断反转前后是否相等
class Solution { public boolean isPalindrome(int x) { if (x < 0){// 负数直接返回false return false; } int ans = 0, m = x; while (m != 0) { // 反转x为ans ans = ans * 10 + m % 10; m = m / 10; } if (x == ans){ return true; }else{ return false; } } }
方法:循环嵌套switch开关,选择对应的转换值
class Solution { public: int romanToInt(string s) { int ans = 0; for (int i = 0;i<s.size();i++) { switch (s[i]){ case 'I': { if (s[i + 1] == 'V') { ans += 4; i++; break; } if (s[i + 1] == 'X') { ans += 9; i++; break; } ans += 1; }break; case 'V':ans += 5; break; case 'X': { if (s[i + 1] == 'L') { ans += 40; i++; break; } if (s[i + 1] == 'C') { ans += 90; i++; break; } ans += 10; }break; case 'L':ans += 50; break; case 'C': { if (s[i + 1] == 'D') { ans += 400; i++; break; } if (s[i + 1] == 'M') { ans += 900; i++; break; } ans += 100; }break; case 'D':ans += 500; break; case 'M':ans += 1000; break; } } return ans; } };
方法:按住第一个串,将其逐个字符与后面的串中对应下标字符比较
注意:当首串当前字符下标与后面某个串的串长相等时,即可不再比较
class Solution { public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) { return ""; } for (int i = 0; i < strs[0].length(); ++i){// 按住第一个串 char c = strs[0].charAt(i); for (int j = 1;j < strs.length; ++j){// 将其与后面的串纵向比较 if (i == strs[j].length() || strs[j].charAt(i) != c){ return strs[0].substring(0, i); } } } return strs[0]; } }
方法:左括号逐个进栈,右括号逐个与栈顶左括号匹配
关键点:
class Solution { public boolean isValid(String s) { Deque<Character> stack = new LinkedList<>(); for (int i = 0; i < s.length(); ++i){ // 若是左括号"(", "[", "{", 入栈 if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){ stack.push(s.charAt(i)); } // 若是右括号")", "]", "}", 判断后出栈 if (s.charAt(i) == ')'){ if (!stack.isEmpty() && stack.peek() == '('){ stack.pop(); }else{ return false; } }else if (s.charAt(i) == ']'){ if (!stack.isEmpty() && stack.peek() == '['){ stack.pop(); }else{ return false; } }else if (s.charAt(i) == '}'){ if (!stack.isEmpty() && stack.peek() == '{'){ stack.pop(); }else{ return false; } } } // 若左括号比右括号多,则不匹配,即栈不为空 return stack.isEmpty(); } }
方法:双指针+哑元
class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode *ehead=new ListNode;//哑节点ehead(头节点) ListNode *e=ehead; while(l1&&l2){ //l1在第一条链移动,l2在第二条链移动 if(l1->val<=l2->val){ e->next=l1; l1=l1->next; }else{ e->next=l2; l2=l2->next; } e=e->next; } e->next = l1 == nullptr ? l2 : l1; //连接后续节点 ehead=ehead->next; //去哑节点 return ehead; } };
方法:快慢指针
关键点:
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size()==0)return 0;
int i=0,j,flag=1;
for(j=i+1;j<=nums.size()-1;++j){//j慢指针,i快指针
if(nums[j]<=nums[i])continue;
else {
nums[++i]=nums[j];
flag++;//有赋值则标记加1
}
}
return flag;
}
};
方法:快慢指针
关键点:
class Solution { public int removeElement(int[] nums, int val) { int i = 0, flag; for (; i<nums.length; ++i){//慢指针遍历数组 if (nums[i] == val) {//如果出现val值,动用快指针 flag=1; for (int j = i; flag==1 && j < nums.length; ++j)//快指针 if (nums[j] != val) {//搜索第一个与val值不同的元素,两者交换 int temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; flag = 0; } if (flag == 1)break;//如果快指针一趟循环后无交换,意味数组已成型 } } return i;//慢指针移动次数=新数组长度 } }
关键点(滑动窗口):
public class Solution {
public int strStr(String haystack, String needle) {
int n = needle.length();
int h = haystack.length();
for (int start = 0; start < h - n + 1; start++) { // 维护长度n的窗口
if (haystack.substring(start, start + n).equals(needle)) {
return start;
}
}
return -1;
}
}
方法:暴力
class Solution {
public int searchInsert(int[] nums, int target) {
for (int i = 0; i < nums.length; ++i){
if (nums[i] < target){
continue;
}else{
return i;
}
}
return nums.length;
}
}
class Solution { public String countAndSay(int n) { // 递归终止条件 if (n == 1) { return "1"; } // 获取到上一层的字符串 String s = countAndSay(n - 1); StringBuilder result = new StringBuilder(); // 记录每个数字的开始索引 int start = 0; for (int i = 1; i < s.length(); i++) { // 当数字发生改变时执行 if (s.charAt(i) != s.charAt(start)) { result.append(i - start).append(s.charAt(start)); start = i; } } // 字符串最后一个数字 result.append(s.length() - start).append(s.charAt(start)); return result.toString(); } }
关键点(动态规划):
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0, maxAns = nums[0];
for (int x : nums) {
pre = Math.max(pre + x, x);// pre维护一个滑窗的子序和(正整数)
maxAns = Math.max(maxAns, pre);// 挑选pre滑过的子序和中最大的一个
}
return maxAns;
}
}
方法:暴力
class Solution {
public int lengthOfLastWord(String s) {
int count = 0;
s = s.toLowerCase();
for (int i = s.length() - 1; i >= 0; --i){
if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z'){// 计算字母数量
count++;
}else if (count > 0){// 从第一个不属于最后一个单词的字母的字符截断
break;
}
}
return count;
}
}
关键点(暴力):
class Solution {
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
digits[i]++;// 加一或进位
digits[i] = digits[i] % 10;// 保证数组元素为单位数
if (digits[i] != 0) return digits;// 无进位,返回
}
digits = new int[digits.length + 1];// 循环结束证明溢出,构建新数组
digits[0] = 1;
return digits;
}
}
关键点(动态规划):方程 F(n)= F(n - 1)- F(n - 2)
class Solution {
public int climbStairs(int n) {
int p = 0, q = 0, r = 1;
for (int i=0; i<n; ++i){// 滚动数组
p = q;// 记录n-2的状态
q = r;// 记录n-1的状态
r = p + q;// 动态规划方程:f(n)=f(n-1)+f(n-2)
}
return r;
}
}
关键点(双指针):
class Solution { public boolean isSymmetric(TreeNode root) { return check(root, root); } public boolean check(TreeNode p, TreeNode q) { // 如果传来的两个节点都为空,则两个父节点都没有这个对称位上的子节点,对称 if (p == null && q == null) { return true; } // 如果只有一个节点为空,则两个父节点中只有一个存在此子节点,则不对称 if (p == null || q == null) { return false; } // 如果都不为空,则将比较当前节点值val得出的结果与下一次递归返回结果做&& return p.val == q.val && check(p.left, q.right) && check(p.right, q.left); } }
关键点:
在计算二叉树的算法基础上加判断:两个子树的高度绝对值是否满足题目定义。
class Solution { public boolean isBalanced(TreeNode root) { return hightree(root) != -1; } public static int hightree(TreeNode root) { int H, H1, H2; if (root == null){ H = 0; } else { H1 = hightree(root.left); H2 = hightree(root.right); if (H1 == -1 || H2 == -1){// 两个子树都不满足,直接返回 return -1; } if (Math.abs(H1 - H2) > 1){// 用高度平衡二叉树的定义作判断 return -1; } H = (H1 > H2 ? H1 : H2) + 1; } return H; } }
关键点:
class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> answers = new ArrayList<List<Integer>>(); for (int i = 0; i < numRows; ++i){ List<Integer> answer = new ArrayList<>(); for (int j = 0; j <= i; ++j){ if (j == 0 || j == i){ answer.add(1); }else{ answer.add(answers.get(i - 1).get(j - 1) + answers.get(i - 1).get(j)); } } answers.add(answer); //answer.clear(); } return answers; } }
关键点:Set中不能添加重复元素
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
for (int x : nums){
if (!set.add(x)){
return true;
}
}
return false;
}
}
关键点(滑动窗口):
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<Integer>();
for(int i = 0; i < nums.length; ++i) {
if (set.contains(nums[i])) {
return true;
}
set.add(nums[i]);// 前进右窗口
if (set.size() > k) {
set.remove(nums[i - k]);// 前进左窗口
}
}
return false;
}
}
关键点(双指针):
class Solution {
public void moveZeroes(int[] nums) {
int a = 0, b = 0;// 慢指针a,快指针b
while (b < nums.length) {
if (nums[b] == 0){// 快指针b遇到0就跳
b++;
continue;
}
nums[a++] = nums[b++];// a、b完成一次赋值就跳
}
while (a < b) { // 填补尾部的0
nums[a++] = 0;
}
}
}
(略)
int fib(int N){
if(N==0)return 0;
if(N==1)return 1;
return fib(N-1)+fib(N-2);
}
关键点(滑动窗口):
class Solution { public double findMaxAverage(int[] nums, int k) { double sum = 0, maxAvg = 0; for (int i = 0; i < nums.length; ++i) { sum += nums[i];// 前进右窗口 if (i == k - 1){ maxAvg = sum / k; } if (i >= k){ sum -= nums[i - k];// 前进左窗口 maxAvg = Math.max(sum / k, maxAvg);// 求最大平均数 } } return maxAvg; } }
方法:排序、按顺序找符合条件的三角形,其周长即为数组内最大
class Solution {
public int largestPerimeter(int[] A) {
Arrays.sort(A);// 从大到小排序
for (int i = A.length - 1; i >= 2; --i) {
if (A[i - 2] + A[i - 1] > A[i]) { // 用三角形定义逐个判断
return A[i - 2] + A[i - 1] + A[i];
}
}
return 0;
}
}
方法:动态规划
int tribonacci(int n) {
if (n < 3)return n==0?0:1;
int x=0, y=1, z=1, tep;
for(int i=0;i<n-2;++i){
tep=x+y+z;
x=y;
y=z;
z=tep;
}
return z;
}
关键点:双指针,尾插,补零相加
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode head = null,tail = null; // 初始化返回链头尾为null int carry = 0; // 初始化进位符 while (l1 != null || l2 != null){ int s1 = l1 == null ? 0 : l1.val; // 两个链表都为null时停止 int s2 = l2 == null ? 0 : l2.val; // 只有一条链为null则将另外一条链对应位补零 int sum = s1 + s2 + carry; // 计算当前和 if (head == null){ // 分配头尾节点的空间 head = tail = new ListNode(sum % 10); }else{ // 尾插链节点,tail永远指向最后的节点 tail.next = new ListNode(sum % 10); tail = tail.next; } carry = sum / 10; // 计算进位 // 前进链1指针 if (l1 != null){ l1 = l1.next; } // 前进链2指针 if (l2 != null){ l2 = l2.next; } } // 溢出则补齐最高 if (carry > 0){ tail.next = new ListNode(1); } return head; // 返回链头 } }
关键点(滑动窗口):
class Solution { public int lengthOfLongestSubstring(String s) { // HashSet,不可加入重复的元素 Set<Character> occ = new HashSet<Character>(); int n = s.length(); int rk = -1, ans = 0; for (int i = 0; i < n; ++i) { if (i != 0) { // 左窗口向右移除一个字符,跳过下面while继续进行for,直至窗口刚好不包含当前重复元素 occ.remove(s.charAt(i - 1)); } // 判断rk+1是否大于n,以及HashSet中是否存在字符串rk+1处的字符 while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) { // 加入HashSet,前进右窗口 occ.add(s.charAt(rk + 1)); ++rk; } // 第 i 到 rk 个字符是一个极长的无重复字符子串,从这些极长的子串中Max一个最长子串 ans = Math.max(ans, rk - i + 1); } return ans; } }
关键点(动态规划):
class Solution { public static String longestPalindrome(String s) { if (s.length() <= 1)return s; // 若串长小于等于1,返回原串 boolean[][] dp = new boolean[s.length()][s.length()]; String ans = ""; for (int i = 0;i < s.length();++i){// 初始化dp数组对角线 dp[i][i] = true; } ans = s.substring(1, 2);// 假设接下来没有找到回文子串,则返回此处初始化为首字符的ans for (int j = 1;j < s.length();++j){// 填表,列从左往右 for (int i = 0;i < j;++i){// 行从上往下 if (j == i + 1){// 对于长度为2的串,判断其是否为回文串 dp[i][j] = s.charAt(i)==s.charAt(j); }else{// 对于其他串,结合dp表以及当前两个端点元素是否相等进行判断 dp[i][j] = (s.charAt(i)==s.charAt(j) && dp[i + 1][j - 1]); } // 获取更大的回文子串 if (dp[i][j] && j - i + 1 > ans.length()){ ans = s.substring(i, j + 1); } } } return ans; } }
关键点:找规律( 详情见 Z字形变换(LeetCode第6题))
class Solution { public: string convert(string s, int numRows) { if (numRows == 1)return s; string ans(""); int down = 2 * numRows - 4, up = 2; //设置up、down的初值 for (int i = 0; i < numRows; i++) { int k = i,flag = 1; //第一行和最后一行的循环 if (i == 0 || i == numRows - 1) { while (k < s.size()) { ans+=s[k]; k = k + 2*numRows-2; } continue; } //中间行(第一行和最后一行之间的行)的循环 else while (k < s.size()) { ans += s[k]; flag++ % 2 == 1 ? k = k+down : k = k+up; //用flag判断每次循环读取需跳跃的值 } down -= 2; up += 2; //每结束一次中间行的循环up和down要变一次 } return ans; } };
方法:有限状态机(不是很会,抄的题解,知道有这回事)
class Solution { public int myAtoi(String str) { Automaton automaton = new Automaton(); int length = str.length(); for (int i = 0; i < length; ++i) { automaton.get(str.charAt(i)); } return (int) (automaton.sign * automaton.ans); } } class Automaton { public int sign = 1; public long ans = 0; private String state = "start"; private Map<String, String[]> table = new HashMap<String, String[]>() {{ put("start", new String[]{"start", "signed", "in_number", "end"}); put("signed", new String[]{"end", "end", "in_number", "end"}); put("in_number", new String[]{"end", "end", "in_number", "end"}); put("end", new String[]{"end", "end", "end", "end"}); }}; public void get(char c) { state = table.get(state)[get_col(c)]; if ("in_number".equals(state)) { ans = ans * 10 + c - '0'; ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE); } else if ("signed".equals(state)) { sign = c == '+' ? 1 : -1; } } private int get_col(char c) { if (c == ' ') { return 0; } if (c == '+' || c == '-') { return 1; } if (Character.isDigit(c)) { return 2; } return 3; } }
关键点(dfs+状态重置):
class Solution { public List<String> letterCombinations(String digits) { List<String> answers = new ArrayList<String>(); if (digits.length() == 0) { return answers; } // 初始化Map为号码与字母串的映射 Map<Character, String> phoneMap = new HashMap<Character, String>() {{ put('2', "abc"); put('3', "def"); put('4', "ghi"); put('5', "jkl"); put('6', "mno"); put('7', "pqrs"); put('8', "tuv"); put('9', "wxyz"); }}; dfs(answers, phoneMap, digits, 0, new StringBuffer()); return answers; } public void dfs(List<String> answers, Map<Character, String> phoneMap, String digits, int deepth, StringBuffer path) { if (deepth == digits.length()) { answers.add(path.toString()); } else { char digit = digits.charAt(deepth);// 获取此层号码 String letters = phoneMap.get(digit);// 获取此号码映射的字母串 for (int i = 0; i < letters.length(); i++) { // 按号码映射的字母串的顺序将字母加入路径(入栈) path.append(letters.charAt(i)); // dfs搜索下一层 dfs(answers, phoneMap, digits, deepth + 1, path); // 状态重置(出栈) path.deleteCharAt(deepth); } } } }
关键点(dfs):状态变量,状态重置,以栈的形式使用Deque(java)
class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res=new ArrayList<>(); if (nums.length==0){ return res; } //状态变量path(栈),used[],deepth Deque<Integer> path=new ArrayDeque<>(); boolean[] used=new boolean[nums.length]; int deepth=0; dfs(nums,res,path,used,deepth); return res; } private void dfs(int[] nums,List<List<Integer>> res,Deque<Integer> path,boolean[] used,int deepth) { if(deepth==nums.length){//“剪枝” res.add(new ArrayList<>(path)); return; } for(int i=0;i<nums.length;++i){ if(used[i]==true){ continue; } path.addLast(nums[i]); used[i]=true; dfs(nums,res,path,used,deepth+1); path.removeLast();//状态重置 used[i]=false; } } }
关键点(动态规划):
class Solution { public int uniquePaths(int m, int n) { int[][] dp=new int[m][n]; for(int i=0;i<m;++i){//首行 dp[i][0]=1; } for(int i=0;i<n;++i){//首列 dp[0][i]=1; } for(int i=1;i<m;++i){//填表 for(int j=1;j<n;++j){ dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } return dp[m-1][n-1]; } }
关键点:行列标记数组,先标记再替换
class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; boolean[] row = new boolean[m]; boolean[] col = new boolean[n]; for (int i = 0; i < m; i++) {// 标记 for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { row[i] = col[j] = true; } } } for (int i = 0; i < m; i++) {// 替换 for (int j = 0; j < n; j++) { if (row[i] || col[j]) { matrix[i][j] = 0; } } } } }
(数据结构基础)
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> answer=new ArrayList();
if(root==null)return answer;
PT(answer,root);
return answer;
}
public void PT(List<Integer> answer,TreeNode root){
if(root.left!=null)PT(answer,root.left);
answer.add(root.val);
if(root.right!=null)PT(answer,root.right);
}
}
关键点(dfs):
class Solution { public void solve(char[][] board) { if (board == null || board.length == 0) return; int m = board.length; int n = board[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 从边缘o开始搜索 boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1; if (isEdge && board[i][j] == 'O') { dfs(board, i, j); } } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == 'O') {// 将被围绕的O填充 board[i][j] = 'X'; } if (board[i][j] == '#') {// 将边界的O还原 board[i][j] = 'O'; } } } } public void dfs(char[][] board, int i, int j) { if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') { // board[i][j] == '#' 说明已经搜索过了. return; } board[i][j] = '#'; dfs(board, i - 1, j); // 上 dfs(board, i + 1, j); // 下 dfs(board, i, j - 1); // 左 dfs(board, i, j + 1); // 右 } }
(数据结构基础)
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> answer=new ArrayList();
if(root==null)return answer;
PT(answer,root);
return answer;
}
public void PT(List<Integer> answer,TreeNode root){
answer.add(root.val);
if(root.left!=null)PT(answer,root.left);
if(root.right!=null)PT(answer,root.right);
}
}
(数据结构基础)
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> answer=new ArrayList();
if(root==null)return answer;
PT(answer,root);
return answer;
}
public void PT(List<Integer> answer,TreeNode root){
if(root.left!=null)PT(answer,root.left);
if(root.right!=null)PT(answer,root.right);
answer.add(root.val);
}
}
关键点(动态规划):
class Solution {
public int rob(int[] nums) {
if(nums.length==0)return 0;
if(nums.length==1)return nums[0];
if(nums.length==2)return Math.max(nums[0],nums[1]);
int[] dp=new int[nums.length];
dp[0]=nums[0];// 只有一个房子
dp[1]=Math.max(nums[0],nums[1]);// 只有两个房子
for(int i=2;i<nums.length;++i){
dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[nums.length-1];
}
}
思路:
class Solution { public int numIslands(char[][] grid) { int num_Islands=0; for(int i=0;i<grid.length;++i){ for(int j=0;j<grid[0].length;++j){ if(grid[i][j]=='1'){// 遇到1 ++num_Islands; dfs(grid,i,j); } } } return num_Islands; } public void dfs(char[][] grid,int i,int j){ if(i<0||j<0||i>grid.length-1||j>grid[0].length-1||grid[i][j]=='0'){ return;// 越界则返回 } grid[i][j]='0';// 替换0 dfs(grid,i-1,j);// 上 dfs(grid,i+1,j);// 下 dfs(grid,i,j-1);// 左 dfs(grid,i,j+1);// 右 } }
关键点(栈):
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { Deque<Integer> s1=new ArrayDeque<>(); while (l1 != null) {// 入栈 s1.addLast(l1.val); l1 = l1.next; } Deque<Integer> s2 = new ArrayDeque<>(); while (l2 != null) {// 入栈 s2.addLast(l2.val); l2 = l2.next; } ListNode answer = new ListNode(0); int carry = 0; while (!s1.isEmpty() || !s2.isEmpty()) { int sum = (s1.isEmpty() ? 0 : s1.removeLast())+(s2.isEmpty() ? 0 : s2.removeLast()) + carry;// 出栈 ListNode newnode = new ListNode(sum % 10); newnode.next = answer.next;// 头插 answer.next = newnode; if (sum >= 10){ carry = sum/10; }else{ carry = 0; } } if (carry != 0) {// 若还有进位 ListNode newnode = new ListNode(1); newnode.next = answer.next; answer.next = newnode; } return answer.next; } }
关键点(动态规划):
class Solution { public boolean PredictTheWinner(int[] nums) { int[][] dp=new int[nums.length][nums.length]; for(int i=0;i<nums.length;++i){ dp[i][i]=nums[i];//初始化dp表的对角线 } for(int i=nums.length-2;i>=0;--i){ for(int j=i+1;j<=nums.length-1;++j){ dp[i][j]=Math.max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1]); //填表,计算所有子问题的净胜分 } } return dp[0][nums.length-1]>=0;//得出结果(最终净胜分是否大于等于0) } } /*优化前的暴力解法,递归中含有重复子问题 public boolean PredictTheWinner(int[] nums) { return Thinking(nums,0,nums.length-1)>=0; } public int Thinking(int[] nums,int start,int end) { if(start==end){ return nums[start]; } int choseleft=nums[start]-Thinking(nums,start+1,end);//选左的净胜分 int choseright=nums[end]-Thinking(nums,start,end-1);//选右的净胜分 return Math.max(choseleft,choseright);//返回一个高的净胜分 } */
(暴力,单调栈为更优解)
//暴力 class Solution { public int[] nextGreaterElements(int[] nums) { int[] ans=new int[nums.length];//用nums初始化新数组ans for(int n=0;n<nums.length;++n){ int count=0; for(int i=(n+1)%nums.length;i<nums.length;i=(i+1)%nums.length){ if(++count>=nums.length){//找不到 ans[n]=-1; break; } if(nums[n]<nums[i]){//找到 ans[n]=nums[i]; break; } } } return ans; } }
关键点(滑动窗口):
class Solution { public boolean checkInclusion(String s1, String s2) { if (s1.length() > s2.length()) return false; //因为字符串都是a-z的字母,所以我们可以使用一个长度为26的int数组来存储每个字母出现的个数 int[] s1map = new int[26]; int[] s2map = new int[26]; for (int i = 0; i < s1.length(); i++) { //这里char类型加减使用Ascii码,-'a'正好对应a-z在数组中的索引,值为该字母出现的次数 s1map[s1.charAt(i) - 'a']++; s2map[s2.charAt(i) - 'a']++; } //滑动窗口 //窗口大小为s1.length,索引从[0 —— s1.length-1]到[s2.length-s1.length —— s2.length-1] for (int i = 0; i < s2.length() - s1.length(); i++) { //如果匹配,直接返回 if (isMatch(s1map, s2map)) { return true; } //如果不匹配,窗口向后移动一位 //窗口加入下一个字母 s2map[s2.charAt(i + s1.length()) - 'a']++; //窗口移除第一个字母 s2map[s2.charAt(i) - 'a']--; } //最后比较i = s2.length-s1.length的情况 return isMatch(s1map,s2map); } /** * 这里两个数组的长度都为26 * @param charArray1 * @param charArray2 * @return */ private static boolean isMatch(int[] charArray1,int[] charArray2 ){ for (int i = 0; i < charArray1.length; i++) { //这里只要出现一个字母个数不一样,就直接返回false if (charArray1[i] != charArray2[i]) { return false; } } return true; } }
(预测赢家的同类题,此处可用数学解,略)
class Solution {
public boolean stoneGame(int[] piles) {
return true;
}
}
//dp法见 486.预测赢家
认识了很多算法,像动态规划、滑动窗口、Dfs、回溯、双指针…认识了很多数据结构,像Java的Set、Deque、ArrayList、LinkedList…
我身边有很多人,参加过很多竞赛,获得过很多荣誉。有人问过我说:他们各方面都比你优秀,努力程度也不比你差,为啥还要努力?我说,有意义的是过程,结果是大家都看得到的,只有过程是真正属于自己的,即使未来不青睐我,我也要继续,因为:
“强大者应持谦卑之心不可因力量而跋扈,
弱小者应持上进之心不可因不敌而麻木。”
继续打题、继续前进…
(未完待续)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。