Tips about algorithm resolving from Leetcode

Here are some tips and notes about how to resolve algorithm issues listed in LeetCode

Rotation problem

Rotate array

Here is one sample from Leetcode

189. Rotate Array
Given an array, rotate the array to the right by k steps, where k is non-negative.

Follow up:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?
 

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

e.g. if k is bigger then array’s length


Tip 1: To find out the smallest rotate count

class Solution {
    public void rotate(int[] nums, int k) {
    	// sample input 
    	// [1,2]
    	// 3
        k=k%nums.length; //[!!!!!] for 'rotation problem', firstly make sure to get smallest iterate count
        if(nums==null || k>nums.length) return ; //[!!! k>nums.length]
        int[] ori=Arrays.copyOf(nums,nums.length);
        for(int i=0;i<nums.length-k;i++){
            nums[i+k]=ori[i];
        }
        for(int i=0;i<k;i++){
            nums[i]=ori[nums.length-k+i];
        }
    }
}

Here is the runtime result

Find next greater element in Rotate array

首先,计算机的内存都是线性的,没有真正意义上的环形数组,但是我们可以模拟出环形数组的效果,一般是通过 \%% 运算符求模(余数),获得环形特效:

回到 Next Greater Number 的问题,增加了环形属性后,问题的难点在于:这个 Next 的意义不仅仅是当前元素的右边了,有可能出现在当前元素的左边(如上例)。

明确问题,问题就已经解决了一半了。我们可以考虑这样的思路:将原始数组 “翻倍”,就是在后面再接一个原始数组,这样的话,按照之前“比身高”的流程,每个元素不仅可以比较自己右边的元素,而且也可以和左边的元素比较了。

Index Stack vs value Stack

Q: Can anyone please tell me the difference between stack and index stack? I mean which one to use on which problems? A: When you need to use index, use the index. When you only need the value, both works.

So the rule of thumb is, if you only need value, both will work. However, if you need the index, for example, to compute the distance, e.g., how many days before getting a wammer day, or how many days the stock prices get higher, you will need to use the index. In such case, you can store index. Plus, you can store multiple pieces of information, such as a tuple (A[i], i, count)…, just an example.

Binary Search

只要数组有序,就应该想到双指针技巧。

BFS & DFS

BFS 的核心思想应该不难理解的,就是把一些问题抽象成图,从一个点开 始,向四周开始扩散。一般来说,我们写 BFS 算法都是用「队列」这种数 据结构,每次将一个节点周围的所有节点加入队列。 BFS 相对 DFS 的最主要的区别是: BFS 找到的路径一定是最短的,但代价 就是空间复杂度比 DFS 大很多

Use case for BFS

我们先举例一下 BFS 出现的常⻅场景好吧,问题的本质就 是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离,这 个例子听起来很枯燥,但是 BFS 算法问题其实都是在干这个事儿

这个广义的描述可以有各种变体,比如走迷宫,有的格子是围墙不能走,从起点到终点的最短距离是多少?如果这个迷宫带「传送门」可以瞬间传送呢?

再比如说两个单词,要求你通过某些替换,把其中一个变成另一个,每次只能替换一个字符,最少要替换几次?

BFS template

// 计算从起点 start 到终点 target 的最近距离 
int BFS(Node start, Node target) {
	Queue<Node> q; // 核心数据结构 Set<Node> visited; // 避免走回头路
	q.offer(start); // 将起点加入队列 visited.add(start);
	int step = 0; // 记录扩散的步数
	while (q not empty) {
		int sz = q.size();
		/* 将当前队列中的所有节点向四周扩散 */ 
		for (int i = 0; i < sz; i++) {
			Node cur = q.poll();
			/* 划重点:这里判断是否到达终点 */
			if (cur is target)
			    return step;
			/* 将 cur 的相邻节点加入队列 */ 
			for (Node x : cur.adj())
				if (x not in visited) { 
					q.offer(x);
					visited.add(x); 
				}
			/* 划重点:更新步数在这里 */
			step++; 
		}
}

怎么套到 BFS 的框架里呢?首先明确一下起点 start 和终点 target 是什 么,怎么判断到达了终点? 显然起点就是 root 根节点,终点就是最靠近根节点的那个「叶子节点」 嘛,叶子节点就是两个子节点都是 null 的节点:

  int minDepth(TreeNode root) {
  	if (root == null) return 0; 
  	Queue<TreeNode> q = new LinkedList<>(); 
  	q.offer(root);
// root 本身就是一层,depth 初始化为 1
int depth = 1;
while (!q.isEmpty()) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */ 
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
/* 判断是否到达终点 */
if (cur.left == null && cur.right == null)
return depth;
/* 将 cur 的相邻节点加入队列 */ if (cur.left != null)
q.offer(cur.left); if (cur.right != null)
q.offer(cur.right);
}
/* 这里增加步数 */
depth++; }
    return depth;
}

