513. 找树左下角的值 (BFS)
题目本身不难，第一次使用java的队列，Queue这个接口，可以由LinkedList来实现。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/class Solution {public int findBottomLeftValue(TreeNode root) {Queue<TreeNode> treeNodeQueue=new LinkedList<>();treeNodeQueue.offer(root);int left=root.val;while(!treeNodeQueue.isEmpty()){int size = treeNodeQueue.size();for(int i=0;i<size;i++){TreeNode treeNode = treeNodeQueue.poll();System.out.println(treeNode.val);if(treeNode.left!=null)treeNodeQueue.offer(treeNode.left);if(treeNode.right!=null)treeNodeQueue.offer(treeNode.right);if(i==0) {left = treeNode.val;}}}return left;}}
Queue的一些方法 offer，add 区别： 一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。 这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。 poll，remove 区别： remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似， 但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。 peek，element区别： element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。
522. 最长特殊序列 Ⅱ （LCS）
简单枚举
class Solution {
public boolean isSubString(String s1,String s2){
int index = 0;
if(s1.length()> s2.length())return false;
for(int i=0;i<s1.length();i++){
int temp =s2.substring(index).indexOf(s1.charAt(i));
if(temp==-1)return false;
else{
index+=temp+1;
if(index>s2.length())return false;
}
}
return true;
}
public int findLUSlength(String[] strs) {
int length = strs.length;
int max=-1;
for(int i=0;i<length;i++){
boolean flag = true;
for(int j=0;j<length;j++){
if(i!=j){
if(isSubString(strs[i],strs[j])){
flag=false;
break;
}
}
}
if(flag){
max=max<strs[i].length()?strs[i].length():max;
}
}
return max;
}
}
其他：1143. 最长公共子序列
532. 数组中的 k-diff 数对
原题链接：https://leetcode.cn/problems/k-diff-pairs-in-an-array/
双指针
主要的思路是排序，如果k==0，统计所有次数出现超过1的数字的个数；如果k!=0，将列表去重，采用双指针，找是否有 k-diff数对
public int findPairs(int[] nums, int k) {
int cnt = 0;
if(k==0){
HashMap<Integer,Integer> temp = new HashMap<>();
for(int i:nums){
if(temp.containsKey(i)){
temp.put(i,temp.get(i)+1);
}else{
temp.put(i,0);
}
}
for (Integer value : temp.values()) {
if(value>0)cnt++;
}
}
else{
if (nums.length == 1) return 0;
Arrays.sort(nums);
List<Integer> lst = new ArrayList<>();
for(int i:nums){
if(lst.isEmpty()||lst.get(lst.size()-1)!=i)lst.add(i);
}
int size = lst.size();
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
if(lst.get(j)-lst.get(i)>k)break;
if(lst.get(j) - lst.get(i) == k){
cnt++;
break;
}
}
}
// TreeSet<Integer> set = new TreeSet<>();
// for (int i : nums) {
// set.add(i);
// }
// List<Integer> lst = new ArrayList<>(set);
// int size = lst.size();
// for (int i = 0; i < size; i++) {
// for (int j = i + 1; j < size; j++) {
// if(lst.get(j)-lst.get(i)>k)break;
// if(lst.get(j) - lst.get(i) == k){
// cnt++;
// break;
// }
// }
// }
}
return cnt;
}
哈希表
参考 宫水三叶
public int findPairs(int[] nums, int k) {
int cnt=0;
Map<Integer,Integer> map = new HashMap<>();
for(int i:nums)map.put(i,map.getOrDefault(i,0)+1);
for(int i:nums){
if(map.get(i)==0)continue; // 防止计算过的数再次统计
if(k==0){
if(map.get(i)>1)cnt++; // 出现过一次以上
}else{
int a = i-k,b=i+k; // b-i=k 或者i-a=k
if(map.getOrDefault(a,0)>0)cnt++;
if(map.getOrDefault(b,0)>0)cnt++;
}
map.put(i,0);
}
return cnt;
}
这个代码就漂亮多了。。
小记：
- Arrays.sort() 用来排序 类似int[]的数组，不过如果是基本类型，只能使用默认的升序，如果像自定义排序，比如使用 Arrays.sort(nums,new Comparator
(){}); 必须将nums转化为Integer[] 类型，如果使用for循环来转换有点费劲。可以使用java8之后的stream操作，其他一些转换见链接https://blog.csdn.net/zx000003/article/details/82691578?spm=1001.2014.3001.5502 https://www.runoob.com/java/java8-streams.html List<Integer> temp = Arrays._stream_(new int[]{1, 3, 1, 3, 5, 4}).boxed().collect(Collectors._toList_());
- 注意
map.getOrDefault(key,defaultValue)的用法，如果key不存在，返回defaultValue
890. 查找和替换模式
原题链接:
https://leetcode.cn/problems/find-and-replace-pattern/
哈希映射
主要思路就是做个哈希映射,但是一开始写的有点蠢
class Solution {
public String getNewPattern(String words){
String newPattern = "";
HashMap<Character, Character> temp_map = new HashMap<>();
int cnt=65;
for(int i=0;i<words.length();i++){
char temp_c = words.charAt(i);
if(temp_map.containsKey(temp_c)){
newPattern+=temp_map.get(temp_c);
}
else{
temp_map.put(temp_c,(char)cnt);
newPattern+=((char)cnt);
cnt++;
}
}
return newPattern;
}
public List<String> findAndReplacePattern(String[] words, String pattern) {
List<String> res = new ArrayList<>();
String row_pattern = getNewPattern(pattern);
for(int i=0;i<words.length;i++){
if(getNewPattern(words[i]).equals(row_pattern)){
res.add(words[i]);
}
}
return res;
}
}
这便每次都要做完整的一个映射,效率较低,可以只用两个大小为26的int数组 分别存pattern和word的映射值
途中有不同的 就可以break 比较下一个,提高效率,改进后:
public List<String> findAndReplacePattern(String[] words, String pattern) {
List<String> res = new ArrayList<>();
for(String word:words){
int[] p = new int[26];
int[] q = new int[26];
boolean flag=true;
for(int i=0;i<pattern.length();i++){
if(p[word.charAt(i)-'a']!=q[pattern.charAt(i)-'a']){
flag=false;
break;
}else{
p[word.charAt(i)-'a']=q[pattern.charAt(i)-'a']=i+1;
}
}
if(flag)res.add(word);
}
return res;
}
926. 将字符串翻转到单调递增
动态规划解法
思路：
相当于是找一个转折点，该转折点，使得该字符串为单调递增的。
令 dp[i][j]表示长度为i，第i个字符是j的最小变换次数，可得：
i从0开始，初始dp[0][0]=dp[0][1]=0。该式子表示
对于一个字符串，假设已知最小反转次数，则加1 个字符，也可以得到新的最小反转次数，所以可以使用动态规划，从头开始添加字符，并每次保存最后一个字符为0和1状态下的最小反转次数，添加字符后：
。。。。。。。。。。
代码：
这里每次 只涉及上一轮的状态，可以只用两个变量即可
class Solution {
public int minFlipsMonoIncr(String s) {
int size = s.length();
int dp0=0;
int dp1=0;
for(int i=0;i<size;i++){
char c = s.charAt(i);
dp1=Math.min(dp1,dp0)+(c=='0'?1:0);
dp0=dp0+(c=='1'?1:0);
}
return Math.min(dp0,dp1);
}
}
若有收获，就点个赞吧
0 人点赞