什么 BFS 可以找到最短距离,DFS 不行吗? 首先,你看 BFS 的逻辑, depth 每增加一次,队列中的所有节点都向前迈一步,这保证了第一次到达终点的时候,走的步数是最少的。

形象点说,DFS 是线,BFS 是面;DFS 是单打独斗,BFS 是集体行动。这个应该比较容易理解吧。

既然 BFS 那么好,为啥 DFS 还要存在? BFS 可以找到最短距离,但是空间复杂度高,而 DFS 的空间复杂度较低。 还是拿刚才我们处理二叉树问题的例子,假设给你的这个二叉树是满二叉 树,节点数为 N ,对于DFS算法来说,空间复杂度无非就是递归堆栈,最 坏情况下顶多就是树的高度,也就是 O(logN) 。 但是你想想 BFS 算法,队列中每次都会储存着二叉树一层的节点,这样的 话最坏情况下空间复杂度应该是树的最底层节点的数量,也就是 N/2 ,用 BigO表示的话也就是 O(N) 。 由此观之,BFS 还是有代价的,一般来说在找最短路径的时候使用 BFS, 其他时候还是 DFS 使用得多一些(主要是递归代码好写)。

Dynamic Porgramming

动态规划的一般流程就是三步:暴力的递归解法 -> 带备忘录的 递归解法 -> 迭代的动态规划解法。 就思考流程来说,就分为一下几步:找到状态和选择 -> 明确 dp 数组/函数 的定义 -> 寻找状态之间的关系。

Backpack

遇到背包问题可以说是手到擒来好吧。 无非就是状态 + 选择,也没啥特别之处嘛。

Super Egg Drop

思路分析

对动态规划问题,直接套我们以前多次强调的框架即可:这个问题有什么「状态」,有什么「选择」,然后穷举。

「状态」很明显,就是当前拥有的鸡蛋数 K 和需要测试的楼层数 N 。随 着测试的进行,鸡蛋个数可能减少,楼层的搜索范围会减小,这就是状态的 变化。 「选择」其实就是去选择哪层楼扔鸡蛋。回顾刚才的线性扫描和二分思路, 二分查找每次选择到楼层区间的中间去扔鸡蛋,而线性扫描选择一层层向上 测试。不同的选择会造成状态的转移。 现在明确了「状态」和「选择」,动态规划的基本思路就形成了:肯定是个 二维的 dp 数组或者带有两个状态参数的 dp 函数来表示状态转移;外加 一个 for 循环来遍历所有选择,择最优的选择更新状态:

我们选择在第 i 层楼扔了鸡蛋之后,可能出现两种情况:鸡蛋碎了,鸡蛋 没碎。注意,这时候状态转移就来了: 如果鸡蛋碎了,那么鸡蛋的个数 K 应该减一,搜索的楼层区间应该从 [1..N] 变为 [1..i-1] 共 i-1 层楼; 如果鸡蛋没碎,那么鸡蛋的个数 K 不变,搜索的楼层区间应该从 [1..N] 变为 [i+1..N] 共 N-i 层楼。

Reference

  • https://labuladong.gitbook.io/algo/

2021

How to user fire extinguisher

Summary As you know, staff and your safety is paramount. So what if emergency take place, such as fire in office, how to help yourself and your colleagues by...

Deep dive into Kubernetes Client API

Summary To talk to K8s for getting data, there are few approaches. While K8s’ official Java library is the most widely used one. This blog will look into thi...

Whitelabel Error Page

Summary Whitelabel Error Page is the default error page in Spring Boot web app. It provide a more user-friently error page whenever there are any issues when...

Google maps no photos reviews

Summary I found a weird problem of the app Google Maps of my Oppo Android phone. That’s when you search a place in Google map, say “Central Park”, ideally th...

Debts in a nutshell

A debt security represents a debt owed by the issuer to an investor. Here, the investor acts as a lender to the issuer which may be a government, organisatio...

Back to Top ↑

2020

Debug Stuck IntelliJ

What happened to a debug job hanging in IntelliJ (IDEAS) IDE? You may find when you try to debug a class in Intellij but it stuck there and never proceed, e....

Awesome Kotlin

Difference with Scala Kotlin takes the best of Java and Scala, the response times are similar as working with Java natively, which is a considerable advantag...

JVM热身

此文是作者英文原文的翻译文章,英文原文在:http://todzhang.com/posts/2018-06-10-jvm-warm-up/

Mock in kotlin

Argument Matching & Answers For example, you have mocked DOC with call(arg: Int): Intfunction. You want to return 1 if argument is greater than 5 and -1 ...

Curl

Linux Curl command

AOP

The concept of join points as matched by pointcut expressions is central to AOP, and Spring uses the AspectJ pointcut expression language by default.

Micrometer notes

As a general rule it should be possible to use the name as a pivot. Dimensions allow a particular named metric to be sliced to drill down and reason about th...

Awesome SSL certificates and HTTPS

What’s TLS TLS (Transport Layer Security) and its predecessor, SSL (Secure Sockets Layer), are security protocols designed to secure the communication betwee...

JVM warm up by Escape Analysis

Why JVM need warm up I don’t know how and why you get to this blog. But I know the key words in your mind are “warm” for JVM. As the name “warm up” suggested...

Java Concurrent

This blog is about noteworthy pivot points about Java Concurrent Framework Back to Java old days there were wait()/notify() which is error prone, while fr...

Back to Top ↑

2019

Conversations with God

Feelings is the language of the soul. If you want to know what’s true for you about something, look to how your’re feeling about.

Kafka In Spring

Enable Kafka listener annotated endpoints that are created under the covers by a AbstractListenerContainerFactory. To be used on Configuration classes as fol...

Mifid

FX Spot is not covered by the regulation, as it is not considered to be a financial instrument by ESMA, the European Union (EU) regulator. As FX is considere...

Foreign Exchange

currency pairs Direct ccy: means USD is part of currency pair Cross ccy: means ccy wihtout USD, so except NDF, the deal will be split to legs, both with...

Back to Top ↑

2018

Guice

A new type of Juice Put simply, Guice alleviates the need for factories and the use of new in your Java code. Think of Guice’s @Inject as the new new. You wi...

YAML

Key points All YAML files (regardless of their association with Ansible or not) can optionally begin with — and end with …. This is part of the YAML format a...

Sudo in a Nutshell

Sudo in a Nutshell Sudo (su “do”) allows a system administrator to give certain users (or groups of users) the ability to run some (or all) commands as root...

Zoo-keeper

ZK Motto the motto “ZooKeeper: Because Coordinating Distributed Systems is a Zoo.”

Cucumber

Acceptance testing vs unit test It’s sometimes said that unit tests ensure you build the thing right, whereas acceptance tests ensure you build the right thi...

akka framework of scala

philosophy The actor model adopts the philosophy that everything is an actor. This is similar to the everything is an object philosophy used by some object-o...

Apache Camel

Camel’s message model In Camel, there are two abstractions for modeling messages, both of which we’ll cover in this section. org.apache.camel.Message—The ...

JXM

Exporting your beans to JMX The core class in Spring’s JMX framework is the MBeanExporter. This class is responsible for taking your Spring beans and registe...

Solace MQ

Solace PubSub+ It is a message broker that lets you establish event-driven interactions between applications and microservices across hybrid cloud environmen...

Core Java

Annotation retention policy What is Retention policy in java annotations?

Apigee

App deployment, configuration management and orchestration - all from one system. Ansible is powerful IT automation that you can learn quickly.

Ansible

Ansible: What Is It Good For? Ansible is often described as a configuration management tool, and is typically mentioned in the same breath as Chef, Puppet, a...

flexbox

How Flexbox works — explained with big, colorful, animated gifs

KDB

KDB However kdb+ evaluates expressions right-to-left. There are no precedence rules. The reason commonly given for this behaviour is that it is a much simple...

Agile and SCRUM

Key concept In Scrum, a team is cross functional, meaning everyone is needed to take a feature from idea to implementation.

Strategy-Of-Openshift-Releases

Release & Testing Strategy There are various methods for safely releasing changes to Production. Each team must select what is appropriate for their own ...

NodeJs Notes

commands to read files var lineReader = require(‘readline’).createInterface({ input: require(‘fs’).createReadStream(‘C:\dev\node\input\git_reset_files.tx...

CORS :Cross-Origin Resource Sharing

Cross-Origin Request Sharing - CORS (A.K.A. Cross-Domain AJAX request) is an issue that most web developers might encounter, according to Same-Origin-Policy,...

ngrx

Why @Effects? In a simple ngrx/store project without ngrx/effects there is really no good place to put your async calls. Suppose a user clicks on a button or...

iOS programming

View A view is also a responder (UIView is a subclass of UIResponder). This means that a view is subject to user interactions, such as taps and swipes. Thus,...

Back to Top ↑

2017

cloud computering

openshift vs openstack The shoft and direct answer is `OpenShift Origin can run on top of OpenStack. They are complementary projects that work well together....

cloud computering

Concepts Cloud computing is the on-demand demand delivery of compute database storage applications and other IT resources through a cloud services platform v...

Redux

whats @Effects You can almost think of your Effects as special kinds of reducer functions that are meant to be a place for you to put your async calls in suc...

reactive programing

The second advantage to a lazy subscription is that the observable doesn’t hold onto data by default. In the previous example, each event generated by the in...

Container

The Docker project was responsible for popularizing container development in Linux systems. The original project defined a command and service (both named do...

promise vs observiable

The drawback of using Promises is that they’re unable to handle data sources that produce more than one value, like mouse movements or sequences of bytes in ...

TypeScript noteworthy notes

Async Await keywords Async Await Support in TypeScript Async - Await has been supported by TypeScript since version 1.7. Asynchronous functions are prefixed ...

JDK source

interface RandomAccess Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary ...

SSH SFTP

Secure FTP SFTP over FTP is the equivalant of HTTPS over HTTP, the security version

AWS Tips

After establishing a SSH session, you can install a default web server by executing sudo yum install httpd -y. To start the web server, type sudo service htt...

Oracle

ORA-12899: Value Too Large for Column

Java Security Notes

Java Security well-behaved: programs should be prevent from consuming too much system resources

R Language

s<-read.csv("C:/Users/xxx/dev/R/IRS/SHH_SCHISHG.csv") # aggregate s2<-table(s$Original.CP) s3<-as.data.frame(s2) # extract by Frequency ordered s3...

SSH and Cryptography

SFTP versus FTPS SS: Secure Shell An increasing number of our customers are looking to move away from standard FTP for transferring data, so we are ofte...

Eclipse notes

How do I remove a plug-in? Run Help > About Eclipse > Installation Details, select the software you no longer want and click Uninstall. (On Macintosh i...

Maven-Notes

Maven philosophy “It is important to note that in the pom.xml file you specify the what and not the how. The pom.xml file can also serve as a documentatio...

Java New IO

Notes JDK 1.0 introduced rudimentary I/O facilities for accessing the file system (to create a directory, remove a file, or perform another task), accessi...

IT-Architect

SOA SOA is a set of design principles for building a suite of interoperable, flexible and reusable services based architecture. top-down and bottom-up a...

Algorithm

This page is about key points about Algorithm

Java-Tricky-Tech-Questions.md

What is the difference between Serializable and Externalizable in Java? In earlier version of Java, reflection was very slow, and so serializaing large ob...

Compare-In-Java

Concepts If you implement Comparable interface and override compareTo() method it must be consistent with equals() method i.e. for equal object by equals(...

Java Collections Misc

Difference between equals and deepEquals of Arrays in Java Arrays.equals() method does not compare recursively if an array contains another array on oth...

HashMap in JDK

Hashmap in JDK Some note worth points about hashmap Lookup process Step# 1: Quickly determine the bucket number in which this element may resid...

Java 8 Tips

This blog is listing key new features introduced in Java 8

IntelliJ Tips

Shortcuts Expand/collapse method body in code editor Cmd + +/- to expand and collapse a method body Show java doc Ctrl+J: To show JavaDoc

Back to Top ↑

2016

Java GC notes

verbose:gc verbose:gc prints right after each gc collection and prints details about each generation memory details. Here is blog on how to read verbose gc

Hash Code Misc

contract of hashCode : Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consis...

Angulary Misc

Dependency Injection Angular doesn’t automatically know how you want to create instances of your services or the injector to create your service. You must co...

Java new features

JDK Versions JDK 1.5 in 2005 JDK 1.6 in 2006 JDK 1.7 in 2011 JDK 1.8 in 2014 Sun之前风光无限,但是在2010年1月27号被Oracle收购。 在被Oracle收购后对外承诺要回到每2年一个realse的节奏。但是20...

Simpler chronicle of CI(Continuous Integration) “乱弹系列”之持续集成工具

引言 有句话说有人的地方就有江湖,同样,有江湖的地方就有恩怨。在软件行业历史长河(虽然相对于其他行业来说,软件行业的历史实在太短了,但是确是充满了智慧的碰撞也是十分的精彩)中有一些恩怨情愁,分分合合的小故事,比如类似的有,从一套代码发展出来后面由于合同到期就分道扬镳,然后各自发展成独门产品的Sybase DB和微...

浅谈软件单元测试中的“断言” (assert),从石器时代进步到黄金时代。

大家都知道,在软件测试特别是在单元测试时,必用的一个功能就是“断言”(Assert),可能有些人觉得不就一个Assert语句,没啥花头,也有很多人用起来也是懵懵懂懂,认为只要是Assert开头的方法,拿过来就用。一个偶然的机会跟人聊到此功能,觉得还是有必要在此整理一下如何使用以及对“断言”的理解。希望可以帮助大家...

Kubernetes 与 Docker Swarm的对比

Kubernetes 和Docker Swarm 可能是使用最广泛的工具,用于在集群环境中部署容器。但是这两个工具还是有很大的差别。

Mac tips

how to show full path in Finder window Open and run following command in terminal window defaults write com.apple.finder _FXShowPosixPathInTitle -bool true; ...

http methods

RFC origion http://www.w3.org/Protocols/rfc2616/rfc2616-sec9.html#sec9.1.2)

Spark-vs-Storm

The stark difference among Spark and Storm. Although both are claimed to process the streaming data in real time. But Spark processes it as micro-batches; wh...

微服务

可以想像一下,之前的传统应用系统,像是一个大办公室里面,有各个部门,销售部,采购部,财务部。办一件事情效率比较高。但是也有一些弊端,首先,各部门都在一个房间里。

kibana, view layer of elasticsearch

What’s Kibana kibana is an open source data visualization plugin for Elasticsearch. It provides visualization capabilities on top of the content indexed on...

kibana, view layer of elasticsearch

What’s Kibana kibana is an open source data visualization plugin for Elasticsearch. It provides visualization capabilities on top of the content indexed on...

iConnect

UI HTML5, AngularJS, BootStrap, REST API, JSON Backend Hadoop core (HDFS), Hive, HBase, MapReduce, Oozie, Pig, Solr

Data Structure

Binary Tree A binary tree is a tree in which no node can have more than two children. A property of a binary tree that is sometimes important is that th...

Something about authentication

It’s annoying to keep on repeating typing same login and password when you access multiple systems within office or for systems in external Internet. There a...

SQL

Differences between not in, not exists , and left join with null

Github page commands notes

404 error for customized domain (such as godday) 404 There is not a GitHub Pages site here. Go to github master branch for gitpages site, manually add CN...

RenMinBi International

RQFII RQFII stands for Renminbi Qualified Foreign Institutional Investor. RQFII was introduced in 2011 to allow qualified foreign institutional investors to ...

Linux Tips

Get permission denied error when sudo su (or hyphen in sudo command) bash: /home/YOURNAME/.bashrc: Permission denied That’s because you didn’t add “-“ hyphen...

Load Balancing

Concepts LVS means Linux Virtual Server, which is one Linux built-in component.

Python

(‘—–Unexpected error:’, <type ‘exceptions.TypeError’>) datetime.datetime.now()

Microservices vs. SOA

Microservice Services are organized around capabilities, e.g., user interface front-end, recommendation, logistics, billing, etc. Services are small in ...

Java Class Loader

Codecache The maximum size of the code cache is set via the -XX:ReservedCodeCacheSize=N flag (where N is the default just mentioned for the particular com...

Back to Top ↑

2007

Back to Top ↑